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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Документ, на который ссылается страница Википедии:

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

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

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

Кроме того, обратите внимание, что рекурсивный спуск - это не самый быстрый способ разбора языков LL-грамматики:

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