Информационно-безопасные системы. Анализ проблемы: Учебное пособие, страница 33

Таблица 8.4.

Состояние Вх. символ	1	2	3	4	5	6
Буква	3 / буфер	6 / ОШИБКА	4 / буфер	4 / буфер	3 / КОНСТ.	ВЫХОД
Цифра	5 / буфер	6 / ОШИБКА	5 / ИДЕНТ.	5 / СлСлово	5 / буфер	ВЫХОД
Двоеточие	2	б / ОШИБКА	2 / ИДЕНТ.	2 / СлСлово	2 /  КОНСТ.	ВЫХОД
Операция	1 / ОПЕРАЦ.	6 / ОШИБКА ИДЕНТ	1 / ОПЕРАЦ СлСлово	1 / ОПЕРАЦ. конст	1 / ОПЕРАЦ.	ВЫХОД
Отношение	1 / ОТНОШЕН.	если "=" , то 1 /  ПРИСВ. ИНАЧЕ 6 / ОШИБКА	1 / ИДЕНТ. ОТНОШЕН.	1/СлСтово ОТНОШЕН.	1 / КОНСТ. ОТНОШ.	ВЫХОД
Лев. скобка	1 / ЛевСкобка	6 / ОШИБКА ЛевСкобка	1 / ИДЕНТ. ЛевСкобка	1 / СлСлово ЛевСкобка	1 / КОНСТ.	ВЫХОД
Прав.скобка	1 / ПрСкобка	6 / ОШИБКА ПрСкобка	1 / ИДЕНТ. ПравСкобка	1 / СлСлово ПрСкобка	1 / КОНСТ.	ВЫХОД
Пробел	1 /  ПРОБЕЛ	6 / ОШИБКА ПРОБЕЛ	1 / ИДЕНТ. ПРОБЕЛ	1 / СлСлово ПРОБЕЛ	1 / КОНСТ.	ВЫХОД
Кон.файла	6 / Конфайл	б / ОШИБКА	6 / КонФайла	6 / КонФайла	6 / КонФайла	ВЫХОД

Если очередное слово состоит более чем из одной буквы, то осуществляется бинарный поиск в таблице зарезервированных слов. Если установлено, что прочтенное слово совпадает с одним из зарезервированных слов, то лексический блок создаст лексему. В противном случае выдается лексема ОШИБКА.

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

Если очередное слово является последовательностью цифр, то поиск осуществляет­ся в таблице констант.

8.4.2. Построение синтаксического блока

Построение синтаксического блока начинается с построения атрибутной LL(1)-грамматики [1, 2]. Для выбранного подмножества языка Паскаль грамматика показана на рис. 8.6.

8.4.3. Построение синтаксического блока на основе МП-автомата

Конечный автомат может решать лишь такие вычислительные задачи, в которых требуется фиксированный конечный объем памяти. Чтобы получить более мощный автомат, память конечного автомата расширяется за счет использования магазина. Магазин часто реализуется в форме динамического списка, в котором доступен только верх­ний (последний помещенный) элемент. В теории автоматов считается, что на дне магазина всегда находится элемент С, т.е. тот элемент, который нельзя вынуть. Символ С называется маркером дна [З].

О том, как задается автомат с магазинной памятью (МП-автомат) см. п.7.5. Над магазином могут быть выполнены следующие операции:

- ВТОЛКНУТЬ(А) - втолкнуть в магазин символ А;

- ВЫТОЛКНУТЬ - вытолкнуть верхний магазинный символ ( если он не является маркером дна);

- ЗАМЕНИТЬ(АВС) = ВЫТОЛКНУТЬ

ВТОЛКНУТЬ(А)

ВТОЛКНУТЬ(В)

ВТОЛКНУТЬ(С);

- оставить магазин без изменений.

Операции над входом могут быть такими:

- СДВИГ - перейти к следующему входному символу ( если текущий не является концевым маркером) и сделать его текущим;

- ДЕРЖАТЬ - оставить данный входной символ текущим.

Теперь введем понятие конечного распознавателя (МП- распознавателя), который лежит в основе процессов распознавания цепочек в трансляторе [4, 5].