Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 6

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

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

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

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

2.  Рассмотрим правила для символа A_i. Если они не содержат левой рекурсии, то переносим их во множество P¢ без изменений, а символ A_i добавляем во множество нетерминальных символов VN¢. В противном случае перепишем эти правила в следующем виде: 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¢ включаем во множество VN¢. Теперь все правила для 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Î(VNÈVT)^*, то заменить их на правила вида 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 исходной грамматики.

Пример.

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

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. Обозначим множество нетерминальных символов VN={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₁¢ заносим в VN¢. Получим VN¢={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₂¢ добавим в VN¢. Получим VN¢={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₃ добавим в VN¢. Получим VN¢={A₁, A₁¢, A₂, A₂¢, A₃}.

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

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

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

1.  A®aa, где aÎVT aÎVN^*.

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

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

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

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

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

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

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

3.4  Виды распознавателей КС-языков

3.4.1  Распознаватели КС-языков с возвратом

Распознаватели КС-языков с возвратом представляют собой самый простой тип распознавателей, основанный на модели недетерминированного МП-автомата. Как известно, при работе такого автомата возможны альтернативные варианты его поведения. Существуют два варианта реализации алгоритма работы недетерминированного МПА.