ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА  
РОССИЙСКОЙ ФЕДЕРАЦИИ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ 

САНКТ-ПЕТЕРБУРГСКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ВОДНЫХ  КОММУНИКАЦИЙ

 

Факультет информационных технологий

 

Кафедра вычислительных систем и информатики

 
 
 

ЯЗЫКИ ПРОГРАММИРОВАНИЯ

 
 
 
 
 

Лабораторная  работа 1, 2

 
 

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

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

 
 
 
 
 
 
 
 
 
 

Выполнила: студент группы ИП-31

 
 

     Проверила :Крупенина Н.В.

 
 
 
 
 
 
 
 

2010 г.

 

Оглавление

 

Введение

 

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

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

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

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

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

       В качестве среды разработки для реализации приложения использован язык программирования С++ и система программирования MS Visual C++ v.6.

 

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

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

 

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

1. Простое рехэширование.
2. Метод бинарного дерева.

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

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

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

 

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

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

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

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

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

 

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

 

       Согласно  данному методу, если для элемента А адрес п₍₎ = h(A), указывает на уже занятую ячейку, то есть в случае возникновения коллизии, необходимо вычислить значение функции n₁ = h₁(A) и проверить занятость ячейки по адресу n₁. Если и она занята, то вычисляется значение h₂(A). И так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h_i(A) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет - выдается сообщение об ошибке размещения идентификатора в таблице.

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

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

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

 

 

       

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

 

      

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

         Построение таблиц идентификаторов по методу бинарного дерева

 

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

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

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

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

       ТЗ = N*О(log2 N).

       TП  = О(log2 N).

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

 

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

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

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

 

Результаты  работы программы:

 
 

Из данного  примера видно, что метод рехеширования  для поиска идентификаторов эффективнее  в 5 раз.

 

 

Следующий результат приведён для поиска всех идентификаторов.

 

 

Входной файл содержит 39 идентификаторов:

 

bbbb

bbbbbb

bbbbbbbbbbb

bbbbbbbbbbbbb

bbbbb

uygygbhk

b

aaa

aaaa

aaaaa

cccccc

cccccccc

ergeg

 

etgtrhr

txt

texet

teeexeeet

gersgtpekh

shryrphjlksrpjlks

ryjsrpyjkrsypkj

rsyjpkrsypjk

ffff

fffff

fddffffffff

fewrgleprgl

ewthorjksohk

 

e

bbbbbbbb

bbbbbbb

bbbbbbbbb

sthosrkhoe

hrtohkrtokh

setjhkgjseth

sehtsert

hsethsethsrtbvtsrhb

resthsrh

srthsrhg

brsh

ggg  
 

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

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

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

 

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

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

- ключевые слова : «for», «do»

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

- константы: целые, десятичные числа в экспоненциальной форме и с плавающей точкой;

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

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

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

      - комментарии, заключенные в «/*», «*/».