Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Курсовой проект - файл ПЗ.doc


Курсовой проект
скачать (204.7 kb.)

Доступные файлы (5):

ПЗ.doc280kb.09.06.2006 00:29скачать
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА.doc148kb.09.06.2006 00:29скачать
Приложение А.doc110kb.09.06.2006 00:29скачать
Приложение Б.doc152kb.09.06.2006 00:29скачать
Приложение В.doc256kb.09.06.2006 00:29скачать

содержание
Загрузка...

ПЗ.doc

Реклама MarketGid:
Загрузка...
Содержание





Лист

Введение

2

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

3

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

3

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

3

1.3 Метод цепочек

3

1.4 Метод бинарного дерева

7

1.5 Результаты

9

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

10

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

10

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

10

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

11

2.4 Результаты

12

3 Построение дерева вывода

13

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

13

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

13

3.3 Результаты

17

Заключение

19

Список использованных источников

20

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

21

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

22

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

23






Введение


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

Для выполнения курсовой работы использована среда программной разработки Microsoft Visual Studio.NET 2003 с дополнительно интегрированной библиотекой классов Trolltech Qt v4.0.1.


1 Таблица идентификаторов


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


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

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


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


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

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


^ 1.3 Метод цепочек


Метод цепочек работает по следующему алгоритму:

Шаг 1. Во все ячейки хеш-таблицы поместить пустое значение, таблица идентификаторов пуста, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i:=1.

Шаг 2. Вычислить значение хеш-функции ni для нового элемента Ai. Если ячейка хеш-таблицы по адресу ni пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе перейти к шагу 3.

Шаг 3. Положить j:=1, выбрать из хеш-таблицы адрес ячейки таблицы идентификаторов mj и перейти к шагу 4.

Шаг 4. Для ячейки таблицы идентификаторов по адресу mj проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе j:=j+1, выбрать из поля ссылки адрес mj и повторить шаг 4.

Для наглядности на рисунке 1 изображена блок-схема алгоритма.

Шаг 5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента Ai (поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе i:=i+1 и перейти к шагу 2.

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

Шаг 1. Вычислить значение хэш-функции n для A. Если ячейка хэш-таблицы по адресу n пустая, то элемент не найден и алгоритм завершен, иначе выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов m.

Шаг 2. Сравнить имя элемента в ячейке таблицы идентификатов по адресу m с именем искомого элемента А. Если они совпадут, то искомый элемент найден, и алгоритм завершон, иначе перейти к шагу 3

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

Рисунок 1 – Блок-схема организации таблицы идентификаторов по алгоритму «метод цепочек».



Рисунок 2 – Блок-схема поиска элемента в таблице идентификатора организованной по алгоритму «метод цепочек»


^ 1.4 Метод рехеширования с псевдослучайным числом


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

Поиск элемента ^ А в таблице идентификаторов будет выполняться по следующему алгоритму:

Шаг 1. Вычислить значение хэш-функции п = h(A) для искомого элемента А.

Шаг 2. Если ячейка по адресу п пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке п с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i := 1 и перейти к шагу 3.

Шаг 3. Вычислить пi = hi(A). Если ячейка по адресу ni пустая или п = пi, то элемент не найден и алгоритм завершен, иначе — сравнить имя элемента в ячейке пi с име­нем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i := i + 1 и повторить шаг 3.

Для наглядности на рисунке 3 изображена блок-схема поиска.

Для организации таблицы идентификаторов по методу рехэширования необходи­мо определить все хэш-функции hi для всех i. Чаще всего функции hi определяют как некоторые модификации хэш-функции h. В данной курсовой работе используется рехэширование с псевдослучайными числами по формуле hi(A) = (h(A) + pi) mod Nm., где pi – псевдослучайное число.




Рисунок 3 – Блок-схема алгоритма поиска по методу рехеширования с псевдослучайным числом.


1.5 Результаты


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

В результате работы программы получены следующие данные:

– метод цепочек:

– всего сравнений: 690;

– в среднем сравнений: 3,63;

– метод рехеширования с псевдослучайным числом:

– всего сравнений: 639;

– в среднем сравнений: 3,36.


На основе полученных результатов можно сделать следующие выводы: при относительно небольшом количестве идентификаторов оба метода показывают примерно одинаковые результаты. В нашем случае при использовании 1068 идентификаторов среднее количество требуемых сравнений для метода цепочек оказалось на 0,27 сравнений больше, чем для метода рехеширования с псевдослучайным числом.

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


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


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


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

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


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


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

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

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


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


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

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

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

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

Схема распознователя представлена в приложении А.


2.4 Результаты


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

program

(* Это

комментарий * (* * *)

begin

a:=11010111;

for i:=10101 downto 0 do

begin

a:=a+1;

end;

if a>0 then a :=11 else i:=0 endif

end ; end.

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



Рисунок 4 – Результат работы лексического анализатора.

Перемменые вида “5per” будут распозанаватся как ошибки, так же ошибкой будет считаться не двоичное число, или число значение которого больше 255, так как числа по заданию должны быть двоичными и типа Byte.

3 Построение дерева вывода


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


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


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


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

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

^ S → program L end.

L → O | O ; O | L ;

O → if B then O else O endif | if B then O endif | begin L end | for M downto E 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 | E <> E | (B) | E << E | E >> E

EET | E + T | T

T → (E) | a | c


Где a это переменная а с констата

Множества крайних левых и крайних правых нетерминальных символов L(U), R(U) представлены в таблице 1.


Таблица 1

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, for, M

endif, end, O, M

M

a

E

L

L, O

O, ;

S

program

end.


В таблице 2 описаны результирующие множества крайних левых и крайних правых нетерминальных символов L(U), R(U).

Таблица 2

U

L(U)

R(U)

T

(, a, c

), a, c

E

E, T, (, a, c

T, ), a, c

H

E, T, (, a, c

E, ), T, a, c

D

not, H, E, T, (, a, c

D, H, E, ), T, a, c

C

C, D, not, H, E, T, (, a, c

D, H, E, ), T, a, c

B

B, C, D, not, H, E, T, (, a, c

C, D, H, E, ), T, a, c

O

if, begin, for, M, a

endif, end, O, M, E, T, ), a, c

M

a

E, T, ), a, c

L

L, O, if, begin, for, M, a

O, ;, endif, end, M, E, T, ), a, c

S

program

end.


Множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) представлены в таблице 3.


Таблица 3

U

Lt(U)

Rt(U)

T

(, a, c

), a, c

E

-, +

-, +

H

<, >, =, <>, (, <<, >>

<, >, =, <>, ), <<, >>

D

not

not

C

and

and

B

or

or

O

if, begin, for

endif, end, do

M

a

:=

L

;

;

S

program

end.


Итоговые множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики представлены в таблице 4


Таблица 4

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, for, a

endif, end, do, :=, -, +, ), a, c

M

a

:=, -, +, ), a, c

L

;, if, begin, for, a

;, endif, end, do, :=, -, +, ), a, c

S

program

end.



Матрица операторного предшествования представлена в виде таблицы, в приложении Б.


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


G' ({ program, end., if, then, else, endif, begin, end, for, 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 | for E downto 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

E → (E) | a | c


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

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


G' ({ program, end., if, then, else, endif, begin, end, for, 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 | for E downto 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 | E <> E | (B) | E << E | E >> E

E → E – E | E + E | E

E → (E) | a | c




Ошибки при синтаксическом аналие возникают при несоблюдений правил грамматики. Например “ if a>c else a-1 ten a+1” вызовет синтаксическую ошибку.


3.3 Результаты

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

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

program


(* Это

комментарий * (* *

*)

begin

a:=11010111;


for i:=10101 downto 0 do

begin

a:=a+1;

end;

if a>0 then a :=11 else i:=0 endif

end ;

end.

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



Рисунок 5 – Результат построения дерева вывода


Исходный текст программы приведен в приложении B.


Заключение


В процессе выполнения курсовой работы была разработана программа, реализующая компилятор заданного подмножества языка Паскаль с незначительными модификациями. Для ее разработки использовалась среда Microsoft Visual Studio .NET 2003 с дополнительно интегрированной библиотекой классов Trolltech Qt v4.0.1.


Список использованных источников


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

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

3. Разработка графического интерфейса с помощью библиотеки Qt3/ Дж. Бланшетт, М. Саммерфелд, 2003.

4. http://www.fi.ru/~mill/ Личная страничка А.Ю. Молчанова.


Скачать файл (204.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru