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