Принципы разработки компиляторов
ВВЕДЕНИЕ
компилятор программа грамматика
Компилятор - программный модуль, задачей которого является перевод
программы, написанной на одном из языков программирования (исходный язык) в
программу на язык ассемблера или язык машинных команд.
Большинство компиляторов переводят программу с некоторого
высокоуровневого языка программирования в машинный код, который может быть
непосредственно выполнен компьютером.
Целью данной курсовой работы является изучение составных частей, основных
принципов построения и функционирования компиляторов, практическое освоение
методов построения составных частей компилятора для заданного входного языка.
Курсовая работа заключается в создании отдельных частей компилятора
заданного языка.
В первой части работы ставится задача разработать программу, которая
получает на входе набор идентификаторов, организует таблицу по заданному методу
и позволяет осуществить многократный поиск идентификатора в этой таблице.
Во второй части работы требуется разработать программу, которая выполняет
лексический анализ входного текста по заданной грамматике и порождает таблицу
лексем с указанием их типов и значений.
В третьей части работы требуется разработать программу, которая на
основании таблицы лексем выполняет синтаксический разбор текста по заданной
грамматике с построением дерева разбора.
Результатами курсовой работы являются программная реализация заданного
компилятора и пояснительная записка, оформленная в соответствии с требованиями
стандартов и задания на курсовую работу.
В качестве среды разработка для реализации программы использован язык
программирования C++ и среда программирования Visual Studio C++ 2012.
1. ОПИСАНИЕ ВХОДНОГО ЯЗЫКА
Входной язык представляет собой подмножество языка программирования Pascal.
Программа на данном языке может включать в себя символы латиницы, цифры,
знак “ _ “, символьные константы, различные операторы. Текст на входном языке
содержится в текстовом файле.
Набор идентификаторов организуются в таблицу по методу упорядоченного
списка. Необходима возможность осуществления многократного поиска
идентификатора в этой таблице. Список идентификаторов считать заданным в виде
текстового файла. Длина идентификатора ограничена 32 символами. Он может
включать в себя символы кириллицы и латиницы, цифры, знаки “ ^ ” и ” _ ”.
Идентификатор не может начинаться с цифры.
Предусмотрены следующие варианты операторов входной программы:
- оператор присваивания (:=);
- зарезервированные слова If, Else, Then, While,
Do, Prog, End;
- арифметические операции (+, -, /, *);
- операндами в выражениях могут выступать идентификаторы и
константы (один символ, заключенный в одинарные кавычки);
- все идентификаторы должны восприниматься как переменные;
- допускается присутствие комментариев оформленных виде:
//комментарий
Для выделения лексем заранее строится конечный автомат.
Данный язык относится к КС-языкам, поэтому может быть описан следующей
грамматикой:
<буква>→”A” |….| ”Z” |….| ”a” |….| ”z” |”_”
<арифм.опер.>→”+” | ”-” | ”*” |”/”
<цифра>→”0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”
< ID >→<буква>
|<ID><буква>
|<ID><цифра>
<симв.конст.> →’<буква>’
|’<цифра>’
<операнд>→<ID>
|< симв.конст.>
<арифм.выр.>→
<операнд><арифм.оп.><операнд>
|<арифм.выр><арифм.оп.><операнд>
|<операнд><арифм.оп.>< арифм.выр >
|<операнд><арифм.выр.><операнд>
<оператор>→<оп.цикла>
|< оп.присв>
|<услов.оп>
<оп.присв.>→<ID>”:=”<операнд>”;”
|<ID>”:=”<арифм.выр.>”;”
<блок опер.> →<оператор> ”;”
<оператор>
|<блок>”;”<оператор>
<тело>→”{“<блок опер>”;}”
<оп.цикла>→ “do”<тело>“while” ”(” <арифм.выр.>”)” ”;”
|“do””{“ <оператор> ”}” “while””(” <арифм.выр.>”)””;”
<услов.оп>→ if “(”<арифм.выр>“)””then”<тело>”else”<тело>
|if “(” <арифм.выр>“)””then”<тело>
|if “(”<арифм.выр>“)”then”<оператор>”else”<оператор>
|if “(” <арифм.выр>“)””then”<оператор>
|if “(”<арифм.выр>“)””then”<оператор>”else”<тело>
|if “(”<арифм.выр>“)””then”<тело>”else”<оператор>
<прогр.>→ “prog”<тело> “end”
|“prog”<оператор> “end”
Далее, используя эту грамматику по методу сдвиг-свертка, производится
проверка входного языка на синтаксические ошибки.
2.
ОРГАНИЗАЦИЯ ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ
.1 Назначение
таблицы идентификаторов
Таблица используется на всех стадиях работы компилятора и формируется на
этапе лексического анализа.
Проверка правильности семантики и генерация кода требуют знания
характеристик идентификаторов, используемых в программе на исходном языке. Эти
характеристики выясняются из описаний и из того, как идентификаторы
используются в программе и накапливаются в таблице символов или таблице
идентификаторов. Любая таблица символов состоит из набора полей, количество
которых равно числу идентификаторов программы. Каждое поле содержит в себе
полную информацию о данном элементе таблицы. Под идентификаторами
подразумеваются переменные.
Основными характеристиками метода построения идентификаторов является
скорость поиска, объем памяти. Оптимальное сочетание этих параметров определяет
выбор метода. В данной работе используется метод упорядоченного списка.
.2 Метод
упорядоченного списка
Этот метод является простым методом построения таблиц идентификаторов.
Элементы записываются в таблицу в порядке возрастания. Так как упорядочивание
таблицы идентификаторов происходит на всех этапах обращения к таблице, то для
ее построения можно пользоваться только алгоритмом прямого упорядоченного
включения элементов. При добавлении нового элемента в таблицу идентификаторов
он сначала добавляется в конец таблицы, а затем идет переупорядочивание
элементов таблицы идентификаторов. Эффективным методом для поиска элементов
является логарифмический поиск, на каждом шаге которого, число элементов,
которые могут содержать искомый элемент, сокращается в два раза. Максимально
число сравнений при поиске 1+log2(N).
Схема алгоритма добавления идентификатора представлена на рис. 1
Рисунок 1 - Алгоритм добавления идентификатора
Схема алгоритма бинарного поиска идентификатора представлена на рис. 2
Рисунок 2 - Алгоритм поиска идентификатора
2.3 Результат
выполнения программы
В результате работы было выявлено, что недостатком такого метода является
требование упорядочивания таблицы идентификаторов на всех этапах обращения к
этой таблице.
К положительным качествам метода можно отнести простоту его организации.
3. ПРОЕКТИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
В основном лексические анализаторы выполняют исключение из текста
исходной программы комментариев и незначащих пробелов, а также выделение лексем
следующих типов: идентификаторов, строковых, символьных и числовых констант,
ключевых (служебных) слов входного языка.
.2 Граф
переходов лексического анализатора
Распознаватель лексем языка для данной грамматики задан конечным
детерминированным автоматом, схема которого представлена на рисунках 3, 4 и 5.
Рисунок 3 - Схема распознавателя 1
Рисунок 4 - Схема распознавателя 2
Рисунок 5 - Схема распознавателя 3
Легенда:
V -
любой определенный алфавитно-цифровой символ (буквы латинского алфавита, знак
«_», десятичные цифры);
V(*) -
любой символ кроме перечисленных в скобках;- буквы латинского алфавита и знак
«_»;(*) - любая буква кроме перечисленных в скобках;
Р - пробел, табуляция, перенос строки;
D -
недопустимые символы (все кроме перечисленных);- сохранение (ID - в таблице идентификаторов; L -в
таблице лексем);
e -
ошибка;- имя лексемы;
Состояния соответствуют:
Н - начальное состояние;
К - конечное состояние;
P1, P2, P3, P4 -
состояния, соответствующие ключевому слову “prog”;
En1, En2 - состояния, соответствующие
ключевому слову “end”;
I1, I2 - состояния, соответствующие
ключевому слову “if”;
E1, E2, E3, E4 -
состояния, соответствующие слову “else”;
T1, T2, T3, T4 -
состояния, соответствующие слову “then”;
W1, W2, W3, W4, W5 - состояния, соответствующие
ключевому слову “while”;
D1, D2 - состояния, соответствующие
ключевому слову “do”;
S1, S2, S3 - состояния, соответствующие символьное константе:
A1, A2 - состояния, соответствующие
оператору присваивания “:=”;
С1, С2 - комментарий;
Программа, реализованная на основе данного автомата, выполняет
лексический анализ текста программы на заданном языке.
.3 Результат
выполнения программы
Результат разбора входных выражений на лексемы представлен на рисунке 6.
Рисунок 6 - Результат работы лексического анализатора (таблица лексем)
Спроектированный лексический анализатор выполняет лексический анализ
входного текста в соответствии с заданной грамматикой и порождает таблицу лексем
с указанием их типов. Программа выводит также сообщения о наличие во входном
тексте ошибок. Этот алгоритм послужит в дальнейшем базой для построения дерева
вывода в 3 части курсовой работы.
4. ПОСТРОЕНИЕ СИТАКСИЧЕСКОГО АНАЛИЗАТОРА
.1 Дерево
вывода
Лексический анализатор выделяет в тексте лексемы языка. Полученная после
лексического анализа цепочка во второй части программы рассматриваться в
соответствии с алгоритмом разбора. После построения цепочки вывода на ее основе
строится дерево разбора.
Программа выполняет лексический анализ входного языка, порождает таблицу
лексем и выполняет синтаксический разбор текста по заданной грамматике с
построением дерева разбора. Текст на входном языке задается в виде символьного
(текстового) файла. Программа должна выдавать сообщения о наличие во входном
тексте ошибок.
Длину идентификаторов и строковых констант считать ограниченной 32
символами.
.2
Синтаксический анализатор
Перед синтаксическим анализатором стоят две основные задачи: проверить
правильность конструкций программы, которая представляется в виде уже
выделенных слов входного языка, и преобразовать ее в вид, удобный для
дальнейшей семантической (смысловой) обработки и генерации кода. Одним из таких
способов представления является дерево синтаксического разбора.
Программирование работы недетерминированного МП-автомата - это сложная
задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики
определить, принадлежит ли ей заданная входная цепочка (алгоритм
Кока-Янгера-Касами).
Доказано, что время работы этого алгоритма пропорционально n3,
где n - длина входной цепочки. Для однозначной КС-грамматики при
использовании другого алгоритма (алгоритм Эрли) это время пропорционально n2.
Подобная зависимость делает эти алгоритмы требовательными к вычислительным
ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка -
большинство конструкций языков программирования может быть отнесено в один из
классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие
от длины входной цепочки.
КС-языки делятся на классы в соответствии со структурой правил их
грамматик. В каждом из классов налагаются дополнительные ограничения на
допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они
используются для синтаксического разбора цепочек с помощью алгоритма
“сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
- простого предшествования;
- расширенного предшествования;
- слабого предшествования;
- смешанной стратегии предшествования;
- операторного предшествования.
Алгоритм построения синтаксического анализатора включает следующие этапы:
) составление правил грамматики языка;
) выявление множества крайних правых и кайних левых терминальных и
нетерминальных символов;
) построение матрицы предшествования.
Рассмотрим эти этапы более подробно.
4.3 Таблицы предшествования
Множество правил грамматики имеет вид:
<буква>→”A” |….| ”Z” |….| ”a” |….| ”z” |”_”
<арифм.опер.>→”+” | ”-” | ”*” |”/”
<цифра>→”0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”
< ID >→<буква>
|<ID><буква>
|<ID><цифра>
<симв.конст.> →’<буква>’
|’<цифра>’
<операнд>→<ID>
|< симв.конст.>
<арифм.выр.>→
<операнд><арифм.оп.><операнд>
|<арифм.выр><арифм.оп.><операнд>
|<операнд><арифм.оп.>< арифм.выр >
<оператор>→<оп.цикла>
|< оп.присв>
|<услов.оп>
|<ID>”:=”<арифм.выр.>”;”
<блок опер.> →<оператор> ”;”
<оператор>
|<блок>”;”<оператор>
<тело>→”{“<блок опер>”;}”
<оп.цикла>→ “do”<тело>“while” ”(” <арифм.выр.>”)” ”;”
|“do””{“ <оператор> ”}” “while””(” <арифм.выр.>”)””;”
<услов.оп>→ if “(”<арифм.выр>“)””then”<тело>”else”<тело>
|if “(” <арифм.выр>“)””then”<тело>
|if “(”<арифм.выр>“)”then”<оператор>”else”<оператор>
|if “(” <арифм.выр>“)””then”<оператор>
|if “(”<арифм.выр>“)””then”<оператор>”else”<тело>
|if “(”<арифм.выр>“)””then”<тело>”else”<оператор>
<прогр.>→ “prog”<тело> “end”
|“prog”<оператор> “end”
Грамматика является грамматикой операторного предшествования, так как она
не содержит l-правил и
правые части правил не содержат смежных нетерминальных символов. Построим
множества крайних левых и крайних правых символов L(U), R(U)
относительно всех нетерминальных символов грамматики.
Таблица 3.1 - Множества крайних правых и крайних левых символов
|
Символ (U)
|
Начало построения
|
|
L(U)
|
R(U)
|
|
<элемент>
|
<число>,ID, <элемент>
|
<число>,ID
|
|
<лев.выр>
|
<элемент>,<лев.выр>
|
<элемент>,<число>
|
|
<выр>
|
<лев.выр>
|
”;”
|
|
<сис.уравн>
|
<сис.уравн>,<выр>
|
<выр>
|
На основе полученных множеств построим множества крайних левых и крайних
правых терминальных символов Lt(U), Rt(U)
относительно всех нетерминальных символов грамматики.
Таблица 3.2 - Множества крайних правых и крайних левых терминальных
символов
|
Символ (U)
|
Начало построения
|
|
L(U)
|
R(U)
|
|
<элемент>
|
<число>,ID
|
<число>,ID
|
|
<лев.выр>
|
<число>,ID
|
<число>,ID
|
|
<выр>
|
<число>,ID
|
”;”
|
|
<сис.уравн>
|
<число>,ID
|
”;”
|
На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики:
Таблица 3.3 - Матрица предшествования исходной грамматики
|
константа
|
переменная.
|
;
|
=
|
-
|
+
|
*
|
/
|
|
Константа
|
-
|
-
|
<
|
<
|
<
|
<
|
<
|
-
|
|
Переменная
|
-
|
-
|
<
|
<
|
<
|
<
|
<
|
|
;
|
<
|
<
|
-
|
-
|
-
|
-
|
-
|
-
|
|
=
|
<
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
-
|
<
|
<
|
-
|
-
|
-
|
-
|
-
|
-
|
|
+
|
<
|
<
|
-
|
-
|
-
|
-
|
-
|
-
|
|
*
|
<
|
<
|
-
|
-
|
-
|
-
|
-
|
-
|
|
/
|
<
|
<
|
-
|
-
|
-
|
-
|
-
|
-
|
На основе
матрицы предшествования производится синтаксический анализ методом
“сдвиг-свертка” в результате которого формируется матрица коэффициентов для
дальнейшего решения методом Гаусса.
5. ГЕНЕРАЦИЯ КОДА
Генерация объектного кода - это перевод компилятором внутреннего
представления исходной программы в цепочку символов выходного языка.
Генерация объектного кода порождает результирующую объектную программу на
языке ассемблера или непосредственно на машинном языке (в машинных кодах).
Внутреннее представление программы может иметь любую структуру в зависимости от
реализации компилятора, в то время как результирующая программа всегда
представляет собой линейную последовательность команд. Поэтому генерация
объектного кода (объектной программы) в любом случае должна выполнять действия,
связанные с преобразованием сложных синтаксических структур в линейные цепочки.
Генерацию кода можно считать функцией, определенной на синтаксическом
дереве, построенном в результате синтаксического анализа, и на информации,
содержащейся в таблице идентификаторов. Поэтому генерация объектного кода
выполняется после того, как выполнены синтаксический анализ программы и все
необходимые действия по подготовке к генерации кода: распределено адресное
пространство под функции и переменные, проверено соответствие имен и типов
переменных, констант и функций в синтаксических конструкциях исходной программы.
Характер отображения входной программы в последовательность команд,
выполняемую генерацией, зависит от входного языка, архитектуры вычислительной
системы, на которую ориентирована результирующая программа, а также от качества
желаемого объектного кода.
5.1
Общие принципы генерации кода
Задача
генератора кода - построение для программы <javascript://> на входном
языке эквивалентной машинной программы. Обычно в качестве входа для генератора
кода служит некоторое промежуточное представление программы.
Генерация
кода включает <javascript://> ряд специфических, относительно независимых
подзадач: распределение памяти (в частности, распределение регистров), выбор
команд, генерацию объектного (или загрузочного) модуля. Конечно, независимость
этих подзадач относительна: например, при выборе команд нельзя не учитывать
схему распределения памяти, и, наоборот, схема распределения памяти (регистров,
в частности) ведет к генерации той или иной последовательности команд. Однако
удобно и практично эти задачи все же разделять, обращая при этом внимание на их
взаимодействие.
В
какой-то мере схема генератора кода зависит от формы промежуточного
представления. Ясно, что генерация кода из дерева отличается от генерации кода
из троек, а генерация кода из префиксной записи <javascript://>
отличается от генерации кода из ориентированного графа. В то же время все
генераторы кода имеют много общего, и основные применяемые алгоритмы
отличаются, как правило <javascript://>, только в деталях, связанных с
используемым промежуточным представлением.
5.2
Основные методы оптимизации
Задача оптимизации кода состоит в создании
эффективного (с точки зрения размера памяти и времени выполнения) целевого
кода. Желаемая степень оптимизации будет зависеть от обстоятельств. Иногда она
не нужна, например, если у программы малое время выполнения, умеренные запросы
к памяти и, возможно, малый срок жизни.
Необходимость оптимизации может требоваться для
программ с большим временем выполнения либо значительными запросами к памяти и,
возможно, с длительным временем существования. Стоимость оптимизации главным
образом оценивается в терминах времени компиляции. Некоторые виды оптимизации
могут быть дорогостоящими в смысле времени компиляции, другие - сравнительно
дешевыми. Обычно более дешевые типы оптимизации всегда стоит осуществлять, а
более дорогие - не всегда.
В средах, где основной является качественная диагностическая информация,
лучше всего полностью отказаться от оптимизации, чтобы избежать возможной
путаницы вследствие некорректных сообщений.
6. ОПИСАНИЕ ПРОГРАММЫ
#include "stdafx.h"
//Подключаем необходимые заголовочные файлы
#include <iostream>
#include <string>
#include <conio.h>
///////////////////
#include "states.h" //функции переходов
автомата
#include "common.h" //вспомогательные функции
///////////////////
//по умолчанию используем пространство имен
"std"namespace std;
//таким образом делаем переменные видимыми в разных модулях
//extern lexem* idtable[MAXHASH]; //таблица
идентификаторовlexem** idtable = NULL;//таблица идентификаторовlexem*
lexTableHead = NULL; //указатель на начало (начальный елемент) таблицы
лексемlexem* lexTableEnd = NULL; //указатель на конец (последний елемент)
таблицы лексем
int row = 0;col = 0;
//"главная" функция_tmain(int
argc, _TCHAR* argv[])
{
setlocale( LC_ALL,"Russian" ); //данная
строчка необходима для корректного отображения кириллицы
header(); //выводим "шапку"
string fileName = "c:/test.txt";
//задаем имя файла
//cout << "Введите путь и имя файла \n";
//cin >> fileName;
//считаем содерживое файла (текст программы) в строку
string programText = readFile(fileName);();lexem =
""; //переменная для хранения имени лексемыcurrState = sBEGIN;
//текущее состояние автомата
//текс программы разберем посимвольно в цикле
for(unsigned int i = 0; i <
programText.length(); i++){c = toupper(programText[i]); //текущий символ(c ==
'\n')
{++;= 0;
}(currState){sBEGIN:.clear();=
beginState(c,lexem);;
/////////////////////////////////////////sIF1:=
if1State(c,lexem);;
/////////////////////////////////////////sIF2:=
if2State(c,lexem);;
/////////////////////////////////////////sELSE1:=
else1State(c,lexem);;
/////////////////////////////////////////sELSE2:=
else2State(c,lexem);;
/////////////////////////////////////////sELSE3:=
else3State(c,lexem);;
/////////////////////////////////////////sELSE4:=
else4State(c,lexem);;
/////////////////////////////////////////sFOR1:=
for1State(c,lexem);;
/////////////////////////////////////////sFOR2:=
for2State(c,lexem);;
/////////////////////////////////////////sFOR3:=
for3State(c,lexem);;
/////////////////////////////////////////sDO1:=
do1State(c,lexem);;
/////////////////////////////////////////sDO2:=
do2State(c,lexem);;
/////////////////////////////////////////sPROG1:=
prog1State(c,lexem);;
/////////////////////////////////////////sPROG2:=
prog2State(c,lexem);;
/////////////////////////////////////////sPROG3:=
prog3State(c,lexem);;
/////////////////////////////////////////sPROG4:=
prog4State(c,lexem); ;
/////////////////////////////////////////sEND1:=
end1State(c,lexem); ;
/////////////////////////////////////////sEND2:=
end2State(c,lexem); ;
/////////////////////////////////////////sSYMBOL1:=
"\'";= symbol1State(c,lexem);;
/////////////////////////////////////////sSYMBOL2:=
symbol2State(c,lexem);;
/////////////////////////////////////////sSYMBOL3:=
symbol3State(c,lexem);;
/////////////////////////////////////////sASSIGN1:=
":";= assign1State(c,lexem);;
/////////////////////////////////////////sASSIGN2:=
"";= assign2State(c,lexem);;
/////////////////////////////////////////sCOMMENT1:=
"";= comment1State(c,lexem);;
/////////////////////////////////////////sCOMMENT2:=
comment2State(c,lexem);;
/////////////////////////////////////////sIDENT:=
idState(c,lexem);;sNUMBER:
/////////////////////////////////////////=
numberState(c,lexem);;
}+= c;++;
}
//сохраняем таблицы();();
//освободим ресурсы (удалим содержимое таблиц)();();<<
endl << L"Для завершения программы нажмите любую клавишу...";
_getch();//"задержка"0;
}
ЗАКЛЮЧЕНИЕ
В результате выполнения курсовой работы для заданного входного языка были
построены отдельные части компилятора.
В первой части работы был разработан программа, которая получает на входе
набор идентификаторов, организует таблицу идентификаторов методом
упорядоченного списка, позволяет осуществить многократный поиск идентификатора
в этой таблице.
Во второй части работы была написана программа, которая выполняет
лексический анализ входного текста и порождает таблицу лексем с указанием их
типов и значений.
Третья часть курсовой работы была посвящена разработке программы, которая
порождает таблицу лексем и выполняет синтаксический разбор текста с построением
дерева разбора.
Отдельные части компилятора, разработанные в данной курсовой работе, дают
представление о технике и методах, лежащих в основе построения компиляторов.
СПИСОК
ЛИТЕРАТУРЫ
1. Гордеев А.В. Молчанов Л.Ю. Системное программное
обеспечение, - СПб.: Питер. 2002. - 734с.
2. Кампапиец Р.II. Манькоп Е.В., Филатов Н.Е. Системное
программирование. Основы построения трансляторов: Учеб. пособие для высших и
средних учебных заведений. - СПб.: КОРОНА Принт, 2000. -256 с.
. Гордеев А.В. Операционные системы: Учебник для
вузов.
. Олифер В.Г., Олифер Н.А. Сетевые операционные системы.
- СПб.: Питер. 2002. - 544 с.
5. Брайан Оверленд C++ без страха,- СПб.: Питер. 2005. -
432с.
. Марченко А.Л. C++ Бархатный путь,- СПб.: Питер.
2005. - 401с.