Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 40
Текст из файла (страница 40)
образователем. Затем исследуем, какие простые СУ-схемы ка 1)(-грамматике можно реализовать таким способом. Мы изучим расширение ДМП-автомата, называемое МП-процессором, которое служит для реализации всего класса СУ-переводов, входными грамматиками которых являются СС- нли 1)т-грамматики. После этого вкратце рассмотрим синтаксически управляемые переводы в связи с алгоритмами разбора с возвратом. 9.2.1. Простые синтаксически упрввпвемые переводы В гл. 3 мы видели, что простую СУ.схему можно реализовать недстерминированньжг МП-преобразователем. В настоящем разделе мы исследуем детерминированные реализации некогорых простых СУ-схем.
-Переводы, определяемые длв языка Е(Е), и эффективность, с которой их можно непосредственно реалиаовать, могут зависеть от входоои грамматики В. Пример 9.1. Пусть требуется отобразить выражения, порождаемые грамматикой б с правилами Е а-(-Е)опЕ(а, в префиксные польские выражения, в предположевии что операция в 2ОТ ГЛ Ч ПЕРЕВОД И ГЕНКРАЦИЯ КОДЛ 2.2. сннтддснческн упРАВляемые переВоды имеет более высокий приоритет, чем +, т е. префиксным выражением для а е о -1-а будет -1- « ааа, н не э а + аа. Не суецествует СУ-схемы, длн которой грамматика 6 была бы входной грамматикой и которая определяла бы такой перевод.
Причина состоит в том, что выходная грамматика такой СУ-схемы должна быть липеипой КС-грамматикой В тоже время нетрудно показать, что множество префиксных польских выражений в алфавите (+, «, а), соответствующих инфнксным выражениям языка Ц6), не является линейным КС-языком. Тем не менее этот конкретный перевод можно определить, пользуясь простой СУ-схемой, у которой входвой грамматикой служит 6, (без правила Р (Е)) П В теореме 3.14 было доказано, что если (х, у) — этемент простого синтакси еески управляемого г!врезала, то выход у можно построить по левому разбору цепочки х с помощью детермнииропапного МП-преобразователя. Отсюда следует, по если грамматику 6 удается естественным образом разобрать детерминирозанно сверку вниз с помощью ДМП-преобразователя М, то М легко модифицировать так, чтобы реализовать любую простую СУ-схему, входной грамматикой которой служит 6.
Если 6— Щй)-грамьеатика, то любой простой сУ-псревод, определенный на 6, реализуется ДМП-преобразователеы следующим образом. Теорема 9.1. Луста Т=( °, 2, Л, й, 5) — семантически одно. зничнил ') проспшч СУ-схгмп, гходной громмапшхой которой служшп Шй)-граммптегха. Тогда перевод ((хб, у)((х, у) Ет(Т)) можно осуи(гоп!гите детерминированным МП-пргсбразооателем.
До к а з а тел ь с т во. Доказательство вытекает из доказательств теорем 3.14 и 3.4. Если 6 — входная грамматика схемы Т, то но алгоритму б.З для 6 можво построить Мпредскааывающий алгоритм разбора. Реалиауем этот й-предсказывающие) аиаливатор >га ДМП-преобразователе М с концевым маркером и выполним перевод следующим образом. Пусть Л' = (и'(ай Л), причем Л' П 2 = 21, и Ь(и) =и' для всех аЕЛ.
Анализатор, сконструированный по алгоритму 3.3, поочередно заменяет нетермипалы драными частямн правил, используя для этого ЕЕ(Ь)-таблицы, содернгащне нетермииалы. Ашочат М делает по существу то же самое. Предположим, что левый аналиватор заменяет А на ш„В,ш, ... В,т„(к нетермина- '! Авторы чедачюуеп пеппе~не, ааределенае которого дееегч чеечадька позже — э Геед З.З. Одааэаечеея СУ-сяеееэ — та абмчпед ау-ехеыг.— Прил Р д лам добавляются некоторые ЕЕ(й)-таблицы, не показанные здесь). Пусть А -- Ы,Веже...
В ш , х,В,х, ... В„х„ — правило ич й. Тогда М заменит А на ш,Мхе)В,тей(х,)... В ог„ Ь(х ). Как и в алгоритме 3.3, всякий раз, когда символ из 2 появляется в верхушке ыагазина, он сравнивается с текущим входным символом, н если они совпадают, то симвот удаляется из магавина, а входная головка сдвигается па одну ячейку вправо. Когда в верхушке магазина оказывается символ а' из Л', М порождает а и удаляет а' из верхуепки магазина, не сдвигая при этом входной головки. М не порождает номеров правил.
Бодее формальное построение автомата М оставляем читателю. рл Пример 9.2. Пусть Т вЂ” простая СУ-схема с правилами 5 а5Ь5с, 15253 5 д,4 Входная грамматика является простой ЕЕ(!)-грамматикой, Поэтому не обязательно запоминать в магазине Е(-таблицы. Пусгь М вЂ” детерминированный МП-преобразоиатель (!3, Тч Л, Г, б, у, 5, (допуск)), где !3 = (д, допуск, ошибна) В = (а, Ь, с, й, 5) Г-.(5,5)()26Л Л вЂ”.-(1, 2, 3, 4) Так как 5 П Л вЂ” — !В, положим Л' = — Л. Функцию б зададим равенствами б(д, а, 5) =(д, 5Ь25сЗ,!) ') б(д,й,5)=(д, е, 4) б Кд Ь, Ь) = (Ч . 'е) б(с, с, с) = (с, е, е) б (4, г, 2) =- (д, г, 2) б (д, е, 3) = (д, е, 3) б[4, 3, 3)--(допуск, г, е) В остальных случаях б(д, Х, 1') =(ошибка, г, г) ') Здесь ны атхгеыэеемся ат ограничений, сйарнухираеанпых прп дадеэе едеюее аюреыы э.! и зеглючеющчхсд е таы, чю апееецчн аараждеаеч зыхалаага спнвалэ и едэпга входной цепачда пасхе ргспазнзггнзя аргенлэ грен гтнхп далжзы еыпапеееьсч а резных техтех гл э пюевод и гзнснлция кодл Легко проверить, что т(М)= ((ху, у)((х, у) Ет(Т)1 Н Рассмотрим теперь простую СУ-схему, входной грамматикой которой служит ЕВ(й)-грамматика.
Поскольку класс 19(й)-грамматик шире класса ).) (Й)-грамматик, интересно исследовать, какой класс простых СУ-схем, входными грамматиками которых служат ЕВ(й)-грамматики, можно реализовать на ДМП-преобразователях. Оказывается, существуют ссыантичсски однозначные простые СУ-схемы, имеюпгие з качестве входных грамматик Ей(й)-грамлгатикн и не реализуемые нн на каком ДМП-прсобразователе. Неформально это объясняется тем, что элемент перевода может требовать порождении выхода задолго да того, как выяснится, что правила, которому приписан этот элемент перевода, действительно было применено. Пример 9.3.
Рассмотрим простую СУ-схему Т с правилами 5 5а, а5а 5 5Ь, ЬВЬ 5 г, е Входная грамматика является ЕВ(1).грамматикой, но по лемме 3.16 не существует ДМП-преобразователя, определяющего перевод ((х 9, у) ((х, у) Е т(Т)). Неформально это объясняется тем, что, согласно первому правилу этой СУ-схемы, символ а должен порождаться раныпе, чем выяснится, что было прнмепена правило 5 5л. Однако, если простая СУ-схема, входная грамматика которой является 19(й)-грамматикой, пе требует, чтобы выход порождался до' того, как будет установлено, какое правило применилось, такой перепоя можно реализовать на ДМ!1-преобразователе. Определение. СУ.схему Т = (Н, 2, Л, )т, 5) будем называть лттфплспой, если каждое правило из (( имеет вид А=.а,р, где йбчРЛ'.
Иными словами, каждый элемент перевода предо~валяет собой цепочку иг петерминалоз, за которыми слелует цепочка выходных символов. Теорема 9.2. Пусть Т=(В, Е, Л, )т,5) — сгмлнтлчгски однозлачлаз простая логтфикглал СУ-схема, входной грамматикой которой служит 09(У)-грамматики Тогда иирсзгд Дх 3, у) ((х, у) Е т(Т)) можно огуя(гстгить дглмрмили роганным МП-преобразователем. Доказательство, Применяя алгоритм б.!1, можно для входной ).В(й)-грамматики сконструировать детерминированный 2!о г з синтлксичаски ьпглвлягмыз пвгсводы правый анализатор М с концевым маркером. Однако, ачесго того чтобы порождать номер правила, М порождает цепочку выходных символов элемента перевода, связанного с этим правилом. Инылгн словами, если А п, рх — правило из )(, где и хй Л*, то всякий раз, когда анализатор порождает номер правила А а, ашомат М порождает цепочку х.
Работая таким образом, автомат М определяет перевод ((хй, у) )(х, у) Ет(Т)), С) В качестве упражнения предлагаем похавать утаержлепие, обратное теореме 9.2, а именно: любое детерминированное МП- преобразование можно выразить в виде постфнксной простой СУ-скемы, заданной на Ей(1)-грамматике.
Пример 9А. Постфнксные переводы полезнее, чем это может покаааться на первый взгляд. Мы расскотрим расширенный ДМП-преобразователь, отображающий арифметические выражения языка Е(П,) в машинный код специальным образом выбранной машины. Магпина имеет магазин при сумматоре. Команда ЕОА0 Х помещает значение, запнсанвое в ячейке Х, в верхушку магазина; все остальные элементы магазина проталкиваются вниз. Команды А00 и ЫРУ соответственно складывают и перемножают содержимое двух верхних ичеек, убирая эти ячейки и помещая результат в магазин. Для разделения команд служит точка с запятой.
Наша СУ-схема имеет вид В этом и во всех последующих прилгерах лгы будем пользовать. ся обозначениями Снпбола, заключая цепочки букв и цифр в правилах перевода в кавычки. Кавычии не являются частью выходной цепочки. Получив на вход цепочку а+(ага) 3, ДМП-преобразоватсль проходит следующую последовательность конфигураций (здесь 19(й)-таблицы из магачинз выброшены) в последовательности опущены, кроме того, некоторые очевидные конфигурации, а |акте 2Ы Е Е)-Т Е Т, Т Тчу, Т Р, (Е), Е а, ЕТ 'А00; ' Т Ту 'МРУ!' Е '1.ОА0 а; ' гл, е пквквод и ганягдция кодл в.т синткксичвски упвдвлягмыа паркводы очевидные состояния и маркер, содержащийся в самой нижней ячейке магазина): [с, а + (а в а) й, е) 1- [а, + (а в а) 3, с[ )- [Е, +(аеа)б, ЕОАР а; г'[Е, + (а ма) б, 1.ОАР а; р-'[Еф(, )б, 1ОЛР а;] )- )Еф(Е, ва) $, СОЛЕВ а;1.0ЛР а)) ! — )Е ф(Т, еа) й, 1.0АР а; 1.ОАР а;) )-'[Е -;.(Т в а, ) б, 1.0АР а; 1.0АР а;) [Е ф(Т к Е, ) й, ЕОАР а; 10АР а; ГОАР а;1 ~- )Е-! (Т, ) С, 10ЛР и; 10АР а; ЕОАР а; Мру)) ,'- [Е -)-(Е, ) $, !.ОАР а; !.ОЛР а; ЕОАР а; МРУ )[ )- )Е (Е), $, 1.ОАР а; ! ОА0 а;1.0АР а)МРУ)! )-в[Е-РТ, б, ГОАР а ', 1ОАР и; ЕОАР а; МРУ;] )- [Е, 3, 1,ОАР а; 1.0АР а; !.ОАР а;МРУ; АРР;) Заметим, что если буквы а, представляющие идентификаторы, снабжены индексами так, что входное выражение имеет, например, вид а, + (а,ма,), то выходиытт кодом будет !ОАР а, 1.0АР а, !.ОЛР а„ й(РУ АРР На нашей машине эта программа вычисляет исходное выражение.
П Хотя мопель вычислителыюй машины, описаннаи в примере ряй, предназначалась тольио Лля дечоистрапии синтаксически управляемого перевода весьма простых выражений, постфиксняк схема гпособна определить полезные классы переводов. В Оставшейся части главы мы покажем, как получается объектный код в других мсиелях вычислительных машин, работающих подобно МП-преобразователям иад тем, что нвляется цо существу простой постфиксной СУ.схемой, у которой входной грамматикой служит 1)т-грамматика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
