Эта фаза процесса компиляции называется лексическим анализом и рассматривается в гл. 3. Остальная часть анализа, т. е. построение дерева, называется синтаксическим анализом, или разбором.

Рис. 1.10

Для проверки определенных требований языков компилятор строит таблицы. Например, в большинстве языков

х:=у

допустимо только в том случае, если объявляется, что -х и у имеют согласованные типы. Из такого объявления, как

int X

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

х:=у

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

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

(>1 + В)Х(С + £)).

Однако во время компиляции может выделяться не весь объем памяти. Рассмотрим описание.

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

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

Запоминающее устройство, как правило, организуется по принципу магазина (первым считывается последнее записанное слово) и носит название стека (см. гл. 9).

Генерирование кода описывается в гл. 10 и 11. В гл. 10 мы рассмотрим получение не зависящего от машины промежуточного кода, а в гл. 11 - способы его отображения на реальной машине. Введение промежуточного языка связано с попыткой разделить зависимые и не Зависимые от машины аспекты генерирования кода. Промежуточный код может состоять из операторов вида

ADD address t, address 2, address 3

что значит «сложить величины, записанные по адресам 1 и 2, и поместить результат по адресу «?». Промежуточный язык не является, по всей вероятности, не зависимым от исходного языка (хотя были предприняты попытки создания универсальнтх промежуточнтх языков, см. [48]). Он отражает основные действия исходного языка и имеет достаточно высокий уровень, чтобы его можно было эффективно реализовать на типичной ЭВМ.

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

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

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

1.3 ПРОЕКТИРОВАНИЕ КОМПИЛЯТОРА

Как уже упоминалось выше, компилятор в некотором смысле определяется тем языком высокого уровня, который он принимает, и машинным кодом (в более общем смысле.- другим языком), который он создает. Из этого, однако, не следует, что, например, все компиляторы Фортрана для машин серии PDP-11 должны быть одинаковыми. Конечно, вряд ли можно ожидать, что два компилятора, написанные разными разработчиками (или группами разработчиков), окажутся одинаковыми, хотя они и должны выдавать идентичный, или эквивалентный, объектный код из одного и того же исходного кода. Два компилятора, реализующие один и тот же язык на одной и той же машине, могут отличаться хотя бы потому, что разработчики преследовали различные цели при их построении. Этими целями могут быть:

получение эффективного объектного кода;

разработка небольших объектных программ;

минимизация времени компиляции программ;

разработка компилятора как можно меньшего размера;

создание компилятора, обладающего широкими возможностями обнаружения и исправления ошибок;

обеспечение надежности компилятора.

К сожалению, эти цели в какой-то степени противоречивы. Почти наверняка компилятор, который должен выдавать эффективный код, будет немного (и даже намного) медленней. Для осуществления некоторых стандартных методов оптимизации [20], таких, как устранение избыточности кода, исключение последовательностей кода из циклов и т. д., может потребоваться очень много времени. Компилятор, в котором выполняются сложные программы оптимизации, является также большим по объему. Размер компилятора может влиять и на время, необходимое ему для компиляции программы. В процессе работы часто невозможно оптимизировать время и объем памяти одновременно. Обычно одно осуществляется за счет другого. Разработчик компилятора должен заранее решить, что именно он предпочитает оптимизировать, а затем уже приступить к оптимизации, полностью отдавая себе отчет в том, к чему это может привести. Кроме того, у него может возникнуть желание потратить как можно меньше времени на написание компилятора, что само по себе является препятствием к включению некоторых сложных методов оптимизации.

Программисты ожидают от компилятора вспомогательного сообщения об ошибке, когда они представляют недопустимую программу. Их не удовлетворит формальный ответ, что программа «написана не на том языке, для трансляции которого предназначен компилятор». Они также предполагают, что компилятор, обнаружив ошибку, не перестанет производить компиляцию программы, а будет продолжать анализировать ее в поисках дальнейших ошибок. Компиляторы крайне отличаются по своим возможностям обнаружения и исправления ошибок, хотя это их свойство не противоречит перечисленным выше целям проектирования. Конечно, компилятор, выдающий полезные сообщения и элегантно выходящий из ситуации ошибки, имеет как следствие несколько больший размер, но это вполне компенсируется повышением эффективности работы программиста. В результате для компиляции правильных программ такому компилятору не потребуется больше времени. Однако проблема исправления ошибок (особенно синтаксических) не проста и полностью пока еще не решена. Более подробно эта проблема рассматривается в гл. 12.

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

Нередко фирмы-изготовители предлагают для какого-либо языка, применимого в серии машин, не один компилятор, а несколько. Так, компанией «Инглиш электрик» б1ли предложены для ЭВМ KDF9 компиляторы Whetstone и Kidsgrove. Компилятор Whetstone является быстрым в компиляции и медленным в прогоне, a Kidsgrove - медленным в компиляции, но выдает очень эффективный машинный код. Идея заключалась в том, чтобы пользователи разрабатывали свои программы с помощью компилятора Whetstone, а затем для работы перекомпилировали их с