А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 31
Текст из файла (страница 31)
те. с2 = а [ СЗ ]. После этого происходит возврат в функцию л а1ие для узла Ор для умножения 2*а [3-]с], где ранее была создана временная переменная с1. При вычислении этого выражения умножения в качестве побочного действия генерируется трехадресная команда С1 = 2 * С2. Наконец, функция ла]ие для всего выражения вызывает функцию Ьа!ие для левой части а [1] и генерирует трехадресную команду а [ 1 ] = с1, в которой правая часть оператора присваивания присваивается его левой части. а Улучшение кода для выражений Можно несколькими путями усовершенствовать функцию гта1ие на рис.
2.45 и генерировать меньшее количество трехадресных команд. ° Уменьшить количество команд копирования в фазе последовательной оптимизации. Например, команды с = 1+1 и 1 = С могут быть объединены в 1 = 1+1, если временная переменная с в дальнейшем не используется.
° Генерировать меньше команд с учетом контекста. Например, если левая часть трехадресного присваивания представляет собой обращение к массиву а [ с ], то правая часть должна быль именем, константой или временной переменной — все они используют только один адрес. Но если левая часть представляет собой имя х, то правая часть может быть операцией у ор а, которая использует два адреса. 151 2.8, Генерация промежуточного кода Избежать некоторых команд копирования можно путем изменений в функции трансляции, чтобы она частично генерировала команду для вычисления, скажем, 3+)с, но не указывала, куда должен быть помещен результат, указывая для него адрес ппП: ппП = 3 + )с (2.8) Позже нулевой адрес заменяется либо идентификатором, либо временной переменной.
Идентификатор будет использован, если присваивание 3+)с находится в правой части присваивания, например 1=3+)сг. В этом случае (2.8) становится — + )с Но если 3+)с является подвыражением, как в случае 3+)с+1, то адрес ппП в (2. 8) заменяется новой временной переменной П и генерируется новая неполная команда — + )с ппП = с + 1 Многие компиляторы делают все возможное для генерации кода, качество которого не хуже качества ассемблерного кода, написанного вручную экспертом в этой области. При использовании методов оптимизации кода наподобие описываемых в главе 9 эффективная стратегия может состоять в применении простейшего способа генерации промежуточного кода в надежде на устранение лишних команд оптимизатором кода.
2.8.5 Упражнения к разделу 2.8 Упражнение 2.8.1. Конструкции )ог в С и )ача имеют вид аког ( ехрг,; ехргз,. ехрг ) х~т~ Первое выражение выполняется до входа в цикл и обычно используется для инициализации счетчика цикла. Второе выражение представляет собой проверку, которая выполняется перед каждой итерацией цикла; цикл завершается, если значение этого выражения становится равным О. Сам цикл может рассматриваться как инструкция (згтг ехргз , .). Третье выражение выполняется в конце каждой итерации и обычно используется для увеличения значения счетчика цикла. Смысл инструкции 1ог аналогичен конструкции ехрг1; м)т11е ( ехргз ) ( хгтг ехргз' Определите класс Рог для конструкции 1ог, аналогичный классу 1) на рис.
2.43. Упражнение 2.8.2. Язык программирования С не имеет булева типа. Покажите, как компилятор С может транслировать инструкцию И в трехадресный код. 152 Глава 2. Простой синтаксически управляемый транслятор 2.9 Резюме к главе 2 Синтаксически управляемые методы из этой главы могут использоваться для создания начальной фазы компилятора, как проиллюстрировано рис. 2.46. 11( рееп == '(и' ) 11пе = 1апе е 1; (И)(О(Ы, "реек") (ея)(сопл(, ')и') О) (Ы, "11пе") (пенял) (Ы, "11 ее") (+) (ппп4, 1) (;) (: 11 = (1по) ')и' 2: 1ГГа1ае реек == 11 оооо 4 3: 11пе = 11пе е 1 леев ((пп вле ')и' 1!ле 1 Рис. 2.46. Две возможные трансляции инструкции + Отправной точкой для синтаксически управляемого транслятора является грамматика исходного языка. Грамматика описывает иерархическую структуру программы.
Она определяется в терминах элементарных символов, именуемых терииналами, и переменных символов, именуемых нетерминалами. Эти символы представляют конструкции языка. Правила, или продукции, грамматики состоят из нетерминалов, называющихся заголовками, или левыми частями продукции, и последовательностей терминалов и нетерминалов, которые называются телами, или правыми частями продукции.
Один из нетерминалов назначается стартовым символом. + При определении транслятора программным конструкциям могут быть назначены атрибуты, которые представляют собой некоторую связанную с конструкциями информацию. Поскольку конструкции представлены символами грамматики, концепция атрибутов является их расширением. Примеры атрибутов включают целочисленные значения, связанные с термина- 2.9, Резюме к главе 2 лом пвш, который представляет числа, или строки, связанные с представляющим идентификаторы терминалом Ы. + Пексический анализатор считывает входные данные по одному символу и выдает поток токенов; каждый токен состоит из терминального символа с дополнительной информацией в виде значения атрибута.
На рис. 2.4б токены изображены в виде кортежей в угловых скобках О. Токен (н), "рее)с") состоит из терминала н1 и указателя на запись в таблице символов, содержащую строку "рее)с". Транслятор использует таблицу для отслеживания зарезервированных слов и уже обработанных идентификаторов. + Синтаксический анализ, или разбор, представляет собой задачу определения, каким образом строка терминалов может быть выведена из стартового символа грамматики путем многократного замещения каждого нетерминала телом одной из его продукций. Концептуально синтаксический анализатор строит дерево разбора, в котором корень помечен стартовым символом, каждый внутренний узел соответствует продукции, а каждый лист помечен либо терминалом, либо пустой строкой е. Дерево разбора дает строку терминалов в листьях, считываемую слева направо.
+ Эффекгивные синтаксические анализаторы можно создать вручную, используя нисходящий (от корня к листьям дерева разбора) метод, называющийся предиктивным синтаксическим анализом. Предиктивлый синтаксический анализатор для каждого терминала имеет свою процедуру; тела процедур имитируют продукции лля нетерминалов. Поток управления однозначно определяется при помощи просмотра одного дополнительного символа из входного потока. Другие методы синтаксического анализа рассматриваются в главе 4.
+ Синтаксически управляемая трансляция выполняется путем назначения правил либо программных фрагментов продукциям грамматики. В этой главе были рассмотрены только силтезируеиые атрибуты, значения которых в любом узле к зависят только от атрибутов в дочерних по отношению к х узлах, если таковые имеются. Синтаксически управляемое определение назначает продукциям правила вычисления значений атрибутов. Схема трансляции вставляет в тела продукций программные фрагменты, называющиеся семантическими действиями. Эти действия выполняются в том порядке, в котором при синтаксическом анализе используются продукции.
+ Результатом синтаксического анализа является представление исходной программы, которое называется лромежуточлыч кодом. На рис. 2.46 показаны два основных типа промежуточных кодов. Абстрактное синтаксическое дерево содержит узлы для программных конструкций; дочерние узлы 154 Глава 2. Простой синтаксически управляемый транслятор представляют значащие подконструкции. Альтернативным вариантом является трехадресный код, который представляет собой последовательность команд, в которой каждая команда выполняет единственную операцию.
+ Таблицы символов являются структурами данных для хранения информации об идентификаторах. Информация помещается в таблицу символов при анализе объявления идентификатора. При последующем использовании идентификатора, например в качестве операнда в выражении, семантическое действие получает информацию о нем из таблицы символов. ГЛАВА 3 Лексический анализ В этой п1аве мы рассмотрим создание лексического анализатора.
Для реализации лексического анализатора вручную отбит начать с диаграммы или иного описания лексем каждого токена. Затем можно написать код, который будет идентифицировать каждую встреченную во входном потоке лексему и возвращать информацию об обнаруженном токене. Можно также получить лексический анализатор автоматически, определив шаблоны лексем для генератора лексическик анализаторов и компилируя их в код, функционирующий в качестве лексического анализатора.
Данный подход упрощает внесение изменений в лексический анализатор, поскольку для этого требуется переписать только измененные шаблоны, но не весь код программы. Он также ускоряет процесс реализации лексического анализатора, поскольку программист при этом работает только с очень высокоуровневыми шаблонами, а детальный код получается в результате работы генератора лексических анализаторов.
В разделе 3.5 вы познакомитесь с одним из таких генераторов, который называется 1,вх (или Яех в более поздних вариантах). Изучение генераторов лексических анализаторов начнется с регулярных выражений, удобной записи для определения шаблонов лексем. Вы узнаете, как можно преобразовать эту запись сначала в недетерминированный, а затем в детерминированный автомат. Последние две записи могут использоваться в качестве входных данных для "драйвера", т.е. кода, который имитирует работу этих автоматов и использует их в качестве руководства для определения следующего токена во входном потоке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
