Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

• ВВЕДЕНИЕ
• 1. ОПИСАНИЕ ВХОДНОГО ЯЗЫКА
• 2. ОРГАНИЗАЦИЯ ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ
• 2.1 Назначение таблицы идентификаторов

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

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

• 3. ПРОЕКТИРОВАНИЕ ЛЕКСИЧЕСКОГО АНАЛИЗАТОРА
• 3.1 Назначение лексического анализатора
• 3.2 Граф переходов лексического анализатора
• 3.3 Результат выполнения программы
• 4. ПОСТРОЕНИЕ СИТАКСИЧЕСКОГО АНАЛИЗАТОРА
• 4.1 Дерево вывода
• 4.2 Синтаксический анализатор
• 4.3 Таблицы предшествования
• ЗАКЛЮЧЕНИЕ
• СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

В качестве среды разработка для реализации программы использован язык программирования 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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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



Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 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 - Множества крайних правых и крайних левых символов

Символ (U)	Начало построения
	L(U)	R(U)
<элемент>	<число>,ID, <элемент>	<число>,ID
<лев.выр>	<элемент>,<лев.выр>	<элемент>,<число>
<выр>	<лев.выр>	”;”
<сис.уравн>	<сис.уравн>,<выр>	<выр>

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

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

Символ (U)	Начало построения
	L(U)	R(U)
<элемент>	<число>,ID	<число>,ID
<лев.выр>	<число>,ID	<число>,ID
<выр>	<число>,ID	”;”
<сис.уравн>	<число>,ID	”;”

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

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

	константа	переменная.	;	=	-	+	*	/
константа	-	-	<	<	<	<	<	-
переменная	-	-	-	<	<	<	<	<
;	<	<	-	-	-	-	-	-
=	<	-	-	-	-	-	-	-
-	<	<	-	-	-	-	-	-
+	<	<	-	-	-	-	-	-
*	<	<	-	-	-	-	-	-
/	<	<	-	-	-	-	-	-

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

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

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

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

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

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

Размещено на Allbest.ru

...