Принципы построения трансляторов

Трансляторы, компоновщики и загрузчики.

Лекция 14

В воображении студентов, впервые приступивших к изучению курса программирования, часто возникает ореол таинственности вокруг компилятора программ. ЭВМ считывает текст программы, написанный на каком-либо языке, и эта программа неким магическим образом выполняется и выдает результаты. Чтобы рассеять заблуждения, достаточно понять, что ЭВМ способна выполнять только очень простые действия, предписанные машинными командами, а назначение компилятора состоит в преобразовании исходного текста программы в формат машинных команд. Компилятор является программой, которая способна воспринимать строку символов определенного вида (т.е. текст программы на исходном языке) и выдавать другую строку символов (программу в машинных кодах).

Например, предложение вида

X:=Y+Z;

компилятор может преобразовать в следующую последовательность машинных кодов:

A1 52 00 03 06 54 00 A3 50 00

mov ax,[0052h] add ax,[0054h] mov [0050h],ax

где [0050h], [0052h], [0054h] – адреса переменных X,Y,Z

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

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

<ИМЯ>:= <ВЫРАЖЕНИЕ>;

Описание смысла предложений, то есть значений слов и их внутренних связей, составляет семантику языка. Правильные с точки зрения синтаксиса предложения могут содержать семантические ошибки. Например, если MyStr – строка символов длиной 5 байт,

var MyStr: string[5];

то синтаксически правильное выражение

MyStr:= ‘ABCDEF’;

является семантически неверным, так как длина выражения превышает длину переменной.

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

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

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

Вторая фаза компиляции – это синтаксический анализ, называемый также грамматическим разбором, на нем проверяется правильность следования операторов. Например, для предложения

IF <ВЫРАЖЕНИЕ> THEN <ПРЕДЛОЖЕНИЕ>;

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

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

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

Процессы лексического и синтаксического анализа достаточно хорошо алгоритмизированы. Однако процесс генерации объектного кода автоматизирован не до конца, поэтому создание хорошего генератора объектных программ до сих пор является в некотором роде искусством.

Хотя в состав любого компилятора входят три описанных выше компонента, их взаимодействие может осуществляться разнообразными способами. Наиболее распространенными вариантами являются: одно-, двух- и трехпроходная структура компиляторов (рис.1–3).

Рис.1. Трехпроходный компилятор. Компилятор фактически состоит из трех программ. Лексический анализатор считывает текст программы и представляет его в форме файла лексем. Синтаксический анализатор читает этот файл и выдает представление программы в виде файла с описанием синтаксического дерева. Наконец, этот файл считывается генератором кода, который создает объектный код программы. Компилятор такого вида назван трехпроходным, так как программа с диска считывается трижды. Недостатки: медленно работает (из-за обращений к диску). Преимущества: нетребователен к объему памяти, гибкость (при модификации компилятора достаточно изменить одну из программ), легко можно добавить программу для оптимизации кодов, вызывая ее между синтаксическим анализатором и генератором кодов.

Рис.2. Однопроходный компилятор. Лексический анализатор и генератор кода являются подпрограммами, которые по необходимости вызывает синтаксический анализатор, который выступает в роли основной управляющей программы. Синтаксический анализатор постоянно обращается к лексическому анализатору, получая от него лексему за лексемой, пока не построит новое предложение, после чего он обращается к генератору кода, который создает объектный код для этого фрагмента программы. Достоинства: быстрота. Недостатки: создаваемый код не оптимален, при загрузке компилятор требует большого объема памяти.

Рис.3. Двухпроходный компилятор – собрал лучшее от трёх- и однопроходной моделей. Синтаксический анализатор, вызывая лексический анализатор, получает лексему за лексемой и строит файл с синтаксическим деревом программы. Генератор кода считывает этот файл и создает объектный код программы. Достоинства: быстрота, возможность добавить блок оптимизации.

Существует ряд компиляторов, которые выполняются на одной машине, а генерируют объектный код для другой ЭВМ. Эти компиляторы получили название «кроссовых» или кросс-компиляторов (от англ. cross – «перекрестный»). Кросс-компиляторы часто используют для создания программ для небольших специализированных ЭВМ, управляющих работой технологического оборудования и т.п.

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

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