Введение
Компилятор – программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.
Целью данной курсовой работы является изучение основных принципов построения и функционирования отдельных фаз компиляции, практическое освоение методов построения составных фаз компилятора для заданного входного языка.
Курсовая работа заключается в разработке отдельных фаз компиляции для заданного входного языка.
В первой части работы ставится задача разработать модуль, который позволит сравнить методы цепочек и бинарного дерева и выбрать из них наиболее эффективный. Для этого модуль, получив на вход набор идентификаторов, должен организовать таблицу идентификаторов обоими методами с возможностью осуществления многократного поиска и добавления идентификаторов в эту таблицу, а также с выводом общего и среднего числа сравнений при построении таблицы идентификаторов, и числа сравнений при добавлении и поиске идентификатора каждым из методов. На основе сравнения этих результатов необходимо определить, какой из методов эффективнее. Для дальнейшей работы используется только этот метод.
Во второй части работы требуется разработать модуль, который должен выполнить лексический анализ входного текста по заданной грамматике, результатом которого является таблица лексем с указанием их типов и значений. После построения таблицы лексем, используя лучший метод из предыдущего пункта, модуль должен также создать таблицу идентификаторов.
В третьей части работы требуется разработать модуль, который должен выполнить на основе таблицы лексем синтаксический разбор текста по заданной грамматике с построением дерева разбора.
Результатами курсовой работы являются программная реализация отдельных фаз компиляции для заданного входного языка и пояснительная записка, оформленная в соответствии с требованиями стандартов и задания на курсовую работу.
В качестве среды разработки для реализации программы был использован Borland
Delphi
7.
1. Организация таблицы идентификаторов
На входе имеется набор идентификаторов. Необходимо написать модуль, который организует данный набор идентификаторов в таблицу идентификаторов методами цепочек и бинарного дерева с возможностью осуществления многократного поиска идентификатора в этой таблице. Список идентификаторов считается заданным в виде текстового файла. Идентификаторы также можно вводить вручную в процессе работы программы.
Требуется программно реализовать возможность определения наиболее эффективного метода организации таблицы идентификаторов. В качестве критериев сравнения эффективности методов необходимо вывести следующие показатели: общее и среднее число сравнений при построении таблицы идентификаторов, а также число сравнений при добавлении и поиске идентификатора. Для метода цепочек также должно выводиться число коллизий. На основе сравнения этих результатов необходимо определить, какой из методов эффективнее. Для дальнейшей работы используется только этот метод.
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице идентификаторов. Таблица идентификаторов состоит из набора полей данных, который содержит всю необходимую компилятору информацию о данном элементе и может пополняться по мере работы компилятора.
Под идентификаторами подразумеваются константы, переменные, имена процедур и функций, формальные и фактические параметры.
1.3.
Метод бинарного дерева
Данный метод организует таблицу идентификаторов в форме бинарного дерева. Каждый узел этого дерева представляет собой элемент таблицы идентификаторов, причем корневым узлом становится первый элемент, встреченный компилятором во входном тексте. Дерево называется бинарным, так как каждая вершина в нем может иметь не более двух вершин (для определенности используют понятия «правая» и «левая» ветви). Схема алгоритма добавления идентификатора приведена на рис. 1.1.
Рис. 1.1. Схема алгоритма добавления идентификатора
Схема алгоритма поиска идентификатора приведена на рис. 1.2.
Рис. 1.2. Схема алгоритма поиска идентификатора
Для данного метода организации таблицы идентификаторов число сравнений зависит от того порядка, в котором поступают идентификаторы, что является существенным недостатком. Также недостатком метода является необходимость хранить две дополнительные ссылки на левую и правую ветви в каждом элементе дерева.
Данный метод основан на хеш-адресации. В таблицу идентификаторов для каждого элемента добавляется еще одно поле, в котором может содержаться ссылка на любой элемент таблицы. Первоначально это поле пустое (никуда не указывает). Также необходима одна специальная переменная, которая всегда будет указывать на первую свободную ячейку в таблице идентификаторов. В ячейках хеш-таблицы храниться либо пустое значение, либо значение указателя на некоторую область памяти в таблице идентификаторов. Хеш-функция вычисляет адрес, по которому происходит обращение сначала к хеш-таблице, а потом уже через нее по найденному адресу – к самой таблице идентификаторов. Для вычисления хеш-функции используется сумма ASCII
-кодов трех первых символов идентификатора. Если идентификатор состоит менее чем из трех символов, то в качестве хеш-функции используется сумма ASCII
-кода имеющихся символов (либо только первого, либо первого и второго).
Метод цепочек является очень эффективным средством организации таблиц идентификаторов. Среднее время на размещение одного элемента и на поиск элемента в таблице идентификаторов зависит только от среднего числа коллизий, возникающих при вычислении хеш-функции. Также происходит экономия используемой памяти за счет промежуточной хэш-таблицы.
Схема алгоритма добавления идентификатора представлена на рис. 1.3.
Рис. 1.3. Схема алгоритма добавления идентификатора
Схема алгоритма поиска идентификатора представлена на рис. 1.4.
Рис. 1.4. Схема алгоритма поиска идентификатора
Достоинства данного метода:
- нет необходимости заполнять пустыми значениями таблицу идентификаторов,
- каждому идентификатору соответствует строго одна ячейка в таблице идентификаторов.
Недостатком метода является организация работы с динамическими массивами.
1.5. Результаты сравнения методов
Поиск информации в таблице идентификаторов выполняется каждый раз, когда компилятору необходимы сведения о том или ином элементе программы. Кроме того, каждому добавлению элемента в таблицу в любом случае будет предшествовать операция поиска – чтобы убедиться, что такого элемента в таблице нет. Следовательно, поиск идентификатора происходит гораздо чаще, чем добавление, поэтому таблица идентификаторов должна быть организована так, время поиска идентификатора было минимально.
На рис. 1.5 представлена экранная форма организации таблицы идентификаторов методом цепочек и методом бинарного дерева.
Рис. 1.5. Экранная форма организации таблицы идентификаторов
В данном случае при наличии во входном файле восемнадцати идентификаторов среднее количество требуемых сравнений для заполнения таблицы идентификаторов методом цепочек оказалось в 8,8 раз меньше, чем методом бинарного дерева, следовательно, и среднее время для организации таблицы идентификаторов методом цепочек значительно меньше, чем методом бинарного дерева.
При добавлении нового идентификатора возможны два случая:
- добавляемого идентификатора в таблице идентификаторов еще нет, добавление происходит успешно, указывается выполненное число сравнений по каждому методу;
- добавляемый идентификатор в таблице идентификаторов уже существует, в поле ошибок выводится соответствующее сообщение, указывается выполненное число сравнений для обнаружения повтора идентификатора по каждому методу.
Экранная форма добавления нового идентификатора представлена на рис. 1.6.
Рис. 1.6. Экранная форма добавления нового идентификатора
Экранная форма добавления существующего идентификатора представлена на рис. 1.7.
Рис. 1.7. Экранная форма добавления существующего идентификатора
В обоих рассмотренных случаях из числа сравнений, выполненных методами цепочек и бинарного дерева, видно, что добавление идентификатора в таблицу идентификаторов методом цепочек происходит значительно быстрее, чем методом бинарного дерева.
При поиске идентификатора также возможны два случая:
- искомый идентификатор в таблице идентификаторов существует, поиск происходит успешно, указывается положение идентификатора в таблице идентификаторов и выполненное число сравнений для обнаружения идентификатора по каждому методу;
- искомый идентификатор в таблице идентификаторов не существует, выводится сообщение о неуспешном поиске и указывается выполненное число сравнений для обнаружения отсутствия идентификатора в таблице идентификаторов по каждому методу.
Экранная форма поиска существующего идентификатора представлена на рис. 1.8.
Рис. 1.8. Экранная форма поиска существующего идентификатора
Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.
Рис. 1.9. Экранная форма поиска несуществующего идентификатора
В обоих рассмотренных случаях число сравнений при поиске идентификатора в таблице идентификаторов выполненное методом цепочек существенно меньше, чем у метода бинарного дерева, то есть метод цепочек осуществляет поиск значительно быстрее метода бинарного дерева. Так как именно время поиска идентификатора определяет эффективность метода, то в дальнейшем для заполнения таблицы идентификаторов исходной программы будет использоваться метод цепочек.
2. Проектирование лексического анализатора
2.1. Исходные данные
Текст на входном языке задается в виде символьного (текстового) файла. Необходимо разработать модуль, выполняющий лексический анализ входного текста, результатом которого является таблица лексем с указанием их типов и значений. Также должны выдаваться сообщения о наличии во входном тексте ошибок, которые могут быть обнаружены на этапе лексического анализа, с указанием их позиций во входном тексте. При обнаружении ошибки выполнение лексического анализа должно прекратиться.
Лексемами данного языка являются:
- ключевыеслова (prog
, end
., begin
, end
, while
,do
, if
, then
, else
);
- скобки ( «(», «)» );
- оператор присваивания ( := );
- операторы сравнения ( >, <, = );
- разделитель ( ; );
- арифметические операции ( +, –, ++);
- шестнадцатеричные константы (тип данных word
);
- идентификаторы;
- логические операции (or
,
not
,
and
).
Кроме перечисленных лексем распознаватель должен определять и исключать из входного текста комментарии (неограниченной длины). Комментарии заключаются в фигурные скобки со звездочкой {*…*}.
2.2. Принцип работы лексического анализатора
Лексический анализатор (или сканер) – это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
Основная задача лексического анализа – разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, то есть выделить эти слова из непрерывной последовательности символов с исключением из входного текста комментариев, незначащих пробелов и переводов строк. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители).
Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем. Этот перечень представляется в виде таблицы, называемой таблицей лексем.
Язык описания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы (КА).
Любой КА может быть задан с помощью пяти параметров:
М
(Q
, V
,δ,q
0
,F
), (2.1)
где: Q
–
конечное множество состояний автомата;
V
–
конечное множество допустимых входных символов (алфавит автомата);
δ – функция переходов, отображающая декартовое произведение множеств V
´Q
во множество подмножеств Q
:R
(Q
);
q
0
 Q
– начальное состояние автомата;
F
 Q
– непустое множество конечных состояний автомата.
Работа автомата выполняется по тактам. На каждом очередном тактеi
автомат, находясь в некотором состоянии qi
ÎQ
, считывает очередной символ v
ÎV
из входной цепочки символов и изменяет свое состояние на q
i
+1
=d(qi
,w
), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i
+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед первым тактом автомат находится в начальном состоянии q
0
.
Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а пометки дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния q
i
в qi
+1
по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q
i
в q
i
+1
.
2.3. Схема распознавателя
Распознавателем лексем входного языка является конечный детерминированный автомат без внешней памяти (приложение Б).
Начальное состояние автомата обозначено H
, конечное S
. В случае ошибочной входной цепочки автомат попадает в состояние ошибки ERR
. При этом работа автомата останавливается. Остальные состояния автомата определяются допустимыми для компилятора исходного языка лексемами.
В графе также используются следующие обозначения:
- ┴ – пробел, табуляция, перевод строки, +, –, =, <, >, (, ), ;, :, {
- ┴c
– перевод строки
- x
0 – любой символ
- x
1 – любой символ, кроме символа *
- x
2 – любой символ, кроме символа }
- x
3 – любой символ, кроме символа ┴
- x
4 – любой символ, кроме символа h
- x
5 – любой символ, кроме символов 0..9, A
..F
- x
6 – любой символ, кроме символа =
- x
7 – любой символ, кроме символа +
- x
8 – символы A
..Z
, c
, f
..h
, j
..m
, q
..s
, u
, v
, x
..z
, _
- x
9 –символы A
..Z
, a
..d
, f
..z
, _
- x
10 – любой символ, кроме символов A
..Z
, a
..z
, _
- x
11 – символыA
..Z
, a
..f
, h
..z
, _
- x
12 – символыA
..Z
, a
..h
, j
..z
, _
- x
13 – символыA
..Z
, a
..g
, i
..z
, _
- x
14 – символыA
..Z
, a
..z
, _
- x
15 – символыA
..Z
, a
..k
, m
..z
, _
- x
16 – символыA
..Z
, a
..m
, o
..z
, _
- x
17 – символыA
..Z
, a
..e
, g
..z
, _
- x
18 –символыA
..Z
, a
..q
, s
..z
, _
- x
19 – символыA
..Z
, a
..n
, p
..z
, _
- x
20 – символыA
..Z
, a
..s
, u
..z
, _
- x
21 – символыA
..Z
, a
..c
, e
..z
, _
- x
22 – символыA
..Z
, a
..k
, m
,o
..z
, _
- x
23 – символыA
..Z
, a
..r
, t
..z
, _
- x
24 – любой символ, кроме символов A
..Z
, a
..z
, _, ┴
- x
25 – символыA
..F
, 0..9
- x
26 – любой символ, кроме символов A
..Z
, a
..z
, _, ┴, '.'
Регулярная грамматика входного языка в форме Бэкуса-Наура имеет вид:
G ( {0..9, A
..Z
, a
..z
, +, – , <, >, =, (, ), ;, :, {, }, *, '.'}, {S
, H
, BEGIN
1, BEGIN
2, BEGIN
3, BEGIN
4, BEGIN
5, WHILE
1, WHILE
2, WHILE
3, WHILE
4, WHILE
5, THEN
1, THEN
2, THEN
3, THEN
4, IF
1, IF
2, PROG
1, PROG
2, PROG
3, PROG
4, VAR
, NOT
1, NOT
2, NOT
3, AND
1, AND
2, AND
3, OR
1, OR
2, DO
1, DO
2, E
1, END
2, END
3, END
4, ELSE
2, ELSE
3, ELSE
4}, P
, S
)
P
:
PROG
1 ®p
PROG
2 ®PROG
1 r
PROG
3 ®PROG
2 o PROG
4 ®PROG
3 g
BEGIN
1 ®b BEGIN
2 ®BEGIN
1 e
BEGIN
3 ®BEGIN
2 g BEGIN
4 ®BEGIN
3 i
BEGIN
5 ®BEGIN
4 n WHILE
1 ®w
WHILE
2 ®WHILE
1 h WHILE
3 ®WHILE
2 i
WHILE
4 ®WHILE
3 l WHILE
5 ®WHILE
4 e
DO
1 ®d DO
2 ®DO
1 o
IF
1 ®i IF
2 ®IF
1 f
THEN
1 ®t THEN
2 ®THEN
1 h
THEN
3 ®THEN
2 e THEN
4 ®THEN
3 n
E
1 ®e ELSE
2 ®E
1 l
ELSE
3 ®ELSE
2 s ELSE
4 ®ELSE
3 e
END
2 ®E
1 n END
3 ®END
2 d
END
4 ®END
3 .AND
1 ®a
AND
2 ®AND
1 n AND
3 ®AND
2 d
OR
1 ®o OR
2 ®OR
1 r
CONST
1 ® 0 CONST
2 ®CONST
1 x
25
CONST
3 ®CONST
2 x
25 CONST
4 ®CONST
3 x
25
CONST
5 ®CONST
4 x
25 CONST
6 ®CONST
5 h
ASSI
1 ® : ASSI
2 ®ASSI
1 =
SEMI
® ; SUB
® –
ADD
® + INC
®ADD
+
OPEN
® ( CLOSE
® )
RAVN
® = MEN
® <
BOL
® >
COMM
1 ® {
COMM
2 ®COMM
1 * | COMM
2 x1
COMM
3 ®COMM
2 *
COMM
4 ®COMM
3 }
VAR
®x
8|BEGIN
1 x
9|BEGIN
2 x
11|BEGIN
3 x
12|BEGIN
4 x
16|BEGIN
5 x
14| VAR
x
14| WHILE
1 x
13|WHILE
2 x
12|WHILE
3 x
15|WHILE
4 x
9| IF
1x
17| WHILE
5 x
14|E
1 x
22| THEN
1 x
13|THEN
2 x
9|THEN
3 x
16|THEN
4 x
14| IF
2 x
14|PROG
1 x
18| PROG
2 x
19|PROG
3 x
11|PROG
4 x
14|OR
1 x
18| OR
2 x
14| NOT
1 x
19|DO
2 x
14| NOT
2 x
20|NOT
3 x
14|AND
1 x
16|AND
2 x
21| AND
3 x
14|END
2 x
21| END
3 x
14|END
4 x
3|ELSE
2 x
23|ELSE
3 x
9| DO
1 x
19|ELSE
4 x
14|
ERR
®BEGIN
1 x
10|BEGIN
2 x
10|BEGIN
3 x
10|BEGIN
4 x
24|BEGIN
5 x
10| DO
1 x
10| WHILE
1 x
10|WHILE
2 x
10|WHILE
3 x
10|WHILE
4 x
10| WHILE
5 x
24| DO
2 x
24| THEN
1 x
10| THEN
2 x
0|THEN
3 x
10|THEN
4 x
24| IF
2 x
24| VAR
x
24| PROG
1 x
10|PROG
2 x
10|PROG
3 x
10|PROG
4 x
24| IF
1 x
10|OR
1 x
10|OR
2 x
24|E
1 x
10| NOT
1 x
10| NOT
2 x
10|NOT
3 x
24| AND
1 x
10|AND
2 x
10|AND
3 x
24|END
2 x
10| END
3 x
26|END
4 x
3| x
3| ELSE
2 x
10|ELSE
3 x
10|ELSE
4 x
24|CONST
1 x
5|INC
x
3| CONST
2 x
5| CONST
3 x
5|CONST
4 x
5|CONST
5 x
4|CONST
6 x
3|ASSI
1 x
6| ASSI
2 x
3| SEMI
x
3|SUB
x
3|ADD
x
7|OPEN
x
3|CLOSE
x
3|RAVN
x
3|MEN
x
3|BOL
x
3| COMM
1 x
1|COMM
2 ┴c
|COMM
3 x
2|COMM
4 x
3
S
®BEGIN
5 ┴|WHILE
5 ┴|DO
2 ┴|THEN
4 ┴|IF
2 ┴|VAR
┴|PROG
4 ┴|OR
2 ┴| NOT
3 ┴|AND
3┴|END
3 ┴|END
4 ┴|ELSE
4 ┴|CONST
6 ┴|ASSI
2 ┴| ADD
┴| SEMI
┴| SUB
┴| UMN
┴|OPEN
┴|CLOSE
┴|RAVN
┴|MEN
┴| BOL
┴|COMM
2 ┴
Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом их характеристик. Этот перечень лексем предоставляется в виде таблицы лексем. Информация об идентификаторах и константах помещается в таблицу идентификаторов.
С теоретической точки зрения лексический анализатор не является обязательной частью компилятора. Все его функции могут выполняться на этапе синтаксического разбора. Но так как он упрощает работу с текстом исходной программы на этапе разбора и сокращает объем обрабатываемой информации, отбрасывая всю незначащую информацию (комментарии, пробел, табуляцию, перевод строки), в данной курсовой работе он используется.
2.4. Результаты работы лексического анализатора
Программа выполняет лексический анализ входного текста в соответствие с заданной грамматикой. Результатом выполнения лексического анализа является таблица лексем с указанием их типов, а также таблица идентификаторов, сформированная методом цепочек. В таблице лексем имеется поле «Адрес», в котором указывается ссылка на место расположения идентификатора в таблице идентификаторов.
Экранная форма работы лексического анализатора представлена на рис.2.1.
Рис. 2.1. Экранная форма работы лексического анализатора
Таблица лексем служит базой для проведения синтаксического анализа и построения дерева вывода в третьей части курсовой работы.
Лексическая ошибка возникает при обнаружении незакрытого комментария, неверного символа в лексеме или если лексема незавершенна (не обнаружен признак окончания лексемы).
Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.
Рис. 2.2. Экранная форма при обнаружении лексической ошибки
В случае обнаружения лексической ошибки программа выдает сообщение об ошибке с указанием ее места в исходном тексте, работа лексического анализатора останавливается.
3. Проектирование синтаксического анализатора
На данном этапе разработанная программа должна выделять и проверять синтаксические конструкции входного языка, то есть выполнить синтаксический анализ входного текста, результатом которого является цепочка вывода, на основе которой строится дерево вывода. На вход синтаксического анализатора поступает таблица лексем, сформированная на этапе лексического анализа. Также программа должна выдавать сообщения о наличии во входном тексте ошибок, которые могут быть обнаружены на этапе синтаксического анализа, с указанием их позиций во входном тексте. При обнаружении ошибки выполнение синтаксического анализа должно прекратиться.
Исходная КС-грамматика имеет вид:
G
({ prog
, end
., begin
, end
, while
, do
, if
, then
, else
, and
, or
, not
, =, <, >, (, ), -, +, ++, a
, c
, ;, :=}, {S
, L
, O
, B
, C
, D
, E
, F
}, P
, S
)
P
:
S
→ prog L end
.
L
→ O
| L
;O
| L
;
O
→ if
(B
) then O else O
| if O then O
| begin L end
| while
(B
) do 0
| a
:=E
| a
++
B
→ B or C | C
C
→ C and D | D
D
→ E
<E | E
>E | E
=E |
(B
) | not
(B
)
E
→E
–F
|
E
+F
|
F
F
→(E
) |
a |
c
3.2. Построение синтаксического анализатора
Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций входной цепочки, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в дерево вывода – вид, удобный для дальнейшей семантической обработки и генерации кода.
Основой для построения синтаксического анализатора являются автоматы с магазинной памятью, или МП-автоматы. В общем виде МП-автомат можно определить следующим образом:
(Q
, V
, Z
,
δ, q
0
, z
0
, F
), (3.1)
где: Q
– множество состояний автомата;
V
– алфавит входных символов автомата;
Z
– специальный конечный алфавит магазинных символов автомата;
δ – функция переходов автомата;
F
–
множество конечных состояний;
q
0
–
начальное состояние автомата;
z
0
–
начальный символ магазина (стека).
Конфигурация МП-автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положение указателя в цепочке) и содержимым стека.
При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой, иначе цепочка символов не принимается.
Для построения распознавателя для языка, заданного КС-грамматикой, воспользуемся алгоритмом «сдвиг-свертка»:
- если на верхушке стека МП-автомата находится цепочка символов g, то ее можно заменить на нетерминальный символ A
при условии, что в грамматике языка существует правило вида A
→ g, не сдвигая при этом считывающую головку автомата («свертка»);
- если считывающая головка автомата обозревает некоторый символ входной цепочки α, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо («сдвиг»).
Распознаватель на основе алгоритма «сдвиг-свертка» является восходящим распознавателем: он читает входную цепочку символов слева направо, строит правосторонний вывод, а дерево вывода строит снизу вверх (от корневых вершин к корню).
Для более легкого построения распознавателя, преобразуем исходную КС-грамматику в грамматику операторного предшествования (это такая приведенная КС-грамматика, в которой правые части всех правил не содержат смежных нетерминальных символов и для которой отношения предшествования можно задать на множестве терминальных символов). При этом для каждой упорядоченной пары терминальных символов определено не более чем одно из трех следующих отношений (=., <., .>).
На основе множества правил грамматики P
определим множества крайних левых и крайних правых символов L
(U
), R
(U
) относительно всех нетерминальных символов грамматики (табл. 3.1).
Таблица 3.1.
Множества крайних левых и крайних правых нетерминальных
символов L
(U
), R
(U
) относительно всех нетерминальных символов грамматики
| Символ (U
) |
Шаг 1 |
Шаг 2 |
| L
(U
) |
R
(U
) |
L
(U
) |
R
(U
) |
| F
|
(, a
, c
|
), a
, c
|
(, a
, c
|
), a
, c
|
| E
|
E
, F
|
F
|
E
, F
, (, a
, c
|
F
, ), a
, c
|
| D
|
E
, (, not
|
E
, ) |
E
, (,a
, c
, not
|
E
, F
, ),a
, c
|
| C
|
C
, D
|
D
|
C
, D
, E
, F
, (, a
, c
, not
|
D
, E
, F
, ), a
, c
|
| B
|
B
, C
|
C
|
B
, C
, D
, E
, F
, (, a
, c
, not
|
C
, D
, E
, F
, ), a
, c
|
| O
|
if
, begin
, while
, a
|
O
, E
, end
, ++ |
if
, begin
, while
, a
|
O
, E
, F
, ), a
, c
, end
, ++ |
| L
|
O
, L
|
O
, ; |
O
, L
, if
, begin
, while
, a |
O
, E
, F
,), a
, c
, end
, ++, ; |
| S
|
prog
|
end
. |
prog
|
end
. |
На основе множества правил грамматики P
и полученных множеств крайних левых и крайних правых символов L
(U
), R
(U
) построим множества крайних левых и крайних правых терминальных символов L
t
(U
), R
t
(U
) относительно всех нетерминальных символов грамматики (табл. 3.2).
Таблица 3.2.
Множества крайних левых и крайних правых
терминальных символов L
t
(U
), R
t
(U
)
| Символ (U
) |
Шаг 1 |
Шаг 2 |
| L
t
(U
) |
R
t
(U
) |
L
t
(U
) |
R
t
(U
) |
| F
|
(, a
, c
|
), a
, c
|
(, a
, c
|
), a
, c
|
| E
|
-, + |
-, + |
(, a
, c
, -, + |
), a
, c
, -, + |
| D
|
<, >, =, (, not
|
<, >, =, ) |
(, a
, c
, -, +, <, >, =, not
|
), a
, c
, -, +, <, >, = |
| C
|
and
|
and
|
(, a
, c
, -, +, <, >, =, not
, and
|
), a
, c
, -, +, <, >, =, and
|
| B
|
or
|
or
|
(, a
, c
, -, +, <, >, =, not
, and
, or
|
), a
, c
, -, +, <, >, =, and
, or
|
| O
|
if
, begin
, while
, a
|
else
, then
, end
, do
, :=, ++ |
if
, begin
, while
, a
|
), a
, c
, -, +, else
, then
, end
, do
, :=, ++ |
| L
|
; |
; |
if
, begin
, while
, a
, ; |
), a
, c
, -, +, else
, then
, end
, do
, :=, ++, ; |
| S
|
prog
|
end
. |
prog
|
end
. |
На основе полученных множеств и правил грамматики G
построим матрицу операторного предшествования (приложение В).
Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому исходную КС-грамматику преобразуем так, чтобы в ней осталось как можно меньше нетерминальных символов (в данном случае два), то есть преобразуем ее в остовную грамматику:
G
({ prog
, end
., begin
, end
, while
, do
, if
, then
, else
, and
, or
, not
, =, <, >, (, ), -, +, ++, a
, c
, ;, :=}, {B
, E
}, P
, E
)
P
:
E
→ prog E end
.
E
→ E
| E
;E
| E
;
E
→ if
(B
) then E else E
| if E then E
| begin E end
| while
(B
) do E
| a
:=E
| a
++
B
→ B or B
| B
B
→ B and B
| B
B
→ E
<E
| E
>E
| E
=E
| (B
) | not
(B
)
E
→ E
–E
| E
+E
| E
E
→ (E
) | a
| c
3.3. Результат
работы синтаксического анализатора
Программа проводит синтаксический анализ исходного теста, поступающего от лексического анализатора на основе правил остовной грамматики. Результатом его работы является дерево вывода.
Экранная форма работы синтаксического анализатора представлена на рис. 3.1.
Рис. 3.1. Экранная форма работы синтаксического анализатора
По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.
Синтаксическая ошибка возникает, если между двумя обозреваемыми символами нет ни одного отношения предшествования, либо не удалось выполнить операцию «свертка», т.е. не найдено правило, совпадающее с основой.
Экранная форма при обнаружении синтаксической ошибки представлена на рис. 3.2.
Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки
В случае обнаружения синтаксической ошибки программа выдает сообщение об ошибке с указанием ее места в исходном тексте, работа синтаксического анализатора останавливается.
Заключение
В результате выполнения курсовой работы для заданного входного языка были построены отдельные фазы компиляции.
В первой части работы разработан модуль, который позволяет сравнить эффективность методов бинарного дерева и цепочек. Получив на входе набор идентификаторов, модуль реализует организацию таблицы идентификаторов обоими методами с возможностью осуществления многократного поиска и добавления идентификаторов.
Было установлено, что заданных методов более эффективным является метод цепочек, так как для него время поиска идентификатора в таблице идентификаторов гораздо меньше, чем для метода бинарного дерева, а именно операция «поиск» является основным критерием сравнения эффективности методов.
Во второй части работы разработан модуль, который выполняет лексический анализ входного текста и порождает таблицу лексем с указанием их типов и значений, а также методом цепочек формирует таблицу идентификаторов, при этом в таблице лексем в поле «Адрес» указывается место расположения идентификатора в таблице идентификаторов. При обнаружении в исходном тексте лексической ошибки выдается сообщение об ошибке, а работа лексического анализатора прекращается.
В третьей части курсовой разработан модуль, который на основе таблицы лексем выполняет синтаксический разбор текста с построением дерева вывода и перечислением всех сработавших правил «свертки». При обнаружении в исходном тексте синтаксической ошибки выдается сообщение об ошибке, а работа синтаксического анализатора прекращается.
Отдельные фазы компиляции, разработанные в данной курсовой работе, дают представление о технике и методах, лежащих в основе построения компиляторов.
Список литературы
1. Гордеев А.В. Молчанов Л.Ю. Системное программное обеспечение. – СПб.: Питер, 2005. – 734с.: ил.
2. Кампапиец Р. II. Манькоп Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Учебное пособие для высших и средних учебных заведений. – СПб.: КОРОНА Принт, 2004. – 256с.: ил.
3. Молчанов Л.Ю. Системное программное обеспечение. Лабораторный практикум. – СПб.: Питер, 2005. – 284с.: ил.
|
