Стр. 64 - Информационные структуры и их преобразование
Упрощенная HTML-версия
62
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
a – то же самое, что и i (терминал),
b – любой терминальный символ из грамматики.
δ
(q, e, ZE+T) = (q, E, 1);
δ
(q, e, ZT) = (q, E, 2);
δ
(q, e, ZT*F) = (q, T, 3);
δ
(q, e, ZF) = (q, T, 4);
δ
(q, e, Z(E)) = (q, F, 5);
δ
(q, e, Za) = (q, F, 6);
δ
(q, b, Z) = (q, Zb, e);
δ
(q, e, ZE) = (q, e, e).
Рассмотрим цепочку a*(a + a):
(q, a*(a + a), Z, e) |
(q, *(a + a), Za, e) |
(q, *(a + a), ZF, 6) |
(q, *
*(a + a), ZT, 64).
|
(q, (a + a), ZT*, 64) |
(q, a + a), ZT*(, 64) |
(q, + a), ZT*(a, 64).
|
(q, + a), ZT*(F, 646) |
(q, + a), ZT*(T, 6464) |
(q, + a), ZT*(E, 64642).
|
(q, a), ZT*(E+, 64642) |
(q, ), ZT*(E+a, 64642) |
(q, ),
ZT*(E+T, 6464264).
|
(q, ), ZT*(E, 64642641) |
(q, e, ZT*(E), 64642641) |
(q, e, ZT*F,
646426415).
|
(q, e, ZT, 6464264153) |
(q, e, ZE, 64642641532).
Работа преобразователя в данном примере:
на такте 1 преобразователь переносит входной символ в магазин.
Всякий раз, когда наверху магазина появится основа, преобразователь может
свернуть ее по правилу 2 и выдать при этом номер используемого правила.
Это происходит до тех пор, пока верхним символом в магазине не станет
начальный символ (Е), за которым следует маркер дна (Z). Это означает, что
входная цепочка прочитана, и по правилу 3 попадаем в заключительное
состояние.
Алгоритм восходящего разбора
Восходящий разбор представляет собой правый анализатор, который
перебирает всевозможные обращённые правые выводы, совместимые с
входной цепочкой.
Шаг алгоритма состоит в считывании цепочки, расположенной в
верхней части магазина. На этом шаге выясняется, образуют ли верхние
символы стека правую часть какого либо правила, если да, то производится
