Главная arrow Средства разработки arrow Как работает компилятор?
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Как работает компилятор? Печать
Обзор процесса компиляции

 

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

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

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


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

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

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

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

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

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

Структуры данных транслятора

 

Строки

Строка - последовательность символов, принадлежащих конечному множеству, или алфавиту. Например, если А – множество {0,1}, то последовательность 01011101101110 есть строка над А. Для отделения строк друг от друга применяются либо спецсимволы, либо сменяется алфавит.

Свойства строк:

  1. длина строк переменна, хотя алфавит фиксирован;
  2. обращение к элементам строки происходит с какого-либо конца (т.е. важна упорядоченность последовательности, а не ее индексация);
  3. если строка представляет конечное предложение некоторого языка, то существуют ограничения относительно того,  какие символы могут встречаться вместе, что задается синтаксисом языка.

Графы

Ориентированный граф - формально определяется как G=(X,U) ,где X - множество элементов, называемых вершинами; U - множество дуг или ребер графа: U->X*X.

Если a и b вершины, а (a,b) - ребро, то говорят, что ребро направленно из a в b. Неориентированный граф - в котором отсутствуют ориентированные ребра: (a,b)->U, то и (b,a)->U. Если в дополнение к графу задана функция w:U->R, то это взвешенный граф. Функция w определяет длину или вес каждого ребра в графе.

Примеры:

  1. карта дорог - взвешенный граф;
  2. карта дорог с односторонним движением - ориентированный граф.

Граф называется регулярным, если из каждой вершины выходит и в каждую вершину входит одно и то же число ребер.

Деревья

Корневое дерево (оpиентиpованное дерево, дерево) – ориентированный граф, в котором:

  1. все вершины, кроме одной (корня), находятся в голове только одной дуги;
  2. корень дерева не находится в голове какой-либо дуги;
  3. корень связан с каждой вершиной дерева.


Двоичное дерево - это дерево, в котором у каждой вершины не более 2-х потомков. Пример:


Обход дерева - это упорядоченная последовательность вершин дерева, в котором каждая вершина встречается только один раз. В каждую вершину попадаем по крайней меpе один pаз, а вообще говоря 3 раза. При обходе дерева могут выполняться различные действия, например, печатать метку. Если печатать метку при первой  встрече с ней, то получается последовательность 6,4,3,5,7; если при второй, то - 3,4,5,6,7; если при третей, то - 3,5,4,7,6. Эти три способа обхода называется  соответственно обходом сверху, обходом слева направо, обходом снизу.


Алгоритмы обходов

Сверху
Слева направо
Снизу
если дерево пусто то закончить иначе обраб.корень; обойти левое поддерево; обойти правое поддерево; закончить
если дерево пусто то закончить иначе обойти левое дерево; обработать корень; обойти левое дерево; закончить
если дерево пусто то закончить иначе обойти левое дерево; обойти правое дерево; обработать корень; закончить

 

 

 

 

Стеки и очереди

Это динамические структуры, приспособленные для того, чтобы добавлять элементы в множества и удалять их оттуда. Стек-память, организованная по принципу LIFO (Last In First Out). Стек - ограниченная с одной стороны последовательность переменной длины. Существуют различные способы проверки того, что стек пуст. В дальнейшем будем пустой стек отмечать специальным символом. Очередь-память, организованная по принципу FIFO (First In First Out).

Списки

Список - последовательность элементов, где  каждый элемент содержит информацию двух типов: внутреннюю - присущую данному элементу, и  внешнюю - о связи данного узла с другими элементами списка. Внешняя информация о связи элемента имеет вид указателей, то есть адресов узлов, связанных с данным. Примером списка может служить строка. Данный список однонаправленный. Могут быть построены двунаправленные, циклические и тому подобные списки. Теоретически у каждого элемента может быть произвольное число указателей. Например, слово "string" посимвольно занесено в однонаправленный список:


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

 

Предложения исходной программы могут быть представлены в виде последовательности лексем (tokens). Лексемы понимаются как фундаментальные кирпичики, из которых строится язык. Например лексемой может быть ключевое слово, имя переменной, и т. п. Точный перечень лексем, которые необходимо распознавать, зависит от языка программирования и от грамматики, используемой для его описания. Например, для языка Паскаль лексемами являются: PROGRAM, INTEGER, REAL, VAR, DO,READ и т.д.

Функции лексического анализатора:

  1. ввод строк исходной программы;
  2. распознавание лексем;
  3. заполнение таблиц идентификаторов и литералов;
  4. печать листинга исходной программы.

Лексический анализатор должен учитывать специфические особенности различных языков программирования. Например, сканер должен учитывать информацию, связанную с соглашением по формату расположения строк исходной программы. Так в языке Фортран число в колонках 1 - 5 в исходном предложении должно рассматриваться как метка, а не как целое число. Кроме того, сканер должен учитывать языково-зависимую информацию: являются ли пробелы ограничителями лексем Паскаль или нет Фортран; могут ли предложения свободно размещаться  в нескольких строках исходного текста Паскаль этого требуется специальные признаки продолжения Фортран.

Для работы сканер использует следующую информацию:

  1. исходный текст программы;
  2. таблицу терминальных символов;
  3. таблицу литералов;
  4. таблицу идентификаторов.

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


Таблица символических имен может иметь следующий вид :


Таблица литералов по структуре аналогична таблице символических имен:


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

FOR I:=1 TO 100 DO Y:=X1 ;

будет получена строка:

<1,06><2,1><1,14><3,1><1,07><3,2><1,08><2,2><1,14><2,3>

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

Функционально в сканере могут быть выделены следующие модули:

  1. выделение из входной строки очередного слова;
  2. поиск в таблицах лексем и определение кода лексемы;
  3. формирование и вывод выходной строки.

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

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

Алгоритм

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

Наиболее ответственной и трудной задачей является выделение лексем из входной строки предложение исходной программы состоят из лексических единиц, разделенных символами - разделителями. Например, в языке Паскаль символами – разделителями являются:, . '   ; : знаки операции (),[]. Распознавание таких объектов ,как идентификаторы и литералы выполняются на основе плавил языка.

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

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

Формальные грамматики

В языке обязательно присутствуют две стороны: синтаксис и семантика. Синтаксис - множество плавил, описывающих структуру(форму) предложений языка - порядок следования слов, а точнее - лексем. Семантика - множество правил интерпретации смысла предложения. Отличием синтаксиса от семантики заключается в том, что он занимается формальной структурой предложений, не затрагивая смысл. Например, фраза «Глокая куздpа штеко будланула бокpа и куpдячит бокpенка», грамматически верно построена, но смысл её не совсем понятен.

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

В общем случае задача синтаксического контроля заключается в проверке структуры предложений языка на соответствие правилам синтаксиса. Совокупность правил синтаксиса образует грамматику языка. Поскольку алгоритмические языки в отличие от естественных языков называют формальными языками, то и грамматики этих языков также именуют формальными. Разработка теории формальных грамматик начата американским ученым Хомским, основные работы которого были опубликованы в 1956 -
1959 г.г.

По определению Хомского, формальная грамматика представляет собой четверку:

G={N,T,P,a}

N - множество нетерминальных символов (или понятий) языка. Например, в грамматиках естественных языков используются понятия «существительного», «подлежащего», «сказуемого» и т.д.; в грамматиках алгоритмических языков - "оператор", "метка", разделитель" и т.д.;

Т - множество терминальных символов языка, т.е. тех символов из которых конструируются предложения языка;

Р - множество правил подстановки. Каждое правило состоит из левой и правой частей, соединенных знаком секвенции «->». Каждая часть представляет собой цепочку нетерминальных и/или терминальных символов. Правая часть правила определяет цепочку символов, которая может  замещать цепочку из левой части;

а - аксиома грамматики - множество нетерминальных символов (понятий) с которых начинается порождение или распознавание любого предложения языка.

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

А - целое число без знака; В - любая цифра;
G={N,T,P,a};
N={A,B};
T={0,1,2,3,4,5,6,7,8,9};
P={A->BA,A->B,B->0,B->1,B->2,B->3,B->4,B->5,B->6,B->7,B->8,B->9};
a={A}

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

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

Бэкусова нормальная форма грамматики

Наибольшее распространение получила развитая американским ученым Бэкусом (1959) система обозначений Хомского. Впервые она была использована другим американским ученым Науром (1960) в официальном сообщении по языку Алгол-60 .В этой системе обозначений нетерминальные символы заключаются в угловые скобки «<», «>», а под термином «символ» понимается в общем случае строка символов. Левая и правая части правила разделяются символом «:=», который заменяет фразу: «По определению есть». Поскольку для одного нетерминального символа возможно несколько различных подстановок, то для их разделения используется символ «?», который заменяет фразу: «или иначе», «либо». Символы «<», «>», «?», «:=» называют метаязыковыми символами, а систему обозначений Бэкуса называют Бэкусовой нормальной формой задания грамматик (БНФ). Например, описанная ранее в символике Хомского грамматика целого числа без знака примет следующий вид в символике Бэкуса.

G={N,T,P,a};
N={<целое без знака>,<цифра>};
T={0,1,2,3,4,5,6,7,8,9};
P={<целое без знака>::=<цифра><целое без знака>?<цифра>, <цифpа>::=0?1?2?3?4?5?6?7?8?9};
a={<целое без знака>};

Ниже рассматривается пример задания грамматики в БНФ.

<опеpатоp безусловного перехода>::= GOTO <метка>
<метка>::=<целое без знака>
<целое без знака>::=<цифpа><пpодолжение целого>
<пpодолж.целого>::=<цифpа><пpодолжение целого>|<пусто>
<цифpа>::=0|1|2|3|4|5|6|7|8|9|
<пусто>::=

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

Процесс синтаксического анализа может рассматривается как построение дерева грамматического разбора для транслируемых предложений. Гpаматики могут использоваться как для порождения так и для распознавания предложений языка. Порождение начинается с начального понятия (или аксиомы грамматики). При распознавании с помощью грамматических правил порождается предложение, которое затем сравнивается с входной строкой. При этом применение правил подстановки для порождения очередного символа предложения зависит от результатов сравнения предыдущих символов с соответствующими символами входной строки. Результат анализа исходного предложения в терминах грамматических конструкций удобно представлять в виде дерева. Такие деревья обычно называются деревьями грамматического разбора или синтаксическими деревьями.

Методы грамматического разбора разбиваются на два больших класса восходящие и нисходящие - в соответствии порядком построения дерева грамматического разбора. Исходящие (методы свеpху-вниз) начинаются с аксиомы грамматики, с корня дерева и пытаются так его наращивать, чтобы последующие узлы дерева соответствовали синтаксису анализируемого выражения. Восходящие (методы снизу-вверх) начинают с элементов предложения (с «листьев») и отыскивают в грамматике какому понятию они соответствуют, т.е. определяют родительскую вершину для этих элементов, и т.д. пока не приходят к корню дерева(аксиоме грамматики). В современных компиляторах применяются как нисходящие, так и восходящие методы.

Кроме этого, алгоритмы синтаксического (грамматического) разбора(контроля) делят на синтаксически-ориентированные и синтаксически-неориентированные. Синтаксически-ориентированные алгоритмы являются универсальными для некоторого семейства языков и переход к распознаванию предложений другого языка выполняется путем смены грамматики, т.е. грамматика выполняет роль некоей «программы» распознавания предложений языка. Главным достоинством этого класса алгоритмов является их универсальность, а недостатком - наличие избыточности вследствие ориентации на семейство языков.

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