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

Восходящий анализ базируется на понятии основа.

Пусть имеется КС-грамматика с правилами:

(1) S®(AS)

(2) S®(b)

(3) A®(SaA)

(4) A®(a)

Рассмотрим разбор цепочки ((a) (((b) a (a)) (b))).

((a) (((b) a (a)) (b))) ►₍₄₎

(A (((b) a (a)) (b))) ►₍₂₎

(A ((S a (a)) (b))) ►₍₄₎

(A ((S a A) (b))) ►₍₃₎

(A (A (b))) ►₍₂₎

(A (A S )) ►₍₁₎

(A S ) ►₍₁₎

S

Таким образом, правый разбор цепочки w в КС-грамматике G=(N, T, P, S) – это последовательность правил, с помощью которых можно свернуть цепочку w к начальному символу S грамматики.

Допустим, что мы строили дерево вывода цепочки w. Тогда в терминах деревьев выводов правый анализ цепочки w представляет собой последовательное определение основ и их удаление (свертка). Такой процесс сводит дерево вывода с кроной w к одной вершине, помеченной начальным символом грамматики S.

Прейдем теперь к формальному определению восходящего анализатора.

Пусть G=(N, T, P, S) - КС-грамматика. Назовем правым анализатором расширенный недерминированный МП-преобразователь

M_r= ({q}, T, NÈ ТÈ{┴}, {1, 2, …, p}, d, q, ┴, {q}), у которого d определяется следующим образом:

1) Если A®a - правило из Р с номером i, то (q, A, i) Î d(q, e, a)

2) d(q, a, e)={(q, a, e)} для всех a Î T

3) d(q, e, ┴S)={(q, e, e)}

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

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

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

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

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

Пример. Построим правый анализатор для грамматики G:

(1) E®E+T

(2) E®T

(3) T®T*P

(4) T®P

(5) P®i

(6) P®(E)

M_r = ({q}, {i, +, *, (,)}, {i, +, *, (,), E, T, P, ┴}, {1, 2, 3, 4, 5, 6}, d, q, ┴, {q})

Определим функцию d:

1. По правилу (2) определения анализатора включаем в d-функцию:
d (q, a, e) ={(q, a, e)} для всех a Î T

2. По правилу (3) определения включаем в d-функцию: d(q, e, ┴E)={(q, e, e)}

3. Для правила грамматики ()1 E®E+T по правилу (1) определения в функцию d(q, e, E+T) необходимо включить элемент (q, E, 1)

4. Повторив аналогичные действия для всех правил грамматики, получим:

1) d(q, e, E+T)={(q, E, 1)}

2) d(q, e, T)={(q, E, 2)}

3) d(q, e, T*P)={(q, T, 3)}

4) d(q, e, P)={(q, T, 4)}

5) d(q, e, (E))={(q, P, 6)}

6) d(q, e, i)={(q, P, 5)}

7) d(q, a, e)={(q, a, e)} для всех a Î{I, +, *, (,)}

8) d(q, e, ┴E)={(q, e, e)}

Для входной цепочки i * (i + I) МП-анализатор M_r среди других может выполнить следующую последовательность тактов:

(q, i *(i + i), ┴, e) ├ (q, (i + i), ┴i, e) ├ (q, *(i + i), ┴ P, 5) ├

(q, *(i + i), ┴ T, 54) ├ (q, (i + i), ┴ T *, 54) ├

(q, i + i), ┴ T *(, 54) ├

(q, + i), ┴ T*(i, 54) ├

(q, + i), ┴ T*(P, 545) ├

(q, + i), ┴ T*(T, 5454) ├

(q, + i), ┴ T*(E, 54542) ├

(q, i), ┴ T*(E +, 54542) ├

(q,), ┴ T*(E +i, 54542) ├

(q,), ┴ T*(E +P, 545425) ├

(q,), ┴ T*(E +T, 5454254) ├

(q, e, ┴ T*(E +T), 5454254) ├

(q, e, ┴ T*(E), 54542541) ├

(q, e, ┴ T*P, 545425416) ├

(q, e, ┴ T, 5454254163) ├

(q, e, ┴ E, 54542541632) ├

(q, e, e, 54542541632) ├

Дата добавления: 2014-01-03