Разработка компиляторов



         

Восходящие анализаторы


Восходящие анализаторы

S -> aABe A -> Abc A -> b B -> d

Свертка цепочки abbcde в аксиому S:

abbcde, aAbcde, aAde, aABe, S.

Правый вывод цепочки:

S->aABe->aAde->aAbcde->abbcde

Восходящий анализатор (bottom-up parsing) предназначен для построения дерева разбора, начиная с листьев и двигаясь вверх к корню дерева разбора. Мы можем представить себе этот процесс как "свертку" исходной строки w к аксиоме грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки w и правой части какого-то правила грамматики и замене этой подстроки на нетерминал, являющийся левой частью правила. Если на каждом шаге подстрока выбирается правильно, то в результате мы получим правый вывод строки w .

Пример. Рассмотрим грамматику

S -> aABe A -> Abc A -> b B -> d

Цепочка abbcde может быть свернута в аксиому следующим образом:

abbcde, aAbcde, aAde, aABe, S.

Фактически, эта последовательность представляет собой правый вывод этой цепочки, рассматриваемый справа налево:

S->aABe->aAde->aAbcde->abbcde.




Содержание    Вперед