Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 63
Текст из файла (страница 63)
Например, 5=О,ммм а, 0011, й (1352544) — 12 и 5=>„О 001! Грамматика 6, не лево- и не правопокрывает 6,, Так как обе грамматики однозначные, то соответствие между разборами фе ксировано. Поэтому гомоморфизм д, доказыва|ощий, что б, лево' покрывает б„должен отображать 1 "2 в (143)'24(5)"+|, а эта как легко показать, невозможно. Можно показать, что многие из конструкций разд. 2.4, пре' образующих грамматики к нормальным формам, дают грамма' тики, лево. или правопокрывающие исходные грамматики.
310 РПР ЛЖИ Е НИЯ Пример 3.28, Ключевой шаг при построении нормальной формы Хомского (алгоритм 2.12) состоят в замене правила А Х,... Х„(п) 2) правилами А — Х,В„В,Х,  — Х„,Х„, Можно показать, что в результате получа с гра 1л тя а левопокрь|ва|ощая исходную: достаточно Отобразить правило А — Х,В| в А — Х,, Х„, а каждое из правил В, Х,вэ  —, — Х„,Х„в пустую цепочку. Если мь| хотим получить пРавое покРытие, то А Х,...
Х„можно заме ть на А- В1Х„, В| В Х„„..., „— Х Х г) Другие РезУльтаты о покрытии оставляем в качестве у ражнений. УПРАЖНЕНИЯ ' 3.4,1. Дайте алгоритм построении дерева вывода по левому вли правому разбору. 3,4.2. Пусть б — КС-грамматика. Покажите, что 7 о — детерми- нированнын КС-язык.
3.4 3. Всегда ли 7,Π— детерминированный КС-языку *3.4.4. Постройте детерминированный МП-преобразователь Р, для которого т(Р)=((и, и')!ПЕ(,1О и и' — правый разбор для того же дерева вывода). +3.4.3. М Можете ли Вы построить такой детерминированный МП-преобразователь Р, что т(Р) — ((и, и')!ПЕ~О и и' — соот- ветствующий левый разбор). 3.4.6. Постройте левые и правые разборы в грамматике 6 для пепочек е (а) ((а)), (б) а-(- (а+ а), (в) а э а я а. 3.4.7.
4 7. Пусть КС-грамматика б определяется следующими за- нумерованными правилал|и: (!) 5 — ИВ 1)|еп5е(эе5 (2) 5 — е (3) в в р, в (4)  — В 'ч' В (5) в-ь Пост Ой Ро"те СУ-схемы, определяющие Т~г и То. ЗА.8, Пос остройте МП-преобразователи, определяющие 77 и Те грамматики 6 из упр. 3.4.7. З|1 Гл. а. ТеОРия переводА РПРАЖНРНИЯ 3.4.9. Докажите теорему 3.10. 3;4.!О. Докажите теорему 3.11.
3.4.1!. Дайте определение СУ-схемы Т~ и докажите, что Ваша схема отображает цепочки нз Е(О) в их правые разборы. 3.4.12. Дайте алгоритм, превращающий расширенный МП- преобразователь в эквивалентный МП-преобразователь. Ваш алгоритм должен быть таким, чтобы при применении его к детерминированному расширенному МП-преобразователю получался ДМП-преобразователь. Докажите, что Ваш алгоритм делает это. 3.4.13. Докажите теорему 3.12.
"3.4.! 4. Постройте детерминированные правые анализаторы для грамматик (а) (1) 5 — 50 (2) 5 — 51 (3) 5- е (б) (1) 5 — АВ (2) А — ОА1 (3) А — е В В1 (5) В- е а3.4.15. Постройте детерминированные левые анализаторы для грамматик (а) (1) 5 05 (2) 5- 15 (3) 5 е (1) 5 051 (2) 5 — А (3) А — А1 (4) А е *3.4.19. Какие из грамматик в упр.
3.4.14 имеют детерминированные левые анализаторы? Какие в упр. 3.4.15 имеют детерминированные правые анализаторы? "3,4.17, Дайте детальное доказательство того, что грамматика из примера 3.25 (3.27) право- (лево-)анализируема, но не лево- (право-)анализируема. 3.4.13. Дополните доказательство теоремы 3.14. 3.4.19. Дополните доказательство леммы 3.15. 3.4.20. Дополните доказательство теоремы 3.15.
3!2 Определение. Левым участком правила с непустой правой частью назовем самый левый символ (термицал или нетерминал) его правой части. Анализом (или ризбором) цепочки ло левому участку называется последовательность правил, соответствующих внутреннвм вершинам дерева разбора этой цепочки, п котором все вершины упорядочены следующим образом. Если верпзина л имеет р прямых потомков п„л,„..., л, то все вершины поддерева с корнем л, предшествуют л. Вершийа л предшествует всем другим ее потомкам.
Потомки вершнны л, предшествуют потомкам вершины л„которые в свою очередь предшествуют потомкам вершины л, и т. д. Грубо говоря, при анализе по левому участку левый участок правила распознается снизу вверх, а остальная часть правила †свер вниз. Пример 3.30. На рис. 3.11 показано дерево разбора цепочки 66ааа6, |юрождеиной грамматикой с правилами (1) 5 А5 (2) 5 ВВ (3) А- ЬАА (4) А а (5) В Ь (5)  — е Упорядочение вершин, о котором идет речь в определении анализа по левому участку, таково, что вершина л, и ее по- о езеа Очам Оеам Оаа!а фаЗ (3)аза фпзз ! Оааы ®азв Рис.
3.1!. Дерево разбора. томки предшествуют вершине л„за которой следуют л, и ее потомки. Вершина л, предшествует вершине л„за которой следуют л„л„и их потомки. Вершнна п, предшествует вершине л,„ за котоРой слеДУют льи п„н их потомки. ПРоДолжаЯ в том же духе, получаем упорядочение вершин ПАП зле П з П з з Паз П за Пз зП з з П зП з ПА з П з ПАП А А П з 3!3 ГЛ. 3. ТЕОРИЯ ПЕРЕНОДА ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ Разбором по левому участку является последовательность правил, соответствующих внутренним вершинам в этом упорядоченни.
Таким образом, разбором цепочки ЬЬаааЬ по левому участку будет последовательность 334441625. 11 Другой метод определения разбора по левому участку для цепочки, порождаемой грамматикой 6, заключается в использовании следующей простой СУ-схемы, ассоциируемой с 6. Определение. Пусть 6=(Ь(, 2', Р, В) — КС-грамматика, в которой правила занумерованы От 1 до р. Пусть Т$ — простая СУ- схема (Х, у, (1,..., р), ??, В), где для каждого правила из Р в множество 1? включается правило, определяемое так: если 1-е правило из Р имеет ввд А — Ва или А — аа, вли А — е, то В содержит правило вида А — Все, В(а'.Илн А — аа, (сх', или А — е, ! соответственно, где а' получается 'из и удалением всех терминальных символов. Тогда если (ю, я) 6т(ТД, то и — разбор по левому участку цепочки те.
Пример 3.3!. Для грамматики из предыдущего примера схема Тг', такова:  — АЗ, А!В В ВВ, В2В А- ЬАА, ЗАА А- а 4  — Ь, 5  — е, 6 Можно убедиться, что (ЬЬаааЬ, 334441625) 6т(Т~О). 3.4.2!. Докажите, что (ю, п)6т(ТУ) тогда и только тогда, когда зт — разбор по левому участку цепочки те, 3.4.22. Покажите, что для каждой КС-грамматики существует (недетерминированный) МП-преобразователь, отображающий цепочки языка, порождаемого этой грамматикой, в их разборы по левому участку. 3.4.23. Разработайте алгоритмы, отображающие разборы по левому участку в (1) соответствующие левые разборы, (2) соответствующие правые разборы, и обратно.
3.4.24. Покажите, что если 6, лево- (право-)покрывает 6, и 6, лево- (право-)покрывает б„то бх лево- (право-)покрывает б,. 3.4.26. Пусть 6„— грамматика без циклов, Покажите, что б, лево- н правопокрывается грамматвками, пе содержащими цепных правил. 3.4.26. Покажите, что каждая грамматика без циклов левон правопокрывается грамматиками в нормальной форме Конского. «3.4.27. Покажите, что не каждая КС-грамматика покрывается грамматикой, не содержащей е-правнл. 314 3.4.26.
Покажите, что алгоритм 2.9, устраняющий бесполезные символы, дает грамматику, лево- н правопокрывающую исходную. **3.4.29. Покажите, что не каждая приведенная грамматика лево- или правопокрывается грамматикой в нормальной форме Грейбах. Указаниет Рассмотрите грамматику  — ВО~ В!~0)1. "*3.4.30. Покажите, что утверждение из упр. ЗА.29 остается верным, если в определении покрытая заменить гомоморфизм конечным преобразованием. «3.4.31. Останется ли верным утверждение из упр 3 4.29, если заменить гомоморфизм МП-преобразованием, Проблема для исследования 3.4.32.
Было бы хорошо, если бы всегда, когда 6, левоили правопокрывает б„каждая СУ-схема с б, в качестве входной грамматики была эквивалентна некоторой СУ-схеме, входной грамматикой которой служит 6,. К сожалению, это не так. Можете ли Вы найти условия, связывающие 6, и б„при которых СУ- схемы с входной грамматикой 6, образуют подмножество СУ- схем с входной грамматикой 6,? Замечания по литературе Дополнительные подробности, кзсзхзщнеся грамматического покрытия, можно нзйтн в роботах Рейнольдсз н Хзскелн !19701, Грэя [19691 н Грэя и Хзррнсоиа !19691. В некоторых рзнннх статьях эпзлнз по левому учзстку нззывэлся восходящим знзлнзом. Более полное изложение метода знвлизв по левому участку содержится в монографии Чнтэма !1967!.
316 3!7 ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Эта глава посвящена алгоритмам синтаксического анализа, применимым ко всему классу контекстно-сободных языков. Не все эти алгоритмы можно применять к любым КС-грамматикам, ио каждый КС-язык имеет хоти бы одну грамматику, к которой все аии применимы. Вначале мы обсудим алгоритмы с полным возвратом. Эти алгоритмы детерминированно моделируют недетерминировапные анализаторы, Емкость памяти, которую 'требуют эти возвратные методы, линейно зависит от длины анализируемой цепочки, но время может выражаться экспонентой.
Алгоритмы, рассматриваемые во втором разделе главы, носят табличный характер; это алгоритм Кока — Янгера — Касами и алгоритм Эрли. Они затрачивают емкость и' и время и". Алгоритм Эрли работает для любой КС-грамматики и для него требуется время и', если грамматика однозначная. Алгоритмы этой главы включены в книгу главным образом для того, чтобы пояснить внутренние проблемы, связанные с построением анализаторов. С самого начала следует вполне определенно заявить, что в большинстве практических применений надо избегать возвратных алгоритмов разбора. Даже табличные методы (а они асимптотически гораздо более быстрые, чем алгоритмы с возвратами) неприемлемы, если для интересующего нас языка существует грамматика, к которой применимы более эффективные алгоритмы, описываемые в гл. 5 и б.
Можно почти не сомневаться в том, что фактически для всех языков программирования существуют легко анализируемые грамматики, к которым эти алгоритмы применимы. Методы данной главы могут оказаться полезными в таких приложениях, когда исходные грамматики не обладают теми специальными свойствами, которых требуют алгоритмы, рассматриваемые в гл. 5 н 6. Например, если требуются неоднозначные еь синтхксичвскип анализ с возвгхтхми грамматики и интерес представляют все разборы цепочки, как это бывает при работе с естественными языками, можно обра- титься к некоторым методам данной главы. 4.1. СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ Предположим, что у нас есть недетерминированный МП- преобразователь Р и входная цепочка ш.
Допустим, что все последовательности тактов, которые может сделать Р для входной цепочки ш, ограничены по длине. Тогда общее число различных последовательностей тактов МП-преобразователя Р тоже конечно, хотя, нозможна, и экспоненциально зависит от длины цепочки ш. Грубый, зато прямой способ детерминированного моделирования МП-преобразователя Р состоит в том, чтобы каким-то образом линейно упорядочить последовательности тактов и затем в предпнсанном порядке промоделировать каждую последовательность. Если нас интересуют все выходные цепочки для данной входной цепочки ш, то мы должны промоделировать все последовательности тактов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
