Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 90
Текст из файла (страница 90)
Х,,) для ' ~ п Построим !', (Х,Х,... Х;): (а) Если [А- а ° Х!з, и] Е !'„(Х,... Х,,), включить [А — аХ; ~, и] в УА(Х,... Х ). (б) Если ситуация .[А а ° В~, и] уже включена в )сА(Х,... Х ) и В- бЕР, включить в )т,(Х,... Х;) ситуацию [В ° Ь, х] для каждой цепочки х Е Г[КВТА(!Зи) при условии, что там ее еще нет. 437 гл. ь. однопгоходнып синтлксическия лнллиз вез возвглтов детеРминиРОЕАнныЙ еосходящип синтАксическиЙ АнАлиз (в) Повторять шаг (26) до тех пор, пока в 1'«(Х,... Х,) нельзя будет включить новую ситуацию. Определение. Повторные применения шагов (16) и (26) алга. ритма 5.8 к некоторому множеству ситуаций будем называть операцией зал«ыкания этого множества.
Определим на множествах ситуаций грамматики О=(Ь), 2, Р, 5) функцию бОТО. Если А — такое множество ситуации, что .ч =-1 «о(у) для некоторой цепочки у Е(Ь) () г)" и Х Е(МОХ)', т„ значением ПОТО( «, Х) будет такое множество 4', что Х =- Р«(уХ) На шаге (2) алгоритма 5.8 вычисляется )' (Х,Х,... Х;) =ООТОК(х,х,... Х;,), Х;) Заметим, что шаг (2) иа самом делс зависит от множества Г«(Х,...
Х«,), а не от Х,... Х, Пример 5.29. Построим множества г'1(е), 1',(5) и 1',(5а) для пополненной грамматики 5' — 5 Я вЂ” ВаЛЬ 5 — е (Заметим, однако, что алгоритм 5.8 не требует, чтобы грамматика была пополненной.) Сначала вычислим 1'(е) (шаг (1) алгоритма 5.8). На шаге (1а) в к(е) включим [5' — 5, е]. На шаге (16) в ~'(е) включим [Я вЂ” ЯаЯЬ, е] и [5-- °, е]. Так как [5 "ЯаЯЬ, е] принадлежит теперь )с(е), то надо включить в 3~(е) также н [5 — 5аЯЬ, х], [Я вЂ” °, х] для всех х Е Г1КЯТ1(аЯЬ) = (а). Таким образом, к'(е) содержит ситуации [5' — 5, е] [Я вЂ” ЯаЯЬ, е)а] [5 — °, е(а] Здесь мы пишем сокращенно [А я 8, х1)х,(...)х„] вместо [А — я 13, х1], [А — я р, х,], ..., [А — я 8, х„].
Чтобы получить к'(5), вычислим бОТО (1'(е), 5). На шаге (2а) в Г(5) включаются три ситуации: [5' — 5, е] и [5- 5 аЯЬ, е(а], Вычисление замыкания не дает новых ситуаций, так что к'(5) состоит из ситуаций [5' — 5, е] [5 — 5'аЯЬ е(а] 'к'(Яа) вычисляется как значение бОТО(1'(5), а) и состоит из шесте ситуаций 5 Яа 5Ь, е)а] 5 — ЯаЯЬ, а~ Ь] [5, а~61 13 Теперь покажем, что алгоритм 5.8 правильно вычисляет 3'«(У) 4ЗВ .Теорема 5.10. (-К(й)-ситуация принадлежит множеству 1'„(у) „еле шага (2) алгоритма 5.8 тогда и только тогда, когда она допустима для 7. д о к а з а т е л ь с т в о. Достаточность. Предоставляем читателю доказать, что алгоритм 5.8 заканчивает работу и правильно вычисляет к«(е).
Мы докажем, что если все допустимые для Х,... Х,, ситуации и только оии содержатся в 1'«(Х,х,... Х;,), то все допустимые для Х,... Х; ситуации и только они содержатся в Г«(Х1... Х;). Предположим, что ситуация [А — 51 8«, и] допустима для Х,, Х;. Тогда существует такой вывод 5=>,"яАш=;>„я5,~,1о, что яб«=Х«Х«...
Х; и и=с)КЯТ«(и1). Надо рассмотреть два случая. Пусть 81 =-(3;Хо Тогда ситуация [А — р; Хф„ и] допустима для Х,... Х,, и по предположению индукции принадлежит 1'„(Х, Х«1). На шаге (2а) алгоритма 5.8 [А КХР]3„и] включается в У«(Х«...Х«). Допустим, что (3,=е, так что в этом случае я=Х,, Хо Так как 5=-.~;яА«о — правый вывод, то в нем найдется промежуточный шаг, на котором появился последний символ Х; цепочки я. Поэтому можно писать 5 =о",я'Ву=),я'ух«бу=>', яАш, где я'у =Х,...Х, „и на каждом шаге вывода я'уХ«бу=Э",яА«о правило применяется к иетерминалу, стоящему справа от явно указанного символа Х, Тогда ситуация [ — у Х,б, о], где о=Г1КЯТ«(у), допустима для Х,...Х,, и по предположению индукции принадлежит 1'«(Х,... Х,,).
Следовательно, на шаге (2а) алгоритма 5.8 [ — уХРб, о] включается 1'„(Х,...Х«). Так как бу=>",Ав, то можно найти такие нетерминалы «3„«1„..., е) н цепочки О,„..., О„Е (1х О 2)*, что б начинается нетерминалом 0„А=«3 и в Р для каждого 1в..«(т есть правило В« — 13„,0, „. Тогда в результате одного из применений шага (26) ситуация [А — (3„и] будет включена в 1'«(Х,...Х,), Читателю предоставляем доказать, что вторая компонента и этой ситуации удовлетворяет нужному условию. Необходимость.
Предположим, что ситуация [А — 13, й„и] включена в 1' (Х,... Х,). Индукцией по числу ситуации, ранее Х Х включенных в 1' (Х ...Х.), докажем что она допустима для 1''' 1'' 1' ° Базис, когда в к' (Х,... Х«) еще нет ситуаций, доказывается просто. В этом случае [А 8, р«, и] включается в р"«(Х«...Х«) на шаге (2а), так что (31=8;Х,. н [А — 8; Х1(3„и] содержится «(Х,... Х,,). Таким образом, Я=Э„'яАт=о„яр«Х(31«о и Я(31= Х, Х;,. Следовательно, ситуация [А — р1.(3«, и] допустима для Х ' Х В доказательстве шага индукции рассуждение то же, что и 439 Гл.
3. ОднОНРОходный синтАксический Анзлиз Без возвРАтов для базиса, если ситуация [А — бэ (1„и] включается в $'э(Х,;Х,) на шаге (2а). Если она включается на шаге (25)„то б,=е и найдется ситуация [ — у Лб, о], ранее включенная в гэ(Хэ...Х ), причем и Е г(Й5ТА(бо). По предположению индукции ситуация  —. у. Аб, о] допустима для Х,... Х„так что существует вывод =:>',сс'Ву=о,а'уАбу, где а'у=-Х,...Х,.
Тогда 5 =!>', Х,, Х,Аду ",Х,... Х;Аг =-.э, Х,... Х р,г где и=р1ЙЗТ (г). Следовательно, ситуация [А — б„и] допустима для Хэ... Хр ( ) Алгоритм 5.8 дает метод построения множества 1Я(й)-ситуаций, допустимых для произвольного активного префикса. При построении правого анализатора для 1,Й(й)-грамматики 6 нас интересуют такие множества для всевозможных активных префиксов грамматики б, а именно система множеств допустимых ситуаций для 6. Так как грамматика содержит конечное множество правил, то число множеств ситуаций тоже конечно, но часто бывает очень большим. Если у — активный префикс правовыводимой цепочки Уш, то, как бУдет показано, 'Р'э(У) содеРжит всю информацию о у, необходимую для продолжения разбора цепочки уиэ.
Приведем алгоритм, обеспечивающий систематический метод вычисления множеств 1Й(й)-ситуаций для 6. Алго ритм 5.9. Система множеств допустимых 1К(Ь)-с и т у а ц и й д л я б. Вход. КС.грамматика 6=(й), Х, В, 5) и целое число Ь. Выход.,У вЂ” (А ] А ==- 1'„(у) и у — активный префикс грамматики 6). Метод, Вначале система г пуста. (!) Поместить Уэ(е) в д', Множество )'э(е) вначале „не огмечено". (2) Если множество ситуаций А системы У не отмечено, отметить А, вычислив для каждого Х Е (Ь( 0 Х) значеняе СОТО(А, Х) (можно с помощью алгоритма 5.8).
Если множество А' — СОТО(А, Х) не пусто и еще не включено в д', то включить его в г' в качестве неотмеченного множестВа ситуаций. (3) Повторять шаг (2) до тех пор, пока все множества ситуаций системы т не будут-отмечены. () Определение. Если б — КС-грамматика, то систему множеств допустимых ЬК(й)-ситуаций для пополненной грамматики будем называть канонической сисоэеээоэ1 множеств ) 1((я)-ситуаций для 6.
Заметим, что множество СОТО(А, 5') никогда не потребуется вычислять, так как оно всегда будет пусто, 440 э э. детеоминиоовзнный восходящий синтзксический Анхлиз Пример 5.30. Вычислим каноническую систему множеств (,р(1)-ситуаций для грамматики б, если соответствующая ей пополненная грамматика состоит из правил 5' — 5 5 5а5Ь 5 е Начнем с вычисления А,=ЦЕ). (Это сделано в примере 5.29.) А,: [5' 5 е] [5 — 5а5Ь, е~а] [5 — °, е(а] Затем вычислим СОТО(А„Х) для всех Х Е (5, а, Ь].
Обозначим СОТО(А„5) через А,. Тогда Аэ: [5'- 5, е] [5 — 5 а5Ь, с~ а] Оба множества СОТО(А„а) и СОТО(А„Ь) пусты, так как ии а, ии Ь не являются активными префиксами грамматики 6, Далее надо вычислить СОТО(А„Х) для Х Е (5; а, Ь). Множества СОТО(А„5) и СОТО(А„Ь) пусты, а СОТО(А„а) =А„где А,: [5 5а 5Ь, е]а] [5 -5а5Ь, а]Ь] [5 °, а( Ь] Продолжая в том же духе, получаем множества 5 — 5а5 Ь, е)а] ' — 5 а5Ь, а!Ь] 5 — 5а 5Ь, а]Ь] ° 5а5Ь, а~Ь] 5 °, а]Ь] 5 5а5Ь, е]а] 5 — 5а5 Ь, а]Ь] 5 — 5 а5Ь, а]Ь] 5 — 5а5Ь, а! Ь]' Аэ. [5 А,: [5 А,: [ А,: А,: Функция СОТО изображена в виде табл, 5.4. Заметим, что множество СОТО(А, Х) будет всегда пусто, если в каждой ситуации из А точка расположена иа правом конце правила. Здесь примерами таких множеств служат А, и Аэ.
Обращаем внимание читателя на сходство между функцией СОТО в табл. 5.4 и функцией переходов 1К(1)-анализатора для грамматики б, приведенной на рис. 5.9. й Гл. а. ОднопРОхОднып синтАксическип АИАлиз Вез ВО3ВРАтОВ Теорема 5.11. Алгоритм 5.9 правильно вычисляет систему,у. Доказательство. По теореме 5.8 достаточно доказать, что множество ситуаций А помещается в У тогда и только тогда, когда существует вывод В=>',аАге=о„а[1ш, где Т вЂ” префикс цепочки ар и А=-к' (у).
Необходимость условия доказы. Тоблияо бм Символ грамматики вается прямой индукцней по порядку, в котором множества ситуаций помещаются в г". Достаточность доказывается не менее очевидной индукцией по длине цепочки у. И то и другое мы оставляем читателю в качестве упражнений, () Множество снтуаннй Аа А', Ав 'уа А4 Аа Ае Ат Ат уа Аа б,в детеоминиРОВАннын ВОСходяшин синтАксическип АнАлиз (2) Рассмотреть каждое множество (.В(й) ситуаций нз У н установить, непротиворечиво ли оно.
(3) Если все множества из еУ иепротиворечивы, выдать ответ ,да". В противном случае выдать иет", т, е. объявить, что 6 не 1.11(й)-грамматика для данного й. Г1 Утверждение о корректности алгоритма 5.10 †э просто переформулировка теоремы 5.9. Пример 5.31. Проверим, является ли грамматика из примера 5.30 Ы(1)-грамматикой, Имеем г" =- (А„..., А,).
Достаточно проверить лишь множества 1.11(1)-ситуаций, содержащие точку на правом конце правила. Такими множествами оказываются А„, А„А„АО А и А . Рассмотрим А„. Для ситуаций [О' — - .В, е~) и [О' .ВаВЬ, е(а) из А, множества ЕРР(В) и ЕРР(Ва) пусты, поэтому они совместимы с ситуацией [В °, е~а), т. е.
А, непротиворечиво. Рассмотрим Г,, Здесь ЕРР(аВЬ) .= ЕРР(аВЬа) =- а, но а ие является аванцепочкой в ситуации [В' — В, е'). Следовательно, А, непротиворечиво. Множества А, и А, непротиворечивы, потому что ЕГГ(ВЬх) и ЕРР(БОВЬх) пусты для всех х. Множества А, и А, очевидно непротиаоречивы. Таким образом, все множества системы д' непротиворечивы и, значит, 6--1.Й(1)-грамматика. Д 5.2.4, Проверка 01(й1-условия Может оказаться, что нам надо знать, является ли интересующая нас грамматика 1В(й)-грамматикой для данного й. Алгоритм, решающий эту проблему, можно построить на основе теоремы 5.9 н алгоритма 5.9. Онределение. Пусть 6=(1А(, Х, Р, В) — КС-грамматика н й— целое число. Множество А !.В(й)-ситуаций для грамматики 6 назовем непротиеоречиеым, если оно не содержит двух различных элементов вида [А- (1 °, и'~и[В- 5, ~а,о1, где иЕЕРГЩР), пРичем Ра может быть пУстой цепочкой. А л г О р и т м 5.10.
П р о в е р к а 1Й(й)-у с л о в и я. Вход. КС-грамматика 6=(й[, Х, Р, В) и целое число й -О. Выход.,Да", если 6 — 1.1Т(й)-грамматика, и „нет" в противном случае. Иетод, (1) С помощью алгоритма 5.9 Вычислить каноническую систему у' множеств (.К(й)-ситуаций для грамматики 6. 5.2.5. Детерминированные правые анализаторы длв ьк(й]- грамматик В этом разделе мы неформально опишем, как по (,К(й)-грамматике построить детерминированный расширенный МП-преобразователь, заглядывающий на й символов вперед, который работает как правый анализатор для этой грамматики. На описанный ранее МП-преобразователь можно смотреть как на алгоРитм разбора типа „перенос--свертка", решающий на основании состояния верхнего символа магазина н аванцепочки, делать ему перенос или свертку, а в последнем случае — какую именно свертку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
