Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ЛР3

.doc
Скачиваний:
4
Добавлен:
25.12.2018
Размер:
95.23 Кб
Скачать

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

Построение распознающего автомата по регулярному выражению

Цель работы: изучение методов построения распознавателя контекстно-свободной грамматики на основе описания грамматик в виде регулярного выражения или грамматики Хомского.

  1. Взаимосвязь регулярных грамматик и конечного автомата.

    1. Порядок построения конечного автомата по регулярной грамматике.

Рассмотрим порядок построения графа переходов конечного автомата на примере грамматики G1

G1:

АЛевая фигурная скобка 2→abC│ad (1)

C→bd│ε

- создается стартовое состояние (q0);

- создается состояние, соответствующее «удачному финишу», то есть допускающее (qf);

- создается по одному состоянию на каждый нетерминал (А и С);

- правилу вида А→aC в автомате соответствует переход из состояния А в состояние С при условии терминального символа а на входе;

- если правило имеет вид А→abC, вводится дополнительное состояние, в которое переходит автомат после обработки входного символа а (состояние q1 на рис.1);

- правилу вида А→d соответствует переход из состояния А в финальное состояние при условии терминального символа d на входе;

- если правило имеет вид C→bd, вводится дополнительное состояние, в которое переходит автомат после обработки входного символа b (состояние q3 на рис.1);

Рисунок 1. Граф переходов конечного автомата, построенный по грамматике G1

    1. Порядок построения регулярной грамматики на базе конечного автомата.

Рассмотрим порядок формирования грамматики на основе графа переходов конечного автомата, приведенного на рис.2

Рисунок 2. Граф переходов конечного автомата

- все состояния автомата обозначаются как нетерминальные символы, причем стартовому состоянию автомата сопоставляется начальный нетерминальный символ S;

- если допускающих состояний несколько, они объединяются с помощью ε-переходов в единое финальное состояние F;

- рассматривается каждый переход автомата, и каждому переходу сопоставляется правило грамматики: если по сигналу b автомат переходит из состояния S в состояние А, в грамматике есть правило S→bA.

Таким образом, графу, преставленному на рис.2, соответствует грамматика G2:

S→aS|bA|εF

A→bA| ε

F→ ε

2. Использование программы JFLAP для моделирования синтаксического анализатора.

Моделировать грамматику Хомского можно, выбрав пункт основного меню «Grammar».

Попадаем в окно редактора грамматик. Каждая строка таблицы соответствует одному правилу. Стрелка появляется автоматически. Нетерминал левой части первого правила считается начальным нетерминальным символом. Пустая правая часть правила заменяется символом λ.

После набора грамматика может быть сохранена в файле. Проверка выводимости цепочки выполняется с помощью пункта меню Input, Brute Force Parser. В поле Input набирается проверяемая терминальная цепочка. При нажатии кнопки Start выполняется полный перебор по грамматике и если цепочка недопустима, она отвергается. Если же цепочка допустима, начинается построение дерева вывода. Нажатие кнопки Step позволяет выстраивать его по уровням.

Также можно переконверировать написанную грамматику в граф, выбрав в меню «Convert» пункт «Convert Right-Linear Grammar to FA ». В открывшемся окне нужно нажать на кнопку «Show All» а потом «Export»

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

3.1 Построить соответствующий индивидуальному заданию граф распознающего автомата и эквивалентную ему КС-грамматику.

    1. Моделировать работу распознающего автомата на тестовых последовательностях, позволяющих выявить все возможные результаты распознавания.

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

    1. Сравнить полученные результаты, убедиться в эквивалентности работы распознавателей.

    2. Автоматически конвертировать регулярную грамматику в граф конечного автомата

    3. Промоделировать работу полученного автомата на тестовых последовательностях, сравнить полученные результаты с результатами п.п.3.2 и 3.3, сделать выводы

  1. Содержание отчета

- цель работы;

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

- построение эквивалентной графу грамматики;

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

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

- выводы.

Соседние файлы в предмете Теория автоматов