Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как противостоять манипуляциям мужчин? Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника







Эквивалентность праволинейных грамматик и конечных автоматов





 

Как мы упоминалось выше, любой конечно-автоматный язык может быть определен праволинейной грамматикой, и наоборот, так что классы языков, определяемых этими формализмами, эквивалентны. Так, для конструирования праволинейной грамматики, соответствующей данному конечному автомату, достаточно включить в грамматику правила вида q→ar для всех переходов вида δ(q,a) = r и правила вида p→ε для всех заключительных состояний p.

 

Таким образом, класс языков, задаваемых праволинейными грамматиками, очень удобен в задачах компиляции, т.к. ему соответствует простой распознаватель (конечные автоматы), для которого алгоритмически разрешимы такие проблемы, как эквивалентность двух языков, пустота определяемого языка и проверка входной цепочки на принадлежность данному языку. Многие "локальные" свойства языков программирования, такие как константы, слова языка и строки, могут быть определены с помощью праволинейных грамматик – например, этот формализм может быть использован в задачах лексического анализа.

 

Однако, класс языков, задаваемых праволинейными грамматиками, слишком узок для описания многих свойств современных языков программирования. Например, в большинстве языков программирования возникает потребность в согласовании подобных скобок и разделителей, таких, как begin-end, (), [], {}. Можно промоделировать подобное согласование с помощью "правильного скобочного языка", в котором алфавит состоит из символов '(' и ')', а количество открывающих скобок совпадает с количеством закрывающих и число закрывающих скобок никогда не превышает число встреченных открывающих скобок. Можно показать, что не существует праволинейной грамматики, описывающий данный язык, но зато его легко записать с помощью следующей контекстно-свободной грамматики: S→(S), S→SS, S→ε.

По этой причине контекстно-свободные грамматики получили значительно большее распространение в компиляции. С их помощью можно задать очень большую часть синтаксиса языков программирования.








Date: 2016-05-25; view: 26; Нарушение авторских прав

mydocx.ru - 2015-2017 year. (0.006 sec.) - Пожаловаться на публикацию