Приведёнными (или грамматиками в каноническом виде) называются грамматики, которые не содержат недостижимых и бесплодных символов, циклов и пустых правил (l-правил).
Рассмотрим некоторую грамматику G(VT,VN,P,S) и дадим необходимые определения.
Нетерминальный символ AÎVN называется бесплодным (или бесполезным), если из него нельзя вывести ни одной цепочки терминальных символов, т.е.
В простейшем случае символ является бесплодным, если во всех правилах, где он находится в левой части, он встречается также и в правой части. В более сложных случаях бесполезные символы могут находиться в некоторой взаимной зависимости, порождая друг друга. Если из правил грамматики удалить такие символы, то эти правила станут проще.
Символ 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. Достаточно устранить цепные правила из набора правил грамматики, чтобы исключить возможность появления циклов.
Для того чтобы преобразовать произвольную КС-грамматику к каноническому виду, необходимо выполнить следующие действия (причём именно в том порядке, каком они перечислены):
§ удалить все бесплодные символы;
§ удалить все недостижимые символы;
§ удалить цепные правила.
Для каждого из названных действий существует свой алгоритм. Рассмотрим эти алгоритмы в том порядке, каком требуется их реализовывать.
1 Удаление бесплодных символов
Выполняется пошаговое построение множества Yi, которое не содержит бесплодных символов рассматриваемой грамматики. На каждом шаге к уже построенному множеству добавляются новые нетерминальные символы. При этом первоначально в него включают те символы, из которых могут быть выведены терминальные цепочки, а на последующих шагах – символы, из которых могут быть выведены цепочки, состоящие как из терминальных символов, так и из символов уже построенного множества. После того, как с некоторого шага множество Yi перестанет изменяться, процесс построения считается законченным. В итоговое множество нетерминальных символов должны входить только символы из построенного множества Yi.
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, затем оно пополняется на основе правил этой грамматики. Множество считается построенным, если в него невозможно добавить ничего нового. Все символы, не вошедшие в это множество, являются недостижимыми, следовательно, их требуется исключить из словаря и из правил грамматики.
3. До тех пор, пока не станет Vi=Vi–1, выполняется i:=i+1 и снова шаг 2.
4. Новая грамматика: множество терминальных символов VT¢=VTÇVi, множество нетерминальных символов VN¢= VNÇVi, S¢=S, а в P¢ входят те правила из P, которые содержат только символы из множества Vi.
Оба рассмотренных алгоритма – удаления бесплодных и недостижимых символов – относятся к первой группе алгоритмов, т.е. их применение приводит к упрощению грамматики, сокращению количества правил и уменьшению объема алфавита.
Пример работы рассмотренных алгоритмов: