|
S®aAB |
B®ACb½b |
|
A®aA½bB |
C®A½bA½cC |
Видно, что получена значительно более простая грамматика, чем исходная.
3 Устранение l-правил
Алгоритм преобразования грамматики к виду без l-правил работает с некоторым множеством нетерминальных символов Wi. Это множество включает символы, из которых либо есть непосредственный вывод пустой цепочки, либо переходы в такие символы.
1. W0={AÎVN | $(A®l)ÎP}, i:=1.
2. Wi=Wi–1È{AÎVN ½$ (A®a)ÎP, aÎWi–1*}.
3. До тех пор, пока не станет Wi=Wi–1, выполняется i:=i+1 и снова шаг 2.
4. Новая грамматика: VT¢=VT, VN¢=VN, в P¢ входят все правила из P, кроме правил вида A®l.
5. Если (A®a)ÎP и в цепочке a присутствуют символы из Wi, то на основе цепочки a строится множество цепочек {a¢} путём исключения из a всех возможных комбинаций символов из Wi, и все правила вида A®a¢ добавляются в P¢.
6. Если SÎWi, то lÎL(G) и тогда в VN¢ добавляется новый символ S¢, который становится целевым символом новой грамматики, а в P¢ добавляются два новых правила: S¢®l½S. Иначе S¢=S.
Рассмотренный алгоритм часто приводит к увеличению количества правил грамматики, но позволяет упростить построение распознавателя для данного языка.
Пример:
Рассмотрим грамматику G({a,b,c},{A,B,C,S},P,S), где P:
S®AaB½aB½cC
A®AB½a½b½B
B®Ba½l
C®AB½c
Удалим l-правила:
1. W0={B}, i:=1.
2. W1={B,A}, W1¹W0, i:=2.
3. W2={B,A,C}, W2¹W1, i:=3.
4. W3={B,A,C}, W3=W2.
5. VT¢=VT, VN¢=VN, в P¢ входят все правила из P, кроме правила B®l.
6. Рассмотрим отдельно каждое из правил множества P¢.
S®AaB½aB½cC. Нужно исключить все комбинации A,B,C. Получим: S®Aa½aB½a½a½c. Добавим новые правила, исключая дубликаты. Получим: S®AaB½aB½cC½Aa½a½c.
A®AB½a½b½B. Исключая все комбинации A и B, получим A®A½B. Добавлять нечего, т.к. правило A®B в множестве P¢ уже есть, а A®A не имеет смысла.
B®Ba. Исключив из этого правила B, получим B®a, следовательно, окончательно B®Ba½a.
C®AB½c. Исключив все комбинации A и B, получим C®A½B, после добавления в P¢ получится C®AB½A½B½c.
7. SÏW3, поэтому не нужно добавлять новый символ S¢, S¢=S.
В итоге получим грамматику G¢({a,b,c},{A,B,C,S},P¢,S), где правила P¢ имеют вид:
S®AaB½aB½cC½Aa½a½c
A®AB½a½b½B
B®Ba½a
C®AB½A½B½c.
Построенная грамматика эквивалентна исходной и не содержит l-правил.
4 Устранение цепных правил
Чтобы устранить цепные правила, для каждого нетерминального символа XÎVN последовательно строится специальное множество цепных символов NX={B½XÞ*B} а затем на основании построенных множеств выполняются преобразования правил P.
1. Шаги 2–5 выполнить для всех нетерминальных символов XÎVN.
2. NX0={X}, i:=1.
3. NXi= NXi–1È{B½(A®B)ÎP, AÎ NXi–1}.
4. Пока NXi¹ NXi–1, выполняется i:=i+1 и снова шаг 3.
5. Когда станет NXi=NXi–1, строим NX = NXi\{X} и переходим к шагу 2 – к очередному нетерминальному символу, до тех пор, пока они не будут рассмотрены все.
6. Новая грамматика: VT¢=VT, VN¢=VN, S¢=S, в P¢ входят все правила из P, кроме правил вида A®B.
7. Для всех правил (B®a)ÎP¢, если BÎNA, то в P¢ добавляются правила вида A®a.
Данный алгоритм так же, как и предыдущий, хотя и увеличивает количество правил грамматики, но упрощает построение распознавателей.
Пример:
Рассмотрим устранение цепных правил для грамматики, построенной в предыдущем примере. Грамматика G({a,b,c},{A,B,C,S},P,S), где P:
S®AaB½aB½cC½Aa½a½c
A®AB½a½b½B
B®Ba½a
C®AB½A½B½c.
Устраним цепные правила. Рассмотрим все нетерминальные символы, начиная с целевого.
1. NS0={S}, i:=1.
2. NS1={S}, NS1=NS0. NS=NS1\{S}=Æ.
3. NA0={A}, i:=1.
4. NA1={A,B}, NA1¹NA0, i:=2.
5. NA2={A,B}, NA2=NA1, NA=NA2\{A}={B}.
6. NB0={B}, i:=1.
7. NB1={B}, NB1=NB0, NB=NB1\{B}=Æ.
8. NC0={C}, i:=1.
9. NC1={C,A}, NC1¹NC0, i:=2.
10. NC2={C,A,B}, NC2¹NC1, i:=3.
11. NC3={C,A,B}, NC3=NC2, NC=NC3\{C}={A,B}.
Получили: NS=Æ, NA={B}, NB=Æ, NC={A,B}, S¢=S. Построим множество правил P¢:
S®AaB½aB½cC½Aa½a½c
A®AB½a½b
B®Ba½a
C®AB½c.
Поскольку элементами множеств NX являются только нетерминалы A и B, требуется рассматривать правила только для символов A и B:
A®AB½a½b. Поскольку AÎNC={A,B}, необходимо добавить правило C®AB½a½b. Но C®AB уже есть, следовательно, добавляем только C®a½b.
B®Ba½a. Поскольку BÎNC={A,B} и BÎNA={B}, необходимо добавить правила C®Ba½a и A®Ba½a. После всех добавлений и устранения дублирующих правил получим новые правила грамматики:
S®AaB½aB½cC½Aa½a½c
A®AB½a½b½Ba
B®Ba½a
C®AB½c½a½b½Ba.
Итоговое множество правил не содержит пустых и цепных правил. Хотя количество правил и увеличилось, но при построении распознавателя с таким множеством работать проще.
3.2.3 Контрольные вопросы
1. С какой целью выполняются преобразования грамматик?
2. Может ли результатом преобразований грамматики являться усложнение вида её правил?
3. Какого вида преобразования грамматик выполняются для упрощения процесса построения распознавателя?
4. Какие грамматики называются приведёнными?
5. Может ли терминальный символ быть недостижимым?
6. Какой символ называется бесплодным? Какой символ может быть бесплодным – терминальный или нетерминальный?
7. Какая грамматика называется грамматикой без l-правил? Допустимо ли наличие пустых правил в такой грамматике?
8. Какие преобразования необходимо выполнить, чтобы привести КС-грамматику к каноническому виду? К какому виду относятся эти преобразования – они упрощают правила грамматики или усложняют их?
9. Какое множество строится при удалении недостижимых символов – сразу нужное или сначала противоположное ему множество?
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.