Организация таблицы идентификаторов

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

ОРГАНИЗАЦИЯ ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ

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

 

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

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

 

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

 

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

 

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

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

 

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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-правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов 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 с.

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

ОРГАНИЗАЦИЯ ТАБЛИЦЫ ИДЕНТИФИКАТОРОВ