Анализ снизу вверх - Bottom-up parsing

В Информатика, разбор раскрывает грамматическую структуру текста линейного ввода в качестве первого шага в выяснении его значения. Анализ снизу вверх сначала распознает мелкие детали самого низкого уровня текста, а затем его структуры среднего уровня, и оставляет общую структуру самого высокого уровня на потом.[1]

Снизу вверх или сверху вниз

Название «снизу вверх» происходит от концепции дерево синтаксического анализа, в котором наиболее подробные части находятся в нижней части перевернутого дерева, а составленные из них более крупные структуры находятся на последовательно более высоких уровнях, пока на вершине или «корне» дерева один элемент не описывает весь входной поток. Восходящий синтаксический анализ обнаруживает и обрабатывает это дерево, начиная с нижнего левого края, и постепенно продвигается вверх и вправо.[2] Синтаксический анализатор может воздействовать на нижний, средний и верхний уровни иерархии структуры, даже не создавая фактического дерева данных; тогда дерево просто неявно присутствует в действиях парсера. Восходящий синтаксический анализ терпеливо ожидает, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем принять решение о том, что представляет собой комбинированная конструкция.

Типичное дерево разбора для
А = В + С * 2; D = 1
Шаги синтаксического анализа снизу вверх
Шаги синтаксического анализа сверху вниз

Противоположным этому является нисходящий синтаксический анализ, в котором общая структура входных данных определяется (или угадывается) в первую очередь, прежде чем работать с частями среднего уровня, оставляя завершение всех деталей нижнего уровня на потом. Нисходящий синтаксический анализатор обнаруживает и обрабатывает иерархическое дерево, начиная сверху, и постепенно продвигается сначала вниз, а затем вправо. Нисходящий синтаксический анализ с нетерпением решает, что представляет собой конструкция намного раньше, когда он только просканировал самый левый символ этой конструкции и еще не проанализировал ни одну из ее частей. Левый угол разбор - это гибридный метод, который работает снизу вверх по левым краям каждого поддерева и сверху вниз по остальной части дерева синтаксического анализа.

Если грамматика языка имеет несколько правил, которые могут начинаться с одних и тех же крайних левых символов, но иметь разные окончания, то с этой грамматикой можно эффективно справиться с помощью детерминированный восходящий синтаксический анализ, но не может быть обработан сверху вниз без догадок и возврат. Таким образом, восходящие синтаксические анализаторы обрабатывают несколько больший диапазон грамматик компьютерного языка, чем детерминированные нисходящие синтаксические анализаторы.

Анализ снизу вверх иногда выполняется возврат. Но гораздо чаще анализ снизу вверх выполняется парсер сдвиг-уменьшение например, Парсер LALR.

Примеры

Некоторые из парсеров, использующих восходящий анализ, включают:

использованная литература

  1. ^ Арвинд Кумар Бансал (14 декабря 2013 г.). Введение в языки программирования. CRC Press. ISBN  978-1-4665-6514-2.
  2. ^ Компиляторы: принципы, методы и инструменты (2-е издание), Альфред Ахо, Моника Лам, Рави Сетхи и Джеффри Уллман, Prentice Hall 2006.
  3. ^ Дик Грюн; Ceriel J.H. Джейкобс (29 октября 2007 г.). Методы синтаксического анализа: практическое руководство. Springer Science & Business Media. ISBN  978-0-387-68954-8.