Приложение 1.

Метод ролей для построения конечного распознавателя.

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

Рассмотрим пример.

Построим автомат для распознавания цепочек, которые могут следовать за словом INTEGER в операторах спецификации Фортран. Примеры таких операторов:

INTEGER A

INTEGER X, I(3)

INTEGER C(3,J,4), B

Будем считать, что массивы могут иметь любую размерность, хотя в большинстве стандартов и компиляторов с Фортрана она ограничена. Входной алфавит будет состоять из пяти символов: v c , ( ) ,где v – лексема, означающая произвольную переменную, с – лексема, соответствующая целочисленной константе. Будем считать, что эти лексемы порождаются каким-то другим автоматом.

Для демонстрации первого шага метода выпишем цепочку языка и пометим ее символы номерами от 2 до 8. Номер 1 зарезервируем для начального состояния автомата и поместим перед началом цепочки:

INTEGER A ( 3 , J , 4 ) , B

1 2 3 4 5 6 5 4 7 8 2

Роли, встречающиеся в примере, словами могут быть описаны так:

2 – имя переменной, описываемой как INTEGER;

3 – левая скобка;

4 – целое число, задающее размерность;

5 – запятая, разделяющая размерности;

6 – переменная, задающая переменную размерность;

7 – правая скобка;

8 – запятая, разделяющая объекты, описываемые как целые.

После того, как все роли опознаны, дальше автомат можно строить по следующему алгоритму:

1. Ввести начальное состояние (1) и состояние ошибки (Е).

2. Ввести состояние для каждой роли (2 – 8).

3. Поместить в таблицу переходы из одного состояния в другое, если соответствующие роли могут следовать одна за другой.

4. Пополнить таблицу переходами в состояние ошибки.

5. Выбрать в качестве допускающих те состояния, роли которых появляются в конце допустимой цепочки.

Для описанного выше примера таблица переходов будет выглядеть следующим образом:

	v	c	,	(	)
1	2	E	E	E	E	0
2	E	E	8	3	E	1
3	6	4	E	E	E	0
4	E	E	5	E	7	0
5	6	4	E	E	E	0
6	E	E	5	E	7	0
7	E	E	8	E	E	1
8	2	E	E	E	E	0
E	E	E	E	E	E	0

Замечание 1. Автомат, построенный по данному методу, не обязательно будет наилучшим в том смысле, что может найтись другой автомат с меньшим числом состояний, который определяет то же множество цепочек.

Минимальным автоматом, эквивалентным построенному в рассмотренном примере, будет следующий:

	v	c	,	(	)
{1,8} А	2	E	E	E	E	0
2	E	E	A	B	E	1
{3,5} B	C	C	E	E	E	0
{4,6} C	E	E	B	E	7	0
7	E	E	A	E	E	1
E	E	E	E	E	E	0

Замечание 2. В случаях, когда за символом в некоторой роли может следовать один и тот же символ в двух разных ролях, сначала можно построить недетерминированный автомат и занести в одну ячейку таблицы требуемое количество переходов, а затем преобразовать недетерминированный конечный автомат в детерминированный.