Войти
В информатике, разбор раскрывает грамматическую структуру текста линейного ввода, как первый шаг в выяснении его значения. При синтаксическом анализе снизу вверх сначала распознаются мелкие детали самого нижнего уровня текста, а затем структуры среднего уровня, а общая структура самого верхнего уровня сохраняется.
Восходящее имя происходит от концепции дерева синтаксического анализа, в котором наиболее подробные части находятся в нижней части перевернутого дерева, а более крупные структуры состоят из них находятся на последовательно более высоких уровнях, пока на вершине или в «корне» дерева один элемент не описывает весь входной поток. Восходящий синтаксический анализ обнаруживает и обрабатывает это дерево, начиная с нижнего левого края, и постепенно продвигается вверх и вправо. Синтаксический анализатор может воздействовать на нижний, средний и верхний уровни иерархии структуры, даже не создавая фактического дерева данных; тогда дерево просто неявно присутствует в действиях парсера. Восходящий синтаксический анализ терпеливо ожидает, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем принять решение о том, что представляет собой комбинированная конструкция.
 Типичное дерево синтаксического анализа для. A = B + C * 2; D = 1 |  Шаги анализа снизу вверх |  Шаги синтаксического анализа сверху вниз |
Противоположным этому является анализ сверху вниз, в котором общая структура ввода сначала решается (или угадывается), прежде чем работать с частями среднего уровня, оставляя завершение всех деталей нижнего уровня на потом. Нисходящий синтаксический анализатор обнаруживает и обрабатывает иерархическое дерево, начиная сверху, и постепенно продвигается сначала вниз, а затем вправо. Нисходящий синтаксический анализ с нетерпением решает, что представляет собой конструкция намного раньше, когда он только просканировал самый левый символ этой конструкции и еще не проанализировал ни одну из ее частей. Левый угол синтаксический анализ - это гибридный метод, который работает снизу вверх по левым краям каждого поддерева и сверху вниз по остальной части дерева синтаксического анализа.
Если грамматика языка имеет несколько правил, которые могут начинаться с одних и тех же крайних левых символов, но иметь разные окончания, то эта грамматика может быть эффективно обработана с помощью детерминированного восходящего синтаксического анализа, но не может быть обработана сверху вниз без догадок и с возвратом. Таким образом, восходящие синтаксические анализаторы обрабатывают несколько больший диапазон грамматик компьютерного языка, чем детерминированные нисходящие синтаксические анализаторы.
Анализ снизу вверх иногда выполняется с помощью поиска с возвратом. Но гораздо чаще восходящий синтаксический анализ выполняется парсером сдвиг-уменьшение, например, парсером LALR.
Некоторые из парсеры, которые используют восходящий синтаксический анализ, включают:
