Автомат с магазинной памятью

Распознавание КС-грамматик выполняется автоматом с магазинной памятью. Автомат с магазинной памятью определяется семеркой:

P_M = (Q, S, Г, d, q ₀, z ₀, F),

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

S – конечный входной алфавит;

Г – конечное множество магазинных символов;

d (q, c_k, z_j) – функция переходов;

q ₀ Î Q – начальное состояние автомата;

z ₀ Î Г – символ, находящийся в магазине в начальный момент,

F Í Q – множество заключительных (допускающих) состояний.

Пример. Синтаксический анализатор выражений.

Алфавит языка записи выражений: S = {<Ид>, +, –, *, /, (,), ◄, ►}. Грамматика описывается синтаксическими диаграммами, представленными на рисунке 8.

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

Подставляем диаграммы одна в другую, исключая промежуточные нетерминалы Терм и Множитель. В результате получаем полную синтаксическую диаграмму (см. рисунок 9), которая состоит из двух частей: основной и рекурсивной, что связано с наличием рекурсивного вложения правил продукции.

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

По диаграмме строим таблицу автомата, которая также будет состоять из двух частей (см. таблицу 8), которые можно объединить в одну.

Таблица 8 – Таблица переходов автомата

Условные обозначения:

К – конец разбора, E – состояние ошибки (все пустые ячейки должны содержать E),

¯ Y = <состояние> – рекурсивный вызов распознавателя, справа указан номер состояния после возврата из данного вызова;

­ Y – возврат из рекурсии, следующее состояние определяется значением Y,

При разработке алгоритма используем следующие обозначения:

Mag – стек (магазин) распознающего автомата, элементы, записываемые в стек, – терминальные и нетерминальные символы; ¯ – запись в стек, ­ – чтение из стека;

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

Table (<Текущее состояние>, <Анализируемый символ>) – элемент таблицы (матрицы) переходов, состоящий из следующих полей: q – следующее состояние (в том числе «¯» – рекурсивный вызов, «­» – возврат из рекурсии), S – состояние после возврата из рекурсии, если необходим рекурсивный вызов, или Æ;

String – исходная строка;

Ind – номер символа исходной строки.

Алгоритм программы, реализующей автомат, будет выглядеть следующим образом:

q:=1

Ind:= 1

Mag:=Æ

Цикл-пока q ¹ «E» и q ¹ «К»

q:= Table [ q, String [ Ind ]]. q