Глава 8. Основные фазы компиляции

Транслятор – это программа перевода текста (программы) с одного языка (исходного) на другой (объектный). Трансляторы различают компилирующего и интерпретирующего типов. Компилятор переводит всю программу, затем её выполняет. Интерпретатор переводит по отдельным операторам программу и сразу каждый из операторов исполняет.

Компилятор должен выполнить анализ исходной программы, а затем синтез объектной. Сначала исходная программа разлагается на составные части; затем из них строятся фрагменты эквивалентной объектной программы. Для этого на этапе анализа компилятор использует и строит целый ряд таблиц, структур данных, которые затем используются как при анализе, так и синтезе. Анализ процессов компиляции позволяет выделить 7 различных логических задач – фаз компиляции. В практических реализациях грани между этими фазами размыты, часть из них может отсутствовать, совмещаться одна с другой.

В этой главе мы лишь кратко остановимся на основных фазах и базах данных компилятора.

1). Лексический анализ – распознавание базовых элементов языка, перевод исходной программы в таблицу стандартных символов (лексем), которые в отличие от элементов исходной программы имеют постоянную длину, что делает последующие фазы компиляции более простыми. Лексический анализатор или сканер группирует определенные терминальные символы исходной программы в единые синтаксические объекты – лексемы. Какие объекты считать лексемами, зависит от определения языка программирования. Лексема – это пара вида: тип лексемы, некоторые данные. Первой компонентой пары является синтаксическая категория, такая как “константа”, “идентификатор” или “терминал” (ключевое слово языка или специальный символ: знак операции, разделитель и т.п.), а вторая – указатель: в ней указывается номер элемента таблицы, хранящий подробную информацию об этой конкретной лексеме. Входной информацией сканера является исходная программа и таблица терминалов языка, выходом – цепочка лексем, таблицы идентификаторов и констант.

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

3). Семантический анализ – определение смыслового значения базовых синтаксических конструкций. Этот процесс синтаксически управляем. То есть фазы 2 и 3 тесно связаны (объединены).

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

Когда встречается оператор присваивания вида

<переменная>:=<выражение>

семантическая программа проверяет переменную и выражение на соответствие типов, а затем заносит информацию об инструкции присваивания во внутреннюю форму программы (ВФП).

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

4). Машинно–независимая оптимизация ВФП – вынесение общих подвыражений, вычисления над константами, оптимизация переходов в сложных условных операторах, вынесение инвариантных вычислений за цикл и т.п.

5). Распределение памяти – модификация таблиц идентификаторов и констант. Определение адресов идентификаторов и констант. Вставки в ВФП, для генерации и распределения динамической памяти. Выделение временной памяти, выравнивание и т.п.

6). Генерация кода и машинно–зависимая оптимизация. С каждой операцией из ВФП связана кодовая продукция, которая и выносится в код сборки. Оптимизация же проводится с целью более эффективного использования регистров ЭВМ, удаление “лишних” команд, связанных с сохранением и загрузкой промежуточных данных на этапе вычислений и т.п.

7). Сборка и выдача – разрешение символических адресов (трансляция с языка ассемблера) и формирование объектного модуля (машинного кода и информации для компоновщика и загрузчика).

Сразу же отметим, что фазы 1 – 4 машинно–независимы и определяются только исходным языком, а фазы 5 – 7 машинно–зависимы и не зависят от исходного языка.

а). Исходная программа – это программа на исходном языке программирования, например, С или Паскаль.

б). Таблица терминальных символов – постоянная таблица, в которой записаны все ключевые слова (IF, THEN, ELSE, WHILE и т.п.) и специальные символы языка (пробел, ‘,’, ‘;’, ‘*’, ‘+’ и т.п.) в символьной форме. На них ссылаются стандартные символы – лексемы программы.

в) Таблица (строка) лексем (стандартных символов) – состоит из полного или частичного списка лексических единиц, расположенных в том порядке, в каком они встречаются в программе (например, TRM(1¸n), IDN(1¸m), CON(1¸k)). Они создаются при лексическом анализе и используются на этапах синтаксического и семантического анализа.

г). Таблица идентификаторов – содержит информацию обо всех переменных программы, в том числе и временных переменных, хранящих промежуточные результаты вычислений, и информацию, необходимую для ссылок (адресации) и отведения памяти. Создается на фазе лексического анализа (1) (на элементы таблицы идентификаторов ссылаются лексемы), модифицируется на фазах семантического анализа (3) и распределения памяти (5), используется также на фазах генерации кода (6), сборки и выдачи (7).

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

е). Правила грамматики (продукции) – могут представляться и неявно в самом теле программы синтаксического анализа. Они обеспечивают, в соответствии с заданным алгоритмом, автоматический анализ синтаксиса исходной программы. Зачастую, в грамматике содержится информация и о семантических действиях (транслирующие и атрибутные грамматики), которые надо предпринимать в процессе обнаружения тех или иных языковых конструкций. ж). Внутренняя форма программы (ВФП) – форма обеспечивающая однопроходную генерацию кодов (в компиляторе) или интерпретацию (выполнение интерпретатором). Пример ВФП – ПОЛИЗ (польская инверсная запись) – где арифметические выражения, да и вся программа представляется не в традиционной инфиксной форме, а в постфиксной или суффиксной бесскобочной формах. В ПОЛИЗе операции располагаются за операндами, над которыми они выполняются в порядке их выполнения.

Например, оператор

a:=b+c*d/(b–c)–10; в ПОЛИЗе примет вид abcd*bc–/+10–:=

Еще чаще в компиляторах в качестве ВФП используется матрица тетрад, где выражение представляется в форме тетрад (оператор, операнд, операнд, результат) в порядке их выполнения. Например, присваивание a:=b+c*d будет представлено как

где M1 и M2 временные переменные, образованные компилятором. (При работе компилятора, операндами в приведенных примерах будут не сами символические имена и значения, а лексемы – ссылки на таблицы, где они были описаны.) ВФП создается на фазе семантического анализа, модифицируется (оптимизируется) на фазе машинно–независимой оптимизации и используется при генерации кода.

з). Кодовые продукции – постоянная таблица, имеющая отдельные элементы, определяющие код для каждой возможной операции ПОЛИЗа или матрицы тетрад (т.е. ВФП). Например, тетрада +, операнд_1, операнд_2, результат или более конкретно +, A, B, M10 может быть представлена следующей кодовой продукцией:

MOV ax, A

ADD ax, B

MOV ax, M10

а тетрада :=, операнд_1,, результат (:=, M20,,ABC) – продукцией

MOV ax, M20

MOV ABC, ax

Таблица кодовых продукций используется на фазе генерации кода.

и). Код сборки – версия программы на языке сборки (аналог языка ассемблера). Создается на фазе генерации кода и используется фазой сборки.

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

Более подробно описание каждой фазы компиляции рассмотрено, например в [7,11].

Заключение

Завершая курс «Основы теории формальных грамматик» следует отметить, что его рамки не позволили рассмотреть и малой толики того объема знаний, который накоплен в данной области. Здесь приведены лишь наиболее важные фрагменты стройной теории компиляции. Заинтересованный читатель откроет для себя массу полезного, если познакомится с работами, приведенными в списке литературы. Обсуждаемые там методы и алгоритмы играют большую роль не только в компиляции, - это часть общей культуры программирования и искусственного интеллекта.