Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 46
Текст из файла (страница 46)
После сверткй получается граф, изображенный Рве З.]З Часть выходного ор е ткэоваэяого ацзклнчвекого графа на рпс 9.!5. Предполагается, что р» указывает на вершину Лля Л, (]11 Если МП-процессор М достиг конца входной цепочки и его л~агазия содержит 5 н некоторые указатели, то указателеы па вершину для 5, является корень нужного выходного графа. Подробный пример мы рассл!отрвм после того, как обсудим интерпретацию графа. Очевидно, что каждая вершина графа „представляет" значение символа перевода в некоторой вершине дерева разбора. Но как зто значение можно получить ив графа? Ив опрслелеиия перевода, связанного с графоы, должно быть ясно, что значение, прелставляемое вершиной л, должно быть конкатенанней слева направо значений, представляемых прямыми потомками вершины и.
Отметим, что в действительгюс~и дна или более прямых потомков могут быть одной и той же вершиной. В вгоч случае значение вершины до,!жно повториться. Учитывая зсе сказанное, можем заключить, что нужный выход порождается следующим метпдом прохожденвя по графу. Алгоритм 95. Перевод графа. Вхо]. Граф с помеченными лнстьямн и единственным корнем.
Выход. Погледоаатетьность символов, помечаюшая листья. Метод. Мы будем использовать рекурсияную процедуру Р (и), где в — вершина графа. Сначала вызывается Р (и,), где л„— корень. Процедура Р (л). (!) Пусть аа аа .,., а„— дуги, исходящие из л в порядке записи. Совершаем шаг (2) для а„а.„, ..., а по порядку. (2] (а) Пусть а,— текущая дуга. Если а, влодит в лист, выдаем ыетку этого листа (б) Если а, входит во внутреннюю вершину и', выполняем Р (л'). уео!лема 9.7.
Если алгоритм 9.5 гери.ивняетел к графу, логтроевному алгоритмом 9.4, то выходом алгоритма 9 5 лвляеглсл перевод !!томи х, подаваемой на вход алгоритми 9.4. (о к аз а тел ьс тяп. Каждая верпшна и, вырабатываелшя аз~ори~люк 9.4, очеоидным образом соответствует аначению символа перевода в данной вершине дерева разбора для х. Индукпией по высоте вер~аииы лтожно показать, что процедура Р (и) вырабатывает значение этого сил!вила перевода. С] Пример 9.!2. Применим алгоритмы 9.4 и 9.5 к ОСУ-схеме из примера 9.!9, задав ца входе цепочку аааа. Последовательность конфигураций процессора приведена в табл. 9.4 (как обычно, 1.9(!)-таблицы опущены].
Тво.шво Э В Графы, построенные после ~па~он б, 7 и 9, приведены на рвс. 9.15. Вершины слева соответствуют значениям для 5„ а справа — для 5,. Примепенве алгоритма 9.5 к графу па рис. 9.15, в требует много вызовов процедуры Р (л]. Раба~а алгоритма начинается с верп1ингв ло поскольку опа соотзегстзует 5,. Выпишем после. довательнос!ь вызовов Р (л) и генераций выходного символа а (обращенвс к Р (ог) обпзпачено проста как л,); пллллрггаплаг|лааллллиаллгглаааллгцгг„оаапллвгллиааа С] э 3 оговщенныс схалгы пегсзодоз Рас. 9.!6.
Граф, ялсгэщл ма алгоритмом 9.4, 9.33Ц Разновидностн переводов Ло сих пор мы рассматривали в схеме перевода переменные, принимающие в качестве значений только цепочки, '1'е жс принпнпы, что привели к определению СУ-схем в ОСУ-схелг, позво ляг определить и реализовать схемы перевода,содержа~гГие также логические и арпфлгегические переменные. Цепочки, вырабатываемые в процессе генерации кода, можно разбить на несколько различных классов: (1] Машинные коды, нли команды асселгблера, которые должны быть выходом компилятора (2] Сообщения об ошибках, это также вымол компилятора, но яе в том выходном потоке, что (1) (3) Команды, указывающие, что некоторые операцив долгкны пРоизводиться иад данными, с которыми иысет дело сам ком.
пилнтор К классу (3) относятся команды, осуществляющие операции по организации информации, арнфметическве операции над перс. мениыми, используемыми компилятором не в механизме сингаксичесхого анализа, н операции по распределению памяти и генерации новых меток лля выходных операторов. Обсуждение то~о, когда выполняются эти операпнн, мы отложим до след)ющего раздела. Впт еще несколько примеров типа переводов, которые могут оказаться полезныма при генерации кода, (1) элементы конечного множества видов (веществеинь4, це лый н т. д.), указыза|ощие иа внд арифметического выражения, (2) цепочки, прелставляющие метки некоторых операторов прн колшнляции структур управления(например, И†!Ьеп — е]зе), (3) целые, указывающие высоту вершины в лерсвс разбора Мы обобщим чипы формул„которью можно прны«нить в СУ схеме для оычислевня переводз. Разумеется, работая с чис ами нпи логическими переменными, мы будем употреблять для иахожпения переводов логические и арифметические операторы Удобно использовать также условные выражении вида И В Итеп Е, е!зе Е.„где  — логическое выражение, а Ег н Е, †произвольн выражении, включая условные.
Например, в праввле вывода А ВС нетерлгинал В мог бы иметь логический перевод В„ а С вЂ д перевода С, и С, с це. пои~сами а качестве зиа гений. формулой перевода для Аг могла бы быть И В, (йеп С, е!ае С,. Это означает, что если левый прямой потомок вергцины, перевод А, которого вычисляется, иьгеет перевол В, =- истина, то в качестве А, надо взять первый перевод С, правого прямого потомка,' иначе надо взять Се Другой с,гучай: петерминал В мог бы иметь перевод В„ првнимающий целое аначеаие, и формулой для А, могла бы быть И В,--- тлэ гл э перевод и ггнеаюшп кодл = 1 !Ьеп С, е)зе С!ю Э,а приведе~ к гому, что значение А, будет го же, что и у С„ если значение Вв не 1.
Мы увидим, что не трудна обобщить алгоритм 9А, работаю щий снизу вверх, так, чтобы в кагествс переводов допускались числа, логические значения илн э.техтснзы некоторого конечного множества. В схеме раба.ы снизу ваерх формулы для этих перехгеппых (и д,ги перемснних. имеющих значениями цепочки) вычисляются толька тогда, когда известны все аргументы В самом леле, часто все свяаанние с вершиной переводы, кроме одного, будут .
огическичи, целыми илн элементами коиеч. ного мпшкества Если этот один (нмсющпи значением цспа к у) переаад ыожно и~лучить с помощью праннл перевода, являющихся по сущсстну правилами простой постфнксной СУ-схемы (возможно, с условияын), то можно выполнить весь перевод на ДМП-преобразователе, хрвпяпгем в гаоем магазине перепади разного типа, в том числе и н. цепочки.
Зги переводы легко „снязат '* с ягейкамн магазина, хранящими нетермнналы; эта будет оквндпая связь между нетермнааламн в магазине и внутрен. ними вершинами дерева разбора. Если некоторый перевод имеет целое значение, мы выходим за пределы описания ДМП-преобразователя, чта, впрочем, нс может сосгавить проблемы прн реализвцвн транслятора на вычи шыельной машине.
Однако обобщение алгоритмов 9.2 и 9 3, работающих сверху вниз, не столь просто. В случае когда должны быть сформировани только цепочки, мы допускали выможносгь неявного развертывания формул, т. е. формулы могли содержать указатели на вершины, которые в кон чнам счете представляют нужную цепочку По может оказаться, что трактовать таким же образом арифметнческве формулы илн формулы с уславиячи невозможно. Что касается алгорнтма 9.2, хюжно сделать следующую модификацию. Если развертывается нетермипал Л, находящийся н верхушке магазина, то указатель остаегся в магазине испо.
средственно под А. О» указывает на першину и, представляющую это вхождение А. После того как А развернут, хказатель снова будет в нерхушке магазина и будут вычислены перепады для всех потоыкоз вершины л (Ми покажем эга нид)к~нпгго.) Затем можно вычислять перевод вершины л точно так, как чы делалв бы, сс.ги бы анализ и~ел снизу вверх. Летали этого обобщения предлагаем в качестве упражнения Закончим раздел неснолькими примераын более общнх схем перевода в в оьаьщенные схемы 'переводов Вудем предполагать, что язык ассемблера содержит команды ЛРО и МРУ и СОЛО и 5ТОПЕ и имеющие очевидный смысл. Перевод будег основан на грамматике бю Каждый ич петер.
ьгнналов Е, Т н Р содержит по два элемента перевода Первый вырабатывает пеночку выходных символов, предсгавляющ)ю последовательность команд, после выполнения которой значение соответствующего входного выражения б)дет размещено на сум- маторе. Второй перевод будет целым чнслоы, представляющим высоту вершины в дереве разбора. Однако при определении высоты мы не будем считать правила Е= Т, Т . Р и Р (Е). Поскольку намерение высоты необходимо только для определе- ния имени ячейки, храншцей промежуточную инфорчапию, эти правила можно не учитынать.
Перечислим шесть правил н соответствующие им элементы перевода; (1) Š— Е 1-Т Е, —.— Т, г; 5ТОПГ Вг Е, ", Е, ', ЛОО 5' Е', Е,= шах (Е„Т,).!.1 (2) Е 7 Е,=1,') Е,=Т, !3) Т Г«Р Т, =Р, '5ТОРЕ 5' Т, '; Г, ", МРУ 5' Т, 7'„— швх (7 „Рв! + 1 Г,=Р, (б) Р (Е) Р, =- Е (б) Р о Р,='!К)ЛЕп МЛМЕ(п1 (МГ Р Для определения пено чек а лемента х перевода мы вновь принимаем соглашения языка Снабол Папочки, звключеннгвс в кааычни, представляют сами себя. Символы без кавычеи обх ° зиачаюг текущее значение символа, которое надо вместо него подставить. Таким образом, в правиле (1) элемент перевод Пример 9.13. Опишем Летально гхшерашпа кола л,гя арпфчетиаеских выражений, о кипрей шлв речь в ргшл 1 2 б, для машины с опним сумма~ором в пропзвольпым даст)пом к паыяпи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
