4. Эквивалентные преобразования кс- и а-грамматик
Напомним, что две грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык ( L(G1)=L(G2) ). Одна из основных задач теории формальных языков - задача выбора наилучшей, по некоторым показателям, грамматики или автомата для описания того или иного языка.
Задача определения эквивалентности двух произвольных грамматик (автоматов) алгоритмически неразрешима. Однако, существуют некоторые преобразования, которые позволяют получить грамматику эквивалентную данной. Преобразования из недетерминированной формы в детерминированную, минимизация, сжатие и ускорение, рассмотренные в разделе 3, - примеры таких эквивалентных преобразований. Ниже будут рассмотрены еще некоторые преобразования, полезные для практики.
4.1. Декомпозиция правил грамматики
Пусть нам дана КС-грамматика G1=(,,P,S).
Теорема 4.1. Если в КС-грамматике G1 существуют правила YX и X, то грамматика G2=(,,P { Y},S) эквивалентна G1.
Доказательство. Проверим, что любая цепочка, выводимая в одной грамматике, выводима и в другой.
Пусть L(G1), тогда дерево вывода в G1 является деревом вывода и в G2. Обратно, пусть L(G2), следовательно существует некоторое дерево вывода в G2. Если при этом правило Y не используется, то дерево вывода в G2 является деревом вывода в G1. Если же правило Y использовалось при выводе в G2 , то фрагмент вывода Y заменяем на фрагмент
Y X .
В результате получим дерево, в котором используются правила только из P, то есть получим вывод цепочки в G1. Следовательно, из L(G2) следует, что L(G1).
Теорема 4.2. Пусть в грамматике G1 имеется множество правил
{Y X, X 1 , X 2, ... , X n} .
Тогда, заменив это множество на множество
{Y 1 , Y 2 , ... , Y n , X 1 , X 2, ... X n},
получим грамматику,
эквивалентную G1.
И далее, если
X
S и других
правил, которые имеют X
в правой части нет, то группу правил X
k
,
можно
удалить.
Доказательство.
Многократно применяя теорему 4.1 в
грамматику добавляем правила Y
k,
где
. Удаление
правила Y
X
не приводит к потере выводимых цепочек,
так как фрагмент дерева вывода Y
X
k
можно заменить на Y
k.
Пример 4.1. Рассмотрим фрагмент грамматики для описания числа
<число> <знак> <чбз>
<знак> +
Здесь в соответствии с теоремой 4.2: Y - <число>, - пустая цепочка, X - <знак>, - <чбз> (число без знака), 1 - +, 2 - , 3 - . Группу приведенных правил заменяем на правила
<число> + <чбз> <чбз><чбз>
Теорема 4.3. Замена группы правил Y1 1X 1 , Y2 2X 2 , ... Ym mXm, X на правила Y1 1 1 , Y2 2 2 , ... Ym m m , X , где других правил с нетерминалом X в левой части нет, приводит к эквивалентной грамматике. Если X S и других правил, которые имеют X в правой части нет, то правило X можно удалить.
Доказательство здесь аналогично теореме 4.2.
Пример 4.2. Замена правил:
S AB.CAB.A.CB..C
A
на правила:
S B.CB..CB..C
приводят к эквивалентной грамматике.
Теорема 4.4. Декомпозиция правил. Замена в грамматике G1 группы правил
на группу правил
, если
и других
в левых и правых частях правил грамматики
нет, приводит к грамматике, эквивалентной
G1.
При декомпозиции n+m правил грамматики заменяется на nm правил.
Пример 4.3. Рассмотрим КС - грамматику идентификатора, имеющую вид:
<И> <Б><Б> <И1>
<И1> <Б><Б> <И1><Ц><Ц> <И1>
<Б> abc...yz
<Ц> 012...89
В предложенной грамматике 42 правила. Проведем в ней декомпозицию по <Б> и по <Ц>. Получим новую грамматику, эквивалентную заданной.
<И> a...za <И1>... z <И1>
<И1> a...za <И1>... z <И1>0...9 0<И1> ...9<И1>
В результате получено 426=104 правил для букв и 210=20 правил для цифр, итого 124 правила. Правил стало больше, но вывод, а следовательно и разбор, будет короче. Нетрудно видеть, что рассмотренная декомпозиция позволила перейти от КС-грамматики идентификатора к А-грамматике.
Отметим в заключении параграфа, что все рассмотренные теоремы работают в обе стороны. Так nm правил при композиции можно заменить на n+m правил. Иногда лучше иметь правил поменьше и компактно описывать язык; иногда, с целью повышения эффективности разбора, их количество необходимо увеличить.