Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 45
Текст из файла (страница 45)
Прн реализацни перевода мы часто заинтересованы в его эффективноств. Равработайте методы оптимизации, аналогичные методам гл. 7, позволяющие цаходигь эффективные трансляторы для полезных классов синтаксически управляемых переводов. Упражнения иа програллпрозпкпг 9.2.19. Напишите программу, которая получает на вход простую СУ-схему пад С!.(1)-грамматнной и выдает транслятор, реализующий зту СУ-гхему 9.2,20. Напишите программу, строящую транслятор, который реализует постфиксную простую СУ-схему пад (ЛС!((1)-граьглшыгкой. 9.2.21.
Напишите програмл|), которая строит транслятор, реализующий произвольную СУ-схему над !.А С (4(! )-грамма тико!ь ззэ ГЛ З ПЕРЕВОД Н ГЕНЕРЛЦИЯ КОДЗ дл ове>ИЩЕИНЫЕ СХЕМЫ ПЕРЕИОДОН Замечания по литературе Впервые поэм жысть реализации прас ой СУ.схемы с «одной 1.С(й). граммтик й па МП.прсобразоеа л б ы м к зю а и Рэж Л акса е <лирозл ) Шбв) Оии также покюалэ, з>о простую пос фо сеу>о СУ-схсиу над Ся(а>-грамматикой м<жио рсалвзопе па ЛМП-преобразователе и любой перепад, выполняемый ЛМП.прыбрпзозателем, можно эффективно описать простой пес>фи с ой СУ-сымой над 1 ЕМ).граммтикой (уор.
2>2 7). Попятив мп-процессора ва::дево дхп и У > ммюч )1оааа) В многих коипилят рах оминлягороз н системах пютросния компиляторов выходной ночпзля ор опигыза . ит, эк оп зете схема синтакснчески управляв юю переезда. Сн>пакснс языка, лля кторог с гюатси компвля ор, определястсе с помтюю коп екстюсвобоавой <рамиза>ки Випдятсе н семантнчесиие «рогрэммы, сзизыные с налдым пранзлом Полученный выходной компилятор меж о промолелироаюь МП процессора» зкодиая цепочка еналнзнруе се к > гором, а зля вычисления выхода еь>зываклс» семаит ческне программы. ЯНРОВ с николом прело;залает собой упрощенную модель системы построения к мпи.
яп>роп ТМО (З1ак-Кмор, 1М й) Мзк-Илрой НЕ72) реалезоеал расширенно ТМО, в котором допусклютсз правила разо ра типа ОЯНРОВ.пртаил и возможно мопелароввиие поведе и» восходя<них анализат рпп. ОЯНРОВ с выходом — это упрощенная мелеть семейс>на комиилятороь ьомпилнторов МЕТЛ (Шорре, !Ч<4), Лва класса прость х Су.схем, «а лый лоры вклюеаег з себя прас>ые СУ схемы нзд 1ьирэимэ иками и псстфиксвые тросам СУ-схемы еад Сй-граммаптками, упоминаются Льюисоь> и С криюм (1Чба), а также Дхо и Ульмзном (Ш72ж) Каждый аэ этих нлассоа можно реалазоза >»в ЛМП. зр образоеагеле. 9.3. ОБОБЩЕННЫЕ СХЕМЫ ПЕРЕВОДОВ В этом разделе мы рассмотрим, как можно естественным образом расширить обсуждаемые ранее схемы перевода с тем, чтобы получить аозь>ожяость выполнять более широкий и более позезяый класс переводов.
Будем считать, что в общем случае элементом перевода, связанным с правилоч, может быль люГ>ои тип функции. Основные расширения заключаются в следующем: допускаются несколько переводов в каждой вершине дерева разбора, используются переменные, принимающие в качестве аиаченнй не только цепочки, разрешается зависимость переводов в вершине от переводон не только в ее прямых потомках, но н в ее прямом предке. Мы обсудим также важный вопрос о раабненнн на фазы при выполнении переводов в различных вершинах. 9ЛВ). Мупьтискеыы переводов ))атис пероое расширение СУ-схемы будет лопугкать в каждан иершине дерева раабора несколько переводов, имеющих значениями цепочки Как и в СУ.схеме, каждый перевод зази.
снг от переводов прямых потомков рассматриваемой вершины. Однако элементал>и перевода могут быть произвольные цепочки выходных символов и сммволов, представляющих переводы в потомках. Таким образом, символы перевода могут повторяться. Определение. Обобщенной сзгмой синтажсичегки рпраиляемого лгргат)а (ОСу схемой) называется шестерка Т =- (Н, т, л, Г, Л>, 5), где К, 2 и Л вЂ” соответственно коне<иные множества не>пермияилоа, е>одних сил<полое и оьжодяыл са мзолон, а )' — конеч<ое мно. жество симаолоз перевода вида Лд зд,есь Л ЕМ и < — целое число.
Мы будем полагать, что 5,Р Г 5 яачильяый гимеол, элемент множества Н. Наконец, )< — множество г<раоил перевода вида А а, Л,=Ею А,=(),...,А удовлетворяющих следующим условзиям: ()) Л< Б)' для ) <) <гл, (2) каждый символ, в>юдяший в ()ю ..,, Р, либо принадлежит Л, либо является таким сима<алом ВзбГ, что  — истер.
мннал, появляющийся в и, (3) если и имеет более одного вхождения символа В, то каждый символ В, во всех д соотнес.сн верхним инлексам с конкретным вхождением В. Мы будем называть А а аяодяым проаи <ам оьтода, А,— пер<ладон нетермннала Л и А>=В < — злгмеитом >ыревода, связанным с этим правилом перевода . Если крез Р оГ>означить множество входные пропил вывода всех правил перевода, го 6 =-(М, т, Р, 5) б>дет зтодяой граммтатикои для Т. Гслп в ОСУ- схеые Т нет двух правил перевода с одинаковым входным правилом вывода, то ее называют сема>итичг<ни оди<знаенои. Выход ОСУ.схемы определим си>иву виерх.
С каждой внутренней веригиной а дерева рааборш (во вход>юй грамматике), помеченной А, свяжем одну цепочку для каждого А, из Г. Эта цепочка называется зяачеиием (или терезодоэ>) символа А, н вершине и. Каждое значение вычнсляе:тон подстановкой значений Вг™г Рнс. Е.>2. ч сть дераое р збор символов перевода данного элемента перевода А<=()о определенных в прямых потомках вершинзы а. Например, пусть А ВаС, А, = ЬВ>Сзр)„А, =-С,сВ, — правило перевода в ОСу.схеые и в вершине А лерева вывода используется входное прави.>о вышила А ВаС (рис. 9.12).
237 гя э. птгивод и генсплция кодл Тогда, если значения символов В„Вх в вершине В и См С, в вершине С таковы, как указано иа рвс. 9.12, то значением символа Ао определенным в вершине А, будет Ьхху,х„а зычением символа А, в этой же вершине будет у,сх . Переводом т(Т), опредсляемым ОСУ-схемой '7, назовем множество ((х, у))х имеет дерево разбора ва входпои грамматике для Т и у -значение символа перевода 5, в корне этого дерева). Пример 9.10.
Пусть Т вЂ .((5), (а), (а), (5„ 5,), Е, 5) †ОСУ- схема, в которой Я состоит из правил 5 — + а5, 5, =-5,5',5,а, 5, =-5„а Тогда т(Т)=((а",оп))лир!). Например, а' имеет дерево раз. бора, изображенное иа рнс, 9.13, а. Значения двух переводов в наждой внутренней вершине показаны иа рис. 9.13, б. ,и 1 л; — ааал эх оэобшенныа схемы пеРеВОдОВ граьхматика Е-Е-,Т)7 Т Тпр)Р Р (Е))з1п(Е))соэ(Е))х)0)1 Свяжем с каждым из Е, Т и Р два перевода, обозначенные индексами 1 и 2. Индснс 1 указывает, что выражение не дифференцировано; 2 уиазывает, что выраженис продифференцировано.
Интересуюшие нас перевод — это Е,. Законы дифференцирования таковы' д () (х) + д (х)) = 4 (х) + 99 (х) И()(х)9(х)) =)(х)дй(х) Рд(х) д) (х) д яп () (х)) =- соз () (х)) д) (х) д соз () (х)) — ми () (х)) д) (х) дх=! дО =-О 91 =- О Г =аэ ! Лхп ааа Л = тл лапая л,=а Лх=а Рпс. 9!3. Обсбмепная схема спптанспчесхх Гпранлясишп пе!мппда. Напрниер, для того чтобы вычислить значение символа 5т в корне, надо подставить в выражсние 5,5х5ха значения длй 5, и 5, а вершние под корнель Втяни зйачениямн являются соответственно а' н а".
Для доказательства того, что т(Т) отооражает а" во", достаточно замет!пь, что От-,' 1)х=гд+2пд 1. Д Пример 9.11. Приведем пример формального дифференцирования выражений, включающих константы О и 1, переменную х и функции сип)с, косинус, + и л. )акис выражения порождает Зги законы рсализуютси ОСУ-схемой Е Е+7 Е Т Т Т Р Т вЂ” Р Р Е Р з(п (Е) Р соз (Е) Р" х Р, О Р 1 Е,=-Е,+7, Е, = Е, -1- Тх Е,=Т, Е, =.Т, 7,=7, Р, Т,=Т, Р,ш(7) Р, Т,=-Р, Р', — -(Е,) Р,. = (Е.,) Р,=жп(Е,) !', = соз (Е,) п (Е,) Р, =соя(Е,) Р, = — з(п (Е,) и (Е) Р =х 1 Р, =-1 Р,=О Р,=-О Р,= — 1 Р,=О ее оьоьщеииыв схемы пы вводов Гл.
е пеРеаОл и Генердцня коле лк лэ рве е 14. дерево вывода лвв мв(сы(в)) 24( 240 Н качестве упражнения предлагаем доказать, что если (ы, !)) б т(Т), то () — производная от и. Цепочкз Р может содер. жать избыточные скобки. Дерево вывода для ып (сов (х)) рх изображена иа рис.
9.(4. Значения символов перевода в каждой внутренней вершинв перечислены в табл. 9.3. Гмь,ккв Э.З Реализация ОСУ-схемы не сильно отличается от реализации СУ-схемы с помощью алгоритмов 9.! н 9.2. Обобщим теперь алгоритм 9.1 так, чтобы на выходе иметь не дерева, а ориентированный ацнклический граф. Тогда можно будет „проходить" по приентированному ациклическому графу так, чтобы иолучался нужный перевод, А л г о р и т м 9.4. В ы п о л н е н н е ОСУ-с х е м ы с н и з у в в е р х. Вхо().
Семантически однозначная ОСУ-схема Т =- ((4, 2, Л, Г, ((, 5) с входной ! (((Д)-гралгматикой В и входная цепочка хб д'. Выход. Ореентированный ацикличесиий граф*), из которого можно получить такой выход у, что (х, р) бт[Т). Метод. Пусть Л вЂ” (.В (й)-анализатор для В, Построим ЫП- процессор М с концевыьг маркерам, которыи будет моделировать ..4 и строить граф. Бели ьй содержит в своем магазине нетерминал А, то М поместит под А по одному указателю для каждого символа перевода Л, б Г, Таким образом, в графе будет столько вершин, соответствующих вершине Л в дереве разбора, сколько существует переводов для А, т.
е. символов Л, в Г. Действия М таковы: (!) Вели Ш выполняет перенес, то М делает то же самое. (2) Предположим, что к( собирается выполнить свертку в соответствиисправиломА и с элеьгентами перевода А,— -()„... , А„— !)„. В этот вгомент в верхушке магазина процессора М находится а, а непосредственно под каждым нетерминалом в ы ') Двв краткости ыы да коков рввдевв будем писать просто „граф",ыч скок слова еоркевтеравеккый вквкввессквй". — Прим.
верее. находятся указатели на каждый нз переводов этого нетерчи- 1 нала. Когда М делает свертку, сначала порождаются гл вершин, по одной на каждый символ перевода А,. Прямые поюмки этих вершин определяются снмволамн нз !)„..., Р . Порождаются новые вершины для выходных символов. Вершиной для символа переяода ВебГ служит вершина, отмеченная тем указателем под нетерманалом В в и, который представляет й.й перевод для В. (Как обычно, если В входит в и более чем один раз, то каждое его конкретное появление будет помечено в элементе перевода дополнительным верхним индексом.) При свертке М гл в пгэлзод и гкнгэлция Кодл в з оаоащвнные схемы пвовводов заменяет цепочку и и ее указатели символом А и т указателячи на переводы для А.
Например, допустим, что 1 выполняет свертку в соответствии с входным правилоы вывола правила перевода А — ВаС, А, .= ЬВ,ф„А, = С,оВ, Тогда в верхушке своего магавина М имеет пеночку р„рв Вар р,С (С . самый верхний символ), где р — указатели на вершины, представляющие переводы. При свертке М заменяет эту цепочку цепочкой рг,рл,А, где рл и рл,— указатели на первый и второй пер~воды для А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
