Алгоритмические основы программной инженерии Конспекты

Глава 5. Компиляция и компоновка.

§1. Компиляция

Компилятор преобразует язык высокого уровня в объектный (машинный) код, а точнее в последовательность машинных кодов.

Процесс компиляции:

1. Лексический анализ (сканирование).

2. Преобразование кода высокого уровня в последовательность лексем с удалением комментариев и лишних незначащих пробелов.

Лексема — структурная единица языка, которая состоит из его элементарных символов и не содержит других его структурных единиц. К лексемам относятся идентификаторы, константы, ключевые слова, знаки операций и т. д. Состав возможных лексем определяется синтаксисом языка.

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

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

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

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

Пример.

Код типа лексемы Номер в таблице ид.

i 5

Каждой лексеме соответствует своя запись в таблице кодов лексем. Причем первой записи соответствует первая лексема.

Синтаксический анализ (парсинг)

На основании таблицы кодов лексем компилятор выделяет конструкции в соответствии с грамматикой языка. К конструкциям относятся операторы, блоки операторов, а также описание процедур и функций.

Состав таких конструкций языка зависит от языка и реализации компиляторов.

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

Семантический анализ

1. Дерево разбора интерпретируется относительно семантики (смысла исходного языка). В том числе выполняется привязка идентификаторов к их декларациям. В том числе переменных к типам.

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

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

3. Примеры синтаксически правильной (но неправильной по семантике) конструкции объявленной константе присваивается значение переменной.

Результатов этапов 1-3 является внутреннее представление программы, понятной компилятору, который имеет одну из следующих форм.

Связочные списочные структуры, представляющие собой синтаксические деревья:

— Многоадресный код с явно именуемым результатом (тетрады).

— Многоадресный код с неявно именуемым результатом (триады).

— Обратная постфиксная польская запись операций.

— Ассемблерный код (или машинные команды).

Отличие одной формы от другой заключается в способе присоединения операторов и операндов.