Изучение конечных автоматов без памяти, способов определения КА – канонического, графового и табличного, методов построения недетерминированного КА по системе регулярных выражений

1. Цели работы

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

2. Задание

·  Используя пакет ВебТрансЛаб, освоить:

o  создание лексических правил на языке регулярных выражений (РВ);

o  использование операций «+, *, ?, конкатенации и выбора» языка РВ;

o  преобразование системы РВ в одноавтоматный лексический акцептор;

o  добавление правил и действий в систему РВ для построения            мультиавтоматного лексического акцептора;

·  Разработать (доработать разработанный при выполнении работы №1) фрагмент системы регулярных выражений для всех (или выбранной самостоятельно части) групп слов языка, определенного заданием на курсовую работу. Построить по этому фрагменту:

o  программный модуль, управляемый графом состояний и переходов;

o  программный модуль, управляемый таблично;

·  Изучить структуру программных модулей, построенных ВебТрансЛабом, изучить алгоритмы работы лексического акцептора для графового и табличного способов реализации КА, сравнить реализации конечных автоматов, управляемых различными способами, между собой;

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

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

·  Изучить те элементы языка шаблонов, которые используются для преобразования внутреннего представления конечного автомата в программную реализацию лексического анализатора.

3. Индивидуальное задание

Идентификаторы и константы

Объявления примитивных типов (целое, вещественное, символьное, булево):

Объявления объектов и создание/уничтожение экземпляров

Оператор присваивания:

Условный оператор:

Переключатель

Оператор цикла:

4.Порядок выполнения работы

В ходе работы были изучены принципы построения лексических правил на языке регулярных выражений (продолжение лабораторной работы №1). Было рассмотрено преобразование системы регулярных выражений в мультиавтоматный лексический акцептор, после чего были разработаны правила для выявления символьных констант, для этого было создано несколько автоматов, а также «привязать» действия к переходам.

После доработки фрагмента системы регулярных выражений были построены программные модули, управляемые:

·  графом состояний переходов,

·  таблично.

Были изучены: структура генерируемых программных модулей, вызов действий определенных в лексических правилах.

Была проверена правильность функционирования конечных автоматов построенных пакетом ВебТрансЛаб.

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

5.Вывод