Задание № 2

1. Тема: «Лексика языков программирования. Конечные автоматы без памяти для обнаружения слов в тексте программы».

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

3. Порядок выполнения работы (рекомендуется использовать примеры систем правил 1simpleLexic.xml и 2LexMultiAutomatForComments.xml):

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

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

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

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

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

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

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

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

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

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

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

3.6. Подготовить, сдать и защитить отчет по заданию (в электронном виде, в формате MS Office 2003).