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

Приведёнными (или грамматиками в каноническом виде) называются грамматики, которые не содержат недостижимых и бесплодных символов, циклов и пустых правил (l-правил).

Рассмотрим некоторую грамматику G(VT,VN,P,S) и дадим необходимые определения.

Нетерминальный символ AÎVN называется бесплодным (или бесполезным), если из него нельзя вывести ни одной цепочки терминальных символов, т.е. {a½AÞ*a, aÎVT*}=Æ.

В простейшем случае символ является бесплодным, если во всех правилах, где он находится в левой части, он встречается также и в правой части. В более сложных случаях бесполезные символы могут находиться в некоторой взаимной зависимости, порождая друг друга. Если из правил грамматики удалить такие символы, то эти правила станут проще.

Символ xÎ(VTÈVN) называется недостижимым, если он не встречается ни в одной сентенциальной форме грамматики G. Это значит, что он не может появиться ни в одной цепочке вывода. Для исключения всех недостижимых символов не обязательно рассматривать все сентенциальные формы грамматики, достаточно воспользоваться специальным алгоритмом удаления недостижимых символов. После удаления таких символов правила также упрощаются.

l-правилами, или правилами с пустой цепочкой, называются все правила грамматики вида A®l, AÎVN. Грамматика G называется грамматикой без l-правил, если в ней нет правил вида (A®l), AÎVN, A¹S, и существует только одно правило (S®l)ÎP, если lÎL(G) и при этом S не встречается в правой части ни одного правила грамматики G. Для упрощения процесса построения распознавателя цепочек языка L(G) любую грамматику целесообразно привести к виду без l-правил.

Циклом в грамматике G называется вывод вида AÞ*A, AÎVN. Очевидно, что такой вывод бесполезен, поэтому в распознавателях КС-языков рекомендуется избегать возможности появления циклов.

Циклы возможны в случае существования в грамматике цепных правил вида A®B, A,BÎVN. Достаточно устранить цепные правила из набора правил грамматики, чтобы исключить возможность появления циклов.

Для того чтобы преобразовать произвольную КС-грамматику к каноническому виду, необходимо выполнить следующие действия (причём именно в том порядке, каком они перечислены):

§  удалить все бесплодные символы;

§  удалить все недостижимые символы;

§  удалить l-правила;

§  удалить цепные правила.

Для каждого из названных действий существует свой алгоритм. Рассмотрим эти алгоритмы в том порядке, каком требуется их реализовывать.

Удаление бесплодных символов

Выполняется пошаговое построение множества Yi, которое не содержит бесплодных символов рассматриваемой грамматики. На каждом шаге к уже построенному множеству добавляются новые нетерминальные символы. При этом первоначально в него включают те символы, из которых могут быть выведены терминальные цепочки, а на последующих шагах – символы, из которых могут быть выведены цепочки, состоящие как из терминальных символов, так и из символов уже построенного множества. После того, как с некоторого шага множество Yi перестанет изменяться, процесс построения считается законченным. В итоговое множество нетерминальных символов должны входить только символы из построенного множества Yi.

1.  Y0=Æ, i:=1.

2.  Yi=Yi–1È{AÎ VN ½$(A®a)ÎP, aÎ(Yi–1ÈVT)*}.

3.  До тех пор, пока не станет Yi=Yi–1, выполняется i:=i+1 и снова шаг 2.

4.  Новая грамматика: множество терминальных символов VT¢ совпадает со старым VT: VT¢=VT, VN¢=Yi, S¢=S, а в P¢ входят те правила из P, которые содержат только символы из множества (YiÈVT).

Удаление недостижимых символов

Данный алгоритм строит множество достижимых символов Vi исходной грамматики. Сначала в это множество входит только целевой символ S грамматики G, затем оно пополняется на основе правил этой грамматики. Множество считается построенным, если в него невозможно добавить ничего нового. Все символы, не вошедшие в это множество, являются недостижимыми, следовательно, их требуется исключить из словаря и из правил грамматики.

1.  V0={S}, i:=1.

2.  Vi=Vi–1È{x½xÎ(VNÈVT) и (A®axb)ÎP, AÎVi–1ÇVN, a,bÎ(VNÈVT)*}.

3.  До тех пор, пока не станет Vi=Vi–1, выполняется i:=i+1 и снова шаг 2.

4.  Новая грамматика: множество терминальных символов VT¢=VTÇVi, множество нетерминальных символов VN¢= VNÇVi, S¢=S, а в P¢ входят те правила из P, которые содержат только символы из множества Vi.

Замечание:

Оба рассмотренных алгоритма – удаления бесплодных и недостижимых символов – относятся к первой группе алгоритмов, т.е. их применение приводит к упрощению грамматики, сокращению количества правил и уменьшению объема алфавита.

Пример работы рассмотренных алгоритмов:

Пусть дана грамматика G({a,b,c},{A,B,C,D,E,F,G,S},P,S), где P:

S®aAB½E

D®a½c½Fb

A®aA½bB

E®cE½aE½Eb½ED½FG

B®ACb½b

F®BC½EC½AC

C®A½bA½cC½aE

G®Ga½Gb.

Удалим бесплодные символы.

1.  Y0=Æ, i:=1.

2.  Y1={B,D}, Y1¹Y0, i:=2.

3.  Y2={B,D,A}, Y2¹Y1, i:=3.

4.  Y3={B,D,A,S,C}, Y3¹Y2, i:=4.

5.  Y4={B,D,A,S,C,F}, Y4¹Y3, i:=5.

6.  Y5={B,D,A,S,C,F}, Y5=Y4.

7.  Бесплодными символами оказались символы, не вошедшие в множество Y5, т.е. E и G. Строим новую грамматику: VT¢=VT={a,b,c}, VN¢=Yi={A,B,C,D,F,S}, S¢=S. Получили грамматику G¢({a,b,c},{A,B,C,D,F,S}, P¢, S),

P¢:

S®aAB

C®A½bA½cC

A®aA½bB

D®a½c½Fb

B®ACb½b

F®BC½AC

Удалим недостижимые символы:

1.  V0={S}, i:=1.

2.  V1={S,A,B,a}, V1¹V0, i:=2.

3.  V2={S,A,B,a,b,C}, V2¹V1, i:=3.

4.  V3={S,A,B,a,b,C,c}, V3¹V2, i:=4.

5.  V4={S,A,B,a,b,C,c}, V4=V3.

6.  Строим новую грамматику: множество нетерминальных символов VN¢¢={S,A,B,a,b,C,c}ÇVN={A,B,C,S}, множество терминальных символов VT¢¢={S,A,B,a,b,C,c}ÇVT={a,b,c}, S¢¢=S, а в P¢¢ входят те правила из P¢, которые содержат только символы из множества Vi. В итоге получаем грамматику G¢¢({a,b,c},{A,B,C,S}, P¢¢, S), где

P¢¢: