Курсовая работа: Конструирование моделей лексического и синтаксического анализа

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Институт (факультет) Информационных технологий

Кафедра Математического и программного обеспечения ЭВМ

КУРСОВАЯ РАБОТА

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

на тему Конструирование моделей лексического и синтаксического анализа

Выполнил студент группы

ИСб-00-21оп

Дьяков Максим Сергеевич

Руководитель

Ганичева Оксана Георгиевна

Череповец, 2017год

Аннотация

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

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

Введение

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

Лексема - это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других структурных единиц языка.

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

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

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

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

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

Изучение и описание предметной области

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

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

Основные функции:

1)исключение из текста исходной программы комментариев

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

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

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

Анализатор должен выполнить следующие действия:

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

- выполнить действия для сохранения информации об обнаруженной лексеме

Для большинства входных языков границы лексем распознаются по заданным терминальным символам. ( пробелы, запятые, точки с запятой и т.п.) Набор таких терминальных символов может варьироваться в зависимости от синтаксиса входного языка.

Лексические анализаторы действуют по следующему принципу:

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

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

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

Постановка задачи

I. Разработайте грамматику для моделирования работы компилятора согласно своему варианту. Для синтаксического анализа - КС-грамматику, для лексического анализа - регулярную грамматику.

II.Постройте лексический анализатор, который решает следующие задачи: выделяет из текста входной программы все лексемы, входящие в заданную языковую конструкцию операторов for и do-while, удаляет лишние пробелы и комментарии из входной строки. Построение лексического анализатора выполнить на основе конечного автомата. По конечному автомату построить соответствующую ему регулярную грамматику.

III. Постройте КС-грамматику, описывающую синтаксис инструкции языка программирования для оператора операторов for и do-while.

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

V. Путем эквивалентных преобразований получите приведенную грамматику.

Примечание 1:

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

2. В задании I заданную грамматику представить в виде: правил КС-грамматики, в форме БНФ и регулярной грамматики.

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

Примечание 2:

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

2. В ходе работы ЛА должны удаляться лишние пробелы и комментарии

Описание конечного автомата

other-любая цифра и буква английского алфавита

б- английская буква (любого регистра), ц- цифра

M=(Q, V, R, q0, P) ), где:

Q - конечное множество состояний автомата; V - конечное множество допустимых входных символов; P - функция переходов автомата; S₀ - начальное состояние автомата; R - непустое множество конечных состояний автомата

V={a..z, A..Z, 0..9, -, +, /, *, =, ;,:, , , , #, &, !, (, ), {, }, <, >, [, ], |}

Q={S₀, S₁, ..S₈₉}

R={ S_3, S_8, S_15, S_19, S_24, S_30, S_34, S_39, S₄₄S_47, S_50, S_54, S_60, S_65, S_70, S_71, S_76, S_78, S_82, S_85, S₈₉} P:

Регулярная грамматика для лексического анализа

регулярная грамматика -- формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям.

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

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

1. A > a

2. A > aB

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

1. A > a

2. A > Ba

Где заглавные буквы (A, B) обозначают нетерминалы, строчные буквы (a, b) обозначают терминалы

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

Регулярная грамматика по конечному автомату:

G=(N, T, P, S)

N={Q}={S₀, S₁, … S₈₉}

T={V}={a..z, A..Z, 0..9, -, +, /, *, =, ;,:, , , , , &, !, (, ), {, }, <, >, [, ]}

S={q0}={S0}

P: