А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 29
Текст из файла (страница 29)
Второе правило — синтаксическое дерево для нетерминала ЫосА представляет собой просто синтаксическое дерево для последовательности инструкций в блоке. Для простоты язык, представленный на рис. 2.39, не включает объявления. В приложении А, где объявления включены в язык, можно увидеть, что синтаксическое дерево блока все равно остается синтаксическим деревом инструкций в блоке.
Поскольку информация из объявлений вносится в таблицу символов, нет необходимости хранить ее в синтаксическом дереве. Таким образом, блоки, с объявлениями или без них, в промежуточном коде представляют собой всего лишь еще одну разновидность инструкции Последовательность инструкций представлена использованием листа пцй для пустой инструкции и оператором зео для последовательности инструкций: Ит1з — ~ зппй1 ~т1 ( хппк.п = петт Бед (зппкыгь ягтш); ) Пример 2Л8.
На рис. 2.40 показана часть синтаксического дерева, представляющая блок или список инструкций. В списке содержатся две инструкции, первая из которых — конструкция ((; а вторая — ттййе. Здесь не показана часть дерева над списком, а все полдеревья представлены просто треугольниками: два дерева выражений для условий и два — для инструкций конструкций (Г и и'п((е. 141 2.8. Генерация промежуточного кода чвве пав Рнс. 2.40. Часть синтаксического дерева для списка инструкций, состоящего нз инструкций !1 н и!и!е Синтаксические деревья для выражений Ранее мы обрабатывали более высокий приоритет умножения по сравнению со сложением при помощи трех нетерминалов ехрг, геге и ~асгог. Количество нетерминалов ровно на ! больше количества уровней приоритетов в выражениях, как говорилось в разделе 2.2.б. На рис.
2.39, кроме обычных операторов сложения и умножения, имеются два оператора сравнения, < и <=, с одинаковым приоритетом, так что в грамматику требуется добавить еще один дополнительный нетерминал — асИ. Абстрактный синтаксис позволяет нам сгруппировать "похожие" операторы для уменьшения количества вариантов и подклассов узлов при реализации выражений. В данной главе под "похожестью" подразумевается схожесть правил проверки типов н генерации кода для этих операторов. Например, обычно операторы + и * могут быть сгруппированы, поскольку они обрабатываются одним н тем же способом — у них одинаковые требования к типам операндов и каждый из них дает одну трехадресную команду, которая применяет один оператор к двум операндам.
В общем случае группированне операторов в абстрактном синтаксисе основывается на требованиях более поздних фаз компилятора. На рис. 2.4! указано соответствие между конкретным и абстрактным синтаксисом для некоторых операторов Зача. В конкретном синтаксисе все операторы левоассоциативны (за исключением оператора присваивания =, который является правоассоциативным).
Операторы в одной строке имеют одинаковые приоритеты; так, == и ! = имеют один и тот же приоритет. Строки таблицы приведены в порядке увеличения приоритета; например, оператор == имеет более высокий приоритет, чем операторы ьь н =. Нижний индекс ипагу в — „„,„использован исключительно для того, чтобы отличить ве- 142 Глава 2. Простой синтаксически управляемый транслятор КонкРРтн~|Й синтлксис Аьстглктн~|Й синтаксис аяя!нп сои|! сов|! ге! «= »= ге| ор ор по| щ|пця ассеяя ичигъ Рнс. 2.41. Конкретный и абстрактный синтаксис некоторых операций |ача гегт — гегт| *~асюг ! |егт.п = пеи' Ор ('*', |егтып, ~асюг.п 1; ! создает узел класса Ор, который реализует операторы, объединенные в группу ор на рис. 2.41. Конструктор Ор в дополнение к параметрам гегтпп и ~аког.п для подвыражений получает параметр '*', который указывает фактический оператор.
2.8.3 Статические проверки Статические проверки представляют собой проверки согласованности, выполняемые в процессе компиляции. Они не только гарантируют, что программа будет успешно скомпилирована, но и обладают потенциалом для раннего перехвата про- дущий унарный минус, как, например, в -2, от бинарного минуса, как, например, в 2-а. Оператор ! ! представляет обращение к массиву, как, например, в а [ з. ] .
Столбец "Абстрактный синтаксис" представляет группировку операторов. Оператор присваивания — единственный в своей группе. Группа сов|! содержит условные логические операторы ьь и !1 Группа ге! включает операторы сравнения в строках, представителями которых являются == и <.
Группа ор содержит арифметические операторы наподобие + и *. Унарный минус, логическое отрицание и обращение к массиву образуют каждый свою собственную группу. Отображение между конкретным и абстрактным синтаксисом на рис. 2.41 может быть реализовано путем написания схемы трансляции. Продукции для нетерминалов ехрг, ге!, а~И, гегт и ~асгог на рис. 2.39 определяют конкретный синтаксис для представительного подмножества операторов на рис.
2.41. Семантические действия этих продукций создают узлы синтаксического дерева. Например, пра- вило 143 2 8. Генерация промежуточного кода граммных ошибок — до выполнения программы. Статические проверки включают следующее. ° Проверки синтаксиса. Эти проверки имеют большее отношение к синтаксису, чем к грамматике. Например, проверки выполнения таких ограничений, как то, что идентификатор должен быть объявлен в области видимости не более одного раза, или что инструкция ЬгеаК располагается в охватывающем цикле или инструкции яич1сЬ, являются синтаксическими, хотя эти требования не кодируются и не обеспечиваются используемой грамматикой.
° Проверки тинов. Правила типов языка гарантируют, что оператор или функция будет применена к корректному количеству операторов допустимого типа. При необходимости преобразования типов, например при сложении целого числа с числом с плавающей точкой, программа проверки типов может вставить соответствующий оператор в синтаксическое дерево.
Преобразования типов будут рассмотрены позже. 1-значения и К-значения Рассмотрим несколько простых статических проверок, которые могут быть выполнены в процессе построения синтаксического дерева для исходной программы. В общем случае сложные статические проверки могут потребовать, чтобы сначала было построено промежуточное представление, и затем они будуг его анализировать.
Имеется существенная разница между смыслом идентификаторов слева и справа от оператора присваивания. В каждом из присваиваний 1=5; + 1 правая сторона определяет целое значение, в то время как левая — место в памяти, где это значение будет храниться. Термины (-значение и г-значение ((-га!ие и г-га(ие) определяют значения, которые могут использоваться в левой и правой частях инструкции присвоения соответственно. Таким образом, г-значения — это то, что обычно подразумевается под словом "значение'*, в то время как (-значения означают ячейки памяти. Статическая проверка должна убедиться, что левая сторона присваивания имеет (-значение.
Идентификатор наподобие 1 является (-значением, так же как и элемент массива наподобие а 12 ) . Однако константа 2 не может находиться слева от оператора присваивания, поскольку она имеет г-значение, но не (-значение. Проверка типов Проверка типов гарантирует, что тип конструкции соответствует ожидаемому в данном контексте. Например, в инструкции Ы 144 Глава 2.
Простой синтаксически управляемый транслятор Н ( ехр» ) з1тг ожидается, что выражение ехр» имеет тип Ьоо!еап. Правила проверки типов следуют структуре "оператор!операнд" абстрактного синтаксиса. Предположим, что оператор ге1 представляет операторы отношений, такие как <=. Правило типов для группы операторов ге! заключается в том, что два операнда такого оператора должны иметь один и тот же тип, а результат должен иметь булев тип Ьоо!еап. Используем атрибут Оре для типа выражения, и пусть Е состоит из применения ге! к операндам Е1 и Ез.
Тип Е может быть проверен после построения узла для этого выражения путем выполнения кода наподобие следующего: Н ( Е1.~уре = Ез.~уре ) Е.~уре = Ьоо1еап; е!яе еггог; Идея соответствия фактического типа ожидаемому применима н в следующих ситуациях. ° Приведение (соегсюп). Осуществляется, когда тип операнда автоматически преобразуется в тип, требуемый оператором. В выражении наподобие 2*3 .
14 обычное преобразование состоит в превращении 2 в эквивалентное число с плавающей точкой 2. О, после чего выполняется умножение двух чисел с плавающей точкой. Определение языка указывает, какие именно приведения допустимы. Например, фактическое правило для ге1, рассматривавшееся выше, может заключаться в том, чтобы Е1.(уре и Ез.гуре могли быть приведены к одному и тому же типу.
В этом случае сравнение, скажем, целого числа и числа с плавающей точкой оказывается вполне законным и коррекгным. ° Перегрузка. Оператор + в )ача представляет сложение при применении к целым числам; в применении к строкам он означает их конкатенацию. Символ называется лерегруженным (очаг!оаг(еб), если он имеет различные значения в зависимости от контекста. Таким образом, оператор + в )ача перегружен.
Значение перегруженного оператора определяется при рассмотрении известных типов его операндов и результатов. Например,мы знаем, что + в к=к+у представляет собой конкатенацию, если все переменные х, у и к имеют строковый тип. Однако если известно, что одна из переменных имеет целочисленный тип, то это означает наличие ошибки типов, и данное применение оператора + не имеет смысла. 2.8.4 Трехадрееный код После построения синтаксического дерева дальнейший анализ и синтез может быть выполнен путем вычисления атрибутов и выполнения фрагментов кода 145 2.8.
Генерация промежуточного кода в узлах дерева. Мы проиллюстрируем эти возможности путем обхода синтаксического дерева для генерации трехадресного кода. В частности, мы покажем, как написать функции, которые обрабатывают синтаксическое дерево и в качестве побочного результата генерируют необходимый трехадресный код. Трехадресные команды Трехадресный код представляет собой последовательность команд вида х =уорх Здесь х, у и х являются именами, константами или генерируемыми компилятором временными переменными; ор представляет оператор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
