Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 48
Текст из файла (страница 48)
В качестве последнего примера этого раздела рассмотрим генерацию кода для вызовов вида саП Х(ЕО', ..., Е'"') Предположим, ч~о в языке ассемблера есть комакда СА!А. Х, которая передает управление на ячейку Х н запоминает з спе- циальном регистре адрес текущей ячейки для послед)тощего возврата из обращения к функции. Будем переводить са11 Х(Е'", ..., Е'"') в код, который вычисляет значения каждого из выражений Ец', ..,, Е'"' н запоминает их в рабочих ячейках За этими вычислениями идет команда ассемблера СЛЕЕ Х н л команд ЛКО !О ., АКО 1„, осуществляющих „хранение значении*' и испольжующихся как указатели на аргу- менты этого вызова Х. Основные правила вывода, описывающие оператор вызова, таковы: 5 — саП ОА А — е((!.) Е Е,!(Е Таким образом, оператором является ключевое слова са)1, за которым следует идентификатор и список аргументов (А) Спис- ком аргументов может быть либо пустая строка, либо список выражений, заключенный в скобки (Е).
Предполагается, что каждое выражение Е имеет два перевода Е, и Еа причем Е,— объектный код, помещающий а сумматор значение Е, а Е, †и рабочей ячейки для запоминания значения Е. Имена для рабо- чих ячеек порождаются функцией ХЕ%ЕАВЕЕ, Требуемый перевод осуществляется следующими правиламк: 5 саПОА З,=А, '(САП.' ХАМЕ(а)А, А (Ц А,— Е, А„=" ,1., А е А,=е А,=е (, Е, Е !.,=Е, ',БТОКЕ' Е, ',*!., 1,=.'ЛКО' Е, ',* 1., 1. Е Е,=Е, ',5'1'ОКЕ'Е, !.,=-'АКО' Е, Например, оператор саП АВ(Е"', Ео') перевалится (в предполажеяии, что рабочими ячейками для Ец' и Ео' являются 55! и е92 соответстиеино) в код для ЕО' 5ТОКЕ 59! для Е'9' ЗТОКЕ $$2 СА1.1. АВ АКО 95! АКО $52 Для реализации вывова можно было бы запоминать значения выражений Ец',, ЕЫ' непосредственно в ячейках, следующих за команлой СЛЕЕ(Х). Построение схемы перевода, генерируюгкей такой код, оставляем читателю в качестве упражнения.
С) 9.3.3. Наследственный м синтезированный переводы Сушссзеус| др)гое оообщеиие сиитексичсскп управляемого переводе, которое может оказаться полезным в некоторых приложениях. До снх пор мы рассматрива.ти переводы нетерминэлав как функции толька переводов прямых потомков вершины. Однако можно донустигь, юабы значение перевода была функцией значений переводов не только прямых потомков вершины, но и ее предков.
Дадим следукицее опрелеление. Опреде99еине. Перевод нетерминала в схеме перевода будем называть силшгэиравалнььк, если он зависит только от перево доз вершины, в которой вычисляетсн, и переводов се прямых потомков. Перевод будем называть иасмдсщеенньш, если ан зависит талька от переводов вершины, в которой вычисляется, и переводов ее прямого предке.
Все переводы, рассмотре99ные Ла сих пор, были синтезированными и, более того, не содержали формул, включающих переводы в самой вершине. Элементы перевода, связанные с правилам вывода, определим обычнымобразом,если определяемый перевод †синтезированн Однако наследственные переводы, связанные с правилом вывала, могут использовать в качестве аргументов переводы левон части правила нывала, зычно.тяя при этом перевод для некоторого конкретного символа в правой части. Значит, необходима о тичать нетермииал слева от любого ега вхождения справа. Как обычно, для этой цели мы б)дем употреблять верхние индексы. Пример 9.15.
Рассмотрим правила перевала г)~ ~ А~ А 9~ А О . аА и А тф 755 ГЛ» ПЕРЕВОД П Г1НЕРАОИЯ КОДА Эдесь А имеет два перевода; сингезированиый перевод А, и наследственный перевод А,. Правило для А, относится к знакомому нам типу. Правила для А!и и Ао' сл)жат примерами правил перевода для наследственных атрибутов. Исследуем часть дерева па рнс. 9.13. Праоило для А(»' говорит о том, что перевод А, в вер!пине и, должен совпадать с переводом А, а и,. Поскольку А, в и, выражается через А» в л,, зто приыер зациклепиого определения, и в такой форме зто правило нсдап)стима. (3 Схема перевода, содержащая кзк наследственный, так и синтезированный переводы, реалиауется не просто. В самом р»с З (а, Ч сть дерез», ОбщЕМ СЛТЧас СиаЧаяа Вада ГОЛПаетЬЮ построить дерево разбзра, а аатем вычислить в каждой вершине все переводы, которые можно вычислить в терминах уже вьшнсленных переводов в потамиах и предках.
Прежде всего надо нзчать с синтезированных атрибутов в вершинах высоты 1. При перевычиглеиии перевода все переводы, от него зависящие, как наследственные, так и синте.'шраванные, также должны вычисляться снова. Тем самым может оказаться, что продесс перевычнсления переводов никогда ие закончится. Такую схему перевода называют зоц!»Хленнои. Проблема распознавания, являе!ся ли схема перевода чаникленной, разрешима, хотя ее решение сложно, и мы предлагаем ее в качестве упражнения. Приведем пример, в которою для любого дерева разбора существует естественный порядок вычисления всех переводов.
Пример 9.19. Скал»пилируем для вычисления арифметических выражений код, ка!орый должен выполняться на машине еда!ма быстрыми регистрами, обозначенными через А н В. Будут использоваться команды СОАОА а СОАРВ а 5ТОЯЕА а 5ТОЯБВ а АРПА о АООВ а МРУ и АТОВ Смысл первых шести вочанд очевилен: можно считыват, запоминать и складывать в любом регистре. Предполагается, что ».3 ОВОЕЩЕННЫЕ СХЕМЫ ПЕРЕВОДОВ команда МРУ берст левый операнд из регистра В и заносит результат в регистр А. Последняя команда, АТОВ, передает содержимое регистра А в регистр В. Как и в примере 9.13, построим перевод на основе грамма. тики Вю Переводы Ео Т, и Р, будут представлять код для вы. числения значения соатветству»ощега входного выражения, зана- сящий результат либо в регистр А, либо в регистр В.
Однако перевод Г», для корня дерева разбора Всегда будет помещать значение выражения в регистр Л. Как и в примере 9.13, Ем Т, и Р„ будут пелыми чвслами, равными высотам вершин. Переводй Ею Т» и Е„ будут логическими выражениями, прини- мающими значение истина тогда н только тогда, когда значение выражения должно остаться в регистре А. Этн переводы †на- следственные, а первые шесть †синтезированн. Методы улуч- шения кода, данные в примере 9.14, здесь не приыенены. Пра.
вила перевода таковы: Е'!' Е'и-(- Т Е',и . 1(Е»»о (йеп Т, ',5ТОЯЕА $' Е',ь" ,ЕР' ',АПРА $' Е'," е!зе Т, '15ТОЯ ЕА $' Еш" ,Е',ь ')АО()В $' Е,'и Еп = шах(Е,"', Т!)+1 Е,'и = Е',о ') Т, =истина Е Т Е, =-Т, Е„=Т, Т» = Е, Т)" = и Т'," (йеп Е, ",5ТОЯЕА $' Т)Я ", Та' ",МРУ $' Т,'и еЬе Р, ',5ТОЯБА $' Т'ь" ,Т)н ',МРУ $' Ти' ПАТОВ' Т,'О =шах (Т,'", Р,) 1-1 Т',и = ложь Е„- истина Т Р Т,=. Е, Т,=Р, Р»=Т, Ти' Т!и РР Р А.лемлжтлив.».З ') Преапсл»гается, что вначале »се логические переводы »л»еют »Р»че ие нстааа. Так»к обр»зсм, сел» Е(п ссылается ее корень, считыюя, что перевал для нега т»ке оереаелее. Р (Е) Тар»еяе Р,з Рае. ЗЛЗ дерезе раеаере. гл. е пзгзвод и геитглция кодл Р,=Е, Р,=Е, Ее=ре Р,=-((Р, Гйеп '(.ОАОА' ХАМЕ(а) е(зе 'ЕОАОВ' ХАМЕ(а) Р,=( Стратегия ваключается в том, чтобы вычислять все правые операнды в регистре Л.
Левый операнд для а всегда вычисляется в В, левый операнд для + вычисляется либо в А, либо в В в завнсилюсти от того, где желательно его разместить. Таким образом, элемент перевода для Е',о, связанный с правилом вывода Е Е-). Т, дает перевод, который вычисляет Т в регистре Л, запоыннает его в рабочей ячейке, затем вычисляет Е либо в А, либо в В в зависимости от того, где желательно, и выполняет сложение. Правило перевода для Т,"', связанное с правилом вывода Т Т е Р, вычисляет Р в регистре Л, запоминает его, вычисляет Т в регистре В, умножает и, если надо, передает результат в регистр В. Лсрево разбора для (а+а)»а показано на рис. 9.(9, на котором некоторым внутренним вершинам присвоены имена. На.
следственные и синтезированные атрибуты переносятся без изменений вверх и вниз по цепям Е Т Р. В табл. 9.5 приведена последовательность вычисления переводов (перенос переводов нз Б в Т, из Т в Р и обратно в таблице не указан). Г) е з. озовщвниык схемы пкгвзодов Ф.ЗЛ. Замечание о разбиении нв фазы Мы обрисовали компилятор так, как будто каждый из его шагов †лексическ анализ, синтаксический анализ и генерация кода †выполнял отдельно в указаннолг порядке. Однако такое деление на Последовательные шаги служит скорее методическим целям представления и па практике может и не соблюдаться. Во-первых, фаза лексического авализа вырабатывает лексемы постольку, поскольку они необходимы для разбора.
Реально же з Юз ГЛ З. ПЕРЕЗОД И ГЕНЕРА!ШЯ КОПА УПРАЖНЕНИЯ входной цепочки лексем, которая была показана для демонстрации действий при разборе, мажет и не быть. Лексемы разыскиваются только по мере того, как они требуются при разборе. Конечно, эта разница никоим образом не влияет на процесс разбора. Как мы уже отиечали выше, разбор и геиерапия кода могут осуществляться одновременно. Таким образом, три фазы могут работать комбинирование.
Обращение к лексическому анализатору проискоднт тогда, когда процесс разбора не мажет идти дальше. После каждой свертки (при разборе снизу вверх) или развертки нетерминала (при разборе сверху вниз) фаза генерации кода обрабатывает вершину или вершины дерева разбора, сформированные только что. Если бы вырабатываемым переводом была одна цепочка, то было бы не столь существенно, когда именно вырабатываюгся различные ее части. Оливка напомним, что отдельные части вырабатываемого перевода могут бьюь различных типов: объектным кодом, диагностикой, командами, выполняемыми самим компилятором (такими, например, как команды по вводу информации в механизмы ее хранения).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
