Пример 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)

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

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

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

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

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

Дата добавления: 2015-07-12