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

Содержание
Лист
Введение 2
1 Организация таблицы идентификаторов 3
1.1 Исходные данные 3
1.2 Назначение таблицы идентификаторов 3
1.3 Метод простого рехэширования 3
1.4 Метод бинарного дерева 5
2 Проектирование лексического анализатора 8
2.1 Исходные данные 8
2.2 Назначение лексического анализатора 8
2.3 Схема распознавателя 9
2.4 Результат выполнения программы 10
3 Построение деревавывода 12
3.1 Исходные данные 12
3.2 Синтаксический анализатор 13
3.3 Таблицы предшествования 14
3.4 Матрица предшествования исходной грамматики 16
3.5 Результат выполнения программы 17
3.6 Вывод 18
Заключение 19
Список литературы 20
Приложение А – Листинги программы 21

Введение
Компилятор – программный модуль, задачей которого является перевод программы, написанной на одном изязыков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.
Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером.
Целью данной курсовой работы является изучение составных частей, основных принципов построения и функ¬ционирования компиляторов,практическое освоение методов построения составных частей компилятора для заданного входного языка.
Курсовая работа заключается в создании отдельных частей компилятора заданного языка.
В первой части работы ставится задача разработать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Программадолжна сообщать среднее число коллизий и среднее количество сравнений, выполняемых для поиска идентификатора.
Во второй части работы требуется разработать программу, которая выполняет лексический анализ входного текста по заданной грамматике и порождает таблицу лексем с указанием их типов и значений.
В третьей части работы требуется разработать программу, которая на основании таблицы лексемвыполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора.
Результатами курсовой работы являются программная реализация заданного ком¬пилятора и пояснительная записка, оформленная в соответствии с требования¬ми стандартов и задания на курсовую работу.
В качестве среды разработка для реализации программы использован язык программирования C++ и система программированияBorland CBuilder 6.

1 Организация таблицы идентификаторов
1.1 Исходные данные
На входе имеется набор идентификаторов, которые организуются в таблицу по одному из двух методов (метод простого рехэширования и метод бинарного дерева). Необходима возможность осуществления многократного поиска идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длинаидентификатора ограничена 32 символами.
Первый метод организации таблицы – простое рехэширование. Второй – метод бинарное дерево.
Требуется, чтобы программа сообщала число коллизий и количество сравнений, выполняемых при поиске идентификатора.
1.2 Назначение таблицы идентификаторов
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программена исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице символов или таблице идентификаторов. Любая таблица символов состоит из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Под идентификаторами подразумеваютсяконстанты, переменные, имена процедур и функций, формальные и фактические параметры.
1.3 Метод простого рехэширования
Для организации таблицы идентификаторов по методу рехэширования необходимо определить все хэш-функции для всех Чаще всего функции определяют как некоторую модификацию хэш-функции h. Например, самым простым методом вычисления функции является ее...