Компилятор

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

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

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

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



1. История развития

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

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

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

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

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


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

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

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

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

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

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

 len: = 3.14 * r; 

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

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

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

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

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

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

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

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

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

 expression: identifier expression: number expression: expression + expression 

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

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


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

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

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

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

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