Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 39
Текст из файла (страница 39)
роста . П я „цвтвкцзапня" состоят в тцн, цтобы в третьей строке заменить Т, нв А, е четвертую строку цмброгцзь. Заз Оператор аида А — ОВ,...В, означает, что г-местную аоервг ь вцню 0 надо применить к текущим зна'!синям переменных В, ..., В„ а полученное значение присвоить переменной А, Соответствующий язык будет формальна определен в разл. 11.!. Многоадресный код с явно именуемыми результатами при каждом присваивании требует име- д ни временной переменной для того, чтобы связать с ним значение выражения, стоящего справа в операторе присваивания. Можно избежать необходимости употреблять временные переменные, если пользоваться многоадресным кодом с с неявно именуемыми результатами В такой записи каждый оператор приснаивания помечается числом.
о Затем мы убираем левую часть опе- ратора и обрапгаемся к промежу- Рве. 9.!. савгедгцзгщце дерево. точным результатам при помощи числа, приписанного оператору, вырабатывающему промежуточный результат. Например, выражсгще (9.1.1) будет представ. лена последовательностью 1: 2: 3: 4: ц.~ галь пеяеводд в пгацессе компиляции межуточной программы значительно труднее, чем в представтеняе ее в виде связной списочной структуры. В качестве второго примера рассмотрим представление опе- ратора (9.1.2) В! = / Вйеп 5, е!ве 5, где 5, и 5, обозначают произвольные операторы. Возможным ностфиксным польским представлением этого опе- ратора может быть 3 Е!3ОЛЕз йь ЗЕАЕЗЕ 5; В 3НМР 5; Здесь 5, и 5,— постфиисные представления длн 5, и 5, соответ- ственно; Е!ЗНАЙ--бинарггая операция, дающая значение истина, <нгереаюр„егдеьд !4 <Виррмелж> Фйвн <д глдюерь ° !вв веерллер Л <ЕЬ(ЕЯНВЕЬЕ> <ИтВОШВДЕЮ <аРЕМЕММРР Е ' Х 1 1 ! Омрдгмммр > р 1 Рнс 9.2.
дерева выводе. если оба аргумента равны, и ложь в противном случае; !.,— константа, именующая начало 5;; ЗЕЛСЗЕ- бинарная операция, нызывающая переход на место, указываемое вторым аргументом, если значение первого аргумента ложь, и ие вызывающая никаких действий, если значение первого аргумента истина; константа й именует первую сзедующую за 5,' команду; ЗЕЛ!Р— унарная операция, вызывающая переход на место, указываемое аргументом. Дерево выпада оператора (9.1.2) приведено на рис. 9.2. Существенную информацию, содержащуюся в этом дереве вывода, можно представгщь синтаксическим деревом, приведенным на рнс.
9.3, где 5( н 5:, †синтаксическ деревья 5, и 5,. Синтаксический анализатор, гевернруюгцнй промежуточную нраграмму, разбирал бы выражение (9.1.2), просматривая дерево на рис. 9.2, но его выходом была бы последовательность команд построения синтаксического дерева рнс.
9.3. УПРАЖНЕНИЯ ГЛ. Ь ПЕРЕВОД И ГЕНЕРАЦИЯ КОДА УПРАЖНЕНИЯ Ркс. 9.3. Оппаксвческсе дерева 20з В синтаксическолг дереве, вообще говоря, внутренняя вершина представляет операцию, операндами которой служат ее врямые потомки. Листья синтаисического дерева соответствуют идентификаторам. Фактически листья являются указателями на таблицу имен, в которой хранятся имена и атрибуты соответствующих идентификаторов. <РЛЕЯРНАЯ „ЕГЛУ"Р е1асть выхода синтаксического анализатора составляют команды занесения информации в таблицу имев. Например, конструкция исходной программы вида 1МТЕОЕК ! будет преобразована в команду, заносяшую атрибут ьцелос" в позицию таблицы имен, зарезервированную для идентификатора !. Явного представления Атой конструкции в пронежуточной программе не будет.
9.1.3. Модвнн процвсев генерации кода Генерация кода — зто отображение промежуточной программы в пепочку. Мы будем считать сто функцией, определенной на синтаисическом дереве и на информации, содержащейся в таблице имен. Характер отображения зависит от исходной нрограммы, нонкретной машины и качества желаемого объектного кода. Одна из простейших схем генерации кода состоит в том, что кажлый оператор многоадресного представления отображается в последовательность команд на выходном языке, независимо от контекста команд в многоадресном представлении.
Например, оператор присваивания вида А +ВС может отображаться в три машинные команды ЕОАЛ В АРР С 5ТОКЕ А Здесь мы предполагаем, что используется однопроцессорная манена, в которой команда СОАЛ В помещает содержимое ячейки В в сумматор, АРР С складывает') содержимое ячейки памяти С с содержимым сумматора, а 5ТОКЕ А помещает содержимое сумматора в ячейку А. Команда 5ТОКЕ содержимого сумматора не изменяет. Однако если в сумматоре уже хранилось содержимое ячсики В (например, в результате выполнения предыдущей команды присваивания В - ) РЕ), то команда ЕОДР В становится лишней.
Кроме того, если следующая команда имеет вид В +АС и А нигде больше не используется, то не нужна и команда 5ТОКЕ А В равд 11.1 и 1!.2 мы изложим несколько приемов генерации кода по операторам многоадресного представления. 9.!.1. Нарисуйте синтакслгческие деревья для следующих операторов входного нзыка; (а) А .=.( — С),'(В + С) (в Фортране), (б) 1= 1.ЕМОТН (С1,)С2) [в ПЛ,'1), (в) Я В>С !Ьеп В Л > Е !неп А г = В ф С е1зе А: =  — С еЬе А;.= ВЕС (в Алголе). 9.!.2. Найдите постфнкспые польские представления для программ из упр. 9,1.!. 9.!.3.
Сгеперируйте многоадресный код с явно именуемыми резуленатами для операторов нз упр. 9.1.1. 9,!А. Постройтс детерминированеый МП-преобразователь, Отабражагоший префиксную польскую запись в посгфиксную польскую запись. 9.!.5. Покажлгте, что не существуетдетерминировавного МП- преобразователя, отображагокдего постфиксную польск)ю запись в префиксную польскую запись. Существуст ли недетерминированный МП.преобразователь, выполпиюпшй такое отображение) ,Уггязомиег См. теорему 3.15. 9.!.б.
Разработайте аягоритм вычисления постфиксного польского выражения, использующий магазин. 9.1.7. Сконструируйте МП-преобразователь, который, получая на вход выражение ж из ь(РА), порождает на выхопе по- ')ДАА простаты тоеустмм, чю г еьс гомько Одев гкя Арифметякк Ггве гккех геаоа нгскгл ко, еьервмгр Ариф тика с фексировкееой е плеземшей точкой, то еерееол Операеии ф будет эаьессгь от иефгрмькяе сб Атркбу ах кмге 3 и С, лапксьенок в гкблеке янек. ГЛ З ПЗРЕВОД И ГКИГРЛЦИЯ КОЛЛ Э З СИНТЛКСИЧЕСКИ УПРЛВЛЯЗМЫЕ ПВРВВОДЫ следовательность команд построения синтаксического дерева (или многоадресного кода) для ш. 9.1.8.
Сгенерируйте программы на языке ассемблера наиболее зникомой Вам машины для программ из упр. 9.!.1. *9.1.9. Разработавте алгоритмы для генерация программ на языке ассемблера наиболее знакомой Вам машины, соответствующих промежуточным программам, представляющим арифмети ческне действия и присваивания, когда промежуточная программа является (а) программой в постфиксной польской записи, (б) программой в многоадресном коде с явно именуемыми результатами, (в) программой в многоадресном коде с неявно именуемыми результатами, (г) некоторым представлением синтаксического дерева. *9.1.10.
Сконструируйте язык, удобный для представления некоторого подмножества Фортрана (или ПЛД, нлн Алгола). Это подмножество должно включать операторы присваивания и некоторые операторы управления. В нем должны допусиаться переменные с индексами. **9.1.! 1. Постройтс генератор кода, отображающий промеуку. точную программу из упр.
9.!.!О в машинный код наиболее знакомой Вам машины. Замечания по литературе К сожзлвхпю, даже дпя прогтих копгпзукзтяй хлою го язикл нюзьзя точно определять пзплучапй <збьектз~ий к| л Те» оо мвпее су~пествуог рхд кхпг н отзыв, пасвяюшпыь переводу рвзлпчхыь языков нрогрзннпровлнпя. Ьзкус н лр.
!!967! полробхо опхсзлн рвкнпй козпплятор Фортрзпз Репдтлл в Рассел (1964(, Грву н др. (1967! Взучпзю ззджу ргмлвззпвп Ллголз 60. Нвкоториз лттзлп реализации нзнкз Ппз! прпводспн в ИБМ (1969), Во нн гхх работях Взлагюотся нет лн, полезное прп гзптрз~твл кода. Кнут (1966В! Всслелолвл рззлпчпие нетоди рвоорздзтенпя памяти. Элсов и Ревк (1970! рассмотрели вопрос о гепсрапн кода для йревоввлп их структур проножуточпою язнкв.
Уплкокс (1971! предствввл пегколько опиях ноделсй дп проколов гтвтрзнпв кола 9.2. СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЕ ПЕРЕВОДЫ В настоящем разделе мы рассмотрим модель компилятора, в которою синтаксический анализ и генерация кода объединены в одну фазу. Такую модель ыожно представлять себе как компилятор, в котором операции генерации кода совиещены с операциями разбора. Для описания компиляции такого типа часто употребляется термин синтпкгичгски управляемая комг1иляВВВ.
Описываемые здесь методы можно применять также при генерации пронежуточного, а пе только объектного кода, или кода на языке ассемблера. Мы приводим один пример перевода В промежуточный код, остальные примеры о1носятся к коду иа языке ассемблера. Нашим отправным пунктом будет схема синтаксически управ. ляемого псрепода (СУ-схема), описанная в гл. 3. Мы покажем, как осуществить синтаксически управляемый перевод с помощью детерминированного МП-преобразователя, выпотняющего нисходящий илв восходищий анализ.
В этом разделе будем считать, что ДМП-преобразователь использует специальный символ в качестве ограничители правого конца входной цепозки. Кроме того, чтобы сделать СУ-схему более гибкой, мы наделим се дополнительными свойствами. Прежде всего, разрешим существо. ванне семантических правил, в которых определяется более одного перевода в различных вершинах дерева разбора.
В фор. мулах для этих переводоо разрешвм повторения и условные выражения. Затем рассмотрим переводы, не явгнющнеся цепоч. ками, полезные дополнительные типы переводов — целые и логические веремениые. Наконец, разрешим, чтобы переводы определялись другими переводами, найденными ве только в прямых потомках рассьзатриваемой вершины, но и в ее прямом предке. Сначала покажем, что всякую простую СУ-схему, заданную на СС.грамматике, можно реализовать детерминированным пре.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
