Приведёнными (или грамматиками в каноническом виде) называются грамматики, которые не содержат недостижимых и бесплодных символов, циклов и пустых правил (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-правила;
§ удалить цепные правила.
Для каждого из названных действий существует свой алгоритм. Рассмотрим эти алгоритмы в том порядке, каком требуется их реализовывать.
1 Удаление бесплодных символов
Выполняется пошаговое построение множества 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).
2 Удаление недостижимых символов
Данный алгоритм строит множество достижимых символов 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¢¢:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.