Logo GenDocs.ru

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

Загрузка...

Курсовой проект - файл Пояснительная Записка (v2.0).doc


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

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

input.txt1kb.05.12.2005 02:28скачать
Main.cpp
Main.dfm
Main.h
MethodsCompare.bpr
MethodsCompare.cpp
MethodsCompare.exe
compare_input.txt1kb.06.12.2005 04:07скачать
Coursework.bpr
Coursework.cpp
Coursework.exe
hyper_matrix.txt2kb.03.12.2005 00:18скачать
input.txt1kb.06.12.2005 01:29скачать
Main.cpp
Main.ddp
Main.dfm
Main.h
Rules.txt1kb.03.12.2005 00:16скачать
Пояснительная Записка (v2.0).doc1487kb.07.12.2005 08:42скачать

содержание

Пояснительная Записка (v2.0).doc

  1   2   3   4

Содержание


Лист

Содержание 1

Введение 2

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

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

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

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

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

6

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

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

2.2 Назначение лексического анализатора 7

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

2.4 Результат выполнения программы 9

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

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

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

3.3 Таблицы предшествования 13

Матрица предшествования исходной грамматики 15

3.4 Результат выполнения программы 16

3.5 Вывод 17

Заключение 18

Список литературы 19

Приложение А – Листинги программы 20

Введение


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

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

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

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

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

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

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

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

В качестве среды разработка для реализации программы использован язык программирования C++ и система программирования Borland CBuilder 6.
^

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

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


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

Первый метод организации таблицы – простое рехэширование. Второй – метод бинарное дерево.

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

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


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

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


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

(1)

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

(2)

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

Блок-схема метода простого рехэширования представлена на рисунке 1.1.



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

в) – Блок-схема функции добавления идентификатора

^

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


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

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

Блок-схема метода бинарного дерева представлена на рисунке 1.2



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

в) – Блок-схема функции поиска идентификатора

1.5 Результат выполнения программы


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

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

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

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

  1   2   3   4



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

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

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