Подготовка к выполнению работы

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

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

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

Таблица 1. – Сводная информация о лабораторных работах

Готовность студента к работе определяется преподавателем путем проведения собеседования. Основным материалом для собеседования являются контрольные вопросы, приведенные в разделе, посвященном выполнению конкретной лабораторной работы.

Для выполнения лабораторных работ студент должен иметь минимальные навыки программирования в Delphi.

Защита лабораторной работы производится после написания студентом программы и оформления отчета.

Структура разделов, посвященных выполнению лабораторных работ:

1 Цель работы. В этом разделе определяется, какие навыки должен приобрести студент в ходе выполнения лабораторной работы.

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

3 Фрагменты программ. Содержимое этих пунктов демонстрирует реализацию ранее изложенного материала. Эти фрагменты могут быть использованы студентом при выполнении задания.

4 Контрольные вопросы.

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

6 Содержание отчета о выполнении лабораторной работы.

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

3 Лабораторная работа №1 “Использование конечного автомата для построения лексического анализатора”

3.1 Цель работы

Целью проведения лабораторной работы является:

- закрепление теоретических знаний в области построения лексических анализаторов;

- получение начальных навыков описания языков в виде регулярных выражений;

- приобретение опыта построения лексических анализаторов с использованием конечных автоматов;

- получение навыков реализации конечных автоматов.

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

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

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

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

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

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

- описание распознаваемого языка в форме регулярных выражений;

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

- преобразование недетерминированного конечного автомата к детерминированному;

- минимизация конечного автомата.

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

3.2.1 Описание распознаваемого языка в форме регулярного

выражения.

Определим, что является регулярным выражением:

1 Пустая строка e является регулярным выражением.

2 Если элемент а принадлежит алфавиту описываемого языка, то а – регулярное выражение.

3 Если r и s регулярные выражения, обозначающие языки L(r) и L(s), то регулярными являются следующие выражения:

а) r | s – объединение языков, то есть утверждается, что элемент должен принадлежать или языку L(r) или языку L(s);

б) r s – конкатенация языков, то есть утверждается, что за элементом языка L(r) следует элемент языка L(s);

в) r* - замыкание Клини языка, то есть ноль или более символов языка L(r);

г) (r) – регулярное выражение в скобках

Кроме того, для описания языков используются операция r+, означающая один или более символов языка r, и операция r?, означающая ноль или один символ языка r.

Опишем букву азбуки Морзе в форме регулярного выражения. Сначала рассмотрим базовый случай. Элементы точка, тире и пробел принадлежат алфавиту распознаваемого языка, следовательно, существуют регулярные выражения “точка”, “тире” и “пробел” (по правилу 2). За каждой точкой или тире следует пробел, следовательно, существуют регулярные выражения “точка пробел” и “тире пробел” (по правилу 3б). В букве может встречаться либо точка с пробелом, либо тире с пробелом, следовательно, имеет место регулярное выражение “точка пробел | тире пробел” (по правилу 3а). Такая последовательность может встретиться в букве множество раз, а может и не встретиться вообще, то есть регулярное выражение имеет вид “(точка пробел | тире пробел)*” (по правилам 3г и 3в). Буква должна заканчиваться пробелом, то есть регулярное выражение для распознавания буквы азбуки Морзе выглядит следующим образом

(точка пробел | тире пробел)* пробел

3.2.2 Преобразование регулярного выражения в недетерминированный конечный автомат

Конечный автомат это пятерка (S, S, d, S₀, F)

S - конечное множество состояний.

S - конечное множество допустимых входных сигналов.

d - функция переходов. Она отражает множество Sх(SÈ {e}) в множество состояний недетерминированного конечного автомата. Для детерминированного автомата функция переходов отражает множество SхS во множество состояний автомата. Другими словами, в зависимости от состояния и входного символа, d определяет новое состояние автомата.

S₀ - начальное состояние конечного автомата, S₀ Î S.

F - множество конечных состояний автомата, F Î S.

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

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

1 Регулярное выражение “e” преобразуется в автомат из двух состояний и e -перехода между ними (рисунок 1).

Рисунок 1. – Автомат для e-перехода

2 Регулярное выражение из одного символа “а” преобразуется в конечный автомат из двух состояний и перехода между ними по входному сигналу а (рисунок 2).

Рисунок 2. – Автомат для перехода по символу а

3 Пусть есть регулярное выражение rs и уже построены конечные автоматы для выражения r и выражения s. Тогда два автомата соединяются последовательно. На рисунке 3 представлены исходные автоматы для языков r и s. На рисунке автомат для распознавания конкатенации этих языков.

Автомат для r Автомат для s

Рисунок 3. – Исходные автоматы

Рисунок 4. – Автомат для конкатенации языков

4 Пусть есть регулярное выражение r | s и уже построены конечные автоматы для выражения r и выражения s (рисунок 3). Тогда в результирующем автомате должна быть альтернатива выполнения одного из двух автоматов. То есть автомат для выражения r | s при автоматах для r и s с рисунка 3 имеет вид, представленный на рисунке 5.

Рисунок 5. – Автомат для объединения языков

5 Пусть есть регулярное выражение r* при построенном конечном автомате r. В этом случае вводятся два новых состояния для возможности обхода автомата выражения r, а также вводится e-переход между конечным и начальным состояниями для возможности многократного повторения автомата r. Если для регулярного выражения r построен автомат аналогичный рисунку 3, то регулярному выражению r* соответствует конечный автомат, представленный на рисунке 6.

Рисунок 6. – Автомат для замыкания Клини языка

Построим конечный автомат для регулярного выражения

(точка пробел | тире пробел)* пробел

Сначала построим конечные автоматы для регулярных выражение “точка”, “тире” и “пробел” по правилу 2. Эти автоматы представлены на рисунке 7.

Рисунок 7

Автомат для регулярных выражений “точка пробел” и “тире пробел” строим конечные автоматы по правилу 3 (рисунок 8).

Рисунок 8

Регулярное выражение “точка пробел | тире пробел” преобразуем по правилу 4. Соответствующий автомат изображен на рисунке 9.

Рисунок 9

Теперь строим конечный автомат для регулярного выражения (точка пробел | тире пробел)*, используя правило 5 (рисунок 10).

Рисунок 10

Применяя правило 3 для построения конечного автомата для полного регулярного выражения, получим следующий автомат для распознавания буквы азбуки Морзе, представленный на рисунке 11.

Рисунок 11. – Недетерминированный конечный автомат

3.2.3 Преобразование недетерминированного конечного автомата к детерминированному

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

Рассмотрим алгоритм преобразования. Входом алгоритма является недетерминированный автомат N, выходом – детерминированный автомат D состоящий из множества состояний Dstates и множества переходов Dtrans.

Введем обозначения.

S - состояние из N;

T - множество состояний из N. При работе алгоритма такие множества становятся состояниями D.

Пусть реализованы следующие функции.

eclosure(S). Эта функция строит e-замыкание состояния S, то есть множество состояний в которые можно перейти из S по e-переходам, это множество включает также само состояние S;

eclosure(T). Функция строит e-замыкание множества состояний T, то есть множество состояний, достижимых из множества состояний T через e-переходы. Это множество включает и состояния, принадлежащие T.

Move(T, a). Функция строит множество состояний, в которые можно перейти из Т по входному символу а.

Алгоритм состоит в следующем.

Dstates: =eclose(S₀);