Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 41
Текст из файла (страница 41)
Предположим, чзо у нас есть простая, но не постфиксиая СУ-схема, входная грамматика которой явлиется Ы(й)-гралтматикой. Как выполнить такой переводр Один из возможных методов состоит в использовании следуюилей многопроходной скемы перевода Втот метод иллюстрирует каскадную связь 2)2 ДМП-преобразователей, Правда, на практике такой перевод можно было бы осуществить и за один проход, если методы следующего раздела применить к произвольным СУ-схемам Пусть Т=(Д, В, Л, ), 5) — семантически однозначная простая СУ-схелта с входной 1.)т(й)-грамматикой 6. Для нахождения тт, врармк рЫтр йм и Рве. 9.4.
Простой Су геревод квд Ьпф)-грвммвтккой. ч (Т) можно построить четырехуроииевую схему перевода. Первый уровень занимает ДМП-преобразователь. Его входом служит входная цепочка шй. Выходом является правый разбор я цепочки ю, соответствующий входной грамматике 6. На зтойоом уровне я Обращается — получается обратный правый разбор я '). Входои для третьего уровня будет пя. Выходом — перевод, определяемый простой СУ-схемой Т' =(В, д', Л, В', 3), где И) содержит правило )В В„, ... В„у„В„... у,й,у, тогда и только тогда, когда А хВхг... В„х„,у Вут...В„у»вЂ” правило из Р, а А х,В,хт ...
В„х„— правило с номером т входной ).)т(й) грамматики. Легко доказать, что (пл, уя) Ет(Т') тогда И ТОЛЬКО татаа, КОГДа (5, 5)гвтил(Ш, У). ') Нвпомквм, что врввмй разбор я — это косведовв»лькосел орвввв в прв. во выводе, ввпвсвкквв в обрезком ворядке. Текам обрезом, и» квеккветск с первого пркмскеккого правила и ввкекеиввется последкам, для вострсеккк »" лхтвточво ерокктвть буфер, в коюром звпясвве восведовктелькос|ь в. в об.
раском порядке. 2!3 ГЛ Э ПЕРЕВОД И ГЕНЕРАЦИЯ КО!!» Т' — это простая СУ.схема, оснаваннаи на ).Е(1)-грамматике, и, следовательно, ее можно реализовать на ЛМП-преобразователе. На четвертом уровне просто обращается выход третьего уровня. Если выход третьего уровня записывается в магазин, то на четвертом уровне символы выталкиваются из магазина и по мере выталнивания пишутся в выходную цепочку. Эга процедура представлена на рис. 9.4.
Число основных операций, выполняемых на каждом из э»их уровней, пропорционально длине цепочкн ш. Таким образом, получаем следующий результат: Теорема 9.3. Любую прмп»ую СУ-схему с входной 1Н(й)-ероиматиеой можно Реализовать зо времл, прапор»(ионолвнос длине входной цепочки.
)(оназа тельство. Локазательство представляе~ собой формализацию изложенного выше. (3 9.2.2. Обобщенный преабрвзаввтень С помощью МП-преобразователя хорошо описываются асс простые СУ-схемы над Е1-грамматиками и неноторые простые СУ-схемы над ЕК-грамматиками, но для реализации (1) непростых СУ-схем, (2) непосгфиксных простых СУ-схем над 1.((-грал»матикал»и, (3) простых СУ.схем над грамматиками, не являющимися 1ц-грань»атнкал»и, (4) синтаксически управляемого перевода в случае, когда разбор проводится недетерминированным образом и не за один проход (иаи в гл. 4 и 6), нам потребуется более гибкая модель транслятора.
Определим теперь новое устройство, называемое МП-процессором. С его помо»цыо можно будет определить синтаксически управляемые переводы, отображающие цепочки в графы. МП-процессор — это МП-преобразователь, выходом которого служит помеченный ориентированный граф, предо»авляющий собой в общем случае дерево илн часть дерева, иоторое строит процессор.
Основная особенность МП-процессора состоит в том, чта в его ма»азине, помимо магазинных символов, могут содержаться указатели па вершины выходного графа. Подобно расширенному МП-автомату, МП-процессор может исследовать верхние й ячеек своего магазина для любого конечного И и произвольным образом обрабатывать их содержимое. Если этн й ячеек содержат указатели на выходной граф, то в отличие от МП.автомата МП.процессор моте~ видоиаменять выходной граф, добавляя или выбрасывая направленные дуги, 214 вв синтлксически РПР«нляемые парсвОды соединяющие вершины, на которые указывают эти указатели.
МП-процессор может таиже создавать новые вершины, помечать нх, создавать указатели на них и строить дуги, саединшащие эти вершины с теми вери»инами, на которые указывают указатели, содержащиеся в верхних ячейках ма! азина. Из-за трудностей, возникающих прн выраб»ггке компактной н ясной формальной записи для описания таких апераиий, будем пользоваться словесным описанием работы МП-пропессора. Так как на каждом шаге рабаты МП-процессора обрабатывае»ся лишь конечное число указателей, вершин н дуг, такой форма.
лизы в принципе возможен, однако ыы считаем, что он только заслонил бы идейную простату рассматриваемых алгоритмов, Начнем сразу с примера. Пример 9.5. Построим МП-процессор Р, отображающий арифл»етнческие выражения языка !.(б!») в синтаксические деревья. Н этом случае синтаксическое дерева будет деревом, в котором внутренние вершины помечены знакачн -1- нли «, а листья — бук.
вами а. На рис. 9.5 и 9.6 перечислены операпин разбора и выдачи, выполняемые МП.процессором д,»я всех возможных кам. бинаций текущего входного сикиона п снмвола, содержавгегося в верхщпке магазина. Р скоиструяровзн на основе 5С(((1)-а»»ализатора для бм показанного нз рнс. 7.37. Правда, в данном случае таблица Т, исключена из рис. 7 37 и правило Р а рассматриваетсн как цепное; »аблицы переименованы следующим обрааом: Старое имя ~(Т, 7, Т» Т» Т Т.7 Т 7 Новое имя ~(Т» Т» ( + «Т» Т, 7» ) Крол»е тога, правым концевым маркером служит символ 5. Операции разбора и выдачи процессора Р приведены на рис 9 5 н 9.6. Для того чтобы определять нужное действие, Р использует 1Н(1)-табтицы.
Помимо этого, когда таблицы ТО ТО Т, и Т, помещаются в магазин, Р прикрепляет н ннм указатели ') Эти )казатели относятся к порождаемому выходному графу, Однако указатели не олнают на процесс разбора. При разборе символы грамматики и магазин не записываются. Тем пе менее имена таблиц указывают, что зго должны бь»ть за символы, Последний столбец на рис. 9.5 содержит имя новой С(((!). таблицы, которую нужно поместить в магазин после свертки, Пустые элементы Обозначают ошибочные ситуации.
Новый вход- ') Нв првкшве этн указателя мов»во ввномвнв~ь в вмгвзнне непосрсхст. венно под твбввцвме. ГЛ, Е. ПЕРЕВОД И ГЕНЕРАЦИЯ КОДА индексами. Здесь левый столбец представлпет содержимое магазина, правый — входную цепочку. Исследуем некоторые интересные такты из этой посдедова. тельности. Переходя из конфигурации (1) в ионфигурацию (2), Р создает вершину лп помеченную символом а, и устанавливает уиазатель р, на эту вертпину. Указатель р, запоминается в магазине вместе с (.)(П )-таблицей Тг Аналогично, переходя из иопфигурапии (4) з конфигурацию (б), Р создает новую вер- тпинУ ле, помеченнУю символом аю и номе(Цвет в магазин Ука.
ватель р, на эту вершину вместе с Щ1)-таблицей Тп В конфигурации (7) образуется еше одна вершина лю помеченная Символом пю и устанавливается указатель р, на эту вершину. Рис. В.5. МП-пронжозр Р Рнс. В.у Вмхол после достижении конфтггурниии (81. Перейдя в конфигурацию (8), Р создает выходной граф, изображенный на рис, 9.7. Здесь р,— указатель на вершину и,. После того как процессор попадает в конфигурацию (11), выходной граф имеет вид, показанный на рис. 9.8. Здесь р,— указатель на вершину п,. В конфигурации (!1) действием таблицы Т, на 217 216 ной символ считывается только после переноса.
Числа в таблице относятся к действиям, приведенным на рис. 9.8. (1) Построить палую вершину л с меткой а. Помес~и~ь и еерхушк> мэгэзинэ символ (тт, р), где р — уиэзэгель на л. прочитать ~голый входной симэол. (2) Иэ эт эле о Верхушке мэгэзнин зэписанэ цепочка нэ четыре сн»- нолли энде Х !Тг, р,) 1-(Т(. р 1, ш р и р, — унззэтелк нэ еершины л, н л, слотэстстэениа Построить и еую перши у л с ч « й ., Сделать л, и л, жэым и правым прелыми потомками ю ршниы л Земеинть 17'о л,( 1-1 Тт, «,1 нн 1 Т, л), где Т .= нерехол(Х), а р — у кэзлтсль нэ лерОтеиг Л (3) То жс, что а (У), но Вместо -1- стоит (4) То же, по и (1), но эмест Т, стоит Тэ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
