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

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

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

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

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

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

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

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

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

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

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

Вариант № 4141243

Выполнил:

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

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

Проверил:

Малявко А.А.

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

Содержание

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

Задание. 4

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

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

Выводы.. 21

Цель работы

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

Задание

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

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

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

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

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

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

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

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

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

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

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

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


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

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

Вариант:

4

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

<Б><Ц><пБЦ>

Константы

целые

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

символьные

7-ричные

L_T/ L_F

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

Вариант:

1

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)  способов реализации КА.

Похожие материалы

Информация о работе