Стр. 65 - Информационные структуры и их преобразование

Содержание 63
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
свёртка. Если свёртка невозможна, то в магазин переносится следующий
входной символ.
Если возможна более чем одна свёртка, то последние упорядочиваются
и применяется правая. Всегда перед переносом делается попытка свёртки.
Если цепочка исчерпана, то следует вернуться к последнему шагу, на
котором была произведена свёртка, и если возможна альтернатива,
использовать её.
Алгоритм:
Описывается, как и предыдущий, в терминах четырёх компонентных
конфигураций:
S - состояния q, b, t;
q – нормальное рабочее состояние (удачное сравнение и процесс
восхождения от листьев дерева к вершине);
b – неудачное сравнение и возврат по дереву;
t – заключительное состояние;
i – указатель позиции;
L1 – стек, хранящий историю переноса свёртки (верх справа);
L2 – стек для хранения результата и факта переноса.
Правила:
1) (q,1,$,e) – начальное состояние;
2) (q, i, $α, γ) | (q, i+1, $αa, Sγ) – перенос;
S - символ характеризующий факт переноса;
γ - некоторая цепочка.
3) (q, i, $αβ, γ) | (q, i, $αB, jγ) – свёртка;
Если есть B=β, то j - номер правила.
4) (q, n+1, $αB, jγ) | (b, n+1, $α, γ) - состояние возврата;
n- количество символов.
5) (q, n+1, $E, γ) | (t, n+1, $E, γ) - последнее состояние.
Пример:
1) E:=E+T;
2) E:=T;
3) T:=T*F;
4) T:=F;
5) F:=a.