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

StackOverflow https://stackoverflow.com/questions/929819

  •  06-09-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top