«Сверху вниз» и «снизу вверх» - отличные описания двух стратегий синтаксического анализа, потому что они точно описывают, как будет построено синтаксическое дерево, если оно будет построено.(Вы также можете думать об этом как о порядке обхода неявного дерева разбора, но здесь мы на самом деле заинтересованы в реальных деревьях разбора.)
Кажется очевидным, что есть преимущество в построении дерева снизу вверх.Когда пришло время добавить узел в дерево, вы уже знаете его дочерние элементы.Вы можете построить узел полностью сформированным за одно (функциональное) действие.Вся дочерняя информация тут же ждет вас, поэтому вы можете добавить семантическую информацию в узел на основе семантической информации его дочерних элементов, даже используя дочерние элементы в порядке, отличном от слева направо.
В отличие от этого, анализатор сверху вниз создает узел без дочерних элементов, а затем должен по очереди добавить каждого дочернего элемента в уже созданный узел.Это конечно возможно, но это немного некрасиво.Кроме того, инкрементная природа конструктора узла означает, что семантическая информация, присоединенная к узлу, также должна вычисляться постепенно или откладываться до тех пор, пока узел не будет полностью построен.
Во многих отношениях это похоже на разницу междуоценка выражений, написанных в обратной польской записи (RPN), из выражений, написанных в (прямой) польской записи [Примечание 1].RPN был изобретен именно для упрощения оценки, что возможно при простом стеке значений.Очевидно, что прямые польские выражения могут быть оценены: самый простой способ - использовать рекурсивный оценщик, но в средах, где на стек вызовов нельзя положиться, это можно сделать с помощью стека операторов, который эффективно превращает выражение в RPN наfly.
Так что это, вероятно, механизм выбора для построения синтаксических деревьев также из анализаторов сверху вниз.Мы добавляем маркер «сокращения» в конец каждой правой части.Так как маркер идет в конце правой части, поэтому он перемещается первым.
Нам также необходим стек значений для записи создаваемых узлов AST (или семантических значений).
В базовом алгоритме у нас теперь есть еще один случай.Мы начинаем с того, что поднимаем вершину стека анализатора, а затем исследуем этот объект:
Вершина стека анализатора была терминалом.Если текущим входным символом является тот же терминал, мы удаляем входной символ из ввода и помещаем его (или его семантическое значение) в стек значений.
Верх анализаторастек был маркером.Связанное действие сокращения запускается, что создаст новый узел AST, вытолкнув соответствующее количество значений из стека значений и объединив их в новый узел AST, который затем помещается в стек значений.(Как особый случай, действие маркера для уникального производства расширенного начального символа S' -> S $ приводит к тому, что анализ принимается, возвращая (только) значение в стеке значений как AST.)
Вершина стека синтаксического анализатора была нетерминальной.Затем мы определяем соответствующую правую сторону, используя текущий символ ввода, и помещаем эту правую сторону (справа налево) в стек синтаксического анализатора.