Алгоритм восходящего разбора

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, q₀, Z, F};

d: Q*S*Г -> Q₁*Г^**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 – указатель позиции;

L₁ – стек, хранящий историю переноса свёртки (верх справа);

L₂ – стек для хранения результата и факта переноса.

Правила:

1) (q,1,$,e) – начальное состояние;

2) (q, i, $α, γ) |¾ (q, i+1, $αa, Sγ) – перенос;