Анализ снизу вверх
В компьютерных науках синтаксический анализ выявляет грамматическую структуру линейного входного текста в качестве первого шага в определении его значения. Синтаксический анализ снизу вверх сначала распознает мелкие детали текста самого низкого уровня, прежде чем его структуры среднего уровня, и оставляет общую структуру самого высокого уровня напоследок. [1]
Название «снизу вверх» происходит от концепции дерева синтаксического анализа , в котором наиболее детализированные части находятся внизу перевернутого дерева, а более крупные структуры, составленные из них, находятся в последовательно более высоких слоях, пока не окажутся наверху или «корне». "дерева одна единица описывает весь входной поток. Анализ снизу вверх обнаруживает и обрабатывает это дерево, начиная с нижнего левого конца, и постепенно продвигается вверх и вправо. [2] Синтаксический анализатор может работать на нижнем, среднем и верхнем уровнях иерархии структуры, даже не создавая фактического дерева данных; тогда дерево просто неявно присутствует в действиях синтаксического анализатора. Синтаксический анализ снизу вверх терпеливо ждет, пока он не просмотрит и не проанализирует все части некоторой конструкции, прежде чем принять решение о том, что представляет собой объединенная конструкция.
Противоположностью этому является синтаксический анализ сверху вниз , при котором сначала определяется (или угадывается) общая структура входных данных, прежде чем обрабатывать части среднего уровня, а завершение всех деталей самого низкого уровня остается напоследок. Нисходящий синтаксический анализатор обнаруживает и обрабатывает иерархическое дерево, начиная с вершины, и постепенно продвигается сначала вниз, а затем вправо. Нисходящий синтаксический анализ с готовностью решает, что представляет собой конструкция, намного раньше, когда он только просмотрел крайний левый символ этой конструкции и еще не проанализировал ни одну из ее частей. Анализ левого угла — это гибридный метод, который работает снизу вверх по левым краям каждого поддерева и сверху вниз по остальной части дерева разбора.
Если грамматика языка имеет несколько правил, которые могут начинаться с одних и тех же крайних левых символов, но иметь разные окончания, то эта грамматика может быть эффективно обработана детерминистическим анализом снизу вверх, но не может быть обработана сверху вниз без догадок и поиска с возвратом . Таким образом, восходящие синтаксические анализаторы обрабатывают несколько больший диапазон грамматик компьютерных языков, чем детерминированные нисходящие синтаксические анализаторы.
Синтаксический анализ снизу вверх иногда выполняется путем поиска с возвратом . Но гораздо чаще синтаксический анализ снизу вверх выполняется синтаксическим анализатором сдвига и уменьшения , таким как синтаксический анализатор LALR .
