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

      Комментарии к записи Устранение левой рекурсии. грамматики в нормальной форме грейбах отключены

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

Символ 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, такого, что ki.

Шаг 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, kj, то и правая часть правил для символа А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 не должно встречаться в правых частях других правил.

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

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

Статьи к прочтению:

Что такое рекурсия | самое простое объяснение


Похожие статьи: