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

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

Опр: символ x ∈ Vt ∪ Vn называется недостижимым в грамматике G, если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов

Вход: КС-грамматика G = <Vt, Vn, P, S>,

Выход: КС-грамматика G' = <Vt', Vn', P', S>, не содержащая недостижимых символов, для которой L(G) = L(G').

Метод:

1. V₀ := {S}; i := 1.

2. V_i := V_{i − 1} ∪ {x | x ∈ Vt ∪ Vn, A → αxβ ∈ P, A ∈ V_{i − 1}, α, β ∈ V*} .

Если V_i ≠ V_{i − 1}, то i := i + 1 и переходим к шагу 2, иначе Vn' := Vi ∩ Vn; Vt' := Vi ∩ Vt ; P' состоит из правил множества P, содержащих только символы из Vi ; G' := <Vt', Vn', P', S>.

Опр: символ A ∈ N называется бесплодным в грамматике G = <Vt, Vn, P, S>, если множество {α ∈ Vt* | A ⇒ α} пусто.

Алгоритм удаления бесплодных символов

Вход: КС-грамматика G = <Vt, Vn, P, S>.

Выход: КС-грамматика G' = <Vt', Vn', P', S>, не содержащая бесплодных символов, для которой L(G) = L(G').

Метод:

Строим множества Vn0, Vn1, ...

1. Vn0 := ∅, i := 1.

2. Vni := Vn_{i − 1} ∪ {A | A → α ∈ P и α ∈ (Vn_{i − 1} ∪ Vt)* }.

Если Vni ≠ Vn_{i − 1}, то i := i + 1 и переходим к шагу 2, иначе Vn' := Vni; P' состоит из правил множества P, содержащих только символы из Vn' ∪ Vt ; G' := <Vt', Vn', P', S>.

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

Алгоритм приведения грамматики

1. Обнаруживаются и удаляются все бесплодные нетерминалы.

2. Обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание. Если в этом алгоритме приведения поменять местами шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Некоторые применяемые на практике алгоритмы разбора по КС-грамматикам требуют, чтобы в грамматиках не было правил с пустой правой частью, т. е. чтобы КС-грамматика была неукорочивающей. Для любой КС-грамматики существует эквивалентная неукорачивающая.

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

(1) X₁ := { A | (A → ε) ∈ P }; i :=2; (2) X_i := {A | (A → α) ∈ P и α ∈ X_{i − 1}*} ∪ X_i−1. Далее, пока X_i ≠ X_{i − 1} увеличиваем i на единицу и повторяем (2). Последнее Xi — искомое множество X.

Граф контекстно-свободной грамматики

Для нахождения бесплодных и недостижимых символов наглядно использовать граф КС-грамматики:

• каждому символу из VT ∪ VN соответствует единственная вершина, помеченная этим символом; если в P есть правило с пустой правой частью ε, то граф имеет вершину, помеченную ε;

• вершина, помеченная символом X, соединяется с вершиной Y дугой (стрелкой), если в грамматике есть правило X → αY β, где α, β ∈ (VT ∪ VN)*;

• X соединяется с вершиной ε, если в грамматике есть правило X → ε.

Пример. Грамматика G₀:

G0 = <{a, b, c, d, e}, {S, A, B, C, D}, P0, S> P0: S → aAB | C D → cDc | d C → aCD A → aA | a | ε B → b

Алгоритм удаления бесплодных символов (граф)

Для заданной грамматики G построить граф и выполнить следующие шаги:

1. Отметить (выделить) вершины графа, помеченные терминальными символами, а также вершину ε, если такая имеется.

2. Если в Р есть правило А → α, где α состоит из символов уже отмеченных вершин, а вершина А еще не отмечена, то отметить эту вершину. Повторять шаг 2 пока возможно.

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

Пример. Рассмотрим грамматику G₀.

G0 = <{a, b, c, d, e}, {S, A, B, C, D}, P0, S> P0: S → aAB | C D → cDc | d C → aCD A → aA | a | ε B → b

Граф G0 после шагов 1, 2 алгоритма: (отмеченные вершины выделены двойным кружком)

Неотмеченной на графе оказалась вершина C. Вычеркиваем в грамматике G₀ символ C и правила, его содержащие: <{a, b, c, d, e}, {S, A, B, C , D}, P₀, S>

P₀: S → aAB | C

D → cDc | d

C → aCD

A → aA | a | ε

B → b

Получаем эквивалентную грамматику G₁, не содержащую бесплодных символов:

G₁ = <{a, b, c, d}, {S, A, B, D}, P1, S>

P₁: S → aAB

D → cDc | d

A → aA | a | ε

B → b

Алгоритм устранения правил с пустой правой частью

Вход: КС-грамматика G = <Vt, Vn, P, S>.

Выход: КС-грамматика G' = <Vt', Vn', P', S>, G' — неукорачивающая, L(G) = L(G').

Метод:

1. Построить множество Х = {A ∈ Vn | A ⇒ ε} ; Vn′:=Vn .

2. Построить P′, удалив из множества правил P все правила с пустой правой частью.

3. Если S ∈ X, то ввести новый начальный символ S′, добавив его в Vn′, и в множество правил P′ добавить правило S′→ S | ε. Иначе просто переименовать S в S′.

4. Изменить P′ следующим образом. Каждое правило вида

B → α₁A₁α₂A₂...α_nA_nα_{n + 1}, где Ai ∈ X для i = 1,..., n, αi ∈ ((Vn′ − X) ∪ Vt)* для i = 1,..., n + 1 (т. е. αi — цепочка, не содержащая символов из X), заменить 2ⁿ правилами, соответствующими всем возможным комбинациям вхождений Аi между αi:

B → α₁α₂...α_nα_{n + 1}

B → α₁α₂...α_nA_nα_{n + 1}

...

B → α₁α₂A₂...α_nA_nα_{n + 1}

B → α₁A₁α₂A₂...α_nA_nα_{n + 1}

Замечание. Если αi = ε для всех i = 1, ..., n + 1, то получившееся на данном шаге правило B → ε не включать в множество P′.

5. Удалить бесплодные и недостижимые символы и правила, их содержащие. (Кроме изначально имеющихся (в неприведенной грамматике), бесполезные символы могут возникнуть в результате шагов 2–4).

Замечание. Если применить данный алгоритм к регулярной (автоматной) грамматике, то результатом будет неукорачивающая регулярная (автоматная) грамматика.

Далее везде, если не оговорено иное, будем рассматривать только приведенные грамматики.

ТАВТ_ч2_19