Нисходящий парсер | это... Что такое Нисходящий парсер? (original) (raw)
Нисходящий парсер
Нисходящий парсер
Метод рекурсивного спуска или нисходящий разбор — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно-свободной грамматикой. Это класс алгоритмов грамматического анализа, где правила формальной грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.
Содержание
Идея метода
Для каждого нетерминального символа K строится функция, которая для любого входного слова x делает 2 вещи:
- Находит наибольшее начало z слова x, способное быть началом выводимого из K слова
- Определяет, является ли начало z выводимым из K
Такая функция должна удовлетворять следующим критериям:
- считывать из еще необработанного входного потока максимальное начало A, являющегося началом некоторого слова, выводимого из K
- определять является ли A выводимым из K или просто невыводимым началом выводимого из K слова
В случае, если такое начало считать не удается (и корректность функции для нетерминала K доказана), то входные данные не соответствуют языку, и следует остановить разбор.
Разбор заключается в вызове описанных выше функций. Если для считанного нетерминала есть составное правило, то при его разборе будут вызваны другие функции для разбора входящих в него терминалов. Дерево вызовов, начиная с самой «верхней» функции эквивалентно дереву разбора.
Наиболее простой и «человечный» вариант создания анализатора, использующего метод рекурсивного спуска, — это непосредственное программирование по каждому правилу вывода для нетерминалов грамматики.
Условия применения
Пусть в данной формальной грамматике N — это конечное множество нетерминальных символов; Σ — конечное множество терминальных символов, тогда метод рекурсивного спуска применим только, если каждое правило этой грамматики имеет следующий вид:
Алгоритмы нисходящего разбора
- Рекурсивный нисходящий парсер (en:Recursive descent parser)
- LL-парсер (en:LL parser)
- Парсер старьёвщика (en:Packrat parser)
Литература
- А. Шень. Программирование: теоремы и задачи. 2-е изд., М.: МЦНМО, 2004
- Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4
- Робин Хантер Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2
Wikimedia Foundation.2010.
Полезное
Смотреть что такое "Нисходящий парсер" в других словарях:
- Рекурсивный нисходящий парсер — (англ. Recursive descent parser) алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно свободной грамматики или БНФ. Применения правил последовательно, слева направо … Википедия
- Нисходящий синтаксический анализ — (англ. top down parsing) это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где правила… … Википедия
- Нисходящий разбор — Метод рекурсивного спуска или нисходящий разбор это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где… … Википедия
- Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
- Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
- Рекурсивный спуск — Метод рекурсивного спуска или нисходящий разбор это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно свободной грамматикой. Это класс алгоритмов грамматического анализа, где… … Википедия
- Синтаксический анализ — В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно… … Википедия
- Грамматический анализ — В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора. Обычно применяется совместно с лексическим … Википедия
- Грамматический разбор — В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора. Обычно применяется совместно с лексическим … Википедия
- Парсинг — В информатике, синтаксический анализ (парсинг) это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом обычно является дерево разбора. Обычно применяется совместно с лексическим … Википедия