Алгоритм восходящего разбора
4 6 4 6
2 3 5 1 4 6 2
E => T => T*F => T*(E) => T*(E+T) => T*(E+F) => T*(E+i) => T*(T+i) =>
=> T*(F+i) => T*(i+i) => F*(i+i) => i*(i+i).
Правый разбор: 6 4 6 4 2 6 4 1 5 3 2.
Набираем в магазине цепочку терминальных символов и смотрим, есть ли в правых частях правил соответствующие нетерминальные символы: МП={Q, S, Г, D, d, q0, Z, F};
d : Q*S*Г -> Q1*Г**D* - функция отображения, где * - означает цепочки.
Будем рассматривать Z как маркер дна магазина,
S {i, (, ), *, +},
D (1…6) 1,2…6 – номера правил,
Г {N È S}.
Рассмотрим несколько примеров функции отображения:
1) d(q, a, Z) = (q, Za, e),
2) d(q, e, Za) = (q, A, i),
3) d(q, e, ZE) = (r, e, e).
A:= a, q Î Q, r Î F;
Е – начальный символ грамматики,
a – то же самое, что и i (терминал),
b – любой терминальный символ из грамматики.
d (q, e, ZE+T) = (q, E, 1);
d (q, e, ZT) = (q, E, 2);
d (q, e, ZT*F) = (q, T, 3);
d (q, e, ZF) = (q, T, 4);
d (q, e, Z(E)) = (q, F, 5);
d (q, e, Za) = (q, F, 6);
d (q, b, Z) = (q, Zb, e);
d (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 попадаем в заключительное состояние.
Восходящий разбор представляет собой правый анализатор, который перебирает всевозможные обращённые правые выводы, совместимые с входной цепочкой.
Шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина. На этом шаге выясняется, образуют ли верхние символы стека правую часть какого либо правила, если да, то производится свёртка. Если свёртка невозможна, то в магазин переносится следующий входной символ.
Если возможна более чем одна свёртка, то последние упорядочиваются и применяется правая. Всегда перед переносом делается попытка свёртки. Если цепочка исчерпана, то следует вернуться к последнему шагу, на котором была произведена свёртка, и если возможна альтернатива, использовать её.
Алгоритм:
Описывается, как и предыдущий, в терминах четырёх компонентных конфигураций:
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.
Рассмотрим входную цепочку: a*a
(q, 1, $, e) |¾ (q, 2, $a, S) |¾ (q, 2, $F, 5S) |¾ (q, 2, $T, 45S) |¾ (q, 2, $E, 245S)|¾
(q, 3, $E*, S245S) |¾ (q, 4, $E*a, SS245S) |¾ (q, 4, $E*F, 5SS245S) |¾
(q, 4, $E*T, 45SS245S) |¾ (q, 4, $E*E, 245SS245S) |¾ (b, 4, $E*a, SS245S) |¾
(b, 3, $E*, S245S) |¾ (b, 2, $E, 245S) |¾ (b, 2, $T, 45S) |¾ (q, 3, $T*, S45S) |¾
(q, 4, $T*a, SS45S) |¾ (q, 4, $T*F, 5SS45S) |¾ (q, 4, $T, 35SS45S) |¾ (q, 4, $E, 235SS45S) |¾
(t, 4, $E, 235SS45S).
Получили дерево: