Восходящий разбор.

Правый разбор цепочки ωв КС-грамматике – это последовательность правил, с помощью которых можно свернуть цепочку ωк начальному символу грамматики S, то есть он представляет собой последовательное определение основ и их удалений (свёртки).

Пример:

Есть КС-грамматика G с правилами

(1) (3)

(2) (4)

Цепочка: ω = ((a)(((b)a(a))(b)))

Сделаем левый разбор цепочки:

1) Выделим основу: ((a)(((b)a(a))(b))) по (4) правилу КС-грамматики;

2) Заменяем: (A(((b)a(a))(b))) по (2) правилу КС-грамматики;

3) (A((Sa(a))(b))) по (4) правилу КС-грамматики;

4) (A((SaA)(b))) по (3) правилу КС-грамматики;

5) (A(A(b))) по (2) правилу КС-грамматики;

6) (A(AS)) по (1) правилу КС-грамматики;

7) (AS) по (1) правилу КС-грамматики;

8) S по (1) правилу КС-грамматики.

Определим восходящий анализатор:

Пусть G – некоторая КС-грамматика. Назовём правым анализатором расширенный недетерминированный МП-преобразователь:

δ определяется следующим образом:

1) если – это правило из P с номером i, то ;

2) ;

3)

Правый анализатор работает следующим образом:

1) переносит входные символы в магазин, используя функцию , построенную по правилу (2) определения;

2) когда наверху магазина появляется основа, анализатор может свернуть её, используя функцию , построенную по правилу (1) определения, и выдать номер правила грамматики, использованного при свёртке;

3) анализатор продолжает переносить в магазин входные символы до тех пор, пока в его верхней части не появится новая основа, которая свёртывается, после чего на выход подаётся номер соответствующего правила грамматики;

преобразователь действует так до тех пор, пока в магазине не останется начальный символ грамматики с маркером дна магазина. В этом случае, используя правило (3) определения, анализатор может перейти в заключительную конфигурацию с опустошением магазина.