Главная Промышленная автоматика.

(б) S~-AB, Л-ОЛ\\е, S-1S1,

(в) 5-051Л, Л--1Л1,

(г) 5~5 + ЛЛ, A-{S)\a{S)\a.

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

5.2.2. Какие из грамматик упр. 5.2.1 являются LR(0)-rpaM-матиками?

5-2.3. Постройте системы LR(l)-тaблиц для тех грамматик из упр. 5.2.1, которые являются LR(l)-rpaMMaTHKaMH. Не забудьте сначала пополнить эти грамматики.

5.2.4. Напишите последовательность шагов, которую сделает ЬК(1)-анализатор для грамматики прн входе (й + с) *

{а-\-{а + а)*а).

*5.2.5. Докажите или опровергните каждое из следующих утверждений:

(а) Каждая праволинейная грамматика является LL-грамматикой.

(б) Каждая праволинейная грамматика является LR-грамматикой.

(в) Каждая регулярная грамматика является LL-грамматикой.

(г) Каждая регулярная грамматика является LR-грамматн-кой.

(д) Каждое регулярное множество определяется LL(l)-rpaM-матикой,

(е) Каждое регулярное множество определяется LR(l)-rpaM-матикой.

(ж) Каждое регулярное множество определяется LR(0)-rpaM-матикой.

5.2.6. Покажите, что каждая LR-грамматика однозначная.

*5.2.7. Для G - (N, 2, Р, S) определим Gr = (N, 2, Pi, S), где Pr - это множество Р, правые части правил которого записаны в обратном порядке, т.е. Pj {А-а\А-сс£Р}. Приведите пример, показывающий, что Gji не обязательно будет LR(/e)-грамматикой, даже если G такова.

*5.2.8. Пусть G = (N, 2, Я, S)-произвольная КС-грамматика. Для и 2** и номера правила 1 определим множество Rk {i, и) = {au\S=*aAw>aw, где п = FIRSTj(ffi) н Л-р -/-е правило}. Покажите, что Rk{i,u) - регулярное множество.

5.2.9. Постройте новый алгоритм разбора для LR(/e)-rpaMMa-тик, который для всех i и и следит за состояниями конечного автомата, распознающего Rk(i, и).

*5.2.10. Покажите, что G является ТР(/г)-грамматикой тогда и только тогда, когда для всех а, р, п и v соотношения и) и apiJ(/, v) влекут за собой Р-е и / = /.

*5.2.П, Покажите, что G является LR {й)-грамматикой тогда и только тогда, когда она однозначна и для всех w, х, у я z из 2* выполнение четырех условий S=:wAy, Л=>*х, S==>* WXZ и FIRSTi/)-FlRSTfe(/) влечет за собой 5=*шЛ2. **5.2.12. Докажите неразрешимость проблемы: является ли КС-грамматика LR(fe)-rpaMMaTnKoH для какого-нибудь k?

**5.2.13. Докажите неразрешимость проблемы: является ли LR (й)-грам.матика LL-грамматикой?

ДМП-автомат, работающий с магазином так же, как LR(fe)-анализатор. Из доказательства теоремы 2.22. извлечем такую константу с, что если ДМП-автомат за с шагов не сделает переноса входного символа и не уменьшит объем магазина, то он зациклится. Следовательно, то же произойдет и с анализатором.

Но, как мы заметили раньше, если обработанную часть входной цепочки нельзя продолжить до цепочки, принадлежащей L{G), анализатор сигнализирует об ошибке. Поэтому зацикливание анализатора означало бы, что найдется цепочка из L{G), имеющая сколь угодно длинные правые выводы. Это противоречит однозначности ЬК()-грамматнки. Таким образом можно заключить, что анализатор не зацикливается и нужная константа с существует. П

5.2.6. Реализация и LR(A;]-aHanH3aTopoB

На первый взгляд кажется, что при реализации LL()- и ЬН(/е)-анализаторов придется помещать в магазин большие таблицы. На самом деле этого можно избежать следующим образом:

(1) Поместить в память по одному экземпляру каждой таблицы, а в магазине заменить сами таблицы указателями на их место в памяти.

(2) Так как в LL{k)- и ЬК(й)-таблицах есть ссылки на другие таблицы, вместо имен таблиц можно использовать указатели.

Заметим также, что наличие в магазине символов грамматики излишне и на практике их можно туда не записывать.

УПРАЖНЕНИЯ

5.2.1. Определите, какие из следующих грамматик являются ЬК(1)-грамматиками:



**5.2.29. Докажите, что каждая ЕС(/е)-грамматика является LR(A)-rpaMMaTHKou.

**5.2.30. Каково максимальное число множеств допустимых ситуаций LR()-rpaMMaTHKH, рассматриваемое как функция от числа символов грамматики, количества правил и длины самого длинного правила?

*5.2.31. Назовем ЕР(ё)-ситуацию существенной, если точка находится в ней не на левом конце (т. е. она появляется иа шаге (2а) алгоритма 5.8). Покажите, что если отвлечься от множества ситуаций, соответствующего и от „сверток" пустой цепочки, то в определении LR()-тaблиlI,ы, соответствующей множеству ситуаций, можно ограничиться существенными ситуациями и при этом таблица не изменится.

*5,2.32. Покажите, что действием LR(l)-тaблицы для символа а будет перенос тогда и только тогда, когда в некоторой ситуации из множества, по которому построена таблица, а находится непосредственно справа от точки.

Упражнения на программирование

5.2.33. Напишите программу, проверяющую, является ли произвольная грамматика LR(l)-rpaMMaTHKOH. Оцените время и емкость памяти, требуемые Вашей программой, как функции от объема входной грамматики.

5.2.34. Напишите программу, использующую для разбора входных цепочек LR(l)-тaблицy, такую, как на рис. 5.9.

5.2.35. Напишите программу, которая строит LR(l)-aнaли-затор для LR(l)-rpaMMaTHKH.

5.2.36. Постройте LR(I)-aнaлизaтop для какой-нибудь небольшой грамматики.

*5.2.37. Напишите программу, проверяющую, образует ли произвольная система LR(l)-тaблиц корректный анализатор для данной КС-грамматики.

Допустим, что LR(l)-aнaлизaтop находится в конфигурации {аТ, ах, л) и таблица Т ассоциирует с символом а операцию ошибка. Как и при LL-разборе, нам хотелось бы в этот момент объявить об ошибке и перейти к процедуре исправления ошибок, которая должна модифицировать входную цепочку и/или содержимое магазина так, чтобы можно было продолжить LR(1)-анализ. Как и в случае LL-анализа, можно устранить входной символ, изменить его или вставить другой входной символ в зависимости от того, какая стратегия кажется наиболее подходящей в рассматриваемой ситуации.

5.2.14. Докажите разрешимость проблемы: является ли LR(ft)-грамматика ЬЬ(Л)-грамматикой для того же значения k.

*5.2.15. Покажите, что каждый КС-язык, не содержащий пустой цепочки е, порождается обратимой КС-грамматикой без е-правил.

*5.2.16. Пусть G = (N, 2, Р, S) - КС-грамматика Rw = ay.. .а,~~ цепочка из 2". Допустим, что, применяя к G алгоритм Эрли, мы обнаружим в списке Z- ситуацию [Л-сср, /] (в смысле алгоритма Эрли). Покажите, что существует такой вывод S=4>*7x, что ситуация [Л-сб*р, и\ (в смысле ЬК()-алгоритма) допустима для у, причем w--FIRSTj(x) и у"а.. .а.

*5.2.17. Докажите утверждение, обратное утверждению в упр 5.2.16.

*5.2.18. С помощью упр. 5.2.16 покажите, что если G - LR (А)-грамматика, то алгоритм Эрли, заглядывающий на k символов вперед (см. упр. 4.2.17), тратит линейное время и емкость памяти.

5.2.19. Пусть Х С N и 2. Покажите, что EFF (Л:а)-=ЕЕЕ (Л) FIRST(a).

5.2.20. Используя упр. 5.2.19, дайте эффективный алгоритм вычисления EFF (а) для любой цепочки а.

5.2.21. Доведите до формальных деталей доказательство того, что в случаях 1 и 3 теоремы 5.9 нарушается LR (й)-условие.

5.2.22. Дополните доказательство теоремы 5.11.

5.2.23. Докажите корректность алгоритма 5.10.

5.2.24. Докажите корректность алгоритма 5.11, обосновав каждое нз замечаний, следующих за описанием этого алгоритма.

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

**5.2.25. Докажите, что каждая ЕЕ()-грамматика является LR(fe)-rpaMMaTHKofi.

**5.2.26. Докажите, что каждый детерминированный КС-язык определяется LR(l)-гpaммaтикoй.

*5.2.27. Покажите, что существуют (детерминированно) пра-воанализируемые грамматики, которые не являются LR-грамма-тиками.

*5.2.28. Покажите, что существуют LR-языки, которые не являются ЕЕЯзыками.



) В этой связи см. также работы Гончаровой [1975] и Шумея и Зониса [1975].-Прим. перев.

Сложность проверки ЬК(/г)-условия изучается в интересной работе Хаита и др, [1975).-/7риж. перев.

) Это пе те функции, которые ассоциируются с LR (/е)-таблицей.

(2) отображает 7»х(2и{$})* в множество {1, 2, ...,р, ошибка} при условии, что если g [а, w)--i, то правая часть г-го правила является суффиксом цепочки а.

Алгоритм типа „перенос-свертка" использует входную ленту, читаемую слева направо, и магазин. На основе того, что находится в магазине и осталось не обработанным на входе, функция / решает, перенести ли текущий входной символ в магазин или вызвать процедуру свертки. Если принимается последнее из этих решений, то функция g решает, какую сделать свертку.

Работу алгоритма типа „перенос-свертка" можно рассматривать в терминах конфигурацией, т. е. троек вида

(1) %Xi.,.Xrn - содержимое магазина, причем Х - верхний символ, X,-Nu2 и S служит маркером дна магазина,

(2) а.. .а - оставшаяся необработанной часть первоначальной входной цепочки, а - текущий входной символ, $ служит правым концевым маркером для входа,

(3) Pi -. .Рг - цепочка номеров правил, примененных при свертке первоначальной входной цепочки к цепочке Xj...X й...а„.

Один шаг алгоритма d можно описать с помощью двух отношений - и 1- , определенных на конфигурациях (индекс с в этих обозначениях будем опускать всюду, где можно):

(1) если f [а, аш) = перенос, то (ct, aw, л)1-(cta, w, л) для а€У*. ш€(2и{$})* и д€{1, р}*,

(2) если f(ap, йу)--свертка, g(ctp, w) = i и Л3 -правило с номером I, то (ар, ш, л)1-"(аЛ, w, ni),

(3) если f(а, li))-допуск, то (а, w, л)- допуск,

(4) в остальных случаях (а, w, л) [- ошибка.

Определим отношение \~ как объединение отношений - и К". Отношения H**" и -* определяются, как обычно.

Для ш2* положим d (w)n, если ($, w%, р)]-* ($S, $, я)1- допуск, и Л (w) = ошибка, если такого я нет.

Будем называть алгоритм Л корректным для грамматики G, если

(1) L{G) = {w\d {bi) ошибка},

(2) п - правый разбор цепочки w, если A(w) = n.

Пример 5.33. Построим алгоритм типа „перенос-свертка" " - {f* S) для грамматики G с правилами

(1) S-SaSb

(2) 5->е

Лейниус [1970] описывает более изощренную стратегию, в которой участвуют ЬН(1)-таблнцы, хранящиеся в магазине.

5.2.38, Напишите ЬН(1)-грамматику для какого-нибудь простого языка. Разработайте процедуру исправления ошибок, которую можно было бы использовать вместе с ЕЯ(1)-анализато-ром для этой грамматики. Оцените эффективность Вашей процедуры.

Замечания по литературе

ЪК()-грамматики впервые были определены Кнутом fl9G5]. Метод построения LR-аиализатора, описанный в этом разделе, дает, к сожалению, очень большие по объему, анализаторы для грамматик, представляющих практический интерес. В гл. 7 мы изучим технику, предложенную Де Рсмером [1969], Кореиьяком [19С9] и А.<о и Ульманом [ 197IJ, которая часто позволяет строить LR-анализаторы меньшего объема.

Идея ЬК(Уг)-грзмматнки была распространена Уолтерсом [1970] па контекстно-зависимые грамматики

Ответы к упр. 5.2.8-5.2. Ш можно найти в книге Хопкрофта и Ульмаиа [I9G9J. Упр. 5.2.12 взято из работы Кнута [1965] 2).

5.3. ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ

Среди грамматик, анализируемых алгоритмами типа „перенос-свертка", можно выделять различные подклассы LR()-rpaMMa-тик. В этом разделе мы точно определим алгоритм разбора типа „перенос - свертка" и рассмотрим класс грамматнк предшествования, которые анализируются легко реализуемым алгоритмом этого типа.

5,3.1. Формальное определение алгоритма типа „перенос-свертка*

Определение. Пусть G(N, 2, Р, 5) -КС-грамматика, правила которой занумерованы числами от 1 до р. Алгоритмом типа /lepenoc-свертка для грамматики G назовем пару функций где Ч называется функцией переноса, а g - функцией свертки. Функции f и g определяются так:

(\) f отображает У*х (2 и {$!)* в множество {перенос, свертка, ошибка, допуск}, где VNu2u{$}, а $ -новый символ, концевой маркер.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 [74] 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0019