Разработка отдельных фаз компиляции для заданного входного языка

Размещено на http://www.allbest.ru/

Уфимский государственный авиационный технический университет

Кафедра Технической Кибернетики

Разработка отдельных фаз компиляции для заданного входного языка

по дисциплине «Системное программное обеспечение»

1304.143072.000_ПЭ3

Группа САУ-301 Фамилия, И.,О.

Студент Новикова Т.С.

Консультант Левков А. А.

Принял Левков А. А.

Уфа-2014



Оглавление

Введение

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

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

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

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

1.4 Метод упорядоченного списка

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

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

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

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

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

2.4 Результаты

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

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

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

3.3 Результаты

Заключение

Список использованной литературы

Приложение А. Блок-схемы лексического анализатора и синтаксического анализаторов

Приложение Б. Граф состояний лексического и синтаксического анализатора



Введение

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

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

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

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

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

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

В качестве среды разработки для реализации приложения использован язык программирования С # и среда программирования Visual Studio.



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

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

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

Простое рехеширование.

Упорядоченный список.

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

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

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

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

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

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

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

Согласно данному методу, если для элемента А адрес

п() = h(A),

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

n1 = h1(A)

и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(A). И так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) не совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет выдается сообщение об ошибке размещения идентификатора в таблице.

Согласно методу простого рехеширования,

hi(A) = (h(A)+i) mod Nm,

где Nm максимальное значение хэш-функции.

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

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



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

1.4 Метод упорядоченного списка

Этот метод является простым методом построения таблиц идентификаторов. Элементы записываются в таблицу в порядке возрастания. Так как упорядочивание таблицы идентификаторов происходит на всех этапах обращения к таблице, то для ее построения можно пользоваться только алгоритмом прямого упорядоченного включения элементов. При добавлении нового элемента в таблицу идентификаторов он сначала добавляется в конец таблицы, а затем идет переупорядочивание элементов таблицы идентификаторов. Эффективным методом для поиска элементов является логарифмический поиск, на каждом шаге которого, число элементов, которые могут содержать искомый элемент, сокращается в два раза. Максимально число сравнений при поиске 1+log2(N). [1]

Недостатком такого метода является требование упорядочивания таблицы идентификаторов на всех этапах обращения к этой таблице.

К положительным качествам метода можно отнести простоту его организации.

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

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



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

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

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

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

ключевые слова: «program», «function», «integer», «var», «until », «if», «repeate »;

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

круглые открывающиеся и закрывающиеся скобки;

константы: шестнадцатиричное представление числа;

знаки операций: «=», «*», «/»;

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

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

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

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

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

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

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

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

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

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

Любой КА может быть задан с помощью пяти параметров:

М(Q, V,д,q0,F),

где: Q - множество состояний автомата;

V - конечное множество допустимых входных символов;

- функция переходов автомата;

q0 Q - начальное состояние автомата;

FQ - множество конечных состояний автомата.

Алгоритм работы простейшего лексического анализатора:

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

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

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

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

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

Блок схема лексического анализатора:

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

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

Входная головка - в каждый момент читает одну входную ячейку. За один шаг входная головка может сдвинуться на одну ячейку влево, вправо и остаться неподвижной.

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

Размещено на http://www.allbest.ru/

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

Входная головка - в каждый момент читает одну входную ячейку. За один шаг входная головка может сдвинуться на одну ячейку влево, вправо и остаться неподвижной.

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

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

Устройство управления с конечной памятью - программа, управляющая поведением распознавателя. Может являться аналогом конечного автомата. Определяет перемещение входной головки и работу с памятью на каждом шаге (такте). Переходит за шаг из одного состояния в другое.

Конфигурация распознавателя - мгновенный снимок, на котором изображены:

состояние устройства управления;

содержимое входной ленты;

содержимое памяти.

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

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

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

Язык, определяемый распознавателем - это множество цепочек, которые он допускает.

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

Язык L праволинейный тогда и только тогда, когда он определяется конечным, односторонним детерминированным автоматом.

Язык L контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью.

Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно ограниченным автоматом.

Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга.

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

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



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

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

2.4 Результаты

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

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

- операторы цикла с перечислением по заданной переменной вида

“if <переменная> = <выражение> then repeat <переменная> = <выражение> until if <переменная> = <выражение> then <переменная> := <выражение>;

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

ключевые слова: «program», «function», «integer», «var», «until », «if», «repeate »;

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

круглые открывающиеся и закрывающиеся скобки;

константы: шестандцатиричное представление числа;

знаки операций: «=», «*», «/»;

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

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

Экранная форма результатов разрешения коллизий методом упорядоченного списка



Экранная форма результатов разрешения коллизий методом простого рехеширования

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

Экранная форма вывода ошибки.

Чтобы выявить эффективность методов, нужно провести тесты.

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

Тест для упорядоченного списка

Несмотря на одинаковое время выполнения метод рехэширования более предпочтителен, так как он имеет меньшее количество операций.



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

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

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

Входной язык задан с помощью следующей КС-грамматики:

G({program, end., if, then, repeat, until, begin, end, =, (, ), ++, /, a ;, :=,}, {S, L, O, B, C, D, E, T}, P,S))

с правилами Р:

S program L end.

L X | Y | W | R

X if B then L | if B then L else L

Y begin L end;

W repeat T until B

R i:= i|i:=c|i++

B i < c | i > c | i= c|c< i|c>i|c=i

Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

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

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

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

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

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

Класс КС-языков допускает распознавание с помощью недетерминированного автомата со стековой (или магазинной) памятью - МП-автомата.

Схема МП-автомата представлена на рисунке

Размещено на http://www.allbest.ru/

Рис. Схема МП-автомата

МП-автоматом выполняется алгоритм «сдвиг-свертка» для грамматики операторного предшествования. Для моделирования его работы необходима входная цепочка символов и стек, в котором автомат может обращаться не только к самому верхнему символу, но и к некоторой цепочке символов на вершине стека. После завершения алгоритма «сдвиг-свертка» решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в состоянии, когда в стеке находятся начальный символ грамматики и символ конца строки. Выполнение алгоритма может быть прервано, если на одном из его шагов возникла ошибка.

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

Взаимодействие двух анализаторов (последовательный метод)

3.3 Результаты

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



Заключение

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

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

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

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

В третьей части курсовой работы разработан синтаксический анализатор, построенный на основе КС-грамматики операторного предшествования, который на основе таблицы лексем выполняет синтаксический разбор текста с построением дерева вывода и перечислением всех сработавших правил «свертки». При обнаружении в исходном тексте ошибки выдается сообщение об ошибке, а работа синтаксического анализатора прекращается. Анализ типа обнаруженной ошибки не производится.



Список использованной литературы

1. Молчанов А.Ю. «Системное программное обеспечение»

2. Карпушин А.Н., Макаров П.С. Конспект лекций по СПО: Основы трансляции

3. Левков А.А. Конспект лекций по СПО

4. http://habrahabr.ru

5. http://ci-sharp.ru/



Приложение А. Блок-схемы лексического и синтаксического анализаторов

Лексический анализатор

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



Приложение Б. Граф состояний лексического анализатора

идентификатор лексический синтаксический анализатор

Граф переходов КА для операторов:

Граф переходов для констант



Граф переходов для комментариев и идентификатора

Размещено на Allbest.ru