Организация таблицы идентификаторов, ее содержание и назначение. Метод бинарного дерева и цепочек. Проектирование лексического анализатора и схема распознавателя. Построение дерева вывода, синтаксический анализатор. Анализ результатов работы программы.
Аннотация к работе
Компилятор - программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд. В первой части работы ставится задача разработать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Во второй части работы требуется разработать программу, которая выполняет лексический анализ входного текста по заданной грамматике и порождает таблицу лексем с указанием их типов и значений. В третьей части работы требуется разработать программу, которая на основании таблицы лексем выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. На входе имеется набор идентификаторов, которые организуются в таблицу по одному из двух методов (метод бинарного дерева и метод цепочек).Для сравнения методов организации таблицы идентификаторов был разработан модуль, иллюстрирующий их работу. Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдает сообщения о наличие во входном тексте ошибок, которые могут быть обнаружены на этапе лексического анализа. Лексический анализатор (или сканер) - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка.Спроектированный лексический анализатор выполняет лексический анализ входного текста в соответствии с заданной грамматикой и порождает таблицу лексем с указанием их типов. Этот алгоритм послужит в дальнейшем базой для построения дерева вывода в 3 части курсовой работы. Программа выполняет лексический анализ входного, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Исходная грамматика имеет вид: S > prog L end. Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода.Была разработана программа, производящая построение дерева вывода заданных логических выражений и проверяющая их синтаксис.В результате выполнения курсовой работы для заданного входного языка были построены отдельные части компилятора. В первой части работы был разработан программа, которая получает на входе набор идентификаторов, организует таблицу идентификаторов методом цепочек и методом бинарного дерева, позволяет осуществить многократный поиск идентификатора в этих таблицах.
Введение
программа идентификатор распознаватель анализатор
Компилятор - программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.
Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером.
Целью данной курсовой работы является изучение составных частей, основных принципов построения и функционирования компиляторов, практическое освоение методов построения составных частей компилятора для заданного входного языка.
Курсовая работа заключается в создании отдельных частей компилятора заданного языка.
В первой части работы ставится задача разработать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Программа должна сообщать среднее число коллизий и среднее количество сравнений, выполняемых для поиска идентификатора.
Во второй части работы требуется разработать программу, которая выполняет лексический анализ входного текста по заданной грамматике и порождает таблицу лексем с указанием их типов и значений.
В третьей части работы требуется разработать программу, которая на основании таблицы лексем выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора.
Результатами курсовой работы являются программная реализация заданного компилятора и пояснительная записка, оформленная в соответствии с требованиями стандартов и задания на курсовую работу.
В качестве среды разработка для реализации программы использован язык программирования C и система программирования Borland CBUILDER 6.
1. Организация таблицы идентификаторов
1.1 Исходные данные
На входе имеется набор идентификаторов, которые организуются в таблицу по одному из двух методов (метод бинарного дерева и метод цепочек). Необходима возможность осуществления многократного поиска идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длина идентификатора ограничена 32 символами.
Первый метод организации таблицы - бинарное дерево. Второй - метод цепочек.
Требуется, чтобы программа сообщала число коллизий и количество сравнений, выполняемых при поиске идентификатора.
1.2 Назначение таблицы идентификаторов
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице символов или таблице идентификаторов. Любая таблица символов состоит из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.
В данной работе мы сравним два метода организации таблицы идентификаторов: метод бинарного дерева и метод цепочек.
1.3 Метод бинарного дерева
Метод построения таблиц, при котором таблица имеет форму бинарного дерева. Каждый узел дерева представляет собой элемент таблицы, причем корневой узел является первым элементом. При построении дерева элементы сравниваются между собой, и в зависимости от результатов, выбирается путь в дереве. Предположим, что надо записать новый идентификатор. Для него выбирается левое поддерево, если этот идентификатор меньше текущего, если же идентификатор больше, выбирается правое поддерево. В случае если текущий узел не является концевым, переходим в следующий узел (согласно выбранному направлению) и опять сравниваем добавляемый идентификатор с текущим.
Для данного метода число требуемых сравнений и форма получившегося дерева во многом зависят от того порядка, в котором поступают идентификаторы.
Блок-схема метода бинарного дерева представлена на рисунке 1.1
Рис. 1. 1 - Блок-схема метода бинарного дерева; а) - Блок-схема алгоритма метода бинарного дерева; б) - Блок-схема функции добавления идентификатора; в) - Блок-схема функции поиска идентификатора
1.4 Метод цепочек
Блок-схема метода цепочек списка представлена на рисунке 1.2
Рис. 1.2 - Блок-схема метода цепочек; а) - Блок-схема алгоритма метод цепочек; б) - Блок-схема функции добавление идентификатора; в) - Блок-схема функции поиска идентификатора
1.5 Результат выполнения программы
Рис. 1.3 - Результаты сравнения методов организации таблицы идентификаторов
При поиске идентификаторов в таблицах организованных методом бинарного дерева и методом цепочек было установлено, что количество сравнений в бинарном дереве в несколько раз больше, чем в методе цепочек.
Вывод
Для сравнения методов организации таблицы идентификаторов был разработан модуль, иллюстрирующий их работу.
Было выявлено, что метод цепочек является более эффективным, чем метод бинарного дерева, так как для поиска идентификатора используется меньшее количество сравнений.
В дальнейшем для заполнения таблицы идентификаторов исходной программы будем использовать метод цепочек.
2. Проектирование лексического анализатора
2.1 Исходные данные
Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдает сообщения о наличие во входном тексте ошибок, которые могут быть обнаружены на этапе лексического анализа.
Предусмотрены следующие варианты операторов входной программы: · оператор присваивания вида :=;
· условный оператор вида if then
· либо if then else ;
· составной оператор вида begin… end;
· оператор цикла do while ;
· арифметические операции сложения ( ), вычитания (-), декремент (-);
· операции сравнения «меньше» (), «равно» (=);
· логические операции and, or, not;
· операндами в выражениях могут выступать идентификаторы и константы;
· все идентификаторы должны восприниматься как переменные целого типа.
2.2 Назначение лексического анализатора
Лексический анализатор (или сканер) - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка.
2.3 Схема распознавателя
Распознаватель лексем языка для данной грамматики задан конечным детерминированным автоматом, схема которого представлена на рисунке 2.1.
Рис. 2.1 - Схема распознавателя h - начальное состояние автомата
S - конечное состояние автомата
Заданные правила могут быть записаны в форме Бэкуса-Наура.
G (VT, VN, P, S)
VT - множество терминальных символов;
VN - множество нетерминальных символов;
P - множество правил;
S - целевой символ.
Регулярная грамматика входного языка имеет вид: G (
{0..9, p, r, o, g, e, n, d, t, h, l, s, b, I, w, ‘ ’, -, ‘;’, ‘(», ‘)’, =, ‘>’, ‘<’, «/’, «*’}, {h, A, B, C, D, E, H, G, K, L, M, R, N, O, P, I, J, Q, V, W, X, Y, Z, T, U, F, AA, AM, AB, AC, AD, AG, AF, AH, AI, AE, AK, AL, AJ, AN, AO, AP, AQ, AR, AT, AU, AV, AW, AX, FF, RR}
P, S
)
P: S > prog L end.
L > O | L; O | L;
B> B or C | C
D > G | not D
G > E E | E=E | (B)
K > G then O
M > K else O
Q > O while G
O > if M | if K| begin L end | do Q | c:=E
E > E-F | E F | E- | F
F > (E) | c | g
2.4 Результат выполнения программы
Результаты разбора входных выражений на лексемы представлен на рисунке 2.2
Рис. 2.2 - Результаты разбора входных выражений на лексемыСпроектированный лексический анализатор выполняет лексический анализ входного текста в соответствии с заданной грамматикой и порождает таблицу лексем с указанием их типов. Программа выводит также сообщения о наличие во входном тексте ошибок. Этот алгоритм послужит в дальнейшем базой для построения дерева вывода в 3 части курсовой работы.
3. Построение дерева вывода
3.1 Исходные данные
Программа выполняет лексический анализ входного, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдавать сообщения о наличие во входном тексте ошибок.
Лексический анализатор выделяет в тексте лексемы языка. Полученная после лексического анализа цепочка во второй части программы рассматриваться в соответствии с алгоритмом разбора. После построения цепочки вывода на ее основе строится дерево разбора.
Длину идентификаторов и строковых констант считать ограниченной 32 символами.
Исходная грамматика имеет вид: S > prog L end.
L > O | L; O | L;
B> B or C | C
C> C and D | D
D > G | not D
G > E E | E=E | (B)
K > G then O
M > K else O
Q > O while G
O > if M | if K| begin L end | do Q | c:=E
E > E-F | E F | E- | F
F > (E) | c | g
3.2 Синтаксический анализатор
Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из таких способов представления является дерево синтаксического разбора.
Программирование работы недетерминированного МП-автомата - это сложная задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами).
Доказано, что время работы этого алгоритма пропорционально n3, где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n2. Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма «сдвиг-свертка». Выделяют следующие типы грамматик предшествования: · простого предшествования;
· расширенного предшествования;
· слабого предшествования;
· смешанной стратегии предшествования;
· операторного предшествования.
3.3 Таблицы предшествования
Множество правил грамматики имеет вид: S > prog L end.
L > O | L; O | L;
B> B or C | C
C> C and D | D
D > G | not D
G > E E | E=E | (B)
K > G then O
M > K else O
Q > O while G
O > if M | if K| begin L end | do Q | c:=E
E > E-F | E F | E- | F
F > (E) | c | g
Грамматика является грамматикой операторного предшествования, так как она не содержит l-правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики.
Таблица 3.1. Множества крайних правы и крайних левых символов
Символ (U) Начало построения Результат
L(U) R(U) L(U) R(U)
S prog end. prog end.
L O L O; OL if begin do c OMKQEGF -) c g end;
B B C C BCDG not E (F c g CDQEF -) c g end
C C D D CDG not E (F c g DGEF -) c g end
D G not GD G not E (F c g DGEF -) c g end
G E( E) E (F c g EF -) c g end
K G O GE (FCD OMKQEGF -) c g end
M K O GKE (F c g OMKQEGF -) c g end
Q O G If begin do c GE) F-c g
O If begin do c MK end Q E EF do c MK end QEOGF-) cg
E E F F - EF (c g F-) c g
F (c g ) c g (c g ) c g
На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики.
Таблица 3.2. Множества крайних правых и крайних левых терминальных символов
Символ (U) Начало построения Результат
L(U) R(U) L(U) R(U)
S prog end. prog end.
L ; ; if begin do c if end do:= else then while - -; =) c g
B or or or and not = (- - c g and not - -; =) c g
C and and and not = (- - c g not =) - -) c g and D not not or not = (- - c g =) not - - c g
G = ( =) = (- - c g =) - - c g
K then then = (- - c g then if end do:= else while - - =) cg
M else else = (- - c g then else then if end do:= else while - - =) cg
Q while while while if begin do c while = - - c g
O if begin do c if end do:= c if begin do c if end do then:= else while - - =) cg
E - - - - - - (c g - -) c g
F (c g ) c g (c g ) c g
На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики: Таблица 3.3. Матрица предшествования исходной грамматики prog end. ; or and not = ( ) if then else do while := - - c g begin end over prog - < < - - - - - - - - < - < < - - - - - < - < - - end. - - - - - - - - - - - - - - - - - - - - - - - - >
Результаты построения дерева разбора входных выражений представлены на рисунке 3.1.
Рис. 3.1 - Результаты построения дерева разбора
По последовательности правил «свертки» легко строится цепочка вывода и дерево синтаксического разбора. Дерево строится сверху вниз путем последовательного применения правил. Алгоритм разбора порождает правосторонний вывод.Была разработана программа, производящая построение дерева вывода заданных логических выражений и проверяющая их синтаксис.В результате выполнения курсовой работы для заданного входного языка были построены отдельные части компилятора.
В первой части работы был разработан программа, которая получает на входе набор идентификаторов, организует таблицу идентификаторов методом цепочек и методом бинарного дерева, позволяет осуществить многократный поиск идентификатора в этих таблицах.
Было также выявлено, что метод цепочек более эффективен, чем метод бинарного дерева, так как для поиска идентификатора в таблице организованной методом цепочек используется меньшее количество сравнений.
Во второй части работы была написана программа, которая выполняет лексический анализ входного текста и порождает таблицу лексем с указанием их типов и значений.
Третья часть курсовой работы была посвящена разработке программы, которая порождает таблицу лексем и выполняет синтаксический разбор текста с построением дерева разбора.
Отдельные части компилятора, разработанные в данной курсовой работе, дают представление о технике и методах, лежащих в основе построения компиляторов.
2. Кампапиец Р. II. Манькоп Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. - СПБ.: КОРОНА Принт, 2000. - 256 с.
3. Гордеев А.В. Операционные системы: Учебник для вузов. 2-е изд.-СПБ.: Питер, 2004. - 416 с.
4. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. - СПБ.: Питер. 2002. - 544 с.