Информатика и выч. техника \ Системное программное обеспечение

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

Страницы работы

21 страница (Word-файл)

Посмотреть все страницы

Скачать файл

Содержание работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Лабораторная работа №2

по дисциплине «Системное программное обеспечение»

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

Вариант № 4141243

Выполнил:

студент группы АМ-610

Ретунский А.Л.

Проверил:

Малявко А.А.

Новосибирск 2009 г.

Содержание

Цель работы.. 3

Задание. 4

Вариант задания. 5

Ход работы.. 6

Выводы.. 21

Цель работы

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

Задание

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

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

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

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

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

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

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

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

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

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

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

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

Вариант задания

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

Вариант:

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

<Б><Ц><пБЦ>

Константы

целые

вещественные

символьные

7-ричные

L_T/ L_F

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

Вариант:

int[e[g[e[r]]]]

float

char

bool

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

Вариант:	4
Классов	define
Экземпляров	get / drop

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

Вариант:	1
	<И> := <В>;

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

В-т:	2
	when <ЛВ> then <ОБ> [else <ОБ>]

II.6 Переключатель

В-т:	4
	with <В> {?<К>:<ОБ> …}

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

В-т:	3
	for<И>from<К>to<К> [step <К>] <ОБ>

Ход работы

1.Сначало, освоил:

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

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

· Операция “+” (одно или несколько) – (см. рис. 1 – строчки 4,5,8,14,19)

· Операция “*” (Пусто, одно или несколько) – (см. рис. 1 – строчки 14,15)

· Операция “?” (Пусто или в точности одно) - (см. рис. 1 – строчки 14)

· Операция конкатенации (не имеющая знака операции), например комментарии (//) примет вид [/][/] – (см. рис. 1 – строчка 3)

· Операция выбора (знак операции |) – (см. рис.1 – строчка 9)

- преобразование системы РВ в одноавтоматный лексический акцептор, на рис.1 строчки 1-15 относятся к автомату main и если остальные строчки опустить, то у нас будет одноавтоматный лексический акцептор.

- добавление правил и действий в систему РВ для построения мультиавтоматного лексического акцептора, на рис. 1 строчки 1-15 относятся к автомату main, строчки 16-18 к автомату symb, 19,20 к автомату priv, строчка 21 к автомату apog. Все вместе образует мультиавтоматный лексический акцептор.

2. Доработал разработанный при выполнении работы №1 фрагмент системы регулярных выражений для всех групп слов языка, определенного вариантом задания (см. рис. 1).

Построил по этой системе:

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

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

За основу взял язык C++, также параллельно осваиваю язык java.

3. Изучил структуру программных модулей, построенных ВебТрансЛабом и алгоритмы работы лексического акцептора для графового (см. ст. 10-11) и табличного (см. ст. 7-8) способов реализации КА.