Компилятор

Компилятор ( англ. Compiler от англ. to compile собирать в целое) - компьютерная программа (или набор к. программ), которая превращает ( компилирует ) программный код, написанный известной языке программирования (язык источника, англ. source language ), на семантически эквивалентный код на другом языке программирования (речь цели, англ. target language ), который, как правило, необходим для выполнения программы машиной, например, компьютером.

Коротко компилятор можно определить, как приложение или техническое средство, выполняющее компиляцию.

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

Для выполнения программа не всегда должна быть переведена компилятором, существует также другой принцип: пошаговое выполнение программных инструкций интерпретатором.

История развития компилятора

Первые компиляторы появились в начале 50-х годов. С тех пор теория и техника построения компиляторов существенно развились. Тогда же велись интенсивные научные исследования и образовывались группы и комитеты по разработке универсальной промежуточного языка. Однако их деятельность великого "индустриального" успеха не имела.

Теоретический вступление

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

1. Анализ (parsing) - разбиение исходной программы на составные части и создание промежуточного представления
2. Синтез - построение целевой программы из промежуточного представления

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

Фазы компиляции

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

1. Лексический анализатор
2. Синтаксический анализатор
3. Семантический анализатор
4. Генератор промежуточного кода
5. Оптимизатор
6. Генератор целевого кода

Анализ (разбор)

Лексический разбор

Лексический разбор выделяют для упрощения построения компилятора. Это линейное сканирование входящей программы, при котором символы группируются в токены - последовательности символов, имеющих определенное совокупное значение. Следующая строка языке Паскаль

len: = 3.14 * r;  

состоит из следующих токенов

1. Идентификатор len
2. Символ присвоения: =
3. Числовая стала 3.14
4. Знак умножения *
5. Идентификатор r
6. Разделитель операторов;

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

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

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

Синтаксис обычно определяется контекстно-независимой грамматикой, состоящий из символов - терминалов и нетерминалов, стартового символа принадлежащего множеству нетерминалов, и контесктно-независимых продукций.

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

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

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

expression: identifier expression: number expression: expression + expression  

Первая строка означает что любой идентификатор является выражением. Вторая строка означает что любое число является выражением. Третья строка означает что любая последовательность из двух выражений разделенных знаком сложения тоже является выражением.

В этой грамматике символами являются expression, number, identifier и +. Expression является стартовым символом и нетерминалом, остальные символов является терминалами.

Классификация компиляторов

Известные компиляторы

• GCC

Генераторы анализаторов

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

В Unix распространены генератор лексических анализаторов (F) Lex, и генераторы синтаксических анализаторов Bison и Yacc.