Разработка компиляторов
Эквивалентность праволинейных грамматик и конечных автоматов
Как упоминалось выше, любой конечно-автоматный язык может быть определен праволинейной грамматикой, и наоборот, так что классы языков, определяемых этими формализмами, эквивалентны. Так, для конструирования праволинейной грамматики, соответствующей данному конечному автомату, достаточно включить в грамматику правила вида для всех переходов вида и правила вида для всех заключительных состояний .
Таким образом, класс языков, задаваемых праволинейными грамматиками, очень удобен в задачах компиляции, т.к. ему соответствует простой распознаватель (конечные автоматы), для которого алгоритмически разрешимы такие проблемы, как эквивалентность двух языков, пустота определяемого языка и проверка входной цепочки на принадлежность данному языку. Многие "локальные" свойства языков программирования, такие как константы, слова языка и строки, могут быть определены с помощью праволинейных грамматик - например, в следующей лекции мы покажем как этот формализм может быть использован в задачах лексического анализа.
Однако, класс языков, задаваемых праволинейными грамматиками, слишком узок для описания многих свойств современных языков программирования. Например, в большинстве языков программирования возникает потребность в согласовании подобных скобок и разделителей, таких, как begin-end, (), [], {}. Можно промоделировать подобное согласование с помощью "правильного скобочного языка", в котором алфавит состоит из символов ' (' и ' )', а количество открывающих скобок совпадает с количеством закрывающих и число закрывающих скобок никогда не превышает число встреченных открывающих скобок. Можно показать, что не существует праволинейной грамматики, описывающий данный язык, но зато его легко записать с помощью следующей контекстно-свободной грамматики: .
По этой причине контекстно-свободные грамматики получили значительно большее распространение в компиляции. С их помощью можно задать очень большую часть синтаксиса языков программирования.
