Таблица 3.9 – Алгоритм работы распознавателя цепочки (((aa) a) a)
Шаг | Стек | Входной буфер | Действие | |
^н | (((aa) a) a)^к | сдвиг | ||
^н( | ((aa) a) a)^к | cдвиг | ||
^н(( | (aa) a) a)^к | cдвиг | ||
^н((( | aa) a) a)^к | cдвиг | ||
^н(((a | a) a) a)^к | свертка S ® a | ||
^н(((S | a) a) a)^к | сдвиг | ||
^н(((Sa | ) a) a)^к | сдвиг | ||
^н(((Sa) | a) a)^к | свертка R ® Sa) | ||
^н(((R | a) a)^к | свертка S ®(R | ||
^н((S | a) a)^к | сдвиг | ||
^н((Sa | ) a)^к | сдвиг | ||
^н((Sa) | a)^к | свертка R ® Sa) | ||
^н((R | a)^к | свертка S ®(R | ||
^н(S | a)^к | сдвиг | ||
^н(Sa | )^к | сдвиг | ||
^н(Sa) | ^к | свертка R ® Sa) | ||
^н(R | ^к | свертка S ®(R | ||
^н S | ^к | строка принята | ||
Шаг 4. Получили следующую цепочку вывода:
S Þ(R Þ(Sa)Þ((Ra)Þ((Sa) a)Þ(((Ra) a)Þ(((Sa) a) a)Þ(((aa) a) a).
Восходящее дерево вывода цепочки представлено на рисунке 3.5.2
Рисунок 3.5 – Дерево вывода для цепочки (((aa) a) a) в грамматике G