(1) Каждый из классов грамматик (а) - (з) порождает в точности класс детерминированных контекстно-свободных языков:

(а) LR, (в) ОПК, (Д) ССП, (ж) обратимые

(2,1)-предшествования,

(б) LR(1), (Г) (1,1).0ПК, (е) простые ССП, (з) анализируемые по Флойду-Эвансу.

(2) LL-языки образуют собственный подкласс детерминированных КС-языков.

контекстнасвабадные грамматшси

анализируемые по Флойду-Эданад

операторного пре&ш.встбобана.п

простые ZZX<

обратимые расш.ирениозо првдш.ест6о8ания л

обратимые слссбозо предилествования

про от о во предисестбо ваиия

Рис. 5.22, Иерархия грамматик.

(3) Обратимые грамматики слабого предшествования порождают в точности класс языков простого предшествования, который

(а) является собственным подклассом Детерминированных КС-языков и

(б) несравним с классом LL-языков.

Для входной цепочки Ьа анализатор сделает такую 1юслед0-вательность шагов:

[L0, $, Ьа$, е][-[1Л, а$, е]

\-[L2, <pb, й$, е]

[-[10, %Ь, а$, е]

h-[LK $Ьа, $. е]

Н[£4, $bS, S, 3]

\-[L5, $65, $, 3]

\-lL4, $S. $, 32]

i-[£5, $5, $, 32]

f-[£6, $5, $ 32]

Цепочка допускается после выполнения оператора L6. Последовательность шагов для цепочки аа такова:

[L0, $, аа$, e]\-[Ll, $а, а$, е]

l-[L4, 5>S, а$, 3]

h-[L5, $S, 4, 3]

h-[L6, $S. a$, 3]

[~[L7, $S, 4, 3]

Оператор L7 объявляет об ошибке, хотя aaL(G).

В примере 5.48 ничего мистического нет. Программа анализатора, написанная на языке Флойда - Эванса, не так тесно связана с грамматикой, для которой она производит разбор, как другие алгоритмы этой главы со своими грамматиками. Ц

В гл. 7 мы дадим алгоритм, механически порождающий анализатор, написанный на языке Флойда - Эванса, для обратимой грамматики слабого предшествования.

S.4.5. Резюме

Диаграмма на рис. 5.22 демонстрирует иерархию грамматик, рассмотренных в этой главе. Все включения на этой диаграмме юбственные. В качестве упражнений предлагаем доказать включения, которые мы не доказывали в этой главе. Включение класса LL-грамматик в класс LR-грамматик будет доказано 5 гл. 8.

Что касается классов языков, порождаемых грамматиками )тих классов, то получены следующие результаты:

(4) Класс языков, порождаемых грамматиками операторного предшествования, тот же, что и для обратимых грамматик этого тина. Он является собственным подклассом языков простого предшествования.

Многие из перечисленных результатов о классах языков можно будет иайти в гл. 8.

Читатель может, конечно, спросить, какой из этих классов грамматик больше всего подходит для описания языков программирования и какой метод синтаксического анализа наилучший. Однозначного ответа на такой вопрос нет. Желание использовать простейший класс грамматик часто может потребовать каких-то манипуляций с данной грамматикой, необходимых для ее преобразования в грамматику из этого класса. При этом нередко грамматика становится неестественной и неудобной для использования ее в схеме синтаксически управляемой трансляции.

Очень привлекательны для практического применения LL(I)-грамматики. Для каждой такой грамматики можно построить компактный быстрый анализатор, производящий левый разбор, что имеет преимущества с точки зрения трансляции. Однако здесь есть и неудобства. ЬЬ(1)-грамматика для данного языка может оказаться неестественной и ее трудно построить. Кроме того, как будет показано в гл. 8, не каждый Детерминированный КС-язык определяется LL-грамматикой, а тем более LL(l)-rpaM-матикой.

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

Метод ЕН(1)-анализа, изложенный в этой главе, очень близок к описаппому в оригинальной работе Кнута. Получающиеся при этом анализаторы могут быть очень большими. В гл. 7 будет описана техника построения ЕН(1)-анализаторов, которые по своим размерам и скорости работы могут для широкого спектра языков программирования конкурировать с анализаторами, работающими методом предшествования. Некоторые эмпирические данные приведены в статье Лалонда и др. [1971]. Так как LR(l)-rpaMMaTHKH образуют широкий класс грамматик, методы ЬК(1)-апализа представляются весьма привлекательными.

Наконец, подчеркнем, что в конкретных приложениях часто

МОЖНО улучшить реализацию любой техники разбора. В гл. 7 мы опишем методы, с помощью которых можно уменьшить объем и увеличить скорость анализаторов.

УПРАЖНЕНИЯ

5.4.1. Постройте алгоритм разбора типа „перенос-свертка" для (1,0)-ОПК-грамматики Gi из примера 5.41.

5.4.2. Какие из следующих грамматик являются (1, 1)-0ПК-грамматиками?

(а) S-aA\B А-0Л1\а B-QBl\b

(б) S~aA\bB Л-0Л101 В~0В1\01

(в) Е-Е + Т\Е - Т\Т Т-Т Е\Т I F\F

F -{Е)\-Е\а

Определение. Приведенная КС-грамматика G = (N, S, Р, S) называется грамматикой (т, п)-ограниченного контекста (ОК), если из условий

(1) $"5$":*a,iyi=>aipiyi в пополненной грамматике,

(2) $"5$"=4>*сс2ЛаУ2=>а2РаТ2""зР1Тз в пополненной грамматике,

(3) последние т символов цепочек и осд, а также первые п символов цепочек у и Уз совпадают

вытекает, что OlglVs ггТг-

5.4.3. Покажите, что каждая (т, п)-ОК-грамматика является (т, /г)-ОПК-грамматикой.

5.4.4. Разработайте алгоритм разбора типа „перенос-свертка" для ОК-грамматик.

5.4.5. Дайте пример ОПК-грамматики, которая не является ОК-грамматикой.

5.4.6. Докажите, что каждая обратимая грамматика расширенного предшествования является ОПК-грамматикой.

5.4.7. Покажите, что каждая ОПК-грамматика является грамматикой расширенного предшествования (не обязательно, разумеется, обратимой).

5.4.8. Для грамматик из упр. 5.4.2, которые являются (1, 1)-ОПК-грамматиками, постройте алгоритмы разбора типа „перенос-свертка" и их реализацию в виде дерева решений.

S. Л-

S-А-

А В •0Л1101 -2S1 i 1 •А\В -0Л101 05111

А\В 0Л1101

01S1 101

5.4.12. Докажите, что каждая обратимая грамматика слабого предшествования является простой ССП-грамматикой.

5.4.13. Является ли каждая (т, п\ т, /г)-ССП-грамматика {т, п)-ОПК-грамматикой?

5.4.14. Докажите теорему 5.24.

5.4.15. Являются ли следующие операторного предшествования?

(а) Грамматика из упр. 5.4.2(6).

(б) -

грамматики грамматиками

5-S-S-В В-5-5.

В-В-

если В ->если В ->-s

-В или Ъ

-9-если В -+если В -9-если В

-9- S

В или b

то то

иначе

иначе

то Si то S то S-y иначе

В пунктах (б) и (в) подразумевается, что если, то, иначе, или, Ь, S-терминальные символы.

5.4.16. Для грамматик из упр. 5.4.15 постройте остовные грамматики.

5.4.17. Постройте алгоритмы разбора d = {fy g) для грамматик из упр. 5.4.15, которые являются грамматиками операторного предшествования.

5.4.18. Докажите теорему 5.25.

5.4.19. Покажите, что для каждой грамматики операторного предшествования G соответствующая остовная грамматика обратима.

*5.4.20. Покажите, что каждый язык операторного предшествования определяется грамматикой операторного предшествования без цепных правил.

*5.4.21. Покажите, что каждый язык операторного предшествования определяется обратимой грамматикой операторного предшествования.

5.4.22. Для грамматик из упр. 5.4.2 напишите анализаторы на языке Флойда-Эванса.

5.4.23. Покажите, что для каждой ОПК-грамматики существует анализатор, написанный на языке Флойда-Эванса.

5.4.24. Покажите, что для каждой ЬЬ(й)-грамматики существует анализатор на языке Флойда-Эванса (порождающий левые разборы).

**5.4.25. Докажите неразрешимость следующих проблем: является ли КС-грамматика

(а) ОПК-грамматикой?

(б) ОК-грамматикой?

(в) ССП-грамматикой?

5.4.26. Докажите, что G = (N, 2, Р, S)-простая ССП-грам-матика тогда и только тогда, когда она грамматика слабого предшествования и если Л-и В-j-a содержатся в Р, причем АфВ, то 1{А)Г\1(В) = 0.

*5.4.27. Допустим, что мы ослабили определение операторной грамматики, не требуя, чтобы она была приведенной и не содержала -правил. Покажите, что L - язык операторного предшествования в смысле нового определения тогда и только тогда, когда L - {е} - язык операторного предшествования в смысле старого определения.

5.4.28. Расширьте алгоритм Домёлки, упоминаемый в упражнениях разд. 4.1, так, чтобы его можно было использовать для анализа ОПК-грамматик.

Определение. Можно обобщить идею операторного предшествования так, чтобы в разборе участвовали не только все терминалы, но и некоторые нетерминалы. Пусть G = (N, 2, Р, S)- приведенная КС-грамматика без е-правил и Т - подмножество множества Nu2, причем 2Г. Пусть KNUS. Грамматику G назовем Т-канонической, если

5.4.9. Докажите необходимость условия из леммы 5.6.

5.4.10. Докажите теорему 5.22.

5.4.11. Какие из следующих грамматик являются простыми ССП -грамматиками?