Главная Промышленная автоматика.

(ii) Лопустим, что элемент / таблицы идентификаторов является константой k. Тогда С {п) - цепочка k.

(2) Если п - ЛИСТ с меткой » или то С (п) - пустая цепочка. (В этом алгоритме нам не нужно или мы не хотим выдавать выход для листьев, помеченных -, * или +)

(3) Если п - вершина типа а и ее прямые потомки - это вершины Пу, /jjj и Лз, то С {а) - цепочка LOAD С {п ; STORE С(п.

(4) Если п-вершина типа б и ее прямые потомки - вершины Пс, и Пз, то С(л) -цепочка С(п) ; STORE $/(0 ; LOAD

C(/ii) ; ADD %l(n).

Эта последовательность команд занимает временную ячейку, именем которой служит знак вместе со следующим за ним уровнем вершины п. Непосредственно видно, что если перед этой последовательностью поставить LOAD, то значение, которое она в конце концов поместит в сумматор, будет суммой значений выражений поддеревьев, над которыми доминируют вершины

и Пз.

Сделаем два замечания относительно выбора временных имен. Во-первых, эти имена должны начинаться знаком $, так что их нельзя перепутать с именами идентификаторов в Фортране. Во-вторых, в силу способа выбора / (п) можно утверждать, что С(п) не содержит временного имени г, если / больше 1(п). В частности, С (п не содержит :j/(/7). Можно, таким образом, гарантировать, что значение, помещенное в ячейку %1 (п), 6yji еще находиться там в тот момент, когда его надо прибавить к содержимому сумматора.

(5) Если п - вершина типа в, а все остальное, как в (4), то С (/:) -цепочка

С(п,) ; STORE $/(п) ; LOAD С(/!,) ; MPY %1{п)

Этот код делает то, что надо, и в сумматоре появится Нужный результат. П

Доказательство корректности алгоритма 1.1 оставляем в качестве упражнения. Оно проводится рекурсивно по уровню вершины.

Пример 1.4. Применим алгоритм 1.1 к дереву, изображенному на рис. 1.3. То же дерево, на котором явно выписаны коды, сопоставляемые с каждой его вершиной, показано на рис. 1.6. С вершинами, помеченными <ид>, <ид>4, связаны соответственно коды COST, PRICE, TAX и =0.98. Теперь мы можем вычислить С(п). Так как 1(п) = \, то формула из правила (4) дает

С (л,) = TAX; STORE $1 ; LOAD PRICE; ADD $1

LOAD STORE LOAD STORE LOAD ADD MPY

=U98 $2 TAX $1

PRICE $1 $2

STORE COST

<ИД>1

COST


STORE

LOAD

STORE

LOAD

PRICE

TAX STORE $1 LOAD PRICE ADD $1

<»Д>2

PRICE

Рис* 1.6. Дерево с генерированными кодами.

Таким образом, код LOAD С {п} вычисляет в сумматоре сумму значений переменных PRICE и TAX, хотя и делает это неуклюже. Неуклюжесть отчасти можно сгладить в процессе оптимизации кода; кроме того, можно разработать правила построения кода, принимающие во внимание особые случаи.

Далее можно вычислить Cin) по правилу (5) и получить С (ГЦ) - = 0.98; STORE $2; LOAD С (/г,) ; MPY $2

Здесь С{Пу) - цепочка, построенная для вершины п, а $2 используется как имя временной ячейки, поскольку 1(п) = 2. Затем вычисляем С {Пз) по правилу (3) и получаем С{п) = LOAD С{п) ; STORE COST

Список команд языка ассемблера (вместо точки с запятой разделителем в нем служит новая строка), который является



переводом нашего первоначального оператора COST - (PRICE+ TAX) 0.98, таков:

(1.2.2)

LOAD

= 0.98

STORE

LOAD

STORE

LOAD

PRICE

STORE

COST

1.2.6. Оптимизация кода

Во многих ситуациях желательно иметь компилятор, который создает эффективно работающие объектные программы. Термин оптимизация кода обычно применяется к попыткам сделать объектные программы более „эффективными", т. е. быстрее работающими или более компактными.

Для оптимизации кода существует широкий спсктг возможностей. На одном его конце находится истинно оптим пирующий алгоритм. В этом случае компилятор пытается сост .вить представление о функции, определяемой алгоритмом п >1>гряммя кп-торого записана на исходном языке, ьсли ондогадается, что это за функция, то может попытаться заменить прежний алгоритм новым, более эффективным алгоритмом, вычисляющим ту же функцию, и уже для этого алгоритма генерировать машинный код.

К сожалению, оптимизация этого типа чрезвычайно трудна. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой программы, эквивалентной данной. На самом деле можно математически доказать, что существуют алгоритмы, вычисления которых можно ускорять во сколько угодно раз. Иначе говоря, существуют рекурсивные функции, обладающие тем свойством, что для любого алгоритма, вычисляющего такую функцию, найдется другой вычисляющий ее алгоритм, который для достаточно больших входов работает в произвольное число раз быстрее.

Таким образом, термин оптимизация совершенно неправильный-на практике мы должны довольствоваться улучшением кода. На разных стадиях процесса компиляции применяются различные приемы улучшения кода.

Вообще все, что мы можем делать, это выполнить над данной программой последовательность преобразований в надежде повысить ее эффективность. Эти преобразования должны, разу-

меется, сохранять эффект, создаваемый во внешнем мире исходной программой. Преобразования можно производить в различные моменты процесса компиляции. Например, можно оперировать с самой входной программой, со структурами, порождаемыми на стадии синтаксического анализа, с кодом, порождаемым в качестве выхода фазы генерации кода. Подробнее оптимизация кода будет обсуждаться в гл. П.

Остальную часть этого раздела мы посвятим следующим преобразованиям, с помощью которых можно сделать код (1.2.2) более коротким:

(1) Если -f -коммутативная операция, можно заменить последовательность команд вида LOAD а; ADD р последовательностью LOAD Р; ADD а. Требуется, однако, чтобы в других местах программы не было перехода к оператору ADD р.

(2) Подобным же образом, если » -коммутативная операция, можно заменить LOAD а; MI>Y р на LOAD р; MPY а.

(3) Последовательность операторов вида STORE а ; LOAD а можно удалить из программы при условии, что либо ячейка а не будет далее использоваться, либо перед использованием а будет заполнена заново. (Чаще можно удалить один лишь оператор LOAD а; для этого только требуется, чтобы к оператору LOAD а не было перехода в других местах программы.)

(4) Последовательность .LOAD а; STORE р можно удалить, если за ней следует другой оператор LOAD и нет перехода к оператору STORE р, а последующие вхождения р будут заменены на а вплоть до того места, где появляется другой оператор STORE р (но исключая его).

Пример 1.5. Эти четыре преобразования выбраны из-за их применимости к программе (1.2.2). Вообще таких преобразований много и надо пробовать применять их в разных комбинациях. Заметим, что в программе (1.2.2) правило (1) применимо к последовательности LOAD PRICE; ADD $1, и можно попробовать временно заменить ее на LOAD $1; ADD PRICE, получив при этом код

(1.2.3)

LOAD

STORE

LOAD

STORE

LOAD

STORE

= 0.98 $2

$1 SI

PRICE

COST



Теперь ясно, что в (1.2.3) можно удалить последовательность STORE $1; LOAD $1 по правилу (3). Таким образом, мы получаем код)

(1.2.4) LOAD -0.98

STORE $2 LOAD TAX ADD PRICE MPY COST STORE COST

Теперь к последовательности LOAD - 0.98; STORE $2 можно применить правило (4). Эти две команды удаляются и $2 в команде MPY $2 заменяется на = 0.98. Окончательный код таков:

(1.2.5) LOAD TAX

ADD PRICE MPY =0.98 STORE COST

Код (1.2.5)-самый короткий, какой можно получить с помощью наших четырех и любых других разумных преобразований. □

1.2.7. Анализ и исправление ошибок

До сих пор мы предполагали, что входом компилятора служит правильно построенная программа и что каждую фазу компиляции можно осмысленно довести до конца. На практике, однако, это во многих случаях не так. Программирование в большой степени является искусством, и поистине неограниченны возможности для проникновения в большинство программ разного рода ошибок. Даже если мы чувствуем, что понимаем проблему, для решения которой пишем программу, и даже если мы выбрали подходящий алгоритм, часто нельзя быть уверенным в том, что написанная программа правильно реализует этот алгоритм.

Компилятор имеет возможность обнаруживать ошибки в программе по крайней мере на трех этапах компиляции: во время лексического анализа, синтаксического анализа, при генерации кода. Если встретилась ошибка, то компилятору трудно по неправильной программе решить, что имел в виду ее автор. Эта задача граничит с приложениями искусственного интеллекта. Но в некоторых случаях легко сделать подходящее предположение.

) Аналогичного упрощения можно было бы достичь, применяя сразу правило (4). Но стараемся дать примеры того, как использовать разные типы преобразовании.

Например, если исходный оператор выглядит как А = В*2С, то вполне правдоподобно, что подразумевалось А -В х-2» С.

Вообще в тех случаях, когда процесс разбора доходит до того места во вхо.ной цепочке, где он не может дальше правильно продолжаться, некоторые компиляторы стараются произвести „минимальное" изменение во входной цепочке, чтобы продолжить разбор. Перечислим несколько возможных изменений:

(1) Замена одного знака. Например, если лексический анализатор выдает синтаксическому анализатору „идентификатор" INTEJER в неподходящем для появления идентификатора месте программы, то компилятор может догадаться, что подразумевалось ключевое слово INTEGER.

(2) Вставка одной лексемы. Например, компилятор может заменить 2С на 2»С (2 + С тоже годится, но в данном случае мы „знаем", что 2*С правдоподобнее).

(3) Устранение одной лексемы. Например, в таком операторе Фортрана, как DO 10 1-1, 20, часто неправильно ставят запятую после 10.

(4) Простая перестановка лексем. Например, вместо INTEGER I может быть неправильно написано t INTEGER.

Во многих языках программирования операторы легко опознаются. Если разбор конкретного неправильно построенного оператора становится безнадежным-даже после того, как произведены изменения вроде описанных выше, часто можно полностью игнорировать этот неправильный оператор и продолжить ра.збор, как будто его и не было.

Вообще, результатов математического характера об алгоритмах, обнаруживающих ошибки, и алгоритмах, выдающих „хорошую* диагностику, мало. В гл. 4 и 5 мы обсудим несколько алгоритмов синтаксического анализа: LL-алгоритм, LR-алгоритм и алгоритм Эрли, обладающие тем свойством, что как только выясняется, что просмотренную часть входной цепочки нельзя продолжить до правильной цепочки, алгоритм объявляет об этом. Это свойство полезно для обнаружения и анализа ошибок, однако далее мы будем рассматривать и такие алгоритмы, которые этим свойством не обладают.

1.2.8. Резюме

На рис. 1.7 приведена наша принципиальная модель компилятора. Здесь фаза онтими.зации следует за фазой генерации кода, но, как мы уже отмечали, разнообразные попытки оптимизации кода могут делаться по ходу всего процесса компиляции.





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.0018