Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
6
лабораторная работа для студентов
специальности ПВС по курсу «Теория
языков программирования и методы
трансляции»
Составил доцент кафедры ПВС
Сайкин А.И.
Саратов, 2001 г.
Данная лабораторная работа рассчитана на четыре аудиторных часа и ещё четыре часа для изучения материала и оформление отчёта.
Объект исследования процесс трансляции заданного языка программирования в машинные коды. Цель изучения состоит в применении математического аппарата конечных автоматов при лексическом анализе. Лексический анализ это начальный этап трансляции, за которым следуют грамматический разбор и этап генерации машинного кода. Наиболее трудоёмким по затратам машинного времени является этап лексического анализа. Для сокращения общего времени трансляции и упрощения лексического анализа целесообразно использовать математический аппарат конечных автоматов. Метод исследований как раз и базируется на его применении.
Выполнение работы производится в дисплейном классе. Характер исследований состоит в сочетании результатов, полученных на ПЭВМ с их аналитической обработкой студентом.
Разработка лексического анализатора выполняется достаточно просто, если воспользоваться хорошо разработанным математическим аппаратом - теорией регулярных языков и конечных автоматов. В рамках этой теории классы однотипных лексем (идентификаторы, константы и т.д.) рассматриваются как формальные языки (язык идентификаторов, язык констант и т.д.), множество предложений которых описывается с помощью соответствующей порождающей грамматики. При этом языки эти настолько просты, что они порождаются простейшей из грамматик - регулярной грамматикой. Построенная регулярная грамматика является источником, по которому в дальнейшем конструируется вычислительное устройство, реализующее функцию распознаваний предложений языка, порождаемого данной грамматикой. Для регулярных языков таким устройством является конечный автомат.
Порождающая грамматика G(N,T,P,S), продукции которой имеют вид АаВ или Св, где А,В,С - нетерминальные символы; а,в- терминальные символы, называется регулярной или автоматной. Язык L(G), порождаемый регулярной грамматикой называется регулярным или автоматным или языком с конечным числом состояний. Основной задачей лексического анализа является распознавание лексических единиц. Математической моделью процесса распознавания регулярного языка является вычислительное устройство, которое называется конечным автоматом. Термин «конечный» подчёркивает то, что вычислительное устройство имеет фиксированный конечный объём памяти и обрабатывает последовательность входных символов, принадлежащих некоторому конечному множеству. Существуют различные типы конечных автоматов, если результатом работы является лишь указание на то, что входная последовательность символов допустима или нет, то такой конечный автомат называется конечным распознавателем.
В данной лабораторной работе необходимо построить конечные автоматы для каждого типа распознаваемых лексем. Проводя лексический анализ, конечные автоматы должны сообщать о допустимости или не допустимости конкретных лексем. Программа лексического анализатора должна распечатывать входной текст и выдавать сообщения обо всех недопустимых лексемах. Hеобходимо также составить техническое задание на разрабатываемую программу лексического анализатора.
Вариант задания по второй лабораторной работе совпадает с вариантом задания по первой лабораторной работе, т.е. входным для лексического анализатора будет текст программы, составленный из заданного алфавита и заданных ключевых слов в соответствие с вариантом задания первой лабораторной работы.
Любая регулярная грамматика G=(N,T,P,S) может быть представлена направленным графом, с помеченными узлами и дугами. Каждый узел помечаем символом из N. Кроме одного конечного узла, который помечаем символом #. Согласно принятым соглашениям, узел, соответствующий начальному символу S помечаем стрелкой, а конечный изображаем в виде прямоугольника. Каждая дуга графа соответствует только одной продукции заданной грамматики G.
Например, пусть регулярная грамматика G имеет следующие продукции:
SaA|bB
AaA|a
BbB|b,
тогда граф, отображающий данную грамматику G, будет иметь вид, представленный на рис.1. Путь на графе всегда соединяет начальную вершину с конечной вершиной графа. Метки, ассоциированные с дугами, составляющими этот путь, образуют некоторую строку. Множество таких строк совпадают с языком L(G). Конкретные пути на графе будут соответствовать некоторой схеме вывода. Например, SaAaaAaaaA
aaaa, т.е. от S к А, от А к А, от А к #. Конечный направленный граф, имеющий начальный узел и один или более конечных узлов сети - есть конечный автомат.
Рис.1. Граф конечного автомата.
Можно дать и второе определение конечного автомата. Конечным автоматом (КА) называется совокупность пяти множеств:
КА={N, T, t, S, F}
где : N-конечное множество состояний автомата, совпадающее с множеством нетерминальных символов грамматики;
T-множество терминальных символов автомата, совпадающее с множеством терминальных символов грамматики;
t-функция переходов, задаваемая таблицей;
S- начальное состояние автомата;
F-конечные состояния автомата.
Функция переходов может быть представлена различными способами. Основные из них: списком команд КА, диаграммой состояний и матрицей переходов. Команда КА представляет собой следующую запись:
(A i, a j)A k
которая представляет собой переход в автомате из вершины. А I в вершину А k по дуге, отмеченной a j. Для КА необходимо составлять список таких команд, причём он должен обязательно содержать переходы в конечную вершину, для нормального завершения работы автомата.
Диаграмма состояний это по сути граф КА. И он содержит полную информацию об КА.
Матрица переходов может быть записана в двух видах. Во-первых, строки матрицы - это вершины КА (нетерминальные символы), столбцы матрицы - терминальные символы, приписываемые соответствующим дугам графа КА. Элементы матрицы - это состояния КА, в которые осуществляется переход. По второму способу матрица переходов записывается в три колонки, соответствующие командам КА. Естественно, что все три способа равнозначны.
КА могут быть детерминированными ДКА и недетерминированными НДКА. В детерминированном автомате из каждой вершины выходят дуги, отмеченные все различными метками. В НДКА имеется хотя бы одна вершина с одинаково отмеченными дугами. Для программирования ДКА гораздо проще. ДКА и НДКА по существу задают эквивалентные языки, но имеет место теорема, что ДКА может принять некоторый язык L, если этот язык принимает НДКА. Переход от НДКА к ДКА осуществляется тривиально, за счёт введения дополнительных фиктивных состояний. Если из одной вершины выходит две дуги, обозначенные одинаково (НДКА), то одну дугу обозначаем по другому, но замыкаем её на фиктивное состояние, из которого проводим ранее переобозначенную дугу к требуемому состоянию (ДКА).
Для практических целей необходимо, чтобы КА сам определял момент окончания входной цепочки символов с выдачей сообщения о правильности или неправильности входной цепочки символов. Для этих целей входная цепочка считается ограниченной справа концевым маркером, в качестве которого могут использоваться обычные разделители. И в диаграмму состояний КА водятся интерпретированные состояния: допустить входную цепочку как лексему, отвергнуть входную цепочку как лексему, запомнить ошибку во входной цепочке.
В общем случае может быть предложен следующий порядок конструирования лексического анализатора (ЛА).
1. Выделить во входном языке L(G) на основании описания его синтаксиса множество классов лексем.
2. Построить для каждого класса автоматную (регулярную) грамматику.
3. Для каждой автоматной грамматики построить КА.
4. Определить условия выхода из ЛА ( переход его в начальное состояние) при достижении конца произвольной лексемы из каждого класса лексем.
5. Разбить символы входного алфавита на непересекающиеся множества.
6. Построить матрицу переходов ЛА.
7. Выбрать формат и код образов лексем-дескрипторов (см. первую лабораторную работу).
8. Запрограммировать ЛА.
4. Содержание отчёта.
В соответствии с вариантом задания каждый студент сотавляет отчёт по работе, в который входят:
1. Титульный лист.
2. Вариант задания.
3. Техническое задание на разработку программы ЛА.
4. Описание программы ЛА.
5. Работающая программа ЛА (демонстрация работы при отчёте).
6. Выводы по работе.
5. Контрольные вопросы.
1. Как задаётся формальная грамматика?
2. Как определяется регулярная грамматика?
3. Чем отличаются сентенции и сентенциальные формы?
4. Что такое лексема?
5. В чём смысл работы ЛА?
6. Назовите основные этапы проектирования ЛА.
7. Как задаётся КА?
8. Как преобразовать НДКА в ДКА?
Литература.
1. Бек Л. Введение в системное программирование. М.: Мир, 1988.
-448 с.
2. Компаниец Р.И. и др. Системное программирование. Основы
построения трансляторов.- СПб.: КОРОНА принт 2000.-256 с.