А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 6
Текст из файла (страница 6)
роахСзоп представляет собой лексему, которая может отображаться в токен (Ы, 1), где И вЂ” абстрактный символ, обозначающий идентификатор, а 1 указывает запись в таблице символов для роазСхоп. Запись таблицы символов для некоторого идентификатора хранит информацию о нем, такую как его имя и тип. 35 1.2. Структура компилятора 2. Символ присваивания = представляет собой лексему, которая отображается в токен (=). Поскольку этот токен не требует значения атрибута, второй компонент данного токена опущен. В качестве имени токена может быть использован любой абстрактный символ, например такой, как аяя!яп, но для удобства записи мы будем использовать в качестве имени абстрактного символа саму лексему.
3. 1птста1 представляет собой лексему, которая отображается в токен (Ы, 2), где 2 указывает на запись в таблице символов для 1птста1. 4. + является лексемой, отображаемой в токен (+). 5. гасе — лексема, отображаемая в токен (Ы, 3), где 3 указывает на запись в таблице символов для гас.е. б. * — лексема, отображаемая в токен (*). 7. 60 — лексема, отображаемая в токен (60).2 Пробелы, разделяющие лексемы, лексическим анализатором отбрасываются. На рис.
1.7 показано представление инструкции присваивания (1.1) после лексического анализа в виде последовательности токенов Ы1 (=) Ы2 (+) ЫЗ (е) (60) (1.2) При этом представлении имена токенов =, + и * представляют собой абстрактные символы для операторов присваивания, сложения и умножения соответственно. 1.2.2 Синтаксический анализ Вторая фаза компилятора — синтаксический анализ или разбор (рагз(пя). Анализатор использует первые компоненты токенов, полученных при лексическом анализе, для создания древовидного промежуточного представления„которое описывает грамматическую структуру потока токенов. Типичным представлением является синтаксическое дерево, в котором каждый внутренний узел представляет операцию, а дочерние узлы — аргументы этой операции.
Синтаксическое дерево для потока токенов (1.2) показано на выходе синтаксического анализатора на рис. 1.7. Технически говоря, для лексемы 60 мы должны создать тскен нвпедобне (пппзвег,4), где 4 указывает нв запись таблицы символов для внугреннеге представления целого числа 60, не обсуждение тскенов для чисел мы отложим де главы 2.
В главе 3 будут рвссмстрены метсды построения лексических анализаторов. Глава 1. Введение в компиляцию рое161оп = Зп161а1 е алое * 60 (Ы, !) (=) (Ы, 2) ( '-) (!6, 3) ( ) (60) (Ы, !) (!й, 2) (Ы, 3) 60 (Ы, 2) (Ы 3) !ацойоа! ! 60 Таблицасимволав 61 = 1ппоо11оао(60) 62 = 1бЗ * 61 13 = 1б2 е 12 1б1 = сз 61 = 1бЗ * 60.0 аб1 = Рб2 е 11 ООГ К2, 1бЗ МООГ К2, К2, 660.0 ООГ К1, 1б2 АООГ К1, К1, К2 БТГ тб1, К1 Рис. 1.7. Трансляция инструкции присваивания 37 1.2. Структура компилятора Это дерево указывает порядок, в котором выполняются операции в присваивании роайТ1оп = 1п161а1 + гасе * 60 Дерево имеет внутренний узел, помеченный *, левым дочерним узлом которого является (Ы,З), а правым — 60. Узел (Ы,З) представляет идентификатор гасе. Узел, помеченный *, явно указывает, что сначала мы должны умножить значение га~е на 60. Узел, помеченный +, указывает, что мы должны прибавить результат умножения к значению 1п1ста1.
Корень дерева с меткой = говорит о том, что следует присвоить результат этого сложения в позиции памяти, отведенной идентификатору ровт~фоп. Порядок операций согласуется с обычными арифметическими правилами, которые говорят о том, что умножение имеет более высокий приоритет, чем сложение, н должно быть выполнено до сложения. Последующие фазы компилятора используют грамматическую структуру, которая помогает проанализировать исходную и сгенерировать целевую программу. В главе 4 мы будем использовать контекстно-свободные грамматики для определения грамматической структуры языков программирования и рассмотрим алгоритмы автоматического построения эффективных синтаксических анализаторов для определенных классов грамматик.
Из глав 2 и 5 вы узнаете, что синтаксически управляемые определения могут помочь уточнить трансляцию конструкций языка программирования. 1.2.3 Семантический анализ Семантический анализатор использует синтаксическое дерево и информацию из таблицы символов для проверки исходной программы на семантическую согласованность с определением языка. Он также собирает информацию о типах и сохраняет ее в синтаксическом дереве или в таблице символов для последующего использования в процессе генерации промежуточного кода. Важной частью семантического анализа является проверка типов, когда компилятор проверяет, имеет ли каждый оператор операнды соответствующего типа.
Например, многие определения языков программирования требуют, чтобы индекс массива был целым числом; компилятор должен сообщить об ошибке, если в качестве индекса массива используется число с плавающей точкой. Спецификация языка может разрешать определенные преобразования типов, именуемые приведениями (соегсюп). Например, бинарный арифметический оператор может быть применен либо к паре целых чисел, либо к паре чисел с плавающей точкой. Если такой оператор применен к числу с плавающей точкой и целому числу, то компилятор может выполнить преобразование целого числа в число с плавающей точкой.
38 Глава 1. Введение в компиляцию 1.2.4 Генерация промежуточного кода В процессе трансляции исходной программы в целевой код компилятор может создавать одно или несколько промежуточных представлений различного вида. Синтаксические деревья являются видом промежуточного представления; обычно они используются в процессе синтаксического и семантического анализа. После синтаксического и семантического анализа исходной программы многие компиляторы генерируют явное низкоуровневое или машинное промежуточное представление исходной программы, которое можно рассматривать как программу для абстрактной вычислительной машины.
Такое промежуточное представление должно обладать двумя важными свойствами: оно должно легко генерироваться и легко транслироваться в целевой машинный язык. В главе 6 мы рассмотрим промежуточное представление, которое называется трехадресиым кодам и состоит из последовательности команд, напоминающих ассемблерные, причем в каждой команде имеется три операнда и каждый операнд может действовать, как регистр. Выход генератора промежуточного кода на рис. 1.7 состоит из последовательности трехадресных кодов Г1 = тпггой1оас160) с2 = 1с)3 * с1 ГЗ = Ы2 + ~2 Ы1= ~3 (1.3) Следует сделать несколько замечаний по поводу трехадресных команд.
Вопервых, каждая трехадресная команда присваивания содержит как минимум один оператор справа. Таким образом, приведенные команды определяют порядок выполнения операций — в исходной программе (1.1) умножение выполняется раньше сложения. Во-вторых, компилятор должен генерировать временные имена для хранения значений, вычисляемых трехадресными командами. В-третьих, некоторые "трехадресные команды" наподобие первой и последней в последовательности (1.3) содержат менее трех операндов. Такое приведение показано на рис. 1.7.
Предположим, что ровтГтоп, тптгта1 и гаге были обьявлены как числа с плавающей точкой и что лексема 60 образует целое число. Проверка типов в семантическом анализаторе на рис. 1.7 определяет, что оператор * применяется к числу с плавающей точкой гаГе и целому числу 60.
В этом случае целое число может быть преобразовано в число с плавающей точкой. Обратите внимание, что на рнс. 1.7 в синтаксическом дереве, полученном на выходе семантического анализатора, имеется дополнительный узел для оператора 1птгоаоаг, который явным образом преобразует свой целый аргумент в число с плавающей точкой. Проверка типов и семантический анализ рассматриваются в главе 6. 39 1.2. Структура компилятора В главе 6 мы рассмотрим основные промежуточные представления, используемые компиляторами. В главе 5 вы познакомитесь с методами синтаксически управляемой трансляции, которые будут применены в главе 6 для проверки типов и генерации промежуточного кода для типичных конструкций языка программирования, таких как выражения, конструкции управления потоком выполнения и вызовы процедур.
1.2.5 Оптимизация кода Г1 = ЫЗ * 60.0 Ы1=Ы2+~1 (1.4) Имеется большой разброс количества усилий, затрачиваемых различными компиляторами на оптимизацию на этом этапе. Так называемые "оптимизирующие компиляторы" затрачивают на эту фазу достаточно много времени, в то время как другие компиляторы применяют здесь только простые методы оптимизации, которые существенно повышают скорость работы целевой программы, при этом не слишком замедляя процесс компиляции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
