А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 139
Текст из файла (страница 139)
° Что делать, если имеется более одного соответствия шаблону? Эффективность сгенерированного кода может зависеть от порядка, в котором выявлялось соответствие шаблонам, поскольку различные последовательности соответствий будут приводить к разным последовательностям машинных команд, одни из которых более эффективны, чем другие. Если соответствия шаблонам не найдено, процесс генерации кода блокируется.
Другим предельным случаем является бесконечное перезаписывание одного узла, что приводит к генерации бесконечной последовательности перемешения значения между регистрами или бесконечной последовательности загрузок и сохранений. Чтобы избежать блокировки, мы полагаем, что любой оператор промежуточного кода может быть реализован при помощи одной или нескольких машинных команд. Далее, мы предполагаем, что имеется достаточно регистров для вычисления каждого узла. Тогда независимо от того, как именно выявляется соответствие шаблонам, остающееся дерево всегда может быть транслировано в команды целевой машины.
684 Глава 8. Генерация кода 8.9.3 Поиск соответствий с использованием синтаксического анализа Перед тем как рассматривать обобщенный поиск соответствий, рассмотрим специализированный подход, состоящий в использовании 1К-синтаксического анализатора для выполнения поиска соответствия шаблонам. Входное дерево можно рассматривать как строку при использовании его префиксного представления. Так, префиксное представление дерева на рис. 8.19 выглядит следующим образом: (пй + + Са Лзр щд + Сг Лзг + АХь С1 Схема трансляции дерева может быть преобразована в схему синтаксически управляемой трансляции путем замены правил преобразования дерева продукциями контекстно-свободной грамматики, в которых правые части являются префиксными представлениями шаблонов инструкций.
Пример 8.21. Синтаксически управляемая схема трансляции на рис. 8.21 осно- вана на схеме трансляции дерева на рис. 8.20. Рис. 8.2!. Синтаксически управляемая схема трансляции, построенная на основе рис. 8.20 Нетерминалами лежащей в основе такой схемы грамматики являются Л и ЛХ.
Терминал т представляет конкретную ячейку памяти, как, например, местоположение для глобальной переменной Ь в примере 8.18. Продукция М вЂ” т в правиле 10 может рассматриваться как соответствие нетерминала АХ ячейке памяти т перед использованием одного из шаблонов, применяющих М. Аналогично вводятся терминал яр для регистра ЯР и продукция Л вЂ” яр.
Наконец, терминал с представляет константы. При использовании этих терминалов строка для входного дерева на рис. 8.19 принимает вид !пд+ +с,яр)пд + с,яр + щьс~ 1) Л; — с, 2) ХЦ вЂ” ЛХ, 3) ЛХ- =ЛХ,Л, 4) М- =!пдЛ;Лу 5) Л; — !по+ с„Л 6) Л; — +Л, !пй+ с, Л, 7) Л,— +Л,Л 8) Л; — +Л, с1 9) Л вЂ” яр 1О) М вЂ” щ 1Р Вг, ()а ( !РВАМ, л ЯТ я, Вг ( Я2' *И, ВХ' ) ( РР Вг, п(й7) АРР Ы, Кг, а(В7) ) АРР Вг, Рл, 87 ) ( 1ЫС В! ) 685 8.9. Выбор команд путем переписывания дерева На основе продукций схемы трансляции мы строим ЕК-синтаксический анализатор с применением одного из методов построения ЕК-синтаксических анализаторов, представленных в главе 4.
Целевой код генерируется путем вывода машинных инструкций, соответствующих каждой свертке. Обычно грамматика генерации кода весьма неоднозначна и поэтому должны быть предприняты дополнительные меры по разрешению конфликтов в процессе создания синтаксического анализатора. При отсутствии информации о стоимости общее правило состоит в предпочтении ббльших сверток меньшим.
Это означает, что в случае конфликта "свертка — свертка" выбирается более длинная свертка, а при конфликте "перенос — свертка" — перенос. Такой подход "максимального разжевывания" приводит к выполнению большего числа операций с помощью одной машинной инструкции. Существует ряд преимуществ использования ЬК-синтаксического анализа для генерации кода. Во-первых, метод синтаксического анализа эффективен и хорошо изучен, а использование алгоритмов, описанных в главе 4, обеспечивает надежность и эффективность генератора кода. Во-вторых, прн этом облегчается перенастройка генератора кода для другой целевой машины. Создание генератора кода для новой машины сводится к разработке грамматики, описывающей инструкции новой машины.
В-третьих, качество генерируемого кода может быть сделано весьма высоким за счет добавления продукций для особых случаев, чтобы использовать преимущества машинных идиом. Однако при этом подходе имеется и ряд трудностей. При синтаксическом анализе фиксирован порядок вычислений слева направо. Кроме того, для некоторых машин с большим количеством режимов адресации грамматика, описывающая целевую машину (и, соответственно, сам синтаксический анализатор), становится необычайно большой. Как следствие необходимы специальные методы для работы с грамматикой описания целевой машины.
При разработке грамматики следует быть крайне осторожным, чтобы полученный анализатор не мог быть заблокирован в процессе разбора дерева выражения из-за того, что грамматика не обрабатывает некоторые шаблоны операторов или синтаксический анализатор выполнил неверное разрешение возникшего конфликта. Следует также гарантировать невозможность входа синтаксического анализатора в бесконечный цикл сверток продукций с одним символом в правой части.
Проблема циклов может быть разрешена путем использования технологии расщепления состояний при генерации таблиц синтаксического анализатора. 8.9.4 Программы семантической проверки В схеме трансляции для генерации кода встречаются те же атрибуты, что и во входном дереве, но зачастую с ограничениями на значения их индексов. Например, машинная команда может требовать, чтобы значения атрибута находились б8б Глава 8. Генерация кода в определенном диапазоне или чтобы два значения атрибутов были связаны некоторым соотношением.
Такие ограничения на значения атрибутов могут быть указаны как предикаты, вызываемые перед выполнением свертки. Использование семантических действий и предикатов может обеспечить большую гибкость и простоту описания по сравнению с чисто грамматической спецификацией генератора кода. Для представления классов инструкций могут использоваться обобщенные шаблоны, а семантические действия при этом могут использоваться для выбора команд в частных случаях.
Например, с помощью одного шаблона могут быть представлены два варианта команд сложения; йг(а = 1) я, с, хоо в,, а., №а Конфликты действий синтаксического анализа могут быть разрешены с помощью предикатов устранения неоднозначностей, которые обеспечивают использование различных стратегий выбора в разных контекстах. Поскольку некоторые аспекты архитектуры целевой машины, например режимы адресации, могут быль выражены с помощью атрибутов, для целевой машины можно получить описание меньшего размера.
Однако при этом трудно проверить, точно ли грамматика атрибутов описывает целевую машину (хотя в той или иной степени эта проблема касается всех генераторов кода). 8.9.5 Обобщенный поиск соответствий Подход к поиску соответствий с использованием 1К-синтаксического анализа основан на префиксном представлении левого операнда бинарного оператора. В префиксном представлении ор Е1 Ез решения №.К-синтаксического анализа с ограниченным предпросмотром должны приниматься на основе некоторого префикса Е,, поскольку операнд Е1 может быть произвольной длины. Таким образом, поиск соответствий может пропустить ряд моментов целевых команд, связанных с правым операндом.
Вместо префиксного представления можно использовать постфиксное, но при этом все сказанное выше останется в силе, просто будет относиться к правому операнду. В случае генератора кода, написанного вручную, можно в качестве руководства при написании воспользоваться шаблонами наподобие показанных на рис.
8.20 и написать узкоспециализированный генератор. Например, если корнем дерева является узел с меткой №пд, то единственный шаблон, соответствующий такому 687 8.9. Выбор команд путем переписывания дерева дереву, — шаблон из правила 5. Если же корень имеет метку +, то соответствие следует искать среди шаблонов из правил 6 — 8. В случае генератора генераторов кода нам требуется более общий алгоритм. Можно разработать эффективный нисходящий алгоритм путем расширения методов поиска соответствия строковым шаблонам из главы 3.
Идея заключается в представлении каждого шаблона в виде набора строк, где строки соответствуют путям от корня к листу в шаблоне. Все операнды рассматриваются одинаково при помощи включения в строки номеров позиций дочерних узлов слева направо. Пример 8.22. При построении множества строк для набора команд мы опускаем индексы, поскольку соответствие шаблонам основано только на самих атрибугах, но не на их значениях. Шаблоны на рис. 8.22 имеют следующий набор строк от корня к листьям: +10 +2!пав!+ 1С +2!пд! + 2Я +2й Строка С представляет шаблон с С в качестве корня. Строка + 1  — + и его левый операнд В в двух шаблонах, у которых корень помечен как +.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
