Стр. 35 - Информационные структуры и их преобразование
Упрощенная HTML-версия
33
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
столбце. Если такой строки нет, то редукция невозможна. Последний
сканируемый символ помещается в стек, и сканируется следующий символ.
Таблица содержит все возможные конфигурации вида:
Tu
R
i
Если в любой момент можно найти совпадение не более чем с одной
строкой в верхней части стека и входного символа, то всякая редукция может
быть выполнена.
Для пояснения работы алгоритма рассмотрим следующий
пример
.
Пусть у нас есть следующие привила:
1.
Z:=V;
2.
Z:=aW;
3.
V:=V1;
4.
V:=bU;
5.
U:=U0;
6.
U:=0;
7.
W:=0W1;
8.
W:=01.
Используя эти правила, можно составить следующую таблицу для
алгоритма:
Tu
R
пр
N
1
a01
#
8
2
001
1
8
3
#aW
#
2
4
#bU
1
4
5
bU0
1
5
6
bU0
0
5
7
#V1
1
3
8
#V1
#
3
9
#V
#
1
10
a0W1
#
7
11
b0
#
6
Ниже приведены несколько цепочек, разобранных по данному
алгоритму:
