Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 102
Текст из файла (страница 102)
5.22. Иерархия грамматик. Диаграмма на рис. 5.22 демонстрирует иерархию грамматик, ~ассмотренных в этой главе. Все включения на этой диаграмме обственные. В качестве упражнений предлагаем доказать вклюения, которые мы не доказывали в этой главе.
Включение ласса ЕЕ-грамматик в класс ЕЙ-грамматик будет доказано гл. 8. Что касается классов языков, порождаемых грамматиками тнх классов, то получены следующие результаты: 503 [ЕО, $, Ьа$, е1'à — [1.1, 1 — [Е2, 1 — [ЕО, 1 — [Е1, (- [Е4, 1 — [Е5, 1 — [Е4, 'г- [Е5, 'г — [Еб, $Ь, а$, е1 $Ь, а$, е[ $Ь, а$, е| $Ьа, $, е1 $Ы, $,31 $Ь5, $, 31 $3, $,32) $$, $, 32) $3, $ 32! (1) Каждый из классов грамматик (а) — (з) порождает в точ- ности класс детерминированных контекстно-свободных языков: (а) !.)1, (б) 1 Й(1), (в) ОПК, (г) (1,1)-ОПК, (д) ССП, (е) простые ССП, (ж) обратимые (з) анализируемые по (2,1)-предшествовання, Флойду — Эвансу.
(2) 1Л.-языки образуют собственный подкласс детерминированных КС-языков. ох и") ! !),!)-Опк просигме ССП одран!им (3) Обратимые грамматики слабого предшествования порождают в точности класс языков простого предшсствования, который (а) является собственным подклассом детерминированных КС-языков и (б) несравним с классом 1.1-языков. Гл.
з, ОднОпРОхОдный сннтлкснчвскин лнллнз Бвз возвРлтов Рпглжнвння (4) Класс языков, порождаемых грамматиками операторного предшествовання, тот же, что и для обратимых грамматик этого типа. Он является собственным подклассом языков простого предшествования. Многие из перечисленных результатов о классах языков можно будет найти в гл. 8. Читатель может, конечно, спросить, какой из этих классов грамматик больше всего подходит для описания языков программирования и какой метод синтаксического анализа наилучший.
Однозначного ответа на такой вопрос нет. 7Келание использовать простейший класс грамматик часто может потребовать каких-то манипуляций с данной грамматикой, необходимых для ее преобразования в грамматику из этого класса. При этом нередко грамматика становится неестественной и неудобной для использования ее в схеме синтаксически управляемой трансляции. Очень привлекательны для практического применения 1Л,(!)- грамматики. Для каждой такой грамматики можно построить компактный быстрый анализатор, производящий левый разбор, что имеет преимущества с точки зрения трансляции.
Однако здесь есть н неудобства. 1.1.(1)-грамматика для данного языка может оказаться неестественной и ее трудно построить. Кроме того, как будет показано в гл. 8, не каждый детерминированный КС-язык определяется 1.1.-грамматикой, а тем более 1(.(1)-грамматикой. Метод операторного предшествовання применялся в нескольких компиляторах, он легко реализуется и работает очень эффективно.
Грамматики простого предшествования тоже легко анализируются, но чтобы получить такую грамматику для данного- языка, часто требуется добавить много цепных правил вида А - Х для устранения конфликтов отношений предшествования. Кроме того, существует много детерминированных КС-языков, которые нельзя определить ни грамматиками простого предшествовання, ни обратимыми грамматиками слабого предшествования. Метод (.К(1)-анализа, изложенный в этой главе, очень близок к описанному в оригинальной работе Кнута.
Получающиеся при этом анализаторы могут быть очень болыпими. В гл. 7 будет описана техника построения (,й(1)-анализаторов, которые по своим размерам и скорости работы могут для широкого спектра языков программирования конкурировать с анализаторами, работающими методом предшествовапия. Некоторые эмпирические данные приведены в статье Лалонда и др. [!97!1. Так как (.Й(1)-грамматики образуют широкий класс грамматик, методы ).)1(!)-анализа прсдставляются весьма привлекательными. Наконец, подчеркнем, что в конкретных приложениях часто 504 улучшить реализацию любой техники разбора. В гл. 7 можно у у мы опишем методы, с помощью которых можно уменьшить о ь бьем и увеличить скорость анализаторов, УПРАЖНЕНИЯ Я 5.4.1.
Постройте алгоритм разбора типа „перенос — свертка для (1,0)-ОПК-грамматики В, из примера 5.41. 5.4.2. Какие из следующих грамматик являются (1, 1)-ОПК- грамматикамиу (а) В- аА!В А 0А1!а  — ОВ1(Ь (б) 3 — аА )ЬВ А ОА! )01  — ОВ1(0! (в) Š— Е+Т(Š— Т! Т т вот е(Т7е(е (Е)! — Е!и Определение. Приведенная КС-грамматика б = (л), г,, Р, В) называется гриилиипикой (т, и)-ограниченного коншекста (ОК), если из условий (!) 5 В'$" =О"а,А,у, =:>а,()д, в пополненной грамматике, (2) 3 В'3"-=:>'а,Агу,=>и,,!1д,.=иод, в пополненной грамматике, (3) последние и символов цепочек а, и а„а также первые п символов цепочек у, и у, совпадают вытекает, что и,А17,=-а,А,7,.
5А.З. Покажите, что каждая (и, и)-ОК-грамматика является (и, п)-ОПК-грамматикой. 5.4.4. Разработайте алгоритм разбора типа „перенос — свертка" для ОК-грамматик. 5.4.5. Дайте пример ОПК-грамматики, которая не является ОК-грамматикой. 5.4.6. Докажите, что каждая обратимая грамматика расширенного предшествования является ОПК-грамматикой. 5.4.7. Покажите, что каждая ОПК-грамматика является грамматикой расширенного предшествовання (не обязательно, разумеется, Обратимой).
5.4.8. Для грамматик из упр. 5.4.2, которые являются (1, 1)-ОПК-грамматиками, постройте алгоритмы разбора типа „перенос — свертка" и их реализацию в виде дерева решений, 505 гл. к однопгоходный синтхксичаский лнллиз ввз аозаглтаа тпелжнения 5.4,9. Докажите необходимость условия из леммы 5.5. 5.4.10.
Докажите теорему 5.22. 5.4,11. Какие из следующих грамматик являются простыми ССП-грамматнками? (а) 6, (б) 5- А)В А — ОА! !01 В- 2В1)! (в) 5 — А (В А- ОА! (О!  — ОВ1) ! (г) 5 — А / В А-- ОА1!01  — 01В! !О! 5.4.12, Докажите, что каждая обратимая грамматика слабого предшествования является простой ССП-грамматикой. 5А.13. Является ли каждая (лг, и; гл, л)-ССП-грамматика (и, п)-ОПК-грамматикой? 5.4,14, Докажите теорему 5.24.
5,4.15. Являются ли следующие грамматики грамматикамн операторного предшествоваиия? (а) Грамматика из упр. 5.4.2(б). (б) 5 — если В та 5 иначе 5 5 — если В то 5 5 з В- В или Ь В вЂ” Ь (в) 5 — если В та 5, иначе 5 5- если В то 5 5,— если В то 5, иначе 5, 5 — з 5,— з В- Вили Ь В вЂ” Ь В пунктах (б) и (в) гюдразумевается, что если, то, иначе, или, Ь, з — терминальные символы.
5.4.16. Для грамматик из упр. 5.4.15 постройте остовные грамматики. 5.4.17. Постройте алгоритмы разбора 4 = (г, д) для грамматик из упр. 5.4.15, которые являются грамматиками операторного предшествования. 5.4.18, Докажите теорему 5.25. 5.4.19. Покажите, что для каждой грамматики операторного предшествования 6 соответствующая остовная грамматика 6, обратима. "5.4.20. Покажите, что каждый язык операторного предшествования определяется грамматикой операторного предшествавания без цепных правил. "5.4.21. Покажите, что каждый язык операторного предшествования определяется обратимой грамматикой операторного пред- шествования. 5.4.22. Для грамматик из упр. 5.4.2 напишите анализаторы на языке Флойда — Эванса.
5.4.23. Покажите, что для каждой ОПК-грамматикн существует анализатор, написанный на языке Флойда — Эванса. 5.4,24. Покажите, что для каждой !.!.(е)-грамматики существует анализатор на языке Флойда — Эванса (порождающий левые разборы). **5.4.25. Докажите неразрешимость следующих проблем: явля. ется ли КС-грамматика (а) ОПК-грамматикой? (б) ОК-грамматикой? (в) ССП-грамматикой? 5.4,26, Докажите, что 6 — (Ь(, Е, Р, 5) — простая ССП-грамматика тогда и только тогда, когда она грамматика слабого предшествования и если А — и и  — а содержатся в Р, причем А че, В, то 1(А) !)1(В) = 8.
*5.4.27. Допустим, что мы ослабили определение операторной грамматики, не требуя, чтобы она была приведенной и не содержала е-правил. Покажите, что 7 — язык операторного предшествования в смысле нового определения тогда и только тогда, когда 1.— (е) — язык операторного предшествовапия в смысле старого определения. 5,4.28. Расширьте алгоритм Домелки, упоминаемый в упражнениях разд, 4.1, так, чтобы его можно было использовать для анализа ОПК-грамматик. Определение.
Можно обобщить идею операторного предшествования так, чтобы в разборе участвовали не талька все терминалы, но и некоторые нетерминалы. Пусть 6 — (Ь(, Х, Р, 5)— првведенная КС-грамматнка без е-правил и Т вЂ” подмножество множества ХИТ, причем Х~ Т. Пусть )'=Ь(0 Х, Грамматику 6 назовем Т-канонической, если 507 ГЛ.
Е. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ УПРАЖНЕНИЯ (!) для каждой правой части правила, скажем яХгр, нз Х(Т следует УЕХ; (2) из А ЕТ н Л=>'я следует, что я содержит символ из Т. Таким образом, В-каноническая грамматика — это то же что операторная грамматика. Для Т-канонической грамматики 6 будем называть множество Т множеством ее знаменательных символов. Зададим для Т-канонической грамматики 6 относиения Т-канонического предшествования на Т0 ф: (!) Если в Р есть правило Л вЂ” +яХ!) у, Х и ! содержатся в Т и 5 — либо е, либо содержится в $' — Т, то Х г.
(2) Если А — яХВ!)ЕР и В~ уг'б, где Х и г' содержатся в Т и у — либо е, либо содержится в )г — Т, то Х ( ) . (3) Пусть Л вЂ” ягВя,2яаЕР, где я,— либо е, либо символ из 7 — Т. Допустим, что 2=='>'()га()„где )т,— либо е, либо содержится в Р— Т и а Е А. (Заметим, что по определению Т-канонической грамматики этот вывод должен быть тривиальным, т. е. состоять из нуля шагов, если я,~е.) Допустим также, что существует вывод В => У,С,б,.=Э У,У,С,б,бг~ ... ~ Уд ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
