Как работают рекурсивные парсингеры? Я написал рекурсивный парсер , но я не очень разбираюсь в парсерах LR. Что я found on Wikipedia только добавил к моей путанице.Как работают рекурсивные парсингеры?
Другой вопрос, почему рекурсивные синтаксические анализаторы не используются больше, чем их таблицы-аналоги. Кажется, что рекурсивные парсеры восхождения имеют большую производительность в целом.
Классический dragon book очень хорошо объясняет, как работают парные анализаторы LR. Существует также Parsing Techniques. A Practical Guide., где вы можете прочитать о них, если я хорошо помню. Статья в Википедии (по крайней мере, введение) неверна. Они были созданы Дональдом Кнутом, и он объясняет их в «Искусстве компьютерного программирования» Том 5. Если вы понимаете испанский, есть полный список книг here, размещенных мной. Не все эти книги находятся на испанском языке.
Прежде чем понимать, как они работают, вы должны понимать несколько концепций, таких как, в первую очередь, следующие и взгляды. Кроме того, я действительно рекомендую вам понять концепции парсеров LL (потомков), прежде чем пытаться понять парсер LR (восходящий).
Существует семейство парсеров LR, в частности LR (K), SLR (K) и LALR (K), где K - это то, сколько нужно, чтобы они работали. Yacc поддерживает парсер LALR (1), но вы можете делать хитрости, а не теорию, чтобы заставить ее работать с более мощными типами грамматик.
О производительности, это зависит от анализируемой грамматики. Они выполняются в линейном времени, но сколько места им нужно, зависит от того, сколько состояний вы создаете для окончательного анализатора.
Том 5 лет! В лучшем случае. Надеюсь, я смогу вернуться на эту страницу в 2020 году или когда и смеяться над этим комментарием. –
Мне лично сложно понять, как вызов функции может быть быстрее - гораздо меньше «значительно быстрее», чем поиск в таблице. И я подозреваю, что даже «значительно быстрее» незначителен по сравнению со всем остальным, что должен делать лексер/парсер (в основном, чтение и токенизация файла). Я посмотрел страницу Википедии, но не следил за ссылками; действительно ли автор профилировал полный лексер/парсер?
Более интересным для меня является снижение парсеров, управляемых таблицами, относительно рекурсивного спуска. Я исхожу из фона C, где yacc (или эквивалент) является генератором синтаксического анализатора. Когда я перешел на Java, я нашел одну управляемую таблицами реализацию (JavaCup) и несколько рекурсивных реализаций спуска (JavaCC, ANTLR).
Я подозреваю, что ответ подобен ответу «почему Java вместо C»: скорость исполнения не так важна, как скорость разработки. Как отмечалось в статье в Википедии, синтаксические анализаторы, основанные на таблицах, практически невозможно понять из кода (когда я их использовал, я мог следить за их действиями, но никогда не смог бы восстановить грамматику из синтаксического анализатора). Рекурсивный спуск, для сравнения, очень интуитивно понятен (что, без сомнения, связано с тем, что оно предшествует ориентированию на таблицы примерно на 20 лет).
+1 от меня - действительно хороший ответ. – duffymo
Рекурсивный спуск медленнее, чем парсеры LR, управляемые таблицами. Мне интересно о рекурсивном восхождении, которое совсем другое зверь. –
Да, в статье рекурсивного восхождения есть встроенные вызовы функций для представления конечного автомата, а не переменная и таблицы. И, как я сказал в первом абзаце, я не покупаю, что это быстрее, особенно в контексте использования парсера. – kdgregory
Статья в Википедии по рекурсивному Восхождение Анализ синтаксического анализа, который кажется оригинальным документом по теме («Очень быстрый анализ LR»). Снимая эту бумагу, я очистил несколько вещей для меня. Что я заметил:
В статье говорится о генерации кода сборки. Интересно, можете ли вы сделать то же самое, что и они, если вместо этого вы генерируете код C или Java? см. разделы 4 и 5, «Восстановление ошибок» и «Проверка переполнения стека». (Я не пытаюсь использовать их технику - это может сработать хорошо - просто сказать, что это то, что вы, возможно, захотите изучить, прежде чем совершать.)
Они сравнивают свой рекурсивный всплывающий инструмент с собственным парсером, управляемым таблицами. Из описания в их разделе результатов, похоже, что их парсер-парсер «полностью интерпретируется»; он не требует какого-либо настраиваемого кода. Интересно, есть ли место, где общая структура по-прежнему работает на основе таблиц, но вы создаете собственный код для определенных действий, чтобы ускорить работу.
Бумага ссылается на страницу Википедии:
Другой бумаги об использовании кода поколения вместо таблицы -интерпретация:
Кроме того, обратите внимание, что рекурсивного спуска разбора не самый быстрый способ разбора LL-грамматики на основе языков:
+1 Я интересно то же самое. Рекурсивные парсеры спуска настолько просты в понимании, но так трудно получить право. Парсеры LR легко писать с генератором (например, YACC), но я никогда не понимал, как это работает «под капотом». – Zifre
Значок «Хороший вопрос» :) –