Устранение левой рекурсии. Грамматики в нормальной форме Грейбах

Определение левой рекурсии

Символ AVN в КС-грамматике G(VT,VN,P,S) называется рекурсивным, если для него существует цепочка вывода вида А+αАβ, где α,β(VTVN)*.

Если α= и β, то рекурсия называется левой, а грамматика G – леворекур­сивной; если α и β=, то рекурсия называется правой, а грамматика G – праворекурсивной. Если α= и β=, то рекурсия представляет собой цикл. Когда грамматика G – приведенная, в ней нет цепных правил и не может встречаться циклов, поэтому далее циклы рассматриваться не будут.

Любая КС-грамматика может быть как леворекурсивной, так и праворекурсивной, а также леворекурсивной и праворекурсивной одновременно (по различ­ным символам из множества нетерминальных символов).

КС-грамматика называется нелеворекурсивной, если она не является леворекурсивной. Аналогично, КС-грамматика является неправорекурсивной, если не является праворекурсивной.

Некоторые алгоритмы левостороннего разбора для КС-языков не работают с ле­ворекурсивными грамматиками, поэтому возникает необходимость исключить левую рекурсию из выводов грамматики. Далее будет рассмотрен алгоритм, ко­торый позволяет преобразовать правила произвольной КС-грамматики таким образом, чтобы в выводах не встречалась левая рекурсия.

Следует отметить, что поскольку рекурсия лежит в основе построения языков на основе правил грамматики в форме Бэкуса–Наура, полностью исключить рекур­сию из выводов грамматики невозможно. Можно избавиться только от одного вида рекурсии – левого или правого, то есть преобразовать исходную граммати­ку G к одному из видов: нелеворекурсивному (избавиться от левой рекурсии) или неправорекурсивному (избавиться от правой рекурсии). Для левосторонних распознавателей интерес представляет избавление от левой рекурсии – то есть преобразование грамматики к нелеворекурсивному виду.

Доказано, что любую КС-грамматику можно преобразовать к нелеворекурсивно­му или неправорекурсивному виду.

Алгоритм устранения левой рекурсии

Условие: дана КС-грамматика G(VT,VN,P,S), необходимо построить эквивалент­ную ей нелеворекурсивную грамматику G’(VN’,VT,P’,S’): L(G) = =L(G’).

Алгоритм преобразования работает с множеством правил исходной граммати­ки Р, множеством нетерминальных символов VN и двумя переменными счетчи­ками: i и j.

Шаг 1. Обозначим нетерминальные символы грамматики так: VN={A1,A2,…An}. i:=1.

Шаг 2. Рассмотрим правила для символа Аi. Если эти правила не содержат левой рекурсии, то перенесем их во множество правил Р’ без изменений, а символ Аiдобавим во множество нетерминальных символов VN’.

Иначе запишем правила для Аi, в виде Аi Aiα1|Aiα2|...|Aiαm|β1|β2|...|βp, где j 1jP ни одна из цепочек Р, не начинается с символов Ak, таких, что ki.

Вместо этого правила во множество Р’ запишем два правила вида:

Ai β1|β2|...|βp|β1Ai’| β2Ai’|…| βpAi’

Ai α1|α2|...|αm|α1Ai’| α2Ai’|…| αmAi’

Символы Aiи Ai’ включаем во множество VN’.

Теперь все правила для Aiначинаются либо с терминального символа, либо с нетерминального символа Ak, такого, что k > i.

Шаг 3. Если i=n, то грамматика G’ построена, иначе i:= i+1, j:=1 и перейти к шагу 4.

Шаг 4. Для символа Аjво множестве правил Р’ заменить все правила вида AiAjα, где α(VTVN)*, на правила вида Ai β1α| β2α |...| βmα, причем Aj β1| β2|...| βm– все правила для символа Аj.

Так как правая часть правил Aj β1| β2|...| βmуже начинается с терминального сим­вола или нетерминального символа Ak, k>j, то и правая часть правил для симво­ла Аiбудет удовлетворять этому условию.

Шаг 5. Если j =i–1, то перейти к шагу 2, иначе j:=j+1 и перейти к шагу 4.

Шаг 6. Целевым символом грамматики G’ становится символ Ak, соответствую­щий символу S исходной грамматики G.

Грамматики в нормальной форме Грейбах

На основании грамматики, в которой исключена левая рекурсия, можно постро­ить грамматику в нормальной форме Грейбах.

КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Грей­бах, если она не является леворекурсивной и в ее множестве правил Р присутст­вуют только правила следующего вида:

1. А  аα, где aVT и αVN*.

2. S, если L(G), причем S не должно встречаться в правых частях других правил.

Никакие другие формы правил не должны встречаться среди правил граммати­ки в нормальной форме Грейбах.

Нормальная форма Грейбах является удобной формой представления грамматик для построения нисходящих левосторонних распознавателей (в тех случаях, ко­гда присутствие левой рекурсии в правилах грамматики недопустимо).