В информатике , синтаксический анализ показывает грамматическую структуру линейного текста ввода, как первый шаг в разработке ее смысл. При восходящем синтаксическом анализе сначала распознаются мелкие детали самого нижнего уровня текста, а затем структуры среднего уровня, а общая структура самого верхнего уровня остается. [1]
Снизу вверх или сверху вниз [ править ]
Название "снизу вверх" происходит от концепции дерева синтаксического анализа , в котором наиболее подробные части находятся в нижней части перевернутого дерева, а составленные из них более крупные структуры находятся на последовательно более высоких уровнях, пока не окажутся наверху или "корень". "дерева" одна единица описывает весь входной поток. Восходящий синтаксический анализ обнаруживает и обрабатывает это дерево, начиная с нижнего левого края, и постепенно продвигается вверх и вправо. [2] Синтаксический анализатор может воздействовать на нижний, средний и верхний уровни иерархии структуры, никогда не создавая фактического дерева данных; тогда дерево просто неявно присутствует в действиях парсера. Восходящий синтаксический анализ терпеливо ожидает, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем зафиксировать то, что представляет собой комбинированная конструкция.
Противоположностью этому является нисходящий синтаксический анализ , при котором сначала определяется (или угадывается) общая структура ввода, прежде чем работать с частями среднего уровня, оставляя завершение всех деталей нижнего уровня на потом. Нисходящий синтаксический анализатор обнаруживает и обрабатывает иерархическое дерево, начиная с вершины, и постепенно продвигается сначала вниз, а затем вправо. Нисходящий синтаксический анализ с нетерпением решает, что представляет собой конструкция намного раньше, когда он только просканировал самый левый символ этой конструкции и еще не проанализировал ни одну из ее частей. Анализ левого угла - это гибридный метод, который работает снизу вверх по левым краям каждого поддерева и сверху вниз по остальной части дерева синтаксического анализа.
Если грамматика языка имеет несколько правил, которые могут начинаться с одних и тех же крайних левых символов, но иметь разные окончания, тогда эта грамматика может эффективно обрабатываться детерминированным восходящим синтаксическим анализом, но не может выполняться сверху вниз без догадок и обратного отслеживания . Таким образом, восходящие синтаксические анализаторы обрабатывают несколько больший диапазон грамматик компьютерного языка, чем детерминированные нисходящие синтаксические анализаторы.
Анализ снизу вверх иногда выполняется с возвратом . Но гораздо чаще восходящий синтаксический анализ выполняется синтаксическим анализатором сдвига-сокращения, таким как синтаксический анализатор LALR .
Примеры [ править ]
Некоторые из парсеров, использующих восходящий анализ, включают:
- Парсер приоритета
- Анализатор ограниченного контекста (BC)
- LR анализатор ( L EFT-направо, R ightmost вывод в обратном)
- Простой парсер LR (SLR)
- Парсер LALR (упреждающий)
- Канонический парсер LR (LR (1))
- Парсер GLR (обобщенный) [3]
- Синтаксический анализатор CYK (Кок – Янгер – Касами)
- Рекурсивный восходящий парсер
- Парсер Shift-уменьшить
Ссылки [ править ]
- ^ Арвинд Кумар Бансал (14 декабря 2013). Введение в языки программирования . CRC Press. ISBN 978-1-4665-6514-2.
- ^ Компиляторы: принципы, методы и инструменты (2-е издание), Альфред Ахо, Моника Лам, Рави Сетхи и Джеффри Уллман, Prentice Hall 2006.
- ↑ Дик Грюн; Кериэль Дж. Х. Джейкобс (29 октября 2007 г.). Методы синтаксического анализа: Практическое руководство . Springer Science & Business Media. ISBN 978-0-387-68954-8.
