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

Содержание

 

	Лист
Введение	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. Вычислить значение хеш-функции n_i для нового элемента A_i. Если ячейка хеш-таблицы по адресу n_i пустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе перейти к шагу 3.

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

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

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

Шаг 5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента A_i (поле ссылки должно быть пустым), в переменную 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, указывает на уже занятую ячейку, то необходимо вычислить значение функции n₁ = h₁{A) и проверить занятость ячейки по адресу n₁. Если и она занята, то вычисляется значение h₂(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h_i(A) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет — выдается информация об ошибке размещения идентификатора в таблице.

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

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

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

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

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

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

 

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

 

1.5 Результаты

 

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

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

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

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

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

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

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

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

 

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

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

 

 

 

 

 

 

 

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

 

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

 

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

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

 

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

 

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

Работа автомата выполняется  по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии q_iÎQ, считывает очередной символ wÎS из входной цепочки символов и изменяет свое состояние на q_i+1=d(q_i,w), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед тактом 1 автомат находится в начальном состоянии q₀.

Графически автомат  отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы  из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния 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 Исходные данные