Теорема 2.13. Грамматика которую строит алгоритм 2.9, не содержит бесполезных символов и L(G) -L{G).

Доказательство. Доказательство того, что L(G) = L{G), оставляем в качестве упражнения. Предположим, что ЛК - бесполезный символ. Тогда по определению бесполезности символа могут представиться два случая:

Случай Г. Вывод S =:>0аЛр ни для каких аир невозможен. В этом случае символ Л устраняется на шаге (2) алгоритма 2.9.

Случай 2: 5=>0аЛр для некоторых а и р, но вывода AQ.w для ЕШИ* не существует. Тогда Л не устраняется на шаге (2) и, кроме того, если ЛоуВд, то и В не устраняется на шаге (2). Таким образом, если Л=5>сШ, то Л =>g, tc. Тога можно заключить, что вывода Ао для шБ* не существует и Л устраняется на шаге (1).

Доказательство того, что ни один терминал в G не может быть бесполезным, проводится аналогично; мы оставляем его в качестве упражнения. □

Пример 2.22. Рассмотрим грамматику G({5, Л, В], {а, &}, Р, 5), где Р состоит из правил

S-a\A

А-АВ

Применим к G алгоритм 2.9. На шаге (i) получим N{S, В] и G = {{S, В], {а, &}, {S-.-(2, fi->&}, S). Применив алгоритм 2.8, получим = а]. Итак, G-({5}, {а}, {5-->а}, S).

Если применить к G сначала алгоритм 2.8, то окажется, что все символы достижимы, так что грамматика не изменится. Затем применение алгоритма 2.7 дает N = {S, В], и результирующей будет грамматика Gi, отличная от G. □

Часто бывает удобно устранить из КС-грамматики G е-пра-вила, т. е. правила вида А-~е. Но если eL(G), то очевидно, что без правил вида А~е не обойтись.

Определение. Назовем КС-грамматику G{N, 2, Р, S) грамматикой без е-правил (или неукорачивающей), если либо

(1) Р не содержит е-правил, либо

(2) есть точно одно е-правило Se н S не встречается в правых частях остальных правил из Р.

Алгоритм 2.10. Преобразование в грамматику без е-правил.

Вход. КС-грамматика G-{N, 2, Р, S).

Выход. Эквивалентная КС-грамматика G = (N, 2, Р\ S) без е-правил.

Метод.

(1) Построить {Л I Л g N и Л =>ое}. Это аналогично тому, что было в алгоритмах 2.7 и 2.8, и остается в качестве упражнения.

(2) Построить Р так:

(а) Если Л-аВаВа.. .Bfpik принадлежит Р, АО и Bie для 1/, но ни один символ в цепочках

(0/) не принадлежит N, то включить в Р все правила вида

Л -аДссДз.. .af Xfp.f,

где Xj - либо В,, либо е, но не включать правило Л-е (это могло бы произойти в случае, если все равны е).

(б) Если 5gN, включить в Р правила S~.e\S

где S - новый символ, и положить N N U {5}. В противном случае положить N = N и S=S.

(3) Положить G = (N, 2, Р\ S). □

Пример 2.23. Рассмотрим грамматику из примера 2.19 с правилами

SaSbS\bSaS\e

Применяя к этой грам.матике алгоритм 2.10, получаем грамматику

>Se

5 aSbS I bSaS \ aSb \ abS \ ab \ bSa \ baS \ ba □

Теорема 2.14. Алгоритм 2.10 дает грамматику без е-правил,

эквивалентную входной грамматике.

Доказательство. Непосредственно видно, что алгоритм 2.10 дает грамматику G без е-правил. Чтобы показать, что L{G) = L (G), достаточно доказать индукцией по длине цепочки w,

j что

\ (2.4.3) A=Q,w тогда и только тогда, когда we н A*qW.

Доказательство этого утверждения оставляем в качестве упражнения. Подставив S вместо Л в (2.4.3), видим, что wL{G) для we тогда н только тогда, когда wL{G). Очевидно, что eQL{G) тогда и только тогда, когда eL{G). Таким образом, L{G)L{G). □ V Р >

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

Алгоритм 2.11. у с]т ранение цепных правил. Вход. КС-грамматнка G без е-правил.

Выход. Эквивалентная КС-грамматика G без е-правил и без цепных правил. Метод.

(1) Для каждого N построить К = {ЛЛ=>*В} следующим образом:

(а) Положить No -{Л} и i -1.

(б) Положить N,--= {с вс принадлежит Р и BgN- ,}U

(в) Если N,-=7N; t, положить i = 1 и повторить шаг (б). В противном случае положить NN,-.

(2) Построить Р так: если В-а принадлежит Р и не является цепным правилом, включить в Р правило Л-для всех таких Л, что BGN.

(3) Положить G=(N, 2, Р. S). □

Пример 2.24, Применим алгоритм 2.11 к грамматике Gq с правилами

F-{E)\a

На шаге (1) lj.= {E, Г, F}, N-=1, F], N/..= {F}. После шага (2) множество Р станет таким:

E~EJrT]TF\{E)\a T-Ty.F\(E)\a F{E)\a □

Теорема 2.15. Грамматика G, которую строит алгоритм 2.11, не имеет цепных правил и L{G)L(G).

Доказательство. Непосредственно видно, что алгоритм 2.11 дает грамматику G без цепных правил. Покажем сначала, что L(G)L{G). Пусть wQL{G). Тогда в грамматике G существует вывод 5=Фс4о=Фа[.. .=Фа„ -йУ. Если при переходе от к a,-i применяется правило Л-р, то существует такой символ BN (возможно, В=Л), что Л=>оВ и fi=$>cP. Таким образом, Л=ФоР и a,-=>Ja,-+i. Отсюда следует, что S=a и ш€(С), так что L(G)L{G).

Теперь покажем, что L(G)L{G). Пусть w£L{G) и S = Kg aj .. .=1 oi, - w-левый вывод цепочки ш в грамматике G. Можно найти последовательность индексов 1,1, •••,4, состоящую в точности из тех /, для которых на шаге aj .yiaLj применяется не цепное правило. В частности, ik - n, так как вывод терминальной цепочки не может оканчиваться цепным правилом.

Так как мы рассматриваем левый вывод, то последовательные применения цепных правил заменяют символ, занимающий одну н ту же позицию в левовыводимых цепочках, из которых состоит соответствующая часть вывода. Отсюда видно, что 5=Фа01,1о{=0.. .=>G <Xiw. Таким образом, w£L{G) н,

значит, L{G)=L{G). □

Определение. КС-грамматика G = (N, 2, Р, S) называется грамматикой без циклов, если в ней нет выводов Л=>-*Л для ЛN. Грамматика С называется приведенной, если она без циклов, без -правил и без бесполезных символов i).

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

Теорема 2.16. Если Ь~КС-язык, то L=L(G) для некоторой приведенной КС-грамматики G.

Доказательство. Применить к КС-грамматике, определяющей язык L, алгоритмы 2.8 - 2.11. □

Определение. А-правилом КС-грамматики называется правило вида Ла (не путайте Л-правило с е-правнлом, которое имеет вид В-

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

Лемма 2.14. Пусть G = (N, 2, Р, 5) - КС-гра.чматика и Р содержит правило Л-aSp, где В, а а и принадлежат {[)2у. Пусть Ву\у\.. .\yf,\~ece ВПравила этой грамматики. Пусть G = (N, 2, Р, 5), где

Р = {Р~{А-.аВ})и{А aViP I «Y.P I • • 1 «Y} Тогда L(G)=L(G).

Доказательство. Упражнение. □

) Часто грамматику называют приведенной, просто если в ней нет бесполезных символов.-перев.

Пример 2.25. Устраним правило АаЛЛ из грамматики G, имеющей два правила А -аАА\Ь. Применим лемму 2.14, полагая (х = а,ВА и р=Л, и получим грамматику С с правилами

А-ааААА\аЬА\Ъ

Деревья выводов цепочки ааЪЪЪ в грамматиках G и G показаны на рис. 2.12. Заметим, что эффект этого преобразования

А А Ь b

Рис. 2.12. Деревья выводов: а-в грамматике G; б -в грамматике С*. СОСТОИТ в "склеивании" корня дерева на рис. 2.12, а с его вторым

прямым ПОТОМКОМ. □

2.4.3. Нормальная форма Хомского

Определение. КС-грамматика G(N, S, Р, S) называется грамматикой в нормальной форме Хомского (или в бинарной нормальной форме), если каждое правило из Р имеет один из следующих видов:

(1) А-ВС, где А, В W С принадлежат N,

(2) Л-а, где аТ.,

(3) S-e, если eQL{G), причем 5 не встречается в правых частях правил.

Покажем, что каждый КС-язык порождается грамматикой в нормальной форме Хомского. Этот результат полезен в тех случаях, когда требуется простая форма представления КС-языка.

Алгоритм 2.12, Преобразование к нормальной форме Хомского.

Вход. Приведенная КС-грамматика G = (N, 2, Р, S). Выход. КС-грамматика G в нормальной форме Хомского, эквивалентная G, т. е. L{G)L{G).

Метод. Грамматика G строится по G следующим образом:

(1) Включить в Р каждое правило из Р вида Л-.-о.

(2) Включить в Р каждое правило из Р вида Л ВС.

(3) Включить в Р правило S-e, если оно было в Р.

(4) Для каждого правила из Р вида А Х.. .Х, где > 2, включить в Р правила

А-.Х[ <Х,...Х,>

<х,..,х,>~.х;<х,...х,>

<Xk-2Xk~lXk> Xk--2 ik-iy

<Xy iX> -> Xk-iXii

где Xi = Xi, если X,-G N; X -новый нетерминал, если XS; <X.. .Xft>--новый нетерминал.

(5) Для каждого правила из Р вида Л-уХХ,, где хотя бы один из символов и Ха принадлежит 2, включить в Р правило Л -<- XiXg.

(6) Для каждого нетерминала вида а, введенпого на шагах (4) и (5), включить в Р правило а-а. Наконец, пусть N - это N вместе со всеми новыми нетерминалами, введенными при построении Р. Тогда искомой грамматикой будет G = {W, 2, P\S)). □

Теорема 2.17. Пусть L - КС-язык. Тогда L = L{G) для некоторой YS-гра.мматика G в нормальной форме Хомского.

Доказательство. По теореме 2.16 L определяется приведенной грамматикой G. Алгоритм 2.12 строит по ней грамматику G, которая, очевидно, имеет нормальную форму Хомского. Остается показать, что L{G)L{G). Это доказывается применением леммы 2.14 к каждому правилу грамматики G, в правую часть которого входит а, а затем к правилам с нетерминалами вида <Х....Ху>. □

Пример 2.26. Пусть G -приведенная КС-грамматика, определяемая правилами

аАВ\ВА А ВВВI а BAS\b

Строим Р алгоритмом 2.12, сохраняя правила 5-ВЛ, Аа, B--AS и В-Ъ. Заменяем S-aAB правилами S-а\АВу и <Лй> АВ, а Л -> fiSB -правилами Л -й <SS> и (ВВу-ВВ. Наконец, добавляем а-а. В результате получаем грамматику

) Авторы забыли исключить S из правых частей правил. Надо либо модифицировать алгоритм 2.12, либо, проще, ввести новые символ S и правило 5->5и прежде, чем применять алгоритм 2.12, сделать приведение грамматики.-/7рш1. ред.