2.4Распознавание регулярных грамматик

2.4.1Конечный автомат и его программная реализация

Распознаватели регулярных грамматик строятся на конечных автоматах. Конечный автомат – это математическая модель, свойства и поведение которой полностью определяются пятеркой: M = (Q, , δ, q₀, F),

где Q – конечное множество состояний;

 – конечное множество входных символов;

δ(q_i, с_k) – функция переходов (q_i – текущее состояние, с_k – очередной символ);

q₀ – начальное состояние;

F = {q_j} – подмножество допускающих состояний.

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

Пример. Автомат «Чет-нечет» описывается следующим образом:

Q = {Чет, Нечет};

 = {0, 1};

δ(Чет, 0) = Чет, δ(Нечет, 0) = Нечет, δ(Чет, 1) = Нечет, δ(Нечет, 1) = Чет;

q₀ = Чет;

F = {Чет}

Строка «10110» приведет такой автомат в состояние Нечет, т. е. будет отвергнута, а строка «110011» – в состояние Чет, т. е. будет принята.

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

Т аблица 4 – Функция переходов

q 	0	1
Чет	Чет	Нечет
Нечет	Нечет	Чет

Рисунок 4 – Граф переходов Рисунок 5 – Синтаксическая диаграмма

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

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

Таблица 5 – Дополненная таблица конечного автомата

q с	0	1	Символы завершения	Другие символы
Чет	Чет	Нечет	Конец	Ошибка
Нечет	Нечет	Чет	Ошибка	Ошибка

Пусть S – строка на входе автомата;

Ind – номер очередного символа;

q – текущее состояние автомата;

Table – таблица, учитывающая символы завершения и другие символы.

Тогда алгоритм работы автомата можно представить следующим образом.

Ind := 1

q := q₀

Цикл-пока q  «Ошибка» и q  «Конец»

q = Table [q, S[Ind]]

Ind := Ind +1

Все-цикл

Если q = «Конец»

то «Строка принята»

иначе «Строка отвергнута»

Все-если

2.4.2Построение лексических анализаторов

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

Алфавит автомата лексического анализатора – все множество однобайтовых (ASCII) или двухбайтовых (Unicode) символов. При записи правил обычно используются обобщающие нетерминалы вида «Буквы», «Цифры». В процессе распознавания может формироваться описываемый объект, например, литерал или идентификатор.

Пример. Распознаватель целых чисел. Синтаксическая диаграмма синтаксиса языка описывается синтаксической диаграммой (см. рисунок 6).

1 – начало разбора; 2 – распознан знак; 3 – целое; К – завершение разбора

Рисунок 6 – Синтаксическая диаграмма

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

Таблица 6 – Таблица переходов

	Знак	Цифра	Разделитель	Другие
1	2, А1	3, А2	Е, Д1	Е, Д4
2	Е, Д2	3, А2	Е, Д3	Е, Д4
3	К, А3	3, А2	К, А3	Е, Д4

а) Подпрограммы обработки:

A0: Инициализация: Целое := 0; Знак_числа := «+».

А1: Знак_числа := Знак

А2: Целое := Целое*10 + Цифра

А3: Если Знак_числа = «-» то Целое := -Целое Все-если

б) Диагностические сообщения:

Д1: «Строка не является десятичным числом»;

Д2: «Два знака рядом»;

Д3: «В строке отсутствуют цифры»,

Д4: «В строке встречаются недопустимые символы»

Обозначим: S – строка на входе автомата; Ind – номер очередного символа; q – текущее состояние автомата; Table – таблица, учитывающая символы завершения и другие символы.

Тогда алгоритм сканера-распознавателя можно представить следующим образом.

Ind := 1

q := 1

Выполнить А0

Цикл-пока q  «Е» и q  «К»

Если S[Ind] = «+» или S[Ind] = «-»,

то j := 1

иначе Если S[Ind]  «0» и S[Ind]  «9»,

то j := 2,

иначе j := 3

Все-если

Все-если

Выполнить A_i := Table [q, j]. A()

q := Table [q, j]

Ind := Ind +1

Все-цикл

Если q = «К»

то Выполнить А3

Вывести сообщение «Это число»

иначе Вывести сообщение Дi

Все-если