Разработка компиляторов
Восходящие анализаторы
Восходящие анализаторы
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.
