Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 79
Текст из файла (страница 79)
5. ОднОпРОхОдный синтА1ссическип АнАлиз вез ЕОзвРАтов м1. 1 ь 1Ю-гРАммктиКи грамматика 6, для которой (5.!.1) если А -«|1 и Л вЂ” у †различн А-правила, то Г1ЮТА(() ГОЬЬО%А(А)) П Г!КЗТА(у ГОЬЬ0% (А)) = г1 называется сильно ЬЬ (й)-граллащикогЬ Каждая ЬЬ (1)-грамма тика — сильно ЬЬ(1)-грамматика, но, как показывает следующий пример, для й > 1 существу1от ЬЬ (й)-грамматики, не являющиеся сильно ЬЬ (й)-грамматиками. Пример 5.8. Пусть грамматика 6 определена правилами 5 — аАаа | ЬЛЬа А- Ь!е С помощью теоремы 5.2 можно убедиться, что это ЬЬ(2)-трам.
матика. Возьмем вывод 5=заАаа. Заметим, что Г!Гс5Т,(Ьаа)п Г1КЗТ,(аа) =й1. В обозначениях теоремы 5.2 сс=-аа, (5=Ь и у = е. Аналогично, если 5=> ЬАЬа, то Г!КЗТа(ЬЬа) и Г1КЗТ,(Ьа) = гд. Так как все выводы в грамматике 6 имеют длину 2, по теореме 5.2 6 будет 1Л. (2)-грамматикой.
Но ГОЬЬОЖ,(А)=-(аа, Ьа), так что Г!КЗТ, (Ь ГОЬЬОЮа (А)) () Г(ПЗТ, (ГОЬЬОЮа(А)) = (Ьа) Условие (5.!.1) нарушено, и, значит, ЬЬ (2)-грамматика 6 не является силы1о ЬЬ(2)-грамматикой. [3 Одно из важных следствий определения ЬЬ(й)-грамматнки состоит в том, что леворекурсивная грамматика не может быть ЬЬ(й)-грамматикой ни для какого й (упр. 5.1.1). Пример 5.9. Пусть грамматика 6 определяется двумя правилами 5 — «5а|Ь. Возьмем, как и в теореме 5.2, вывод 5=у5а', где 1) О, А =5, сс=е, р=-5а н Т=Ь. Тогда для 1) й Г1!(5ТА (5аа') П Г1ПЗТА (Ьа1) = Ьа" 1 Таким образом, 6 не может бь~ь ЬЬ(й)-грамматикой ни для какого й. Ы Важно также заметить, что каждая ЬЬ(й)-грамматика однозначна (упр.
5.1.3). Поэтому, если дана неоднозначная грамматика, сразу можно сказать, что она не ЬЬ(й)-грамматика. В гл, 8 мы покажем, что для многих детерминированных КС-языков не существует ЬЬ(й)-грамматик. Один из таких языков — язык (а"ОЬ" |и) 1) ц(а"1Ьаа|и) Ц, Кроме того, неразрешима проблема распознавания, существует ли для данной КС-грамматикн 6, не являющейся ЬЬ(й)-грамматикой (й фиксировано), эквивалентная ей ЬЬ(й)-грамматика. Но несмотря на эти неприятности, есть все же ситуации, в которых к данной не ЬЬ(1)-грамматике можно применить преобразования, позво- 384 13 Ааа, Дж.
Уаьааа, т, 1 385 лающие превратить ее в эквивалентную ЬЬ (1)-грамматику. Приедем здесь два таких преобразования. Первое — устранение левой рекурсии. Проиллюстрируем этот прием на примере, Пример 5.!О. Пусть 6 — грамматика 5 5а|Ь, которая, как мы видели в примере 5.9, не является ЬЬ-грамматикой. Эти два правила можно заменить тремя правилами 5 Ь5' 5' — а5'|е получив при этом эквивалентную грамматику 6'.
С помощью теоремы 5.3 легко показать, что 6' — ЬЬ(1)-грамматика. Другое полезное преобразование — левая 4акторизация (или вынесение левого множителя). Этот прием тоже проиллюстрируем на примере. Пример 5.11. Рассмотрим ЬЬ(2)-грамматику 6 с двумя правилами 5 — а5|а. В этих двух правилах,„вынесем влево за скобки" символ а, записав их в виде 5 — о(5|е). Иными словами, мы считаем что Операция конкатенации дистрибутивна относительно операции выбора альтернативы (обозначаемой вертикальной чертой).
Затем заменим эти правила иа 5-- аА А — 5|е получив тем самым эквивалентную ЬЬ(1)-грамматику, Г') В общем случае процесс левой факторизации заключается в замене правил А- сф,|...|сгр„правилами А — аА' и А'— Р |" |1.. 5.1А. Разбор дпя ЬЬ(1)-грамматик Ядром й-предсказывающего алгоритма разбора является управляющая таблица М. В этом и следующем разделах мы покажем, как для каждой ЬЬ(й)-грамматики 6 построить корректную управляющую таблицу, н таким образом докажем, что для нее возможен левый разбор с помощью й-предсказывающего алгоритма.
Сначала исследуем важиый частный случай, когда 6-ЬЬ (1)-грамматика. Алгоритм 5.1. Управляющая таблица для ЬЬ(!)- г р а м м а т и к и. Вход. ЬЬ(1)-грамматика 6=(51,2, Р,5). Выход. Корректная управляющая таблица М для грамматики 6, ГЛ. 5. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ Метод.
Будем считать„что $ — маркер дна магазина. Таб. лица М определяется на множестве (с(Цл()($))х(л!1(е)) еле. дуюсцим образом: (1) Если А — а †прави из Р с номером с, то М (А,а) †. (а, с) для всех а~е, принадлежащих Р1ЙЗТ,(а). Если е Е Р11(ЗТ„(а), то М (А, Ь) = (а, с) для всех Ь Е РОЬЬ0%', (А). (2) М (а, а) = выброс для всех а Е 2. (3) М ($, е) .= допуск. (4) В остальных случаях М (Х, а) =-ошибка для Х ЕМ() л В($) и аЕВВ(е).
Д Прежде чем показать, что алгоритм 5.! дает для грамматики 6 корректную управляющую таблицу, рассмотрим пример. Пример 5.!2. Посмотрим, как строится управляющая табли. ца для грамматики 6 с правилами (1) Š— ТЕ' (2) Е' — + ТЕ' (3) Е' — е (4) Т вЂ” РТ' (5) Т' — а РТ' (6) Т' --.е (7) Р (Е) (8) Р— а С помощью теоремы 5.3 можно проверить, что 6 — ЬЬ(1). грамматика.
На самом деле внимательный читатель заметит, что грамматика 6 получена нз 6, в результате устранения ле- Ф ( ) + а в Ряс. блн Уаравляюя(ая таблица для грамматики 6. 5.! . Еь (а)-ГРАммАтики й рекурсии, как в примере 5.10. Кстати, 6, не является ЬЬ- грамматикой. На шаге (1) алгоритма 5.1 найдем элементы строки таблицы ля нетерминала Е. Здесь Р1ЙЗТ, [ТЕЦ = ((, а), так что М[Е, (!=- [ТЕ', Ц и М [Е, а( =[ТЕ', Ц. Все остальные элементы этой с(роки — ошибки, Вычислим теперь строку для нетерминала Е'.
Заметим, что РИЗТ! с+ТЕЦ = +, так что М[Е', +( =[+ТЕ', 21. Так как есть правнлоЕ' е, мы должны Вычислить РОЬЬОЪГ,[ЕЦ == („)). Таким образом, М[Е',е[=-М[Е',)( — [е,З(. Каждый из остальных элементов строки для Е' — ошибка. Продолжая в том же духе, получим управляющую таблицу для 6, показанную на рис, 5.4. Ячейки, в которых должна стоять ошибка, оставлены пустыми. 1-предсказывающий алгоритм разбора с помощью этой таблицы проанализирует входную цепочку (ааа) так: [(ааа), Е$,е!! — [(ааа), ТЕ'е, Ц [ — [(ааа), РТ'Е'$, 14) (-[(ааа), (Е) Т'Е'$, 147) 1 — [а а а)„Е) Т'Е'$, 1471 ! — [а а а), ТЕ') Т'Е'$, 147 Ц (-.
[а а а), РТ'Е') Т'Е'$, 147141 ( — [ааа), аТ'Е') Т'Е$, !47148) ! — [аа), Т'Е') Т'Е'$, !47148( )--. [а и), а РТ'Е') Т'Е'Ъ, 1471485) [ — (а), РТ'Е') Т'Е'$, !4714851 1 — [а), оТ'Е') Т'Е'$, !47148581 )- [), Т'Е') Т'Е'$, 147!4858( ! — [), Е') Т'Е'$, 147148586( ! — [), ) Т'Е'$, 147!485863( )- [е, Т'Е', 14714858631 ! — [е, Е $, !4714858636( ! — [е, $, 147148586363( Д Теорема 5.4. Алгоритлс 5.1 строит корректную управляющую таблицу для ЬЬ(1)-грамматики 6. Доказательство. Заметим сначала, что если 6 — ЬЬ(1)- грамматика, то на шаге (!) алгоритма 5.! для каждого элемента М (А, а) управляющей таблицы определяется пе более одного з ачения.
Это замечание — просто переформулировка теоремы 5.3. Далее, прямой индукцией по числу шагов 1-предсказываю!пего алгоритма Л с управляющей таблицей М можно показать, что если (хУ,З$,е)[--"(У,с($, и), то Зя=>ха. ДРУгой индУкцией ЗВТ гл. Б. ОднОпРОхОдный синтАкя1ческип АнАлиз Без возвРАРОЕ 3.1. Еь 1»)-ГРАммАтики (по числу шагов левого вывода) можно доказать обратное утверждение, а именно: если 5 => хсг, где а †незаконченн часть цепочки хи, и НСВТ,(у)ы Г1й5Т,(а), то (ху,5$, е) 1 — *(у, а5, и), из всего этого следует, что (гв,55,е) ! — '(е, $, и) тогда и только тогда, когда 5„-.->ге.
Таким образом, й — корректный алгоритм разбора для грамматики 6, а гИ вЂ” корректная управляющая таблица. П 5А.5. Разбор дпя !.Цгг]-грамматик Построим теперь управлякицую таблицу для произволыюй 1.1. (Iг)-грамматики 6=(>1, м, Р, 5), где й) 1. Если 6 — сильно 1 Е(й)-грамматика, то можно применить алгоритм 8.1 с аванцепочками, содержащими до й символов.
Однако ситуация несколько усложняется, если 6 не является сильно ЕЕ(!г)-грамматикОЙ. В 1-предсказывающем алгоритме разбора для Е(. (!)-грамматики в магазин помещались только символы из Х О )»( и оказывалось, что для однозначного определения очередного применяемого правила достаточно знать нетерминальный символ наверху магазина н текущий входной символ.
Но если 6 не является сильно 1.!. (1г)- грамматикой, то нетерминального символа и аванцепочки не всегда достаточно для однозначного Определения очередного правила. Возьмем, например, ЕЕ (2)-грамматику 5 — аАаа ( ЬАЬа А — Ь(е из примера 5.8. Если даны нетерминал А и аванцепочка Ьа, то не известно, какое из правил А Ь и А- е надо применить.
Неопределенности такого рода можно, однако, разрешить, связав с каждым нетсрминалом и частью левовыводимой цепочки, которая может появиться справа от него, специальный символ, называемый 1-Е(!г)-таблицей (пе надо смешивать ее с управляющей таблицей). По данной аванцепочке 1Е (л)-таблица будет однозначно определять, какое применить правило на очередном 1паге левого вывода в грамматике 6. Определение. Пусть >' †некотор алфавит.
Если Ег и Е,— подмножества >:*, то положим Е,Я»Е =-(гв ~ для некоторых хбЕ1 и у ВЕ либо ю=-ху, если ~ху ~~/г, либо ю состоит нз первых й символов цепочки ху) Пример 5.13. Пусть Е,=(е, аЬЬ) иЕ,=-(Ь,ЬаЬ). ТогдаЕ,Я,Е,— '' (Ь, Ьа, аЬ). („) 388 Лемма 5,1. Для любой КС-грамматики 6=-(Ь(, В, Р,5) и любых а, ~Е(г(()г-)* Г1!(БТ»о (ар) = Г1КВТ»о (а) Я» Г1!>5Т»с (()) доказательство. Упражнение. Определение. Пусть 6 =- (1»1, Ез Р, 5) — КС-грамматика, для каждых АЕЬ! и Е: — Х'» определим )-Е(й)-таблицу Т„г, соответствуюгцую А и Е, как функцию, значением которой'для данной аванцепочки ибВ'» служит либо символ ошибка, либо А- правило и конечный список подмножеств множества Х'», а именно (!) Т„ь(и) =ошибка, если в Р нет такого правила А — а, что Г(ЮТ»(а)Я»Е содержит и; (2) Тл ь(и)=-(А а, <1 О )~„..., 1' >), если А — и — единственное правило из Р, для которого Г(ИВТ»(а) Я» Е содержит и; если а=х,В,х,В,х,...В х (т~О) где В1ЕЯ и хгЕХ', то )'1=Г!!»5Т»(х»В1~1хг»».
° ° В,х,)Я»Е (назовем )'1 локальным множеством для Вг', если т = О, то Тл,ь(и)=(А и, З))1 '(3) Тл1(и) не определено, если в множестве А — а, )а,(...(сг„ цайдутся два (или более) таких правила А — и; и А —.а,, что и Е (Г(В5Т» (аг) Я»Е) П (НВ 5Т» (ау) Я~» Е) (Эту ситуацию иногда называют конфликтом между правилами А- аг и А а,. Еслп 6 — 1Л. (Ь)-грамматика, то таких конфликтов не возникает.) Интуитивно это означает, что если Тл1 (и)=ошибка, то в 6 невозможен вывод вида Ах =>+ ио для хб Е и Р Е В'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
