Организация таблиц компилятора

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет математики и информатики

Отчет по лабораторной работе №6

Выполнили:

студенты группы М-42

Жак Т. Ю.

Овчинникова К.В.

Проверил:

Сенашова М. Ю.

КРАСНОЯРСК 2005 г.

Задание:

Организация таблиц компилятора

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

Программа должна (основные функции):

1) читать текст из файла с исходным кодом (идентификаторами)

2) размещать их в таблицах с использованием указанных методов

3) выполнять поиск указанных идентификаторов по требованию пользователя

Выбранная хэш-функция:

Первый символ идентификатора.

Организация таблицы идентификаторов методом упорядочивания:

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

Алгоритмы поиска:

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

2.  В таблице ищем строку, соответствующую первому символу данного идентификатора. Затем в этой строке производим поиск идентификатора, равного данному. Выдаем его позицию в таблице.

Анализ эффективности.

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

Но создание кодов, как для организации, так и для поиска, 2 методом сложнее.

Таким образом, 2 метод эффективнее применять при больших размерностях текста идентификаторов.