Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 18
Текст из файла (страница 18)
Мел!од. Делать шаги (1) и (2) для всех вершин уровня О, затем для вершин уровня 1 и т. д., пока не будут обработаны все вершины дерева. (1) Пусть и — лист с меткой <ид>;. (!) Допустим, что элемент 1 таблицы идентификаторов является переменной. Тогда С(п) — имя этой переменной. ГЛ. Ц ВБЕДЕ НИИ В КОМПИЛЯЦИЮ (В) Допустим, что элемент 1 таблицы идентификаторов является константой й. Тогда С(п) — цепочка = й. (2) Если п — лист с меткой =, е или +, то С(п) — пустая цепочка.
(В этом алгоритме нам не нужно или мы не хотим выдавать выход для листьев, помеченных =, » или -~.) (3) Если и — вершина типа а и ее прямые потомки — это вершины п„и, и п„то С(п) — цепочка 1.0АР С(п,); ВТОКЕ С(и,). (4) Если и — вершина типа б и ее прямые потомки — вершины и„п, и и„то С(п) — цепочка С(п,); ВТОЙЕ 51(п); 1.0АР С(п,); АРР 81(и). Эта последовательность команд занимает временную ячейку, именем которой служит знак $ вместе со следующим за ним уровнем вершины и. Непосредственно видно, что если перед этой последовательностью поставить 1.0АР, то значение, которое она в конце концов поместит в сумматор, будет суммой значений выражений поддеревьев, над которыми доминируют вер~нины и,ип,.
Сделаем два замечания относительно выбора временных имен. Во-первых, эти имена должны начинаться знаком А, так что их нельзя перепутать с именами идентификаторов в Фортране. Во-вторых, в силу способа выбора 1(п) можно утверждать, что С(п) не содержит временного имени 81, если 1 больше 1(п). В частности, С(п,) не содержит 81(п).
Можно, таким образом, гарантировать, что значение, помещенное в ячейку 81(и), будет еще находиться там в тот момент, когда его надо прибавить к содержимому сумматора. (5) Если п — вершина типа в, а все остальное, как в (4), то С (и) — цепочка С(и,); ВТОРОЕ $1(п); 1.0АР С(п,); МРУ 81(п) Этот код делает то„что надо, и в сумматоре появится нужный результат. Г~ Доказательство корректности алгоритма 1.1 оставляем в качестве упражнения. Оно проводится рекурсивио по уровню вершины. Пример 1.4. Применим алгоритм 1.1 к дереву, изображенному на рис.
1.3. То же дерево, на котором явно выписаны коды, сопоставляемые с каждой его вершиной, показано на рис. 1.6. С вершинами, помеченными <ид>„..., (ид>„связаны соответственно коды СОЗТ, РИСЕ, ТАХ и = 0.98, Теперь мы можем вычислить С(п,). Так как 1(и,) =1, то формула из правила (4) дает С(п,)=ТАХ; ВТОНЕ 51; 1.0АР РИСЕ; АРР 81 86 ! г ОБЗОР пРОцЕССА КОИПИЛЯЦИИ ЕОАО =О98 6ТОЯЕ чг2 ЕОАО ТАХ 5ТОЕЕ Э1 -айй ОРЕ ег2 О ТАХ ОВЕ $1 ШАО Рй1СЕ СОВТ ОО ~1 <»п>е в.вв + (кв~з ТАХ <ав >г Рй(СЕ Рггс, Цз. Дерево с геиерироваиимми кодами. Таким образом, код (.ОАР С(п,) вычисляет в сумматоре сумму значений переменных РИСЕ и ТАХ, хотя и делает это неуклюже. Неуклюжесть отчасти можно сгладить в процессе оптимизации кода; кроме того, можно разработать правила построения кода, принимающие во внимание особые случаи.
Далее можно вычислить С(п,) по правилу (5) и получить С(п,):=- = 0.98; ВТОЙЕ $2; 1.0АР С(п,); МРУ 52 Здесь С(п,) — цепочка, построенная для вершины и„а ч2 используется как имя временной ячейки, поскольку 1(п,) =2. Затем вычисляем С(и,) по правилу (3) и получаем С(и,) =- 1.0АР С(п,); ВТОКЕ СОЗТ Список команд языка ассемблера (вместо точки с запятой разделителем в нем служит новая строка), который является 87 гл. с. введение в компиляцию переводом нашего первоначального оператора СОВТ=(РЙ1СЕ+ ТАХ) и0.98, таков: (1.2.2) ЕОАР ЗТОЙЕ 1.0АР 8ТОЙЕ 1.0АР АРР МРУ БТОЙЕ = 0.98 $2 ТАХ $1 РЙ1СЕ $1 82 С0$Т Ъ2.
ОБЗОР ПРОЦЕССА КОМПИЛЯЦИИ меется, сохранять эффект, создаваемый во внешнем мире исходной программой. Преобразования можно производить в различные моменты процесса компиляции. Например, можно оперировать с самой входной программой, со структурами, порождаемыми на стадии синтаксического анализа, с кодом, порождаемым в качестве выхода фазы генерации кода.
Подробнее оптимизация кода будет обсуждаться в гл. 1!. Ос альную часть этого раздела мы посвятим следующим прет 1.2.21 образованиям, с помощью которых можно сделать код (1.2. ) более коротким: 1.2.6. Оптнмнзацня кода Во многих ситуациях желательно иметь компилятор, который создает эффективно работающие объектные программы. Термин оппси.иизас(ил кода обычно применяется к попыткам сделать объектные программы более „эффективными", т. е. быстрее работающими или более кохспактньсьссс. Для оптимизации кода существует широкий спсктГ возможностей. На одном его конце находится истинно оптим~ зссрующий алгоритм. В этом случае компилято пытается сост ~вить п еста се о нкции, оп еделяемои алгоритмом п Ог ото г записана иа исхо иом языке.
сли он догадается, что это за функция, то может попытаться заменить прежний алгоритм новым, более эффективным алгоритмом, вычисляющим ту же функцию, и уже для этого алгоритма генерировать машинный код. К сожалению, оптимизация этого типа чрезвычайно трудна. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой программы, эквивалентной данной.
На самом деле можно математически доказать, что существуют алгоритмы, вычисления которых можно ускорять во сколько угодно раз. Иначе говоря, существуют рекурсивные функции, обладающие тем свойством, что для любого алгоритма, вычисляющего такую функцию, найдется другой вычисляющий ее алгоритм, который для достаточно больших входов работает в произвольное число раз быстрее. Таким образом, термин оппсизсизас(сся совершенно неправильный — на практике мы должны довольствоваться рлссчсиенссезс кода. На разных стадиях процесса компиляции применяются различные приемы улучшения кода.
Вообще все, что мы можем делать, это выполнить над данной программой последовательность преобразований в надежде повысить ее эффективность. Эти преобразования должны, разу- зз (1) Если + — коммутативная операция, можно заменить последовательность команд вида 10АР а; АРР р последовательностью )ОАР р; АРР сс. Требуется, однако, чтобы в других местах программы не было перехода к оператору АРР (1. (2) Подобным же образом, если э — коммутативная операция, можно заменить 1.0АР сс; й(РУ () на 1.0АР (1; МРУ сс. (3) Последовательность операторов вида $ТОЙЕ я; 1.0АР сс м ожно удалить из программы при условии, что либо ячейка а Я н у е будет далее использоваться, либо перед использованием будет заполнена заново. (Чаще можно удалить один лишь оп- ератор 1.0АР сс; для этого только требуется, чтобы к оператору 10АР сс не было перехода в других местах программы.) (4) Последовательность 10АР а; 8ТОЙЕ (! можно удалить, если за ней следует другой оператор 1.ОА!9 и нет перехода к оператору ВТОЙЕ !), а последующие вхождения () будут заменены на сх вплоть до того места, где появляется другой оператор $ТОЙЕ (! (но исключая его).
1.0АР ЯТОЙЕ 1.0АР 8ТОЙЕ 1.0АР АРР МРУ БТОЙЕ = 0.98 $2 ТАХ $1 $1 РИСЕ $2 СОВТ (1.2.3) П имер 1.5. Эти четыре преобразования выбраны из-за их применимости к программе (1.2.2), Вообще таких преобразовани Р й много и надо пробовать применять их в разных комбинациях. Заметим, что в программе (1.2.2) правило (1) применимо к последовательности !.ОЛР РЙ!СЕ; АРР $1, и можно попробовать временно заменить ее на 1.0АР $1; АРР РЙ1СЕ, получив при этом код гл. г. Введение В кОмпиляцию гд.
овзог гшоцессл компиляции Теперь ясно, что в (1.2.3) можно удалить последовательность ВТОКЕ 51; ЕОАО 51 по правилу (3). Таким образом, мы получаем код') (1.2.4) 1.ОАО = 0.98 8ТОКЕ 82 ЕОАО ТАХ А1)Р РК1СЕ МРЪ' СОБТ ЗТОК Е СОЗТ Теперь к последовательности ).ОАО = 0.98; 5ТОКЕ $2 можно применить правило (4). Эти две команды удаляются и $2 в команде МР"г' 52 заменяется на =- 0.98. Окончательный код таков: (1.2.5) ЕОАР ТАХ АОО РК!СЕ МР г' = 0.98 БТОКЕ СОЗТ Код (1.2.5) — самый короткий, какой можно получить с по. мощью наших четырех и любых других разумных преобразований. Д 1.2.7. Анализ и исправление ошибок До сих пор мы предполагали, что входом компилятора служит правильно построенная программа и что каждую фазу компиляции можно осмысленно довести до конца.
На практике однако, это во многих случаях не так. Программирование в большой степени является искусством, и поистине неограниченны возможности для проникновения в большинство программ разного рода ошибок. Даже если мы чувствуем, что понимаем п о- Р блему, для решения которой пишем программу, и даже если мы выбрали подходящий алгоритм, часто нельзя быть уверенным в том, что написанная программа правильно реализует этот алгоритм. Компилятор имеет возможность обнаруживать ошибки в программе по крайней мере иа трех этапах компиляции: во время лексического анализа, синтаксического анализа, при генерации кода.
Если встретилась ошибка, то компилятору трудно по неправильной программе решить, что имел в виду ее автор. Эта задача граничит с приложениями искусственного интеллекта. Но в некоторых случаях легко сделать подходящее йредположение, и л ) Аналогнчного упрощения можно было бы достичь, прнменнн сразу пра. вяло (4). На мы стараемся дать примеры того, как использовать разные типы преобразованна, 90 Например, если исходный оператор выглядит как А= Ве2С, то вполне правдоподобно, что подразумевалось А=Ве2нС. Вообще в тех случаях, когда процесс разбора доходит до того места во входной цепочке, где он не может дальше правильно продолжаться, некоторые компиляторы стараются произвести „минимальное" изменение во входной цепочке, чтобы продолжить разбор. Перечислим несколько возможных изменений: (1) Замена одного знака, Например, если лексический анализатор выдает синтаксическому анализатору „идентификатор" 1)к)ТЕЗЕК в неподходящем для появления идентификатора месте программы, то компилятор может догадаться, что подразумевалось ключевое слово 15)ТЕЙЕК, (2) Вставка одной лексемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
