Проектирование лексического анализатора

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

Содержание

Введение

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

1.1 Исходные данные

1.2 Назначение таблиц идентификаторов

1.3 Метод простого рехеширования

1.4 Метод простого списка

1.5 Результаты

2. Проектирование лексического анализатора

2.1 Исходные данные

2.2 Принципы работы лексического анализатора

2.3 Схема распознавателя

2.4 Результаты

3. Проектирование синтаксического анализатора

3.1 Исходные данные

3.2 Построение синтаксического анализатора

3.3 Результаты

Заключение

Список использованной литературы

Приложение А Исходный текст программы

Приложение Б Граф состояний лексического анализатора

Приложение В Матрица операторного предшествования

Введение

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

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

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

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

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

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

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

В качестве среды разработки для реализации приложения использован язык программирования Delphi 7 и система программирования Borland Delphi 7.

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

1.1 Исходные данные

На входе имеется набор идентификаторов, которые организуются в таблицу идентификаторов по одному из двух методов:

1. Простое рехеширование.

2. Простой список.

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

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

1.2 Назначение таблиц идентификаторов

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

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

Данные методы основаны на хеш-адресации, то есть на использовании значения, возвращаемого хеш-функцией, в качестве адреса ячейки из некоторого массива данных. Хеш-функция вычисляется путем выполнения над цепочкой символов некоторых простых арифметических и логических операций. Самой простой хеш-функцией для символа является ASCII-код символа.

В данной курсовой работе принята хэш-функция сумма ASCII-кодов первых и пятых символов цепочки.

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

1.3 Метод простого рехеширования

Согласно данному методу, если для элемента А адрес п() = h(A), указывает на уже занятую ячейку, то есть в случае возникновения коллизии, необходимо вычислить значение функции n1 = h1(A) и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(A). И так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет выдается сообщение об ошибке размещения идентификатора в таблице.

Согласно методу простого рехеширования, hi(A) = (h(A)+i) mod Nm, где Nm максимальное значение хэш-функции.

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

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

Рис. 1. Блок-схема добавления элемента в таблицу идентификаторов по методу простого рехеширования

Рис. 2. Блок-схема алгоритма поиска элемента в таблице идентификаторов, организованной по методу простого рехеширования

1.4 Простой список

Простой список является простейшим способом организации ТИ. Он состоит в том, что добавление элементов ведется в порядке их поступления. Поиск в этом случае требует сравнения с каждым элементом ТИ, пока не будет найден подходящий. Для ТИ, содержащей n элементов, в среднем будет выполнено n/2 сравнений. Если n велико, то способ не является эффективным.

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



Рис. 3. Блок-схема добавления элемента в таблицу идентификаторов по простого списка.

Рис. 4. Блок-схема алгоритма поиска элемента в таблицу идентификаторов, организованной по методу простого списка.

1.5 Результаты

Для сравнения метода простого рехеширования и простого списка выбран текстовый файл, содержащий 20 строк.

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

Таблица 1

	Метод простого рехеширования	Простой список
Коллизий	5
Сравнений	3	17
Среднее число сравнений	0,058	0,8571

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

Недостатки метода простого рехеширования:

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

среднее время на размещение элемента и на поиск элемента в таблице зависит от заполненности таблицы идентификаторов и качества используемой хеш-функции;

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

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

Достоинства простого списка:

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

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

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

Недостатком метода простого списка является большое время поиска.

Простое рехеширования является более эффективным методом организации таблицы идентификаторов. Именно он и будет в дальнейшем использован для хранения информации об идентификаторах в курсовой работе.

2. Проектирование лексического анализатора

2.1 Исходные данные

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

В соответствии с заданием должны распознаваться:

ключевые слова : «prog», «end.», «begin», «end», «if», «then», «else», «while», «do», «and», «or», «not»;

идентификаторы: любые последовательности латинских символов и цифр; идентификатор должен начинаться с символа;

константы: двоичное представление числа;

знаки операций: «=», «<», «>», «-», «+», «*», «/»;

оператор присваивания: «:=»;

разделитель: «;»;

комментарии, заключенные в «{», «}».

2.2 Принципы работы лексического анализатора

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

Конечный автомат задается пятеркой:

M=(Q,,,q0,F), где:

Q - конечное множество состояний автомата;

- конечное множество допустимых входных символов;

- множество функций перехода автомата;

q0 Q - начальное состояние автомата;

FQ - множество конечных состояний автомата.

Работа автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии qiQ, считывает очередной символ vV из входной цепочки символов и изменяет свое состояние на qi+1=(qi,v), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом . Считается также, что перед тактом 1 автомат находится в начальном состоянии q0.

Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют входному символу. Если функция перехода предусматривает переход из состояния q в q' по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q'.

2.3 Схема распознавателя

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

Начальное состояние автомата на рисунке обозначено "Н". В случае ошибочной входной цепочки автомат попадает в состояние ошибки E. При этом работа автомата останавливается.

Кроме того, типичными для автомата являются состояния I (переменная) и G (константа). Остальные состояния автомата определяются допустимыми для компилятора исходного языка лексемами.

Каждый переход в конечное состояние "S" сообщает о конце текущей входной цепочки. В этом случае производится анализ распознанной цепочки и перезапуск автомата для очередной входной цепочки символов. Заметим также, что возможна повторная обработка некоторых символов входной цепочки символов. Это необходимо в тех случаях, когда символ, приведший к переходу автомата в конечное состояние, является началом следующей цепочки символов.

2.4 Результаты

На основе сравнения методов организации таблиц идентификаторов, проведенного в первой части курсовой работы, выбран метод простое рехэширования. На основе таблицы идентификаторов, заполненной по методу простого рехеширования, организована таблица лексем. На рис. 5 и рис. 6 представлены таблица идентификаторов и таблица лексем, построенные при обработке следующего текстового файла:



Рис. 5. Результат работы лексического анализатора таблица лексем

Рис. 6. Результат работы лексического анализатора таблица индефикаторов

3. Проектирование синтаксического анализатора

3.1 Исходные данные

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

3.2 Построение синтаксического анализатора

Исходная КС-грамматика:

G ({ prog, end., if, then, else, endif, begin, end, , white, do, and, or, not, =, <, >, (, ),{, }, -, +, *, /, a, c, ;, :=}, {S, L, O, B, C, K, D, H, E, T, M},P, S)

P:

S > prog L end.

L > O | L ; O | L ;

O > if B then O else O endif | if B then O endif | begin L end

| while (B) do O| M

M> a:=E

B > B or C | C

C > C and D | D

D >not D | H

H > E < E | E > E | E = E | (B)

E > E - T | E + T | E * T | E / T| T

T > (E) | a | c

Смысл нетерминальных символов грамматики:

S - вся программа,

L - последовательность операторов(может состоять из одного оператора),

O - оператор,

B, C, D - логическое выражение и его элементы,

H - операции сравнения или логические выражения в скобках,

E,T - арифметические выражения и его элементы,

a - переменная,

с - константа.

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

Грамматикой операторного предшествования называется приведенная КС-грамматика без -правил, в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования строится матрица операторного предшествования, которая содержит только терминальные символы грамматики. Отношения =, < и > называют отношениями предшествования.

Исходная КС-грамматика, представленная выше, является грамматикой операторного предшествования.

Строятся множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 2.

Таблица 2

U	L(U)	R(U)
T	(, a, c	), a, c
E	E, T	T
H	(, E	E, )
D	not, H	D, H
C	C, D	D
B	B, C	C
O	if, begin, while, (	endif, end, O, M
M	a	E
L	L, O	O, ;
S	prog	end.

На основе полученных множеств строятся множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 3.

Таблица 3

U	Lt(U)	Rt(U)
T	(, a, c	), a, c
E	-, +,*, /, (, a, c	-, +,*, /, ), a, c
H	<, >, =, (, -, +,*, /, a, c	<, >, =, ), -, +,*, /, a, c
D	not, <, >, =, (, -, +,*, /, a, c	not, <, >, =, ), -, +,*, /, a, c
C	and, not, <, >, =, (, -, +,*, /, a, c	and, not, <, >, =, ), -, +,*, /, a, c
B	or, and, not, <, >, =, (, -, +,*, /, a, c	or, and, not, <, >, =, ), -, +,*, /, a, c
O	if, begin, while, a	endif, end, do, :=, -, +, ), a, c
M	a	:=, -, +, ), a, c
L	;, if, begin, a	;, endif, end, do, :=, -, +, ), a, c
S	prog	end.

На основе данных множеств и правил исходной КС-грамматики G построим матрицу операторного предшествования, которая представлена в приложении В.

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

Остовная грамматика, полученная на основе исходной грамматики:

G' ({ prog, end., if, then, else, endif, begin, end, for, to, downto, do, and, or, not, =, <, >, (, ), -, +,*, /, a, c, ;, :=}, {E}, P', S)

E > program E end.

E > E | E ; E | E ;

E > if E then E else E endif | if E then E endif| begin E end| while (E) do E| E

E > a:=E

E > E or E | E

E > E and E | E

E > not E | E

E > E < E | E > E | E = E | (E)

E > E - E | E + E | E * E| E / E | E

E > (E) | a | c

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

Преобразованная остовная грамматика имеет следующий вид:

G' ({ prog, end., if, then, else, endif, begin, end, for, to, downto, do, and, or, not, =, <, >, (, ), -, +,*, /, a, c, ;, :=}, {E}, P', S)

E > program E end.

E > E | E ; E | E ;

E > if B then E else E endif | if B then E endif | begin E end |while (E) do E| E

E > a:=E

B > B or B | B

B > B and B | B

B > not B | B

B > E < E | E > E | E = E | (B)

E > E - E | E + E | E * E| E / E | E

E > (E) | a | c

3.3 Результаты

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

На вход подается следующий текстовый файл:

prog

while ( df > 0 ) do begin {

ddd }

if ( vxb > 0 ) and ( a = b ) then begin

c := nb / 0110 + 101 ;

d := 10110 ;

end

else c := 1011 endif

end

end.prog

if (p=0110b) then begin y := h; end

endif; {komment }

for k:=0011b to u do k:=k+00101b;

end.

Результат работы синтаксического анализатора представлены на рис. 7.

Рис. 7. Результат построения дерева разбора

На вход подается следующий текстовый файл:

prog

while ( df > 0 ) do begin

if ( vxb > 0 ) and ( a = b ) then begin

c := nb / 0110 + 101 ;

d := 10110 ; )

end

else c := 1011 endif

end

end.prog

if (p=0110b) then begin y := h; end

endif; {komment }

for k:=0011b to u do k:=k+00101b;

begin

end.

Результат работы синтаксического анализатора при подаче на вход анализатора ошибочных конструкций представлен на рис. 8.

Рис. 8. Результат построения дерева разбора при подаче на вход анализатора ошибочных конструкций

Заключение

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

Список использованной литературы

1. Системное программное обеспечение: Учебник для вузов/ А.Ю. Молчанов- СПб.: Питер, 2003.- 396 с.

2. Системное программное обеспечение. Лабораторный практикум/ А.Ю. Молчанов- СПб.: Питер, 2005.- 284 с.

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