Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 47
Текст из файла (страница 47)
24б '1 Прн абрвбаткс сваха«свчесвага керавв, в ве ырсвв рвэбарв, вет свар. та«в саагве~сйвв с арввввамв «ывавв Л вЂ”. Т, Г Р в Р (Е) Поэт л1Г в рсаввввпив вез веабхаввыаств атрвывгь грввпввьвеы призвав асрсвазв, саатвсгсгвую~аве этвч првввави вывода. зы гл. а. парквод и гвнкрлцня кодл г.ь оаовщкниыс схьмы пггвводов для Е, построен так, что значением Е, должна быть конкатенация (1) гиачсния нетерминала Тм за которылг следует точка с запятой; !.О"О аг наг; О$1; ыатйх Оаг;БГОНЕ$1! Оа;ДОО$1 К„=)пап аз Т=1 Рис, З.Ы.
Дгргаа разбора с перггодгын. (2) командм 5ТОЕЕ с адресолг!гл, где л — высота вершины для Е (в правой части правила вывода), за которой следует точка с запятой; (3) значения нетерлгинала Е, (левого аргумента операции +), за которым следует точка с запятой; (4) команды А00 5л, где л то же, что и в (2). Здесь $л служит рабочей ячейкой, и перевод для Е, (в правой части элемента перевода) эту ячейку использовать не будет из-за способа обработки Ем Т, и Ем (2) Е Т В правьше (б) применяется МАМЕ(а), где ХАМŠ— функция, учашвующая в организации информации и дающая внутреннее (для коыпвлятора) иыя идентификатора, представленного лек- сеыой а.
Напомним, что терминальные символы асса наших грамматик — -зто лексемы Если лексема представляет идсншгфи- катор, то она будет содержать указатель на позицию в таблице имен, в которой храншся информация об этом идентификаторе. Зга информация говорит как о том, какой именно идентифвка- тор представляет данную лексему, так и о том, каковы атри. буты *того идентификатора.
Нз рнс. 9 !7 показано дерево разбора цепочки (а Ра) э (а+а] и даны значения некоторых символов перевода. й!ы предполагаем, что ХАМЕ(а) для четырех идентификаторов, представленных сныаолоч а, Лает значения оы а,, а, п а, Лл Пример 9.14. )ход, вырабатываемый в примере 9.13, никоим образом не оптныалеп. Его лгожно значительно улучшить, если заыет~гть, что когда праный операнд-. просто нденю1фикатор, нет необходимости читать его и запоминать в раба гей ячейке. Позгоыу ыы добавим третий перевод в правилах Е, Т и Е, являющийся логической переменной и принимающий значение истина тогда и только тогда, когда выражением, соответствую- ~г!ии данной вершине, яв.гнется просто идентификатор.
Первым переводом для Е, Т н Е вновь будет код, вычисляю- щий зыражснне. Однако если выражение — идентификатор, то переводом будет только „МАМЕ" этого идентификатора. Таким образом, схема перевода не „трудится" над одиночныч нденти. фикатором. Это приводит, впрочем, к некоторым неудобствам, поскольку можно считать, что грамматика для выражений со- ставляет часть грамматики для оператора присваивания, а перевод для таких операторов приснаивания, как А В, ос)зцествляется на более высоком уровне. Новые правила таковы: (!) Е Е+Т Е,=ИТ,1йеп НЕ,1йеп'(.ОАО'Е, ХА00' Т, еже Е, !А00' Т, е)хе ЕЕ, бпеп Т, ';5ТОЙЕ51; 1.0А0'Ег '; А00 $1' е1зе 7, ',5ТОЕЕ5' Е„';'Е, ', А00$'Е, Е,=шах(Ем Т,) 1-1 Е,=ложь Е,=Т, Ег = Тг ГЛ 9 ПЕРЕВОД И ГЕВРР|Ш|И КОЛЛ 9,| ОБОБ|ЦЕИПЫВ СХЕМЫ ПЕРЕВОДОВ В правиле (!) формула для Е, проверяет, являе|ся ли один из аргументов или оба просто идентификаторами.
Если правый аргумент в идентификатор, то генерируется код для вычисления лепота аргул|снта и сложения правого аргумента с содержимым сумматора Если левый аргумент †идентификат, то генерируелп |й код будет именем идентификатора.
В этол| случае ему должна предшествовать ').ОАВ'. Отметим, что тогда Е,--1, так что н качестве рабочей можно взять $1, а Ое ячейку '$'Ев (которая В этом случае все равно была бы $1). Код, вырабатываемый для (а а) Р(а-1 и), ил|ест вид 1 ОАВ ад АВВ иб $!ОВВ $2; 1ОАВ аб АВВ аб МРУ $2 В ||ил правилах перевода не предполагас|ся, что операции -1- и 9 коммута|ивпы. Наш слсдуюо|нй пример снова сэа*ан с арифметическими выра|кеннями. Оа показывает, как с помощью ОСУ-схемы можно описать процесс, в основе ноторого лежит прас|за СУ-схема, но детерминированный МП-преобразователь, реализующий эту скему, способен хранить В ячейках своего магазина некоторую дополшщельную ввнфорлва|лию. В начес|не промсжуто |ного языка выбран трехадресный код. Пример 9.1$.
Вудем переводить Е(бв) в последовательность трехадресных операторов вида Л - - ! ВС и Л В ВС, означающих, что переменной Л надо присвоить сумму или соответственно (3) Т ТРЕ (4) Т Е (5) Е (Е) (б) Е.-. а Т,=ПЕВ!й П Т, (реп '1.ОАВ' Т, ', МРУ' Е, ещет, ВМРУ'Е, еЬеПТ,!Веп Е, ",ВТОВЕ91, !.ОАВ' Т, ", МРУ $1' е!Ве Г, ',5ТОКВ2' Тв ", Т, ', МРУЪ' Т, Т, — |пах (Т„Е,) 1 1 7'в =- ложь Т, =. /', ҄—.. Е, 7 Ев Е,=Е, / в =- Е„ Е,=Е, Е, = (/АМЕ(а) Е,=! Р„ = истина произведение В и С. В этом примере Л будет цепочкой видай/, где | — целое. Основные переводы ЕО Т, н Е, будут последо- вательностями грсхадресных операторов, вычисляющими значе- цие выражения, соответствующее рассматриваемой вершине; Е„Т„и Е',— целые числа, указывающие, как и в предыдущем примере, уровни; Е„ТВ и ń— имя переменной, которой при- сваивается упомянутое выше значение выражения.
Этим иыенем будет программная переменная, ести выражение — просто иден- тификатор, и имя рабочей ячейки в противном случае. Схизма перевода такова: Е Е 1 Т Е,=. Е,Т,'1,'тах(Е,, Т,)' -1-'ЕвТВ ", Е, -- тах (Е„Т,) —, 1 Е, . '$' тах (Е„ТВ) Е Т Е,=Т, Е,=Т, Е„=- Т„ Т ТРЕ Т,=Т,Е,'$'тах(Т„Е)' — В*Т,ГВ '; Т„=- тах (Т„ЕВ) Р 1 Т, =- '$' тах (То Е„) Е Т,=.Р, Т,— -Е, Т, =-Е, Р (Е) Е,.=Е, Е,=Е, Е, =- Е, à — а Е,:= е Е,=) Е, —. //Ал(Е(и) Например, переводом для а,»(ивфа,) будет $! -1 иа,; $2 — РО,$1; Предоставляем читателю проследить, что правила перевода для Е„Т, и Е, образуют простую постфиксную СУ-схеыу. в предположении, что входныл|и символами являются значения второго н третьего переводов для Е, Т и Е.
Практически пере- вод можно осущестанть с помощью ДМП-преобразователя, хра- нящего в своем магаанне значения второго и третье| о переводов н выполняющего разбор грамматики б, методом СК(1). Такам образом, каждая нчейка магазина, содержащая Е, булет также содержать значения Е„и Е, для соответствующих вершин дерева разбора (аналогично для ячеек, содсржещих Т и Г), ГЛ. 9 ПЕРЕВОД И ~ ЕНРРЛ!ГГГЯ КОДЛ 9 3, ОЕОВЩЕННЫВ СХЕМЫ ПЕРЕВОДОВ Перевод осуществляется выдачей шах(Е„ТВ) ' р ' Е97'„ прв каждой свертке Е-).Т в Е; здесь ЕВ, Е,, Т, и Т, — значе- ния, приписанные ячейкам магазина, участвующим н свертке.
При свертке Т вЂ”. Т 9 Е производятся аналог!юные действия, а при остальных свергках не выдается ни гего. Следует огмегнть, что, поскольку второй и третий псревопы для Е, Т и Е могут принимать бесконечное число значений, устройство, осуществляющее перевод, не я в.чяетс я, строго говоря, ДМП-преобразователем. Однако на практике эта расширение легко реализуется на вычислительной мацшие с пронзаолыгым доступом. Пример 9.16. Будем генерировать код на языке ассемблера для условных Оператороа вида И вЂ” 1йеп — еше.
Предполагается, что нстерминал 5 представляет оператор и одно нз правил вы- вола — эго 5 И В !Ьеп 5 еЬе 5. Предполагается также, ч!о5 имеет пер. Вол 5„являющийся кодом лтя выполнения этого оператора. Если для 5 используе щя правило вывода, отличное от приведенного выше, будем считать, что перевод 5, вычислен правильно. Условимся также, гто В предсгавляет логическое выраже- ние и переводы В, н В, дзш В вычисляются ио другим прави- лам системы перевода.
В частности, В, †к, вызывающий переход на ячейку В„ если логичссное выражение принимает аначение ложь. Для генерации требуемого кола необходимо, чтобы у иетер- минала 5 был еще одни перевод 5„являющийся иьгеием ячейки, на которую будет передано управление после того, как заг<он- чится выполнение оператора 5. Будехг предполагать также, чга в вычислительной машине есть команда зх)й1Р щ Осуществляю- щая передачу упранлення па ячейку с имсисм а, Для генерации иыен этих ячеек применяется функггия )4ЕУРЕАВЕЕ, при обращении к которой генернруетсн имя для метки, никогда раныие не встречающееся Напргглгер, кохгпнля- тор может хранить глобальную переменную с целым значением г. Каждое обращение к ХЕУгг(.АИЕЕ может приводить к тому, что г' будет увеличиваться на 1, а в качестве значения будет выдаваться ичя Ейй Па самом деле функция х)ЕЮЕАБЕЕ в ука- занном выше правиле вывода еля 5 не вызывается, а вызывается в некоторых других правилах вывола для 5 и В.
Мы будем использовать также удобную псевдооперацию, по- добную которой можно найти в большинстве языков ассемблера. Эта команда ассемблера имеет ннд ЕО(/АЕ п, () Она нс генерирует никакого кода, а в результате ее выполнения ассемблер рассматривает а и й как нхгена одной н той же ячейки Команда ЕОПАЕ нужна потому, что каждое нз вхождений 5 в правой части правила Вывола 5 И В !Ьеп 5 еЬе 5 солержят имя команды, которая дотхкгга быть выполнена следующей. Мы должны быть хверены, что ячейка, участвующая в одно» из них, те же, что и в другом. Элементы перевода для этого правила нывода таковы: 5 И В Епеп Уп еЬе 5'и 5,='ЕЯОА1259" ',' 5',ь ", 1 Таким образом, перевол 5 состоит из конка геггацигз (!) команды, означающей, что 52' п 5)е представтяют одну' и т> же ячейку; (2) объектного кода для логического выражепня (В,), вычываюп!его переход на ячейку В„, сели его аначением является ложь; (3) объектного кола для первого Оператора (5В'), за которым следует перехол па ячейку, помеченную 5„'В (ячейка с этой меткой находится вне компилируемого Оператора); (4) объектного кола для второго оператора (5',ь), Первая я гейка этого кода помечена В,.
Перевод 5, для данного оператора тот же, что н перевод 5, для первого полоператора. Тгкнч образом, независимо от того, истин~го или ложно В, управление на ячейку 5',В (совпадающую теперь с 5';В) будет передано. 1эассмотрим сложпый пператор И Ве' йгеп И В'и !Ьеп 5'х' еЬе 5'и еЬе 5'з> вовникаюищй в результате лвух применений рассматриваемого правила вывопа (строго говоря, верхних индексов здесь не должно быть; они приведены для удобства ссылок). Объектным кодом, генерируемым для этого оператора, будет ЕО()АЕ У,", Уи код штя Вп' ГО!)АЕ 5',", 5!Я код для Вп' код для Ум Л)МР 5(г' В',ь; код для 5'м М)МР 5'," В',": код для Ум гл 9 пеРсаол и геиеРлцня кодл 9 9 ОЕОЗЩЕИНЫС СХЕМЫ ПЕРЕВОДОВ (Здесь точки с запятой ааменены переходами на новую строку.) ° Пример 9.17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
