Структура компилятора

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

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

Синтез строит требуемую целевую программу на основе промежуточного представления и информации из таблицы символов. Анализ часто называют на­чальной стадией, а синтез — заключительной.

Если рассмотреть процесс компиляции более детально, можно увидеть, что он представляет собой последовательность фаз, каждая из которых преобразу­ет одно из представлений исходной программы в другое. Типичное разложение компилятора на фазы приведено на рис. 1.6. На практике некоторые фазы могут объединяться, а межфазное промежуточное представление может не строиться явно. Таблица символов, в которой хранится информация обо всей исходной про­грамме, используется всеми фазами компилятора.

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

1. Лексический анализ

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

{имя_токенау значение атрибута)

Он передается последующей фазе, синтаксическому анализу. Первый компонент токена, имя_токена, представляет собой абстрактный символ, использующий­ся во время синтаксического анализа, а второй компонент, значение атрибута, указывает на запись в таблице символов, соответствующую данному токену. Ин­формация из записи в таблице символов необходима для семантического анализа и генерации кода.

Предположим, например, что исходная программа содержит инструкцию при­сваивания

position = initial + rate * 60                                       (1.1)

Символы в этом присваивании могут быть сгруппированы в следующие лексемы и отображены в следующие токены, передаваемые синтаксическому анализатору.

1. position представляет собой лексему, которая может отображаться в токен (id, 1), где id — абстрактный символ, обозначающий идентификатор, а 1 указывает запись в таблице символов для position. Запись табли­цы символов для некоторого идентификатора хранит информацию о нем, такую как его имя и тип.

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

3. initial представляет собой лексему, которая отображается в токен (id, 2), где 2 указывает на запись в таблице символов для initial.

4. + является лексемой, отображаемой в токен (+).

5. rate — лексема, отображаемая в токен (Id, 3), где 3 указывает на запись в таблице символов для rate.

6. * — лексема, отображаемая в токен (*).

7. 60 — лексема, отображаемая в токен (60)

Пробелы, разделяющие лексемы, лексическим анализатором отбрасываются.

На рис. 1.7 показано представление инструкции присваивания (1.1) после лек­сического анализа в виде последовательности токенов

id 1 (=) id2 (+) id3 (*) (60)                               (1.2.)

При этом представлении имена токенов =, + и * представляют собой абстрактные символы для операторов присваивания, сложения и умножения соответственно.

Читайте в следующей статье – Синтаксический и Семантический анализ.