Преобразование грамматик

Введение

Приведенными грамматиками являются контекстно-свободные грамматики (КС-грамматики), в которых не содержатся недостижимые и бесплодные символы, циклы и \lambda-правила, то есть «пустые» правила. Приведенные грамматики именуют также как КС-грамматики в канонической форме.

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

1. Выполнить удаление всех бесплодных символов.
2. Выполнить удаление всех недостижимых символов.
3. Выполнить удаление \lambda - правил.
4. Выполнить удаление цепных правил.

Необходимо отметить, что операции по преобразованию следует выполнять именно в представленном выше порядке, и никак иначе.

Преобразование грамматик

В отдельных случаях КС-грамматика содержит недостижимые и бесплодные символы, не участвующие в образовании цепочек языка, и по этой причине их можно удалить из грамматики. Символ A ∈ VN именуется бесплодным в грамматике G = (VT, VN, P, S), когда множество { α | α ∈ VT*, A ⇒ α} является пустым.

Алгоритм, который удаляет бесплодные символы, может быть представлен следующим образом:

1. На вход поступает КС-грамматика G = (VT, VN, P, S).
2. На выходе получается КС-грамматика G’ = (VT, VN’, P’, S), которая не содержит бесплодных символов и для которой L(G) = L(G’).

Метод реализации данного алгоритма может быть представлен так. В рекурсивном режиме необходимо построить множества $N_0, N_1, ... N_ί$:

1. $N_0 = ∅, \ ί = 1$.
2. $N_ί$ = ${$A | (A → α) ∈ P \ и \ α ∈ (N{ί-1} ⋃ VT)*$}$⋃ N{ί-1}$..
3. Если $N_ί ≠ N_{ί-1}$, то ί = ί+1 и далее следует перейти к шагу два, иначе $VN’ = N_ί$. P’ должно состоять из правил множества P, которые содержат лишь символы из VN’ ⋃ VT; G’ = (VT, VN’, P’, S)

Символ $x \in (VT \cup VN)$ именуется недостижимым в грамматике G = (VT, VN, P, S), если его нет ни в одной из сентенциальных форм данной грамматики. Алгоритм, предназначенный для удаления недостижимых символов, имеет следующий вид:

1. На вход поступает КС-грамматика G = (VT, VN, P, S).
2. На выходе получается КС-грамматика G’ = (VT’, VN’, P’, S), которая не содержит недостижимых символов и для которой L(G) = L(G’).

Метод, реализующий данный алгоритм, может быть представлен следующим образом:

1. $V_0$ = {S}; ί = 1.
2. $V_ί$ = {x | x ∈ (VT ⋃ VN), (A → αxβ) ∈ P и A ∈ $V_{ί-1}$} $⋃ V_{ί-1}$.
3. Если $V_ί ≠ V_{ί-1}$, то ί = ί+1 и далее следует перейти к шагу два, в противном случае VN’ = Vί ⋂ VN; VT’ = Vί ⋂ VT. P’ должен состоять из правил множества P, которые содержат лишь символы из Vί; G’ = (VT’, VN’, P’, S).

КС-грамматика G именуется приведенной, когда не содержит недостижимых и бесплодных символов.

Алгоритм, который выполняет приведение грамматики, может быть представлен следующим образом:

1. Необходимо обнаружить и удалить все бесплодные не терминалы.
2. Необходимо обнаружить и удалить все недостижимые символы.

Удаление символов должно сопровождаться удалением правил вывода, которые содержат данные символы. Следует помнить, что если в данном алгоритме поменять местами первый и второй шаги, то необязательно в итоге будет достигнута приведенная грамматика. Для того чтобы описать синтаксис языков программирования, рекомендуется применять однозначные приведенные КС-грамматики.

Правило грамматики типа $A \rightarrow B$, где $A,B \in VN$, именуется цепным правилом. Для КС-грамматики G, которая содержит цепные правила, возможно выстроить эквивалентную ей грамматику G', не обладающую цепными правилами. Данное утверждение может быть доказано на основании следующего предположения. Если грамматика G обладает правилами:

$A \rightarrow B$, $B \rightarrow C$, $C \rightarrow aX$,

то такие правила можно заменить одним правилом $А \rightarrow aX$, так как вывод $A \Rightarrow B \Rightarrow C \Rightarrow aX$ цепочки aX в грамматике G можно получить в грамматике G' при помощи правила $A \rightarrow aX$.

В общем случае доказать последнее утверждение можно следующим образом. Необходимо разбить множество правил P грамматики G на два подмножества $P_1 \ и \ P_2$, включив в $P_1$ все правила типа $A \rightarrow B$. Для всех правил из $P_1$ следует найти множество правил $S(A_ί)$, которые сформированы следующим образом:

1. Когда $A_ί$ ⇒ $* A_j$ и в $P_2$ есть правило $A_j$ → α, в котором α является цепочкой словаря (VN ⋃ VT)*.
2. Тогда в $S(A_ί)$ следует включить правило $A_ί$ → α.
3. Далее следует построить новое множество правил P’, объединив правила $P_2$ и все построенные множества $S(A_ί)$.
4. В результате будет получена грамматика G' = {VN ,VT , P’, S}, которая является эквивалентной заданной и в ней не содержатся правила типа A → B.

Преобразование не укорачивающих грамматик связано с удалением из грамматики правил, имеющих пустую правую часть. Правило типа $A \rightarrow \lambda$ именуется как «пустое», то есть аннулирующее, правило. Грамматика именуется не укорачивающей или грамматикой, не имеющей «пустые» правила, в следующих случаях:

1. Когда в схеме грамматики не содержатся аннулирующие правила
2. Когда в схеме грамматики содержится лишь одно правило типа $S \rightarrow \lambda$, в котором S является начальным символом грамматики, и символ S не должен встречаться в правой части оставшихся грамматических правил.

Для грамматик, которые содержат совокупность аннулирующих правила, справедливым является такое утверждение. А именно, для любой КС-грамматики G', которая содержит набор аннулирующих правил, может быть построена эквивалентная ей не укорачивающая грамматика G, такая что L(G')=L(G).

Формирование не укорачивающей грамматики может привести к возрастанию количества правил заданной грамматики из-за того, что будут построены дополнительные правила, получаемые в результате исключения не терминалов аннулирующих правил. Для того чтобы сформировать дополнительные правила, следует осуществить все допустимые подстановки пустой цепочки, заменив ими аннулирующие не терминалы во всех правилах грамматики.

А в случае, когда в грамматике имеется правило типа $S \rightarrow \lambda$, в котором S является начальным символом грамматики, и символ S есть в правых частях других правил грамматики, то необходимо выполнить задание нового начального символа S’ и замену правила $S \rightarrow \lambda$ на два новых правила:

1. $S' \rightarrow \lambda$.
2. $S'\rightarrow S$.