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

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

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

Шаг 1. Обозначим нетерминальные символы грамматики так: VN = {А₁,А₂,...,А_П}. i := 1.

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

Иначе запишем правила для aj в виде aj -» A_ia_I|A_iaβ|...|A_ia_m|β₁|β₂|...|P_p, где Vj I <j < β ни одна из цепочек pj не начинается с символов Аk, таких, что k < i.

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

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

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

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

Шаг 4. Для символа aj во множестве правил Р' заменить все правила вида Aj->Aja, где aE(VTuVN)*, на правила вида Ai->Pia|β₂a...|β_ma, причем A_j->β₁|β₂|...|β_m — все правила для символа aj.

Так как правая часть правил Aj->β₁|β₂|...|β_m уже начинается с терминального символа или нетерминального символа A_k, k > j, то и правая часть правил для символа aj будет удовлетворять этому условию.

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

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

Рассмотрим в качестве примера грамматику для арифметических выражений над символами «а» и «b» G({+,-,/,*,а,b}, {S.T.E}, Р, S):

Эта грамматика является леворекурсивной. Построим эквивалентную ей нелеворекурсивную грамматику G'.

Шаг 1. Обозначим VN = {А_ь А₂, А₃}. i := 1. Тогда правила грамматики G будут иметь вид:

Шаг 2. Для А₁ имеем правила А₁->А₁+А₂|А₁-А₂|А₂. Их можно записать в виде А1-»A1a1|A1a2|β1, где a1 = + A₂, a₂ = -A₂, βi = A₂.

Запишем новые правила для множества Р':

Добавив эти правила в Р', а символы A_t и А1’ во множество нетерминальных символов, получим: VN' = {Aj.Aj¹}.

Шаг 3. i = 1 < 3. Построение не закончено: i := i+1 = 2, j := 1.

Шаг 4. Для символа А₂ во множестве правил Р' нет правила вида А₂->А1а, поэтому на этом шаге никаких действий не выполняем.

Шаг 5. j = 1 = i-1, переходим опять к шагу 2.

Шаг 2. Для А₂ имеем правила А₂-»А₂*А₃1А₂/А₃1А₃. Их можно записать в виде А₂-» -»А₂а, |А₂а₂1 pj, где а! = *А₃, а₂ = /А₃, pj = А₃.

Запишем новые правила для множества Р':

Добавим эти правила в Р', а символы А₂ и А₂' во множество нетерминальных символов, получим: VN' = {А₁,А₁',А₂₍А₂'}.

Шаг 3. i ⁼ 2 < 3. Построение не закончено: i := i+1 = 3, j := 1.

Шаг 4. Для символа А₃ во множестве правил Р' нет правила вида A₃-»Aia, поэтому на этом шаге никаких действий не выполняем.

Шаг 5. j - 1 < i-1, j := j+1 = 2, переходим к шагу 4.

Шаг 4. Для символа А₃ во множестве правил Р' нет правила вида А₃-»А₂а, поэтому на этом шаге никаких действий не выполняем.

Шаг 5. j - 2 - i-1, переходим опять к шагу 2.

Шаг 2. Для А₃ имеем правила А₃ -» (А1) | а | b. Эти правила не содержат левой рекурсии. Переносим их в Р', а символ А₃ добавляем в VN'. Получим: VN' = -s {А₁,А₁',А₂,А₂',Аз}.

Шаг 3. i = 3 = 3. Построение грамматики G' закончено.

В результате выполнения алгоритма преобразования получили нелеворекурсивную грамматику G({+,-,/,*,а,b}, {А1,A1’,A2,A2;,A3}, Р', A1) с правилами: