Принципы разработки компиляторов

компилятор программа грамматика

Компилятор — программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.

Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером.

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

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

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

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

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

Результатами курсовой работы являются программная реализация заданного компилятора и пояснительная записка, оформленная в соответствии с требованиями стандартов и задания на курсовую работу.

В качестве среды разработка для реализации программы использован язык программирования 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. ОРГАНИЗАЦИЯ ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ

2.1 Назначение таблицы идентификаторов

Таблица используется на всех стадиях работы компилятора и формируется на этапе лексического анализа.

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

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

2.2 Метод упорядоченного списка

Этот метод является простым методом построения таблиц идентификаторов. Элементы записываются в таблицу в порядке возрастания. Так как упорядочивание таблицы идентификаторов происходит на всех этапах обращения к таблице, то для ее построения можно пользоваться только алгоритмом прямого упорядоченного включения элементов. При добавлении нового элемента в таблицу идентификаторов он сначала добавляется в конец таблицы, а затем идет переупорядочивание элементов таблицы идентификаторов. Эффективным методом для поиска элементов является логарифмический поиск, на каждом шаге которого, число элементов, которые могут содержать искомый элемент, сокращается в два раза. Максимально число сравнений при поиске 1+log₂(N).

Схема алгоритма добавления идентификатора представлена на рис. 1

Рисунок 1 — Алгоритм добавления идентификатора

Схема алгоритма бинарного поиска идентификатора представлена на рис. 2

Рисунок 2 — Алгоритм поиска идентификатора

2.3 Результат выполнения программы

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

К положительным качествам метода можно отнести простоту его организации.

3. ПРОЕКТИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА

3.1 Назначение лексического анализатора

Лексический анализатор (или сканер) — это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.

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

3.2 Граф переходов лексического анализатора

Распознаватель лексем языка для данной грамматики задан конечным детерминированным автоматом, схема которого представлена на рисунках 3, 4 и 5.

Рисунок 3 — Схема распознавателя 1

Рисунок 4 — Схема распознавателя 2

Рисунок 5 — Схема распознавателя 3

Легенда:

V — любой определенный алфавитно-цифровой символ (буквы латинского алфавита, знак «_», десятичные цифры);

V (*) — любой символ кроме перечисленных в скобках;

B — буквы латинского алфавита и знак «_»;

B (*) — любая буква кроме перечисленных в скобках;

Р — пробел, табуляция, перенос строки;

D — недопустимые символы (все кроме перечисленных);

F — сохранение (ID — в таблице идентификаторов; Lв таблице лексем);

e — ошибка;

s — имя лексемы;

Состояния соответствуют:

Н — начальное состояние;

К — конечное состояние;

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.3 Результат выполнения программы

Результат разбора входных выражений на лексемы представлен на рисунке 6.

Рисунок 6 — Результат работы лексического анализатора (таблица лексем)

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

4. ПОСТРОЕНИЕ СИТАКСИЧЕСКОГО АНАЛИЗАТОРА

4.1 Дерево вывода

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

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

Длину идентификаторов и строковых констант считать ограниченной 32 символами.

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

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

Программирование работы недетерминированного МП-автомата — это сложная задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами).

Доказано, что время работы этого алгоритма пропорционально n³, где n — длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n². Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка — большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

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

Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма «сдвиг-свертка». Выделяют следующие типы грамматик предшествования:

— простого предшествования;

— расширенного предшествования;

— слабого предшествования;

— смешанной стратегии предшествования;

— операторного предшествования.

Алгоритм построения синтаксического анализатора включает следующие этапы:

1) составление правил грамматики языка;

2) выявление множества крайних правых и кайних левых терминальных и нетерминальных символов;

3) построение матрицы предшествования.

Рассмотрим эти этапы более подробно.

4.3 Таблицы предшествования Множество правил грамматики имеет вид:

<�буква>>"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»

Грамматика является грамматикой операторного предшествования, так как она не содержитправил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики.

Таблица 3.1 — Множества крайних правых и крайних левых символов

На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов L_t(U), R_t(U) относительно всех нетерминальных символов грамматики.

Таблица 3.2 — Множества крайних правых и крайних левых терминальных символов

На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики:

Таблица 3.3 — Матрица предшествования исходной грамматики

На основе матрицы предшествования производится синтаксический анализ методом «сдвиг-свертка» в результате которого формируется матрица коэффициентов для дальнейшего решения методом Гаусса.

5. ГЕНЕРАЦИЯ КОДА

Генерация объектного кода — это перевод компилятором внутреннего представления исходной программы в цепочку символов выходного языка.

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

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

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

5.1 Общие принципы генерации кода

Задача генератора кода — построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.

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

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

5.2 Основные методы оптимизации

Задача оптимизации кода состоит в создании эффективного (с точки зрения размера памяти и времени выполнения) целевого кода. Желаемая степень оптимизации будет зависеть от обстоятельств. Иногда она не нужна, например, если у программы малое время выполнения, умеренные запросы к памяти и, возможно, малый срок жизни.

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

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

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

6. ОПИСАНИЕ ПРОГРАММЫ

#include «stdafx.h»

//Подключаем необходимые заголовочные файлы

#include

#include

#include

#include «states.h» //функции переходов автомата

#include «common.h» //вспомогательные функции

//по умолчанию используем пространство имен «std»

using namespace std;

//таким образом делаем переменные видимыми в разных модулях

//extern lexem* idtable[MAXHASH]; //таблица идентификаторов

extern lexem** idtable = NULL;//таблица идентификаторов

extern lexem* lexTableHead = NULL; //указатель на начало (начальный елемент) таблицы лексем

extern lexem* lexTableEnd = NULL; //указатель на конец (последний елемент) таблицы лексем

int row = 0;

int col = 0;

//" главная" функция

int _tmain (int argc, _TCHAR* argv[])

{

setlocale (LC_ALL," Russian"); //данная строчка необходима для корректного отображения кириллицы

header (); //выводим «шапку»

string fileName = «c:/test.txt» ;

//задаем имя файла

//cout << «Введите путь и имя файла n» ;

//cin >> fileName;

//считаем содерживое файла (текст программы) в строку

string programText = readFile (fileName);

initIdTable ();

string lexem = «»; //переменная для хранения имени лексемы

STATE currState = sBEGIN; //текущее состояние автомата

//текс программы разберем посимвольно в цикле

for (unsigned int i = 0; i < programText. length (); i++){

char c = toupper (programText[i]); //текущий символ

if (c == 'n')

{

row++;

col = 0;

}

switch (currState){

case sBEGIN:

lexem.clear ();

currState = beginState (c, lexem);

break;

case sIF1:

currState = if1State (c, lexem);

break;

case sIF2:

currState = if2State (c, lexem);

break;

case sELSE1:

currState = else1State (c, lexem);

break;

case sELSE2:

currState = else2State (c, lexem);

break;

case sELSE3:

currState = else3State (c, lexem);

break;

case sELSE4:

currState = else4State (c, lexem);

break;

case sFOR1:

currState = for1State (c, lexem);

break;

case sFOR2:

currState = for2State (c, lexem);

break;

case sFOR3:

currState = for3State (c, lexem);

break;

case sDO1:

currState = do1State (c, lexem);

break;

case sDO2:

currState = do2State (c, lexem);

break;

case sPROG1:

currState = prog1State (c, lexem);

break;

case sPROG2:

currState = prog2State (c, lexem);

break;

case sPROG3:

currState = prog3State (c, lexem);

break;

case sPROG4:

currState = prog4State (c, lexem);

break;

case sEND1:

currState = end1State (c, lexem);

break;

case sEND2:

currState = end2State (c, lexem);

break;

case sSYMBOL1:

lexem = «'» ;

currState = symbol1State (c, lexem);

break;

case sSYMBOL2:

currState = symbol2State (c, lexem);

break;

case sSYMBOL3:

currState = symbol3State (c, lexem);

break;

case sASSIGN1:

lexem = «:» ;

currState = assign1State (c, lexem);

break;

case sASSIGN2:

lexem = «» ;

currState = assign2State (c, lexem);

break;

case sCOMMENT1:

lexem = «» ;

currState = comment1State (c, lexem);

break;

case sCOMMENT2:

currState = comment2State (c, lexem);

break;

case sIDENT:

currState = idState (c, lexem);

break;

case sNUMBER:

currState = numberState (c, lexem);

break;

}

lexem += c;

col++;

}

//сохраняем таблицы

saveIdentTable ();

saveLexTable ();

//освободим ресурсы (удалим содержимое таблиц)

clearIdentTable ();

clearLexTable ();

wcout << endl << L" Для завершения программы нажмите любую клавишу…" ;

_getch ();//" задержка"

return 0;

}

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

1. Гордеев А. В. Молчанов Л.Ю. Системное программное обеспечение, — СПб.: Питер. 2002. — 734с.

2. Кампапиец Р.II. Манькоп Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. — СПб.: КОРОНА Принт, 2000. -256 с.

3. Гордеев А. В. Операционные системы: Учебник для вузов.

2-е изд.-СПб.: Питер, 2004. — 416 с.

4. Олифер В. Г., Олифер Н. А. Сетевые операционные системы. — СПб.: Питер. 2002. — 544 с.

5. Брайан Оверленд C++ без страха, — СПб.: Питер. 2005. — 432с.

6. Марченко А. Л. C++ Бархатный путь, — СПб.: Питер. 2005. — 401с.