Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 68
Текст из файла (страница 68)
В мг)ьт в, А, л команды привелены в габл. 11 4 в инфнксной записи, как обычно. Значение сумматора А в конце программы соответствует (ип. фиксному) выражению 7 и (Х -1- У]. Таким образом, эта программа вычисляет Хн(ХХУ), помещая результат на сумматор А. Формально вычисляется также и значение выражении 3. Е) В наставшем разделе мы формально определим (арифметическое) синтаксическое дерево как помеченное двоичное дерево Т, имеювгее одну илн бояее таких вершин, что (1] каждая внутренняя першина помечена бинарной операцией 088 (2) все листья помечены различиымн именами переменных Х 8 2.
Для удобства будем предполагать, что множества )) и 2 не пересекаются. На рис. 11.8 изображено дерево для Хн(Х+1'). Рнс. )).а. днрннн лля Хл(Х".у). Вершинам дерева, начиная снизу, можно следующим обрнзом пряписать значения: (1) если а †ли, помеченный Х, то л имеет значение Х, [2) если л †внутренн вершина, помеченная 8, н ее аря. МЫМН ПатОМКаын ЯВЛЯЮТСЯ Л, И Л, СО ЗиаЧЕНИЯМИ О, Н Ои та Н имеет значение Оор, Значением дерева будем считать значение его корня. Например, значением дерева иа рис.
11.0 будет в ннфикспой записи Х н (Х вЂ”,'- 1'). гл и. оптимизация кодл Рассмотрим кратко связь между блоками на промежуточном языке (равд. 11.1) н программамн на языке ассемблера, которые мы только что определили. Прежде всего если дан приведенный блок, в котором (1) все операции бинарныс, (2) на кажд)чо входную переменную делается одна ссылка, (3) есть в точности одна выходная переменная, то граф, связанный с эткм блокам, является деревом. По нашей терминологин это дерево синтаксическое. Значение дерева -зто в то же время н значснне блока. Можно естественным образом, оператор ва оператором, преобразовать блок на промежуточном языке в программу на языке ассемблера Оказывается, что если при этом преобразовании учесть возможность оставлять вычисленные значения на сумматорах, то оптнмальную программу на языке ассемблера можно получить нэ данного приведенного о~крытого блока, произведя сначала только преобразование Т„ как зто предлагалось в теореме 11.5, и выполнив затем преобразование в язык ассемблера.
Однако все эта, быть может, не вполне оювидно; читатель должен сам проверить все эти утверждения. Именно в рсэуль. тате супгественаой переделки многих определений из равд. 11.1 для случая программ на языке ассемблера мы добиваемся возможности показать, что нет такой оптимальной программы на языке ассемблера, которая не была бы связана с блококг на промежуточном немке, получаемым из приведенного открытого блока, некоторым естественным пооператорным преобразованием н преобразованием Т,. п.т лгнеметнческнв Выглження (1) Если вершина есть лист, являющийся левым прямым потомком своего прямого предка, нлн корень (т.
е. дерево состоит нз одной этой вершины), помечаем зту вершину 1; если вершина есть лист, являющийся правым прялгым потомком, помечаем ее О. (2) Пусть вершина л амеег прямых потомков л, н л„помеченных 1, н 1,. Если 1, ~1„берем в качестве ее метки большее аз чисел 1 н 1. Если 1, = 1м берем в качестве ее метка число 1 Пример 11.!Б. Арифметическое выражение А ч ( — С)1(О ч (Š— Е)) Рас. !!.З. Памеченэое сэятэкснческое дерево. 1!.2.2.
Разметка деревьев Основное в алгоритме генерация кода для выражений — это метод назначения дополнительных меток вершинам синтаксического дерева, Такимн метками будут целые чнсла, и в дальнейшем мы будем ссьшаться на ннх как на метни вершин, несмотря на то, что каждая вершнна помечена также операцией нли переменной. Целочисленные метки определяют номера с)мматороп, нужных для оптимального вычисления ныраження. Алго рнтм 11,1. Разметка синтаксического дерева. Вход.
Сннтакснческое дерево Т. Выход. Помеченное синтаксическое дерево. Мешод. Вершинами дерева Т рекурснвно, начиная снизу, назначаем целочясленные меткн: изображено в виде дерева на рнс. !1.9, на котором проставлены целочисленные метки, Е) Дадим теперь алгорнты, преобразующий помеченное синтаксическое дерево в программу на языке ассемблера для машины с М с мматорами. Мы покажем, что для любого М получаемая програыма оптимальна относительно различных оценок, включая такис, как длина программы. Алгорнчм !1.2. Построение кода на языке ассемблераа для выражсн н й.
Вхо). Помеченное сннтакснческое дерево Т и Ф сумматоров Ао А„..., Аго где МЪ 1. В д. Программа Р на языке ассемблера, после последней мха. р т. с. Р, вы. команды которой значением о(А,) становятся о(Т)! т. с., вы. чнсляет выражение, предсгавлениое дерсвом Т, н помещает результат на сумматор А,. зьг гл и Оптимизация кодл п.л. лРиэметичаские ВыглжРиия )щл — )г )щу — ), (б) (б) (7) збэ Метод. Предполагается, что дерево Т помечено в соответствии с алгоритмом 1!.1. Затем рскурснвно выполняется процедура соде(л, г). Входом для соде служит вершина л дерева Т н целое число ) от 1 до У.
Число г означает, что в данный момент для вычисления выражения в вершине л доступны сумматоры АО Ала„..., Ал, Выходом для собе(л, г) служит последовательность команд нзыка ассемблера, которая вычисляет значение о(л) и помешает результат на сумматор А,. Сначала выполняется соде(л„, 1), где л, †коре дерева Т. Последовательность команд, генерированных этим вызовом процедуры соде, и будет нужной программой на языке ассемблера.
Процедура сабе(л, !). Предполагается, что и †верши дерева Т, а г †цел число между ! я 7У. (1) Если л — лист, выполняем шаг (2). В протнвном случае выполняем шаг (3). (2) Если вызвана процедура сабе(л, 1), а л — лнст, то л вгегдв будет левым прямым потомком (нли корнем, если и — единственная вершина дерева). Если с листом л связано имя перелив. ной Х, то сабе(л, г) ='ЕОАО Х, А)' (это означает, что выходом процедуры соде(л, г) служит команда ЕОАП Х, Аг). (3) В это место мы приходим, только если л -внутренняя вершина.
Пусть с вершиной л связана операция 0 и ее прямыми потомками являются л, и л, с метками 1, н 1, (см. рнсувок). Следующий шаг определяется значениями меток 1, и 1,: (а) если 1,=-0 (л,— правый лист), выполняем шаг (4), (б) еслн ! ((1г ( 1„и 1, < лр, выполннем шаг (6), (в) если ! ~~!а (1, и 1„(В, выполняем шаг (6), (г) если Л) ~(л н ТУ (1„выполняем шаг (7). (4) соде(л, г) =соде(п„() 'ОР 8 Ап Х, А Здесь Х вЂ” переменнав, связанная с листом л„а ОР 0 — код операция 8.
Выходом для соде(а, г) служит выход для соде(ли г), сопровождаемый командой ОР 8 Ал, Х, А, зэв (5) соде(л, 1) = собе(77„1) соде(л „г' -1-! ) 'ОР 8 Агап Аь А,' (6) соде(и, 1) =-соде(л„г) соде(л,, !+1) 'ОР 8 А„А„О А,' (7) себе(л, г) = сабе(л„г) Т пеи (еп)р 'БТОКЕ Аг, Т' соде(л„() 'ОР0 АОТ,А Здесь пем1ешр — функцня, которая прн обращении к ней вырабатывает новую временную ячейку памяти для запоминанни промежуточных результатов. С) Позже мы увндим, что прн выполненни шагов (5) — (7) алгорвтма 11.2 спрвведлнвы соотношения между 1„ 1, н 1, приведен- Табл Ча П 5 ные в табл. !1.5.
Отметим также, что для алгоритма !1.2 требуются команды типа (4) вида ОР0 А,В,А ОР0 А,В,В Несколько усложнив процедуру соде на шаге (5), можно избежать использования команд вида ОР8 А,В,В не входящих в определенный ками выше набор кот~вид машин с многими регистрами (слг. упр. !1.2 )!).
Можно рассматрнвать соде(л, г) как функцию, вычисляющую перевод в каждой вершние выражения в германах переводов и меток ее прямых потомков. Чтобы лучше понять алгорятл) 11.2, разберем несколько примеров Пример 11,!6. Пусть Т вЂ” синтакснческое дерево, состоящее ляжь из вершнны Х (помегепной !). В соответствия с шагом (2) соде это единственная команда ЕОАЭ Х, А,.
!!.! Аипомвгнчсскин Вырвжвния гл.!!. оптимизлция кодл плг "лг 71! т ццц ы.т вш ш ! )а:накал,д, соде(), 1) соде(*л, 1) сод (П, 1) оде( — л, 2) соде(Е 2) см)е(е», И соде(А, 1) сми( — ! 2) соде(П, 2) (ЗГ) (зв) (2) (Зе) (2) (Зе) (2) (Зе) (2) Годиицо Ы 6 соде(, 1) с 'де(2, 1) соде(-1-, 2) соде(Х, 2) фе) (2) (Зе) (П зм зто Пример !1.!7. Пусть Т вЂ помеченн синтаксическое дерева, изображенное на рнс. 11.10. В табл. 11.6 показано, квк выра.
батывается алгоритмом 11.2 програмиа на языке ассемблера лля т при .ч = 2. приведены вызовы процедуры соде(л,!) и со- Рис. 11.10. Помеееицое синтеисичесиое дерева с переводимо. ответствующие им шщн алгоритма 11.2, Вершина указывается при помощи связанной с ней перел!синай или операции. Вызов соде(Х, 2) генерирует команду мОАР Х, »1„явля!о- щуюся переводов!, связанным с вершиной Х. Вызов соде(+, 2) генерирует паследооатслы»ость команд ЕОАР Х, Л, АРР Ам У,А, являющуюся переводом для вер!нины +.
Вызов соде(2, 1) генерирует команду ЕОАР 2, Ам являющуюся переводом длн вершины 2, Вызов соде(», 1) генерирует окончательную програмл1у †перев корня: ЕОАР 2, А, ЕОАР Х, А, АРР Ам 1', А, МОЕТ А„Ам А, Эта программа аналогична (но не идентична) программе из при. мера 11.14. Очевидно, что в конце программы на сумматоре А! будет заачение Хе(ХА-У). О Пример 11.18. Применим алгоритм 11.2 прн У =2 н спитак.
сическому дереву рис. 11.9. Последовательность вызовов соде(л, !) приведена в табл. 11.7. Здесь ол — ссылка на левый потомок веРшины А ея — на пРавый потомок веРшнны ), — с — на пРавый потомок всрп!ины вс, а — л — на правый потоиок вершины ел. Указаны также шаги алгоритма 11.2, выполняемые при каждом вызове. Пропедура соде(1, 1) генерирует программу ЕОАР Р, А, ЕОАР Е, А, З(!ВТК А„Е, А, МОЕТ Ам Ам А, ВТОРОЕ Ам ТЕМР! ЕОАР А, А, 1ОАР В, А, ЗРВТ!1 А С А М(.0ЕТ Л„А„А, Р!Ч Ао ТЕМЕ(, А, Гл, 11 ОптимизАция кодл и.т АРиометические ВЫРАжения Здесь ТЕЛ!Р( — ячейка памяти, генернрованная функцией пем(еюр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
