Разработка компилятора языка С++

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

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

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

Задачей данной курсовой работы является проектирование, и реализация анализирующей части компилятора языка С++. Язык реализации С++.

Требования к реализации компилятора

Базовые требования к реализации компилятора, на удовлетворение которых должны быть направлены решения:

· полнота и конформность стандарту языка — реализация должна поддерживать все свойства языка С++, определенные в стандарте, и обеспечивать полное соответствие стандарту;

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

· эффективность — реализация должна обеспечивать производительность, сравнимую с современными промышленными компиляторами С++.

Структура компилятора

Процесс компиляции состоит из следующих этапов.

1. Лексический анализ. На этом этапе последовательность символов исходного файла преобразуется в последовательность лексем.

2. Синтаксический (грамматический) анализ. Последовательность лексем преобразуется в дерево разбора.

3. Семантический анализ. Дерево разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их декларациям, типам, проверка совместимости, определение типов выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным деревом разбора, новым деревом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.

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

5. Генерация кода. Из промежуточного представления порождается код на целевом языке.

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

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

Помимо этого лексический анализатор может решать и другие задачи, такие как:

· отбрасывание пробельных символов и комментариев (пробел, символы табуляции и новой строки, а также, возможно, некоторые другие символы, использующиеся для отделения токенов друг от друга во входном потоке);

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

Существует несколько способов реализации лексического анализа: конечные автоматы или генераторы лексических анализаторов (lex, Flex, gplex, OOlex).

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

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

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

Принципы программной реализации:

· каждому состоянию ставится в соответствии метка;

· анализируемые альтернативы проверяются условными операторами;

· если результат проверки является истиной, проводится обработка контекста, берется следующий символ и осуществляется переход на новую метку (в новое состояние);

· процесс повторяется до тех пор, пока не произойдет переход в одно из заключительных состояний.

компилятор алгоритм синтаксический анализатор

Алгоритм работы лексического анализатора

В программе лексемы разделены на классы: ключевые слова, операторы, пунктуаторы, символы, скобки, числа.

Описание класса:

class KeyWord

{ private:

list keyword; //список ключевых слов

public:

KeyWord ();

bool operator ()(const AnsiString s); //проверяет принадлежность к списку

};

Входные данные помещаются в массив vector sym_table (посимвольно).

Структура symbol передает символ, строку, столбец, длину символа и позицию от начала.

Выходные данные формируются в массиве vector scaner_result.

Структура cell содержит описание типа, саму лексему, строку, столбец, длину лексемы и позицию от начала.

Символ из массива sym_table проверяется на принадлежность к определенному классу лексем, если функция возвращает значение истина, то символ переписывается в переменную curr_cell (объект структуры cell) и переходим к следующему символу, так же проверяем на принадлежность к этому же классу лексем, если функция возвращает значение ложь, то записываем данные из переменной curr_cell в массив scanner_result, обнуляем переменную curr_cell, проверяем если ли в массиве sym_table еще символы, если он не пустой, то переходим к следующему.

Данные об ошибках хранятся в массиве error_result.

Как только массив sym_table оказался пуст, данные из массивов scanner_result и error_result выводятся в таблицы.

Исходный код программы, выбранной для разбора, представлен в Приложении А. Результат разбора кода лексическим анализатором представлен на рисунке 1.

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

Так «область видимости» лексического анализатора узка, то без помощи других компонентов компилятора ему достаточно сложно обнаружить ошибки в исходном тексте программы, например, если в программе токен F впервые встретился в контексте F=a*33. Поскольку F является корректной лексемой, лексический анализатор должен вернуть этот токен синтаксическому анализатору, который в свою очередь должен обработать ошибку «Неопределенный тип».

Рисунок 2 — Результат работы лексического анализатора с найденными ошибками Полученная последовательность токенов, записанная в массив scaner_result передается синтаксическому анализатору. Компилятор переходит к следующей фазе.

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

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

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

Рисунок 3 — Место синтаксического анализатора в модели компилятора Существуют различные формы промежуточного представления программы, например, троичный код или абстрактное синтаксическое дерево. В данном случае используется абстрактное синтаксическое дерево.

Методы, обычно применяемые в компиляторах, можно классифицировать как нисходящие (сверху вниз — top-down) или восходящие (снизу вверх — bottom-up). Как следует из названий, нисходящие синтаксические анализаторы строят дерево разбора от корня и листьям, тогда как восходящие начинают с листьев и идут к корню. В обоих случаях входной поток синтаксического анализатора сканируется посимвольно слева направо.

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

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

Алгоритм работы синтаксического анализатора

Создана структура TLexeme, переменная curr_par типа cell, в нее записываются данные из массива, который передает лексический анализатор. Из переменной curr_cell данные переписываются в массив Lexemes. Дальше работаем только с массивом Lexemes.

struct TLexeme

{ String type; //тип токена

String body; //сам токен

int position; //строка

};

TLexeme* Lexemes; // Найденные лексемы: тип, тело, строка

cell curr_par; //объект структуры (сама структура в 1. h)

int Number = Form1->scaner_result.size (); //передаем количество лексем

Lexemes = new TLexeme [Number]; //нейденные лексемы

for (int i=0, j=0; i

{ //в «строку» перемещаем данные из БОЛЬШОГО массива

curr_par=Form1->scaner_result[j];

//сразу записываем в новый

Lexemes[j]. type=curr_par.type;

Lexemes[j].body=curr_par.value;

Lexemes[j].position=curr_par.str;

j++;

}

Дальше по циклу проверяем принадлежность лексемы к какой-либо синтаксической конструкции.

Если лексема принадлежит конструкции, записываем ее в корень, получаем необходимые параметры, для тела, если это цикл, структура, функция (т.е. для того, что в {}) вызывается рекурсия.

if (Lexemes[i]. body=="struct")

{ add_tabs (dest, tabs);

dest<<" struct" <<'n';

tabs++; i++;

if (Lexemes[i]. type=="Идентификатор")

{ add_tabs (dest, tabs);

dest<<" Имя" <<'n';

tabs++;

add_tabs (dest, tabs);

dest<<<'n';

i++; tabs—;

}

add_tabs (dest, tabs);

dest<<" {}" <<'n';

if (Lexemes[i]. body=="{")

{ //i++;

i=MakeBinTree (dest, tabs, tabs, i,1," @#$%^&(«, tecFN); //вызов рекурсии для того, что в {}

i++;

//tabs—;

}

if (Lexemes[i]. type=="Идентификатор") //18:48 добавила условие, чтобы выводились объекты структуры

{ while (Lexemes[i]. type=="Идентификатор" || Lexemes[i]. body==",")

{ if (Lexemes[i]. type=="Идентификатор")

{ add_tabs (dest, tabs);

dest<<<'n';

}

i++;

}

}

tabs—;

}

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

Для записи объекта в текстовый файл используется функция add_tabs.

void add_tabs (ofstream &dest, int tabs)

{ //передаю уровень, иду по циклу ставлю табуляцию

for (int j=0;j

dest<<'t';

}

В результате разбора строится синтаксическое дерево Рисунок 4.

Синтаксические ошибки включают неверно поставленные точки с запятой или лишние недостающие скобки, отсутствие условий (для оператора while), отсутствие тела (switch, while, do while), неверное количесво параметров (for), неопределенный тип (если переменная не была объявлена).

Рисунок 4 — Результат работы синтаксического анализатора Рисунок 5 — Результат работы синтаксического анализатора с найденными ошибками

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

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

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

Рисунок 6 — Построение таблицы идентификаторов

Заключение

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

1) лексический анализ результатом, которого является таблица токенов;

2) синтаксический анализ результатом, которого может быть дерево разбора в случае корректности анализируемого кода;

3) построена таблица идентификаторов.

Реализованное приложение позволяет анализировать файлы с расширением и *.cpp, *.h, *.c, *.hpp.

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

1. Ахо, Лам, Сети, Ульман. Компиляторы: принципы, технологии и инструментарий, 2-е изд.: Пер. с англ. — М.: ООО «И.Д. Вильямс», 2008. — 1184 с.: ил.

2. Мозговой М. В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. — СПб.: Наука и Техника, 2006. — 320 с.: ил.

3. Серебряков В. А., Галочкин М. П. Основы конструирования компиляторов, Москва, 2001. — 224с.

Приложение А

Текст тестовой программы для проверки корректности работы лексического анализатора

#include

/*fbdfbdfbdfbdf fhdfh/* fdhfghf

ghfgh */

//—————-;

int main ()

{const n=34u, m=12LU;

const l=12.6f, t=23.6L;

float u=11e-10f;

int a=0012, b=0xabcd, c=-12; float d=07;

float a=12.11, t=12e2, u=-0.23e-12;

char a='a', t='', v='123', k='xab';

char t[]="gfbfgnft" «» hmnghjmh

jyhjghghjgh" ;

&=

>>=

new

signed

inline

return 0;

}

Текст тестовой программы для проверки корректности работы синтаксического анализатора

#include

//test

enum RET {red, green=1}

int main (int s, double z)

{ int a, b=4,c=0,d=121, q;

a=10;

if ((a+b* c)<10 && c

{ for (int i=0; i<5; i++)

{ q+=1;

do {++a;}

while (b+a<20)

}

}

/*/*olololo

123 */

if (a<10)

if (b>10 && b<15)

{ int s=b; }

else s=a;

return s;

}

//——————————;

Приложение Б

Хранение лексем

bool Punkt: operator () (const AnsiString s)

{ return find (punkt.begin (), punkt. end (), s)≠punkt.end ();

}

Punkt:Punkt ()

{ punkt. push_back («…»); punkt. push_back («;»);

punkt.push_back («:»); punkt. push_back («,»);

Проверка на принадлежность

if (ISpunkt (sym_table[i]. chr))

{ int len=0;

curr_cell.str=sym_table[i]. str;

curr_cell.sym=sym_table[i].sym;

curr_cell.pos=pos;

curr="" ;

do {curr+=sym_table[i++]. chr; len++; pos++;}

while (ISpunkt (sym_table[i]. chr));

if (ISpunkt (curr))

curr_cell.type="Пунктуатор" ;

curr_cell.value=curr;

curr_cell.len=len;

result.push_back (curr_cell);

i—;

continue;

}

Функция проверяет на наличие арифметических операций в выражении

int if_there_arifmetic_ops (long ii)

{ TLexeme* Lexemes; // Найденные лексемы: тип, тело, строка

cell curr_par; //объект структуры (сама структура в 1. h)

int Number=Form1->scaner_result.size ();

Lexemes = new TLexeme [Number]; //нейденные лексемы

for (int t=0, j=0; t

{ //в «строку» перемещаем данные из БОЛЬШОГО массива

curr_par=Form1->scaner_result[j];

//сразу записываем в новый

Lexemes[j]. type=curr_par.type;

Lexemes[j].body=curr_par.value;

Lexemes[j].position=curr_par.str;

j++;

}

int f=0;

long i;

int cs=0;//Счет скобок

for (i=ii;i

Lexemes[i]. body=="<"

return f;

delete []Lexemes;

}