Как работают парсеры рекурсивного восхождения?

Question

Как работают парсеры рекурсивного восхождения? Я сам написал рекурсивный парсер спуск , но не очень хорошо понимаю парсеры LR. То, что я нашел в Википедии , только добавило моего замешательства.

Другой вопрос, почему рекурсивные синтаксические анализаторы не используются чаще, чем их табличные аналоги. Похоже, что рекурсивные синтаксические анализаторы в целом имеют более высокую производительность.

Answer 1

Классическая книга драконов очень хорошо объясняет, как работают парсеры LR. Существует также Техника синтаксического анализа. Практическое руководство. где вы можете прочитать о них, если я хорошо помню. Статья в википедии (хотя бы введение) не права. Они были созданы Дональдом Кнутом, и он объясняет их в своей книге «Искусство компьютерного программирования», том 5. Если вы понимаете испанский, здесь есть полный список книг здесь , опубликованных мной. Не все эти книги тоже на испанском.

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

Существует семейство синтаксических анализаторов LR, особенно LR (K), SLR (K) и LALR (K), где K - это количество ожидающих их работы. Yacc поддерживает парсеры LALR (1), но вы можете сделать твики, не основанные на теории, чтобы они работали с более мощными грамматиками.

Что касается производительности, это зависит от анализируемой грамматики. Они выполняются за линейное время, но сколько места им нужно, зависит от того, сколько состояний вы создадите для конечного анализатора.

Answer 2

Мне лично трудно понять, как вызов функции может быть быстрее - гораздо менее "значительно быстрее", чем поиск в таблице. И я подозреваю, что даже «значительно быстрее» несущественно по сравнению со всем остальным, что должен делать лексер / парсер (в первую очередь чтение и токенизация файла). Я посмотрел на страницу Википедии, но не следовал ссылкам; действительно ли автор профилировал полный лексер / парсер?

Более интересным для меня является снижение количества парсерных таблиц в отношении рекурсивного спуска. Я пришел из C-фона, где yacc (или его эквивалент) был предпочтительным генератором парсера. Когда я перешел на Java, я обнаружил одну реализацию на основе таблиц (JavaCup) и несколько реализаций с рекурсивным спуском (JavaCC, ANTLR).

Я подозреваю, что ответ похож на ответ "почему Java вместо C": скорость выполнения не так важна, как скорость разработки. Как отмечалось в статье в Википедии, анализаторы на основе таблиц практически невозможно понять из кода (когда я использовал их, я мог следить за их действиями, но никогда не смог бы восстановить грамматику из анализатора). Для сравнения, рекурсивный спуск очень интуитивен (и это, несомненно, объясняется тем, что он предшествует настольному управлению примерно через 20 лет).

Answer 3

Статья в Википедии о рекурсивном восхождении разборе ссылок на то, что кажется оригинальной статьей по теме («Очень быстрый анализ LR»). Просматривая эту бумагу, я кое-что прояснил. Вещи, которые я заметил:

1. В статье рассказывается о генерации кода сборки. Интересно, можете ли вы сделать то же самое, что и они, если вместо этого вы генерируете код на C или Java; см. разделы 4 и 5 «Восстановление после ошибок» и «Проверка переполнения стека». (Я не пытаюсь подделать их технику - это может сработать нормально - просто говорю, что это то, на что вы, возможно, захотите взглянуть перед фиксацией.)

2. Они сравнивают свой инструмент рекурсивного всплытия с собственным анализатором, управляемым таблицей. Из описания в их разделе результатов видно, что их анализатор, управляемый таблицами, «полностью интерпретирован»; это не требует никакого сгенерированного кода. Интересно, есть ли середина, где общая структура все еще управляется таблицами, но вы генерируете собственный код для определенных действий, чтобы ускорить процесс.

Статья, на которую ссылается страница Википедии:

• "Очень быстрый разбор LR" (1986)
• http://portal.acm.org/citation.cfm?id=13310.13326

Еще одна статья об использовании генерации кода вместо интерпретации таблиц:

• "Очень быстрые парсеры, совместимые с YACC (для очень небольшого усилия)" (1999)
• http://www3.interscience.wiley.com/journal/1773/abstract

Также обратите внимание, что синтаксический анализ с рекурсивным спуском не является самым быстрым способом анализа языков на основе LL:

• Разница между LL и парсером рекурсивного спуска?