Программно методический комплекс для обучения процессу создания компиляторов (стр. 2 из 14)
Компилятор компиляторов (КК) – система, позволяющая генерировать компиляторы; на входе системы - множество грамматик, а на выходе, в идеальном случае, - программа. Иногда под КК понимают язык программирования, в котором исходная программа - это описание компилятора некоторого языка, а объектная программа - сам компилятор для этого языка. Исходная программа КК - это просто формализм, служащий для описания компиляторов, содержащий, явно или неявно, описание лексического и синтаксического анализаторов, генератора кодов и других частей создаваемого компилятора. Обычно в КК используется реализация схемы т.н. синтаксически управляемого перевода. Кроме того, некоторые из них представляют собой специальные языки высокого уровня, на которых удобно описывать алгоритмы, используемые при создании компиляторов.
1.2 Логическая структура компилятора
На рисунке 1 представлена структурная схема компилятора.
 |
Рисунок 1 – Схема компилятора
Исходная программа – текст программы на языке высокого уровня (например Паскаль), который должен быть переведен в машинный код.
Информационные таблицы - самостоятельные структуры, заранее заполненные (таблица терминальных символов), а также заполняющиеся в ходе лексического анализа и дополняющиеся во время работы.
Лексический анализатор выполняет распознавание лексем языка и замену их соответствующими кодами. Под лексемами понимаются элементарные единицы, входящие в структуру предложения языка, такие как ключевые слова, константы, имена и т.п. Правильность задания структуры предложения языка на фазе лексического анализа не выполняется. Результатом является поток лексем (кодов – ссылок на таблицы), эквивалентный исходному тексту.
Синтаксический анализатор необходим для того, чтобы выяснить, удовлетворяют ли предложения, из которых состоит исходная программа, правилам грамматики этого языка.
Семантический анализ. На этом этапе осуществляется контроль типа и вида всех идентификаторов и других операндов.
Генерация промежуточного кода. Происходит преобразование исходной программы в промежуточную (например, польскую) форму записи.
Оптимизация промежуточного кода – выделение общих подвыражений и вычисление константных подвыражений.
Фаза оптимизации предназначена для уменьшения избыточности программы по затратам времени и памяти. В зависимости от критериев проектирования транслятора данная фаза обработки программы может исключаться из цикла обработки программы.
Распределение памяти. На этом этапе выделяются конкретные адреса пользователя под переменные, которые генерируются компилятором.
Генератор объектного (ассемблерного) кода – выполняет подстановку кодовых образцов на выходном языке, соответствующих промежуточным кодам программы. Генератору кода могут не требоваться шаблоны, он весь может быть реализован в процедурном виде.
Машинно-зависимая компиляция. Зависит от того, какие используются регистры. Работа этой процедуры зависит от соглашений, принятых для исполняемой части программы. Например, выделяется базовый регистр для текущей активной записи в стеке.
На всех этих этапах происходит работа с различного рода таблицами. В частности, для каждого блока (если таковые существуют в языке) идентификаторы, описанные внутри, запоминаются вместе со своими атрибутами. Условно все эти этапы можно изобразить следующим образом:
 |
Рисунок 2 – Работа с таблицами
Очевидна зависимость структуры компилятора от структуры ЭВМ, точнее, от имеющейся производительности системы. Например, при малой памяти увеличивается количество проходов компиляции (т.н. многопроходные компиляторы), а при наличии памяти большого объема можно все этапы компиляции произвести за один проход (и тогда мы имеем дело с однопроходным компилятором).
Далее мы рассмотрим некоторые из этих составных частей процесса компиляции.
1.3 Лексический анализ. Сканер
Лексический анализатор представляет собой модуль разбора текста программы. Разбор происходит в зависимости от имеющихся у него в памяти терминальных символов и правилами определения типов данных. Каждый язык имеет свои ограничения по типам данных, допущения и особенности создания (строения) конструкций, применению операторов и т.п. При работе сканера используются три таблицы: таблица терминальных символов, таблица символических имен и таблица литералов – это заполняемые таблицы. Таблица терминальных символов хранит все ключевые слова и специальные символы используемые в языке, а также коды, соответствующие каждому символу. Таблица символических имен заполняется в процессе разбора текста программы и хранит в себе имена идентификаторов (символических имен). Таблица литералов также заполняется в процессе разбора программы и хранит в себе литералы: численные и строковые значения, с указанием типов данных и относительных адресов.
Распределение по таблицам происходит следующим образом.
Сканер в процессе анализа текста программы выделяет один из элементов текста и сравнивает с каждым терминальным символом. Если такой символ найден, то в выходной код передаются код таблицы и спецификатор (номер строки в таблице). В случае если этот элемент не является терминальным символом проверяется, является ли он идентификатором (первый символ обычно буква, остальные могут быть либо буквой, либо цифрой), если такой определен, то данный элемент заносится в таблицу символических имен, а к выходному коду добавляется пара численных значений: номер таблицы и спецификатор найденного элемента. В случае если такой элемент в таблице уже имеется, то в выходной код заносится номер таблицы и его спецификатор. В таблицу литералов заносят численные, строковые и иные определенные языком значения. При этом распознается тип значения и тут же заполняется относительная таблица адресов.
Выходной код, сформированный сканером, передается на следующую стадию обработки – синтаксический анализ.
Таким образом, алгоритм работы простейшего сканера можно описать так:
· просматривается входной поток символов программы на исходном языке до обнаружения очередного символа, ограничивающего лексему;
· для выбранной части входного потока выполняется функция распознавания лексемы;
· при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;
· при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера - либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).
Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.
Таблица терминальных символов в простейшем случае может иметь следующий вид как показано в таблице 1.
Таблица 1 – Таблица терминальных символов
| № п.п. | Терминальный символ | Комментарий (обозначение) |
| 1 | PROGRAM | Заголовок программы |
| 2 | VAR | Описание переменных |
| 3 | BEGIN | Начало тела программы |
| 4 | END | Конец тела программы |
| 5 | INTEGER | Целый тип данных |
| 6 | FOR | Счетный оператор цикла (для) |
| 7 | TO | Ключевое слово счетного оператора цикла (до) |
| 8 | DO | Ключевое слово (выполнить) |
Продолжение таблицы 1
| № п.п. | Терминальный символ | Комментарий (обозначение) |
| 9 | WHILE | Оператор цикла с предусловием (пока) |
| 10 | DIV | Деление целочисленное |
| 11 | MOD | Остаток от целочисленного деления |
| 12 | AND | Логическое И |
| 13 | OR | Логическое ИЛИ |
| 14 | := | Присвоить значение |
Сначала заполняется таблица лексем (терминальных символов), затем начинается считывание и обработка входного текста программы пользователя. При работе сканера происходит заполнение таблиц символических имен и литералов.
Данные таблицы могут выглядеть следующим образом:
Таблица 2 – Таблица символических имен
| № п.п. | Идентификатор | Тип | Размер, занимаемый в памяти, байт | Относительный адрес в памяти |
| 1 | I | INTEGER | ||
| 2 | Y | REAL | ||
| 3 | X1 | REAL | ||
| … |
Таблица 3 – Таблица литералов
| № п.п. | Литерал | Тип | Размер, занимаемый в памяти, байт | Относительный адрес в памяти |
| 1 | 1 | INTEGER | 2 | 0 |
| 2 | 100 | INTEGER | 2 | 2 |
| … |
Результатом работы сканера является последовательность кодов лексем. Каждый код лексемы обычно представляется кодом таблицы и спецификатором (порядковый номер в таблице, куда занесена лексема). Это позволяет избежать дополнительного поиска по таблицам на следующих этапах трансляции. Например в результате обработки сканером следующего предложения языка Паскаль
FORI:=1 TO 100 DOY:=X1
будет получена строка:
<1,06><2,1><1,14><3,1><1,07><3,2><1,08><2,2><1,14><2,3>,
где в угловых скобках пара чисел задает код таблицы и спецификатор. Можно оформить и в виде таблицы.
Таблица 4 – Таблица выходных символов
| № п.п. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Таблица | 1 | 2 | 1 | 3 | 1 | 3 | 1 | 2 | 1 | 2 |
| Строка | 6 | 1 | 14 | 1 | 7 | 2 | 8 | 2 | 14 | 3 |
Функционально в сканере могут быть выделены следующие модули[4]: