А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 60
Текст из файла (страница 60)
а) Грамматика из упражнения 4.2,2, а. б) Грамматика из упражнения 4.2.2, б. в) Грамматика из упражнения 4.2.2, в. г) Грамматика из упражнения 4.2.2, г. д) Грамматика из упражнения 4.2.2, д. е) Грамматика из упражнения 4.2.2, ж. И Упражнение 4.4.2. Возможно ли путем некоторой модификации грамматики построить предиктивный синтаксический анализатор для языка из упражнения 4.2.1 (постфиксные выражения с операндом а)? Упражнение 4.4.3.
Вычислите НКЯТ и ЕОЬЬ0% для каждой из грамматик из упражнения 4.2.1. Упражнение 4.4.4. Вычислите НКЯТ и РОЬЬ0% для каждой из грамматик из упражнения 4.2.2. Упражнение 4.4.5. Грамматика о — а Я а ~ а а генерирует все строки четной длины из символов а. Можно разработать для этой грамматики синтаксический анализатор, работающий методом рекурсивного спуска с возвратом. Если выбирать для разворачивания первой продукцию Я вЂ” а а, то будет распознаваться только одна строка — иа. Следовательно, корректный синтаксический анализатор, работающий методом рекурсивного спуска, должен первой испытывать продукцию Я - а о' а.
299 4.4. Нисходящий синтаксический анализ а) Покажите, что такой синтаксический анализатор будет распознавать строки аа, аааа и аааааааа, но не аааааа. б) Какой язык распознает данный синтаксический анализатор? Следующие упражнения являются шагами представления произвольной грамматики в нормальной форме Хамски (Спошз1су поппа1 Гопп — СЬ(Г), определенной в упражнении 4.4.8. ! Упражнение 4.4.6. Грамматика называется е-свободной если в ней отсутствуют продукции, тело которых представляет собой е (называюшиеся е-нродукиияии). а) Разработайте алгоритм для преобразования произвольной грамматики в есвободную грамматику, генерирующую тот же язык (с возможным исключением в виде пустой строки — ни одна е-свободная грамматика не может генерировать е). Указание: сначала найдите все нетерминалы, которые в состоянии генерировать е, пусть даже путем длинного порождения.
б) Примените ваш алгоритм к грамматике 5- а Я 6 Я ~ Ь Я а Я ) е. ! Упражнение 4.4.7. Единичной (гйп81е) продукцией называется продукция, тело которой состоит из единственного нетерминала, т.е. продукция вида А — В. а) Разработайте алгоритм для преобразования произвольной грамматики в есвободную грамматику без единичных продукций, генерирующую тот же язык (с возможным исключением в виде пустой строки). Указание: сначала удалите е-продукции, а затем найдите, для каких пар терминалов А и В выполняется соотношение А =~ В путем последовательности единичных продукций.
б) Примените ваш алгоритм к грамматике (4.1) из раздела 4.1.2. в) Покажите, что как следствие из п. а данного упражнения можно преобразовать грамматику в эквивалентную ей грамматику без циклов (порождений А =~ А за один или несколько шагов для некоторого нетерминала А). ! Упражнение 4.4.8. Грамматика называется грамматикой в нормальной форме Хамски (СЬошз1гу поппа1 Гопп — СМГ), если все ее продукции имеют вид А — ВС или А — а, где А, В и С вЂ” нетерминалы, а а — терминал. Покажите, как преобразовать любую грамматику в грамматику в нормальной форме Хомоки для того же языка (с возможным исключением в виде пустой строки — ни одна СЬ(Г- грамматика не может генерировать е). ! Упражнение 4.4.9.
Любой язык с контекстно-свободной грамматикой может быть распознан за время О (пз) для строки длиной и. Простой способ сделать это— Глава 4. Синтаксический анализ применить алгоритм Кока — Янгера — Касами (Сос1се — Уоипйег-Кавани' — СУК), основанный на динамическом программировании.
Для данной строки ачаз...а„ строится таблица Т размером п х и, такая, что Тц представляет собой множество нетерминалов, генерирующих подстроку а,а,+~... а . Если в основе языка лежит С)4Р-грамматика (см. упражнение 4.4.8), то одна ячейка таблицы может быть заполнена за время О (и), если заполнять ячейки в правильном порядке, начиная с наименьших значений ) — г, Разработайте алгоритм, который корректно заполняет ячейки указанной таблицы, и покажите, что он имеет время работы О (пз). Если у вас имеется заполненная таблица, как в этом случае определить, принадлежит ли строка а~ аз...
а„языку? ! Упражнение 4.4.10. Покажите, как при наличии заполненной таблицы из упражнения 4.4.9 можно восстановить дерево разбора для а~аз... а„за время О(п). Указание: модифицируйте таблицу таким образом, чтобы для каждого нетерминала А в каждой ячейке Т, она записывала некоторую пару нетерминалов в других ячейках таблицы, которые обосновывают помещение А в Т; .
! Упражнение 4.4.11. Модифицируйте ваш алгоритм из упражнения 4.4.9 таким образом, чтобы для любой строки он находил наименьшее количество вставок, удалений и изменений отдельных символов, необходимых для превращения указанной строки в корректную строку грамматики. ! Упражнение 4.4.12. На рис.
4.24 представлена грамматика для некоторых инструкций. В ней е и в можно рассматривать как терминалы, обозначающие соответственно условные выражения и "прочие инструкции". Если разрешить конфликт, связанный с разворачиванием необязательного е1яе (нетерминал атг2йл), путем обязательной выборки из входного потока имеющегося там е1ве, то для приведенной грамматики можно построить предиктивный синтаксический анализатор.
Воспользуйтесь идеей синхронизирующих символов из раздела 4.4.5 и выполните следующее. а) Постройте для данной грамматики таблицу исправляющего ошибки предиктивного синтаксического анализа. б) Покажите, как поведет себя ваш синтаксический анализатор для следующих входных строк: 1) 11е 1Ьеп в; 11 е 1Ьеп а епд й) иЬИе е йо Ье81п а; 11 е 1Ьеп я; епй 4.5. Восходящий синтаксический анализ згт! — !Т е ГЬеп згтг згтгТа!1 нЫ!е е йо згт! Ьей!п Ъ! епд и згтгТаг1 — еае згт! е згт! 1В7Та!1 1гз7Та!1 — Ь я! Рис. 4.24.
Грамматика для некоторых инструкций 4.5 Восходящий синтаксический анализ Восходящий синтаксический анализ соответствует построению дерева разбора для входной строки, начиная с листьев (снизу) и идя по направлению к корню (вверх). Удобно описывать синтаксический анализ как процесс построения дерева разбора, хотя начальная стадия компиляции может в действительности быть выполнена и без явного построения дерева. Последовательность "снимков" деревьев разбора на рис.
4.25 иллюстрирует восходящий синтаксический анализ для потока токенов н! * И в соответствии с грамматикой выражений (4.1). Т Ы т Ы 7' » Р Е Ы Ы Ы ~ Ы Т ~ Ы 1 Ы т /!'~ т ю е т йи ! !и т /!'~ т * т Т Ы Рис. 4.25. Восходящий синтаксический анализ для строки !а * Ы В этом разделе будет рассмотрен общий вид восходящего синтаксического анализа, известный как синтаксический анализ типа "перенос/свертка" (зЬ1й-гебпсе). В разделах 4.6 и 4.7 будет рассмотрен большой класс грамматик, для которых могут быть построены синтаксические анализаторы, работающие по принципу переноса/свертки — 1.К-грамматики. Хотя построение !.К-анализатора вручную — задача очень трудоемкая, автоматические генераторы синтаксических анализаторов делают создание эффективных (.К-анализаторов для соответствующих грамматик достаточно простым занятием.
Концепции, рассматриваемые в данном разделе, полезны при написании грамматик для эффективного использования генератора зог Глава 4. Синтаксический анализ ЬВ-анализаторов. Алгоритм для реализации генераторов синтаксических анали- заторов приводится в разделе 4.7. 4.5.1 Свертки Можно рассматривать восходящий синтаксический анализ как процесс "свертки'* строки ш к стартовому символу грамматики. На каждом шаге свертки (гедисг)оп) определенная подстрока, соответствующая телу продукции, заменяется нетерминалом из заголовка этой продукции. Ключевые решения, принимаемые в процессе восходящего синтаксического анализа, — когда выполнять свертку и какую продукцию применять. Пример 4.23.
Снимки на рис. 4.25 иллюстрируют последовательность сверток; используемая грамматика — грамматика выражений (4.1). Свертки будут рассматриваться в терминах последовательности строк Ы*Ы,Е*Ы,Т*Ы,Т*Е,Т,Е Строки этой последовательности образованы корнями всех поддеревьев на снимке. Последовательность начинается со входной строки И*И. Первая свертка дает Е * Ы путем свертывания крайнего слева Ы в Е с использованием продукции Š— Ы. Вторая свертка дает Т я И при помощи свертывания Е в Т. После этого у нас есть выбор между сверткой строки Т, которая является телом продукции Š— Т, и строки, состоящей из следующего И, являющегося телом продукции Š— Ы. Вместо того, чтобы выполнять свертку Т в Е, свернем второй Ы в Е, получая строку Т*Е. Затем эта строка сворачивается в Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
