Левая рекурсия. Нормальная форма Грейбах

Символ AÎV_N в КС-грамматике G(V_T,V_N,P,S) называется рекурсивным, если для него существует цепочка вывода вида AÞ⁺aAb, где a, bÎ(V_NÈV_T)^*.

Виды рекурсии различают в зависимости от цепочек a и b. Если a=e, а b¹e, то рекурсия называется левой, а грамматика – леворекурсивной. Если наоборот: a¹e, а b=e, то рекурсия называется правой, а грамматика – праворекурсивной. Если обе цепочки a=b=e, то рекурсия представляет собой цикл. В дальнейшем будем рассматривать только приведённые грамматики, в которых нет цепных правил и, соответственно, циклов.

Замечание.

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

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

Заметим, что рекурсия лежит в основе построения языков на базе правил грамматики в форме Бэкуса-Наура, поэтому полностью исключить рекурсию из правил вывода невозможно, можно только устранить какой-то один из её видов – левый или правый.

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

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

1. Обозначим нетерминальные символы грамматики как V_N={A₁,A₂,…,A_n}, i:=1.

2. Рассмотрим правила для символа A_i. Если они не содержат левой рекурсии, то переносим их во множество P¢ без изменений, а символ A_i добавляем во множество нетерминальных символов V_N¢. В противном случае перепишем эти правила в следующем виде: A_i®A_ia₁½A_ia₂½…½A_ia_m½b₁½b₂½…½b_p, где "j½1 £ j £ p ни одна из цепочек b_j не начинается с символов A_k, таких, что k £ i. Вместо этого правила во множество P¢ записываем два правила вида:

A_i®b₁½b₂½…½b_p½b₁A_i¢½b₂A_i¢½…½b_pA_i¢,

A_i¢®a₁½a₂½…½a_m½a₁A_i¢½a₂A_i¢½…½a_mA_i¢

Символы A_i и A_i¢ включаем во множество V_N¢. Теперь все правила для A_i начинаются либо с терминального символа, либо с нетерминального символа A_k, такого, что k > i.

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

4. Если для символа A_i во множестве правил P есть правила вида A_i®A_ja, aÎ(V_NÈV_T)^*, то заменить их на правила вида A_i®b₁a½b₂a½…½b_ma, причём A_j®b₁½b₂½…½b_m – все правила для символа A_j. Поскольку правая часть правил A_j®b₁½b₂½…½b_m уже начинается с терминального символа или нетерминального A_k, k>j, то и правая часть правил для A_i будет удовлетворять этому условию.

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

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

Пример 7.

Пусть дана грамматика для арифметических выражений:

G ({+,–,/,*,a,b,(,)}, {S,T,E}, P, S), где правила P имеют вид:

(1) S ® S+T½S–T½T (2) T ® T*E½T/E½E (3) E ® (S)½a½b.

Эта грамматика леворекурсивная. Выполним эквивалентные преобразования и построим нелеворекурсивную грамматику G¢.

Шаг 1. Обозначим множество нетерминальных символов V_N={A₁,A₂,A₃}, i:=1. Тогда правила грамматики примут вид:

A₁ ® A₁+A₂½A₁–A₂½A₂

A₂ ® A₂*A₃½A₂/A₃½A₃

A₃ ® (A₁)½a½b.

Шаг 2. Правила для A₁: A₁ ® A₁+A₂½A₁–A₂½A₂ запишем в виде A₁®A₁a₁½A₁a₂½b₁, где a₁= +A₂, a₂= –A₂, b₁=A₂. Согласно алгоритму, запишем в P¢ новые правила для A₁:

A₁ ® A₂½A₂A₁¢, A₁¢ ® +A₂½–A₂½+A₂A₁¢½–A₂A₁¢. Символы A₁ и A₁¢ заносим в V_N¢. Получим V_N¢={A₁, A₁¢}.

Шаг 3. Поскольку i=1<3, i:=i+1=2, j:=1, переходим на следующий шаг.

Шаг 4. Для символа A₂ во множестве правил P нет правила вида A₂®A₁a, поэтому на этом шаге никаких действий не выполняется.

Шаг 5. Так как j=1=i–1, переходим на шаг 2.

Шаг 2. Правила для A₂: A₂ ® A₂*A₃½A₂/A₃½A₃ запишем в виде A₂®A₂a₁½A₂a₂½b₁, где a₁=*A₃, a₂=/A₃, b₁=A₃. Согласно алгоритму, запишем в P¢ новые правила для A₂:

A₂ ® A₃½A₃A₂¢, A₂¢ ® *A₃½/A₃½*A₃A₂¢½/A₃A₂¢. Символы A₂ и A₂¢ добавим в V_N¢. Получим V_N¢={A₁, A₁¢, A₂, A₂¢}.

Шаг 3. Поскольку i=2<3, то i:=3, j:=1, переходим на следующий шаг.

Шаг 4. Для символа A₃ во множестве правил P нет правила вида A₃®A₁a, поэтому на этом шаге никаких действий не выполняется.

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

Шаг 4. Для символа A₃ во множестве правил P нет правила вида A₃®A₂a, поэтому на этом шаге никаких действий не выполняется.

Шаг 5. Так как j=2=i–1, переходим на шаг 2.

Шаг 2. Правила для A₃: A₃ ® (A₁)½a½b не содержат левой рекурсии, поэтому поместим их в P¢ без изменений. Символ A₃ добавим в V_N¢. Получим V_N¢={A₁, A₁¢, A₂, A₂¢, A₃}.

Шаг 3. Поскольку i=3, построение грамматики закончено.

В итоге получили нелеворекурсивную грамматику G ({+,–,/,*,a,b,(,)}, {A₁, A₁¢, A₂, A₂¢, A₃}, P, A₁), где правила P имеют вид:

A1 ® A2½A2A1¢,	A2 ® A3½A3A2¢,
A1¢ ® +A2½–A2½+A2A1¢½–A2A1¢.	A2¢ ® *A3½/A3½*A3A2¢½/A3A2¢.
	A3 ® (A1)½a½b.

Грамматика называется грамматикой в нормальной форме Грейбах, если она не является леворекурсивной и в её множестве правил присутствуют только правила следующего вида:

1. A®aa, где aÎV_T aÎV_N^*.

2. S®e, если eÎL(G) и S не встречается в правых частях правил.

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

Алгоритм 7. Преобразование приведенной КС-грамматики без левой рекурсии к нормальной форме Грейбах с применением линейного порядка:

Вход: Нелеворекурсивная приведенная КС-грамматика G = (V_N, V_T, Р, S).

Выход: Эквивалентная КС-грамматика G' в нормальной форме Грейбах. Описание алгоритма:

Шаг 1. Построить такой линейный порядок (<) на N, что каждое A-правило начинается либо с терминала, либо с такого нетерминала В, что А < В. Упорядочить N = {А₁, А₂,..., А_п) так, что А₁< А₂<... < А _n. Причем правила, начинающиеся с нетерминала A_N < A_T правил, начинающихся с терминала. Между правилами вида A_T порядок значения не имеет.

Шаг 2. Положить i = п’, где n’ –число правил, начинающихся с терминала

Шаг 3. Если i = 0, то перейти к шагу 5 алгоритма. В противном случае заменить каждое правило вида A_i®А_j a, где j > i, правилами А_i ® b₁a | b₂a

| … | b_ma,  где A_j®b₁ | b₂| … | b_m –все правила A_j

Шаг 4. Положить i= i-1 и перейти к шагу 3.

Шаг 5. Теперь правая часть каждого правила начинается терминальным символом. В каждом правиле А ® аХ_i...X_k заменить X_jÎV_T  новым нетерминалом X'_j.

Шаг 6. Для новых нетерминалов X'_j, введенных на 5-ом шаге,

добавить правила X'_j ® X_j

Пример 8. G={{*,n},{S,A,B},{S→B*A, B→n | A*B, A→n},S}

1. Упорядочим символы S<B<A, i=2 (шаги 1,2)

2. Заменяем правило B→n | A*B на B→n | n*B, подставляя из A→n (шаг 3)

3. i=1 (шаг 4)

4. Заменяем правило S→B*A на S→ n*A |n*B*A, подставляя из B→n | n*B

5. i=0 (шаг 4)

6. Введем нетерминальный символ <*> (шаг 5)

7. Заменим * на <*>

P’: S→ n<*>A |n<*>B<*>A

    B→n | n<*>B

A→n

<*>→*

              G’= ({*,n},{S,A,B, <*>},P’, S)

4.2.3.3. Контрольные вопросы

1. Какого типа грамматики могут быть приведены к нормальной форме Хомского?

2. Каковы требования на правила грамматики в БНФ?

3. Обязательно ли наличие рекурсии в правилах грамматики? Какого вида рекурсия в них может использоваться? Может ли в правилах одной грамматики присутствовать рекурсия разных видов?

4. От какого вида рекурсии в правилах грамматики принято избавляться и для чего это делается?