Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 88
Текст из файла (страница 88)
(в) Если ) (и) = ошибка, разбор прекращается (на практике надо перейти к процедуре исправления ошибок). (г) Если ) (и) = допуск, остановиться и объявить цепочку, записанную на выходной ленте, правым разбором первоначальной входной цепочки..
Пример 5.23. Пусть алгоритм 5,7 начинает работу в начальной конфигурации (Т„ааЬЬ, е). Будем пользоваться 1К,(1)-таблицами, приведенными на рис. 5 9. Здесь аванцепочкой служит и. Значением функции действия таблицы Т, на цепочке а будет свертка 2, где 2 — номер правила 5 — е. На шаге (26) надо устранить из магазина 2 ~!е1=-0 символов и выдать номер 2. Верхней таблицей в магазине все еще остается Т,. Так как функция переходов таблицы Т, на аргументе 5 принимает значение Т„то наверху магазина помещаем БТ,— это приводит к конфигурации (Т„БТ„ааЬЬ, 2). Пройдем еще раз через этот цикл.
Аванцепочкой по.прежнему служит а. Значением функции действия таблицы Т, на а будет перенос, так что символ а переносим со входа в магазин. Функ. ция переходов таблицы Т, на аргументе а принимает значение Т„ так что после этого шага получится конфигурация(Т,БТ ОГЗ,ОЬЬ,2). Продолжая, в том же духе, ).К-анализатор сделает такую последовательность тактов: (Т„ааЬЬ, е) ( — (Т,БТ„ааЬЬ, 2) '-- (Т,БТ,ЗТ„аЬЬ, 2) ) — (Т,БТ,аТ,БТ„аЬЬ, 22) )- (Т,БТ,аТ,БТ,аТ„ЬЬ, 22) 1 — (Т,БТ,ОТ„БТ,аТ,БТ„ЬЬ, 222) ! — (Т,БТ,аТ,БТ,ОТ,БТ,ЬТ„Ь, 222) ! — (ТаБТа(зТаБТЗ, Ь, 222! ) ( — (Т,БТ,аТ,БТ,ЬТ„е, 2221) 1 — (Т,БТ„е, 222! 1) Заметим, что эта последовательность шагов по существу совпадает с той, что была в примере 5.21, а ЕК(1)-таблицы как раз поясняют способ, которым в том примере принимались решения.
сд В данном разделе будут разработаны необходимые алгоритмы, обеспечивающие автоматическое построение ЕК.анализатора ука ванного вида для каждой 1К-грамматики. Мы увидим, что о является ЕК(й)-грамматикой тогда и только тогда, когда дли 426 нее можно построить ЕК(й)-анализатор. Но сначала вернемся к основному определению 1К (Ь)-грамматнки и изучим некоторые его следствия. Чтобы доказать, что для ЕК(й)-грамматики алгоритм 5.7 правильно осуществляет разбор, надо значительно развить теорию 1 К(й)-грамьсатик.
Убедимся сначала в том, что из определения БК(й)-грамматики фактически вытекают паши интуитивные представления о том, какой должна быть детерминнрованно правоаиализируемая грамматика. Пусть дана такая правовыводимая цепочка арса пополненной ЕК(Ь)-грамматики, что аАН)=з,(хрсс), Покажем, что после чтения (хр и Е(К5ТА(п)) не может быть никаких недоразумений по поводу (1) позиции правого конца основы, (2) позиции левого конца основы, (3) свертки, которую нужно сделать для данной выделенной основы. (1) Допустим, что с) ществует другая правовыводимая цепочка а()у, для которой Е!КБТ„(у)-. Г!КБТА(са), но у можно записать в виде у,уау„где  — у,— правило и сфу(Вуа — правовыводимая цепочка, т.
с. 5' =~, а(1у)Вуа =), а!ау,уауа Такой случай явно исключается определением 1.К(Ь)-грамматики. Это станет очевидным, если положить в этом определении х=-у, н уВ=ару)В. Правый конец основы мог бы оказаться левее конца цепочки р, т. е. могла бы найтись другая правовыводимая цепочка уаВпу, для которой В у,— правило, Г!КБТА(у)=- Г1КБТ (и)) и у,Впу=~, уставу=. а()у. Этот случай тоже исключается, если в ш)ределенйи 1.К(й)-грамматики положить уВ=у,В и х-..—.
су. (2) Допустим теперь, что положение правого конца основы правовыводимой цепочки известно, но есть еще сомнения относительно левого конца. Иначе говоря, допустим, что аЛН) и а'А'у— такие правовыводпмые пеночки, что Р1КБТ„(се) = Е(КБТА(у) и аАп)=::а„а5(с), сс'А'у=>„а'р'у=а()у. Однако в 1.К(й).определении требуется, чтобы было ссА = гз.'Л', так что р=(!' и А = А'. Поэтому левый конец основы определяется однозначно. (3) Недоразумений типа (3) тоже не может быть, потому что, как уже отмечалось, А =- А'. Таким образом, нетерминал, которым надо заменить основу, всегда определяется однозначно.
Дадим теперь несколько примеров (.К- и пе ЕК-грамматик. ПРимеР 5.24. ПУсть ба — пРаволипейнаЯ гРамматика с НРавилами 5--С(0 С аС!Ь )3-- а0(с П а,— са()). а . '). ')н „,„„а На),а, „, 429 гл. А. Однопгоходнын синтАксическип Анзлиз вез возвРАтов Каждый (правый) вывод в пополненной грамматике 6, имеет вид 5'=!> 5=о С =Ф' а'С =э а'Ь для ( =: 0 нли 5'=> 5 =~ Т) =>'а'0 =о а'с для !" ~ 0 Вернемся к определению ) й(1)-грамматики и допустим, что есть выводы 5'=>,"яАш=о,а!)ге и 5'~',УВХ=='>,сну. Тогда, так как 6; — праволинейная грамматика, должно быть в= х-=е. Если Р1КЗТ,(!с).=-Р!КЗТт(у), то у=- е.
Надо теперь показать, что аА =-УВ, т. е. а — у и А =-В, Пусть  — б — правило, примененное при переходе от УВх к аВу. Нужно рассмотреть следующие три случая: Случай 1: А=5' (т. е. вывод 5'=Р„"аА!с тривиален). Тогда а=--е и р=5. Из вида выводов в 6; следует, что правовыводимую цепочку 5 можно вывести лишь одним способом; поэтому у =. е и В = 5', что и требовалось доказать. Случай 2; А = С. Тогда () †ли аС, либо Ь. В первом случае должно быть В= С, так как только в правилах для С и 5 правые части оканчиваются символом С. Если В=5, то нз вида выводов в 6; следует, что у= е.
Тогда УВ ~ а~. Таким образом, можно заключить, что В=С, 6 =аС и у= — а. Во втором случае ((! -- 6) должно быть В=-С, потому что только для С существует правило, оканчивающееся символом 6. Отсюда снова непосредственно следует, что у=-а и В =.А. Случай 62 А =О. Этот случай симметричен случаю 2. Заметим, что 6, не является 1).-грамматикой. Пример 5.25. Пусть 6,— леволинейпая грамматика с правилами 5 АЬ|Вс А — Аа(е В Ва)е Заметим, что Е(6,) —.Ц6,), где 6,— грамматика из предыдущего примера.
Однако 6, не является 1 К(й)-грамматикой ни для какого й. Допустим, что 6,— 1.К(й)-грамматика. Рассмотрим два правых вывода в пополненной грамматике 6;: 5'=~, 5 =Ф," Аа"Ь -~, а "Ь 5'=о„5 ~, "Ваес =-'., аес Эти два вывода удовлетворяют условию из определения ! К(Ь) грамматики при а=-е„()=е, ге=аАЬ, у=-е и у=а"с. Но так как 430 З М ДЕТЕРМИНИРОВАННЫЙ ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ заключение неверно, г.
е. А т В, то 6,— не 1.К(й)-грамматика. полее того, так как 1-й(й)-условие нарушается для всех й, то 6,— не 1.К-грамматика. П Грамматика из примера 5.25 пе обратима, и хотя мы знаем, где в правовыводимой цепочке расположена основа, но, если вне правого конца основы разрешается просмотреть только ограниченное число терминальных символов, мы не всегда знаем, свернуть ли первую основу, которая является пустой цепочкой, к А или к В.
Пример 5.25. Ситуации, в которой нельзя однозначно определить положение основы, встречается в грамматике 6, с правиламн 5 — АВ А — а  — СР ( а.Е С вЂ” аЬ В вЂ” ЬЬ Е вЂ” ЬЬа 6,— не Ей(!)-грамматика. Это можно усмотреть, взяв два правых вывода в пополненной грамматике 5'=-:А5=е АВ=Э АСЕ!=Ф АСЬЬ =!ААаЬЬЬ 5'=~ 5=~ АВ=~ АаЕ=-,> АОЬЬа Если известен только первый символ цепочки !с, нельзя определить„где в правовыводимой цепочке Аабш находится правый конец основы — между Ь н !с (когда ю=ЬЬ) илн справа от АаЬ (когда ю — Ьа).
Заметим, однако, что 6,— 1 К (2)-грамматика. Можно дать неформальиос„ио наглядное определение Ей(й)- грамматики в терминах деревьев выводов. Грамматика 6 будет ьй(й)-грамматикой, если, просмотрев только часть кроны дерева вывода в этой грамматике, расположенную слева от данной внутренней вершины, и часть кроны, выведенную из нее, а также следующие й терминальных символов, можно установить, какое правило было применено к этой вери!ине.
Например, рассмотрев цепочки ис и Р1КЗТА(!е) иа рис. 5,10, можно точно определить, какое правило было применено к вершине А. В отличие от этого о"Ределение 1.1(й)-грамь!атики говорит о том, что правило, примененное к А, можно определить по цепочкам и и Р1К5Т„(о!е). 43! гл. а. ОднОпрохОдныя синтАксическия АнАлиз зез ВОЗВРАТОВ з а дстеРМиНиРОВАННЫЙ ВОСХОДЯЩИЙ СИНТАКсИчеСКИЙ АНАЛиз Грамматика 6, из примера 5.25 не была 1 К(Й)-грамматикой потому что по первым Й символам а нельзя было определить какое из правил А — с и  — е применялось для вывода пустой' цепочки в начале всей входной цепочки.
Это нельзя решить, ч Рис. ЗЛО. дерево разбора. пока не будет Виден последний входной символ, Ь или с. В гл. 8 мы попытаемся сделать аргументацию такого типа более строгой, но, хотя интуитивно идея понятна, ес довольно трудно формализовать. Р.2.3. Следствия определения Ей(Й)-грамматики Теперь займемся теорией, необходимой для конструирования 1К(Й)-анализаторов. Определение. Допустим, что 5=,р„'аЛш=ьа)аш — правый вывод в грамматике 6. Назовем цепочку у активным префиксом грамматики 6, если у — префикс цепочки а(), т.
е. у — префикс некоторой правовыводимой цепочки, не выходящий за правый конец ее основы. Ядро ЕК(Й)-анализатора составляют таблицы. Они аналогичны Ь1-таблицам для 1.1-грамматик, которые по данной аванцепочке подсказывали иам, какое правило надо применить слсдующиаь Для 1К(Й)-грамматики каждан таблица соответствует некоторому активному префиксу. Таблица, соответствующая активному префиксу у, для данной аванцепочки, состоящей из Й символов, сообщает о том, достигнут ли правый конец основы.
Если да, тс она сообщает также, какова эта основа и какое правило надо применить для ее свертки. Здесь возникает несколько проблем. Так как цепочка у может быть сколь угодно длинной, то неясно, можно ли Обойтись ко нечным множеством таблиц. 1К(Й)-условие говорит о том, что основу правовыводимой цепочки можяо определить однозначно если известен весь отрезок этой цепочки слева от основы, а также Й 432 Очередных входных символов. ПоэтомУ Яе очевидно, что основУ всегда можно определить, располагая только фиксированным количеством информации о цепочке, предшествующей основе.
Кроме того, если 5=>',иАш~,ар~о и можно ответить на вопрос: Кончается ли некоторый правый вывод цепочки сага правилом р?", то еще неисно, можно ли вычислить таблицы, соответствУющие аА, по таблицам, соответствующим а5, способом, „реализуемым" на МТ1-преобразователе (или, быть может, каким-нибудь другим удобным способом). 11оэтому таблицы должны содержать достаточно информации, чтобы по таблице, соответствующей ий, можно было вычислить таблицу для аА, если аЛш=>„ирш. Итак, мы приходим к следующему определению.
Определение. Пусть 6= (Р(, Е, Р, 5) — КС-грамматика. Будем называть [А (), ре, и] ЬК(Й).ситуацией (для данных Й и 6, но эти параметры не будут явно указываться, когда это не может привести к недоразумениям), если А — ٠— правило из Р и и Б Е"А. Будем говорить, что 1.К(Й)-ситуация [А — (), 5„и] допустима для активного префикса а(), если существует такой вывод 5=!>,*ОАш=ь„ай,й,ш, что и=В!К5Т (ш). Заметим, что может быть ()е=-е и для каждого активного префикса найдется хотя бы одна допустимая для него ЕК(Й)-ситуация. Пример 5.27, Рассмотрим грамматику 6, из примера 5.24. Ситуация [С вЂ” а С, е] допустима для ааа, так как существует вьшод 5->,"ааС=О,аааС, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
