Декомпозиция правил грамматики

Определение: две грамматики эквивалентны, если они порождают один и тот же язык. G₁~G₂, если L(G₁)=L(G₂).

Теорема: не существует алгоритма, определяющего эквивалентность или неэквивалентность двух грамматик, тем не менее существуют такие преобразования исходных грамматик, которые приводят к новым грамматикам, не выходящим из класса грамматик, эквивалентных исходным.

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

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

Для доказательства эквивалентности исходной автоматной грамматики и построенной грамматики во вполне детерминированной форме необходимо доказать, что любая цепочка, принадлежащая языку L₁, выводится и в грамматике G₂ и наоборот: L₁=L_2, если L(G₁) ÌL(G₂) и L(G₂) ÌL(G₁).

Согласно построению, если в исходной грамматике существует правило вида S→aA₁, то в преобразованной грамматике будет правило вида <S>→a<..A₁…>.

Аналогично рассуждаем для произвольного шага: если A_i→a_i+1 A_{i+1 , то}

<..A_i..>→a_i+1<..A_i+1..>

На последнем шаге вывода, имея в исходной грамматике правило вида A_k-1→a_kF, в преобразованной грамматике имеем правило <..A_k-1..>→a_k<..F..>, то есть существует последовательность шагов вывода:

<S>_a1 <..A₁…>.._ak<..F..> => φ ÎL(G₂)

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

Пусть φ=a₁…a_k ÎL(G₂)=> существует вывод этой цепочки в языке, порождаемом грамматикой G₂, то есть существует вывод цепочки: <S>_a1 <..A₁…>.._ak<..F..>.

По построению, если существует правило вида <S>→a₁<..A₁…>, то в исходной грамматике существует правило вида S→a₁ A₁.

Рассуждая аналогично, имея правило вида <..A_k-1..>→a_k<..F..> в исходной грамматике, имеем правило вывода A_k-1→a_kF, то есть φ ÎL(G₁) и => L(G₂) ÌL(G₁), откуда L₁=L₂. Что и требовалось доказать.

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

Пусть дана КС-грамматика G₁=( V_N,V_T, R, S).

Теорема 4.1. Если в КС-грамматике G₁ существуют правила Y®aXb и X®g, то грамматика G₂=( V_N, V_T,R È { Y®agb},S) эквивалентна G₁.

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

Пусть j Î L(G₁), тогда дерево вывода j в G₁ является деревом вывода j и в G₂. Обратно, пусть j Î L(G₂), следовательно существует некоторое дерево вывода j в G₂. Если при этом правило Y®agb не используется, то дерево вывода j в G₂ является деревом вывода j в G₁. Если же правило Y®agb использовалось при выводе j в G₂ , то фрагмент вывода Y Þ agb заменяем на фрагмент Y Þ aXb Þ agb.

В результате получим дерево, в котором используются правила только из P, то есть получим вывод цепочки в G₁. Следовательно, из j Î L(G₂) следует, что j Î L(G₁). 

Теорема 4.2. Пусть в грамматике G₁ имеется множество правил

{Y® a Xb, X® g₁ , X® g₂, ... , X® g_n} .

Тогда, заменив это множество на множество

{Y® ag₁b , Y® ag₂b , ... , Y® ag_nb , X® g₁ , X® g₂, ... X® g_n},

получим грамматику, эквивалентную G₁. И далее, если X ¹ S и других правил, которые имеют X в правой части нет, то группу правил X® g _k , можно удалить.

Доказательство. Многократно применяя теорему 4.1 в грамматику добавляем правила Y® ag_kb, где . Удаление правила Y® aXb не приводит к потере выводимых цепочек, так как фрагмент дерева вывода Y Þ aXb Þ ag_kb можно заменить на YÞ ag_kb.

Пример 4.1. Рассмотрим фрагмент грамматики для описания числа

<число> ® <знак> <чбз>

<знак> ® +½ -½e .

Здесь в соответствии с теоремой 4.2: Y - <число>, a - пустая цепочка, X - <знак>, b - <чбз> (число без знака), g₁ - +, g₂ - -, g₃ - e. Группу приведенных правил заменяем на правила

<число> ® + <чбз>½- <чбз>½<чбз> .

Теорема 4.3. Замена группы правил Y₁® a ₁Xb ₁ , Y₂® a ₂Xb ₂ , ... Y_m® a _mXb_m, X® g на правила Y₁® a ₁gb ₁ , Y₂® a ₂gb ₂ , ... Y_m® a _mgb _m , X® g , где других правил с нетерминалом X в левой части нет, приводит к эквивалентной грамматике. Если X ¹ S и других правил, которые имеют X в правой части нет, то правило X® g можно удалить.

Доказательство здесь аналогично теореме 4.2. ƒ

Пример 4.2. Замена правил:

S ® AB.C½AB.½A.C½B.½.C

A ® -

на правила:

S ® -B.C½-B.½-.C½B.½.C

приводят к эквивалентной грамматике.

Теорема 4.4. Декомпозиция правил. Замена в грамматике G₁ группы правил

на группу правил , если

и других в левых и правых частях правил грамматики нет, приводит к грамматике, эквивалентной G₁.

При декомпозиции n+m правил грамматики заменяется на n*m правил. ƒ

Пример 4.3. Рассмотрим КС - грамматику идентификатора, имеющую вид:

<И> ® <Б>½<Б> <И₁>

<И₁> ® <Б>½<Б> <И₁>½<Ц>½<Ц> <И₁>

<Б> ® a½b½c½...½y½z

<Ц> ® 0½1½2½...½8½9

В предложенной грамматике 42 правила. Проведем в ней декомпозицию по <Б> и по <Ц>. Получим новую грамматику, эквивалентную заданной.

<И> ® a½...½z½a <И₁>½...½ z <И₁>

<И₁> ® a½...½z½a <И₁>½...½ z <И₁>½0½...½9½ 0<И₁> ½...½9<И₁>

В результате получено 4*26=104 правил для букв и 2*10=20 правил для цифр, итого 124 правила. Правил стало больше, но вывод, а следовательно и разбор, будет короче. Нетрудно видеть, что рассмотренная декомпозиция позволила перейти от КС-грамматики идентификатора к А-грамматике. ƒ

Отметим в заключении параграфа, что все рассмотренные теоремы работают в обе стороны. Так n*m правил при композиции можно заменить на n+m правил. Иногда лучше иметь правил поменьше и компактно описывать язык; иногда, с целью повышения эффективности разбора, их количество необходимо увеличить.