Главная Промышленная автоматика. ГЛ, [. ВВЕДЕНИЕ в КОМПИЛЯЦИЮ Если да, то лексема, соответствующая новому вхождению этого идентификатора, будет той же, что и у предыдущего вхождения. Например, если в программе, написанной на Фортране, после Таблица 1.1
указанного выше оператора следует оператор, содержащий переменную COST, то лексемой для второго вхождения COST должна быть <ид>, - та же, что и для первого вхождения. Таким образом, эта таблица должна обеспечивать (1) быстрое добавление новых идентификаторов и новых сведений о них, (2) быстрый поиск информации, относящейся к данному идентификатору. Обычно применяют метод хранения данных с помощью таблиц расстановки; они будут обсуждаться в гл. 10 (том 2). 1.2.4. Синтаксический анализ Как уже упоминалось, выходом лексического анализатора является цепочка лексем. Эта цепочка образует вход синтаксического анализатора, исследующего только первые компоненты лексем-их типы. Информация о каждой лексеме (вторая компонента) используется на более позднем этапе процесса компиляции для генерации машинного кода. Синтаксический анализ, или разбор, как его еще называют,- это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Какова синтаксическая структура данной цепочки, существенно знать также и при генерации кода. Например, синтаксическая структура выражения А-[-В к-С должна отражать тот факт, чТо сначала перемножаются В и С, а потом результат складывается с А. При любом другом порядке операций нужное вычисление не получится. Разбор - одна из наиболее попятных фаз компиляции. По совокупности синтаксических правил можно автоматически построить синтаксический анализатор, который будет проверять, имеет ли исходная программа синтаксическую структуру, определяемую этими правилами. В гл. 4 - 7 мы изложим несколько различных методов разбора и алгоритмов построения синтаксических анализаторов по заданной грамматике. Выходом анализатора служит дерево, которое представляет синтаксическую структуру, присущую исходной программе. В некотором отношении синтаксический анализ программы напоминает разбор предложений, который все мы проводили в школе. Пример 1.3, Допустим, что выход лексического анализатора - цепочка лексем (1.2.1) <ид>, - «ид>з + <ид>д) <ид>, Эта цепочка передает информацию о том, что необходимо выполнить в точности следующее: (1) <ид>з прибавить к <ид>о, (2) результат (1) умножить на <ид,\, (3) результат (2) поместить в ячейку, зарезервированную для <ид>1. Эту последовательность шагов можно представить наглядно с помощью помеченного дерева, показанного на рис. 1.3. Внут- <ид>4 <иа>э Рис. 1.3. Древовидная структура. ренине вершины дерева представляют те действия, которые надо выполнить. Прямые потомки каждой вершины либо представляют аргументы, к которым нужно применить действие (если соответствующая вершина помечена идентификатором или является внутренней), либо помогают определить, каким должно быть это действие (в частности, это делают знаки +, *, =). Заметим, что скобки в цепочке (I.2.I) в дереве явно не указаны, хотя мы могли бы изобразить их в качестве прямых потомков вершины Роль скобок только в том, что они влияют на порядок операций. Если бы в цепочке (I.2.I) их не было, следовало бы поступить согласно обычному соглашению о том, что умножение „предшествует" сложению, и на первом шаге перемножить <ид>з и <ид>4. □ 1.2.5. Генерация кода Дерево, построенное синтаксическим анализатором, используется для того, чтобы получить перевод входной программы. Этот перевод может быть программой в машинном языке, но чаще он бывает программой в промежуточном языке, таком, как язык ассемблера или „трехадресный код" (последний образуется из простых операторов, каждый из которых включает не более трех идентификаторов; например, А-В, АВ + С или GOTO А). Если требуется, чтобы компилятор произвел существенную оптимизацию кода, то предпочтительнее код трехадресного типа. Так как трехадресный код не привязывает вычисления к конкретным регистрам вычислительной машины, регистры легче использовать для более эффективной оптимизации. Если предполагается малая оптимизация или никакая, то в качестве промежуточного языка лучше взять язык ассемблера или даже машинный код. Для того чтобы проиллюстрировать узловые моменты процесса трансляции, рассмотрим бегло пример трансляции на язык ассемблерного типа. Пусть в этом примере nania машина имеет один рабочий регистр (сумматор, или регистр результата) и команды языка ассемблера, вид которых определен в табл. I. 2. Запись „с (т) -> сумматор" означает, что содержимое ячейки памяти m надо поместить в сумматор. Через -т обозначено численное значение т. Из этих замечаний ясен смысл всех семи команд. Выходом синтаксического анализатора служит дерево (или некоторое представление дерева), представляющее синтаксическую структуру цепочки лексем, полученной на выходе лексического анализатора. С помощью этого дерева и информации, хранящейся в таблице имен, можно построить объектный код. На практике построение дерева и генерация кода часто осущест- вляются одновременно, но методически удобнее считать, что они происходят последовательно. Существует несколько методов построения промежуточного кода по синтаксическому дереву. Один из них, называемый синтаксически управляемым переводом (трансляцией), особенно изящен и эффективен. В нем с каждой вершиной п связывается Таблица 1.2
Предполагается, что ADD и МРУ - операции с плавающей точкой. цепочка С {п) промежуточного кода. Код для вершины п строится сцеплением в фиксированном порядке кодовых цепочек, связанных с прямыми потомками вершины д, и некоторых других фиксированных цепочек. Процесс перевода идет, таким образом, снизу вверх (т. е. от листьев к корню). Фиксированные цепочки и фиксированный порядок задаются используемым для перевода алгоритмом. Подробнее об этом будет изложено в гл. 3 и 9. Здесь возникает важная проблема: для каждой вершины п выбрать код С(п) так, чтобы код, приписываемый корню, оказался искомым кодом всего оператора. Вообще говоря, иужна какая-то интерпретация кода С{п), которой можно было бы единообразно пользоваться во всех ситуациях, где может встретиться вершина п. Для арифметических операторов присваивания нужная интерпретация получается весьма естественно; мы опишем ее в следующих абзацах. В общем случае при применении синтаксически управляемой трансляции интерпретация должна задаваться создателем компилятора. Эта задача может оказаться легкой или трудной, и в трудных случаях, возможно, придется учитывать структуру всего дерева. В качестве характерного примера опишем синтаксически управляемую трансляцию арифметических выражений. Заметим, что на рис. 1.3 есть три типа внутренних вершин, зависящих от того, каким из знаков =, + , « помечен средний потомок. Эти три типа вергиин показаны на рис. ] .4, где треугольниками изображены произвольные поддеревья (возможно, состоящие из единственной вершины). Для любого арифметического оператора присваивания, включающего только арифметические операции + и *, Рис. 1.4. Типы онутрениих вершин. дюжно построить дерево с одной вершиной (корнем) типа а и остальными внутренними вершинами только типов б и б. Код, соответствующий вершине п, будет иметь следующую интерпретацию: (1) Если п - вершина типа а, то С (п) будет кодом, который вычисляет значение выражения, соответствующего правому поддереву, и помещает его в ячейку, зарезервированную для идентификатора, которым помечен левый потомок. (2) Если п - веришиа типа б или в, то цепочка LOAD С (л) будет кодом, засылающим в сумматор значение выражения, соответствующего поддереву, над которым доминирует вершина я. Так, для дерева, изображенного на рис. 1.3, код LOAD С {п засылает в сумматор значение выражения <ид>2 -[- <ид>з, код LOAD С {п) засылает в сумматор значение" выражения (<ид>2-1-<ид>з) * <ид>4, а код С{п) засылает в сумматор значение последнего выражения и помещает его в ячейку, предназначенную для <ид>1. Теперь надо показать, как код С (п) строится из кодов потомков вершины п. В дальнейшем мы будем предполагать, что операторы языка ассемблера записываются в виде одной цепочки и отделяются друг от друга точкой с запятой или началом новой строки. Кроме того, мы будем предполагать, что каждой вершине п дерева приписано число 1(п), называемое ее уровнем, которое означает максимальную длину пути от этой вершины до листа. Таким образом, 1{п) = 0, если л - лист, а если л имеет потомков «1,..., fill, то /(я)=тал / (/г/) + L Уровни / (/2) можно вычислять снизу вверх одновременно с вычислением кодов С (/г). Уровни записываются для того, чтобы контролировать использование временных ячеек памяти. Две нужные нам величины нельзя засылать в одну и ту же ячейку памяти. На рис. 1.5 показаны уровни вершин дерева, изображенного на рис. 1.3. Теперь определим синтаксически управляемый алгоритм генерации кода, предназначенный для вычисления кодов С (п) всех Рис. 1.5. Дерево с уровнями. вершин дерева, состоящего из листьев, корня типа а и внутренних вершин типов б и е. Алгоритм 1.1. Синтаксически управляемая трансляция простых операторов присваивания. Вход. Помеченное упорядоченное дерево, представляющее оператор присваивания, включающий только арифметические операции + и . Предполагается, что уровни всех вершин уже вычислены. Выход. Код в языке ассемблера, вычисляющий этот оператор Присваивания. Метод. Делать шаги (1) и (2) для всех вершин уровня О, затем для вершин уровня 1 и т. д., пока не будут обработаны Все вершины дерева. (1) Пусть л -лист с меткой <ид>у. (i) Допустим, что элемент / таблицы идентификаторов является переменной. Тогда С (я) -имя этой переменной. 0 1 2 3 4 5 6 7 8 9 10 11 [12] 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 0.0022 |