Цели преобразований грамматик

В общем случае для КС-грамматик невозможно проверить их однозначность и эквивалентность. Но для конкретных случаев бывает можно и нужно привести заданную грамматику к некоторому определённому виду таким образом, чтобы получить грамматику, эквивалентную исходной. Заранее определённый вид зачастую позволяет упростить работу с языком и построение распознавателей для него. Итак, преобразования грамматик могут преследовать две цели:

1) упрощение правил грамматики;

2) облегчение создания распознавателя языка.

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

Все преобразования грамматик условно разбиваются на две группы:

1. исключение из грамматики тех правил и символов, без которых она может существовать (позволяет упростить правила);

2. изменение вида и состава правил грамматики. При этом могут появиться новые правила и нетерминальные символы (упрощений правил нет).

4.2.2.2. Приведённые грамматики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-07-12