Что такое IELR (1) -парсер?

Я пытаюсь научить себя использованию зубров. На странице man bison (1) говорится о зубре:

Создайте детерминированный LR или обобщенный анализатор LR (GLR) с использованием таблиц LALR (1), IELR (1) или канонических LR (1).

Что такое IELR-парсер? Все соответствующие статьи, которые я нашел во всемирной паутине, оплачиваются.

formal-languages terminology formal-grammars parsers FUZxxl
источник

Включая cs.clemson.edu/~malloy/papers/sac08/paper.pdf ?

reinierpost

@reinierpost Я чувствую себя так глупо сейчас. Почему я не нашел это?

FUZxxl

Я не знаю - Google персонализирует результаты ...

reinierpost

@reinierpost, не могли бы вы ответить на этот вопрос, цитируя свою ссылку, чтобы очистить этот вопрос ?

Merbs

Хммм ... если это все, что нужно, хорошо.

reinierpost

Ответы:

Алгоритм разбора IELR (1)

Алгоритм (1) синтаксический IELR был разработан в 2008 году Джоэл Е. Denny как часть его Ph.D. исследования под руководством Брайана А. Маллой в Университете Клемсона. Алгоритм IELR (1) представляет собой разновидность так называемого «минимального» алгоритма LR (1), разработанного Дэвидом Пейджером в 1977 году , который сам является вариацией алгоритма синтаксического анализа LR (k), изобретенного Дональдом Кнутом в 1965 году . IE в IELR (1) означает устранение неадекватности (см. Последний раздел).

LR (1) Алгоритмы

LR (1) часть IELR (1) означает L EFT направо, R ightmost вывод с 1 опережение маркера. Парсеры LR (1) также называются каноническими парсерами. В этом классе алгоритмов синтаксического анализа используется стратегия синтаксического анализа "снизу вверх" и "сдвиг-уменьшение" с таблицей стеков и переходов состояний, определяющей следующее действие, которое необходимо выполнить во время синтаксического анализа.

Исторически алгоритмы LR (1) были в невыгодном положении из-за больших требований к памяти для своих таблиц переходов. Пейджером было улучшено создание метода объединения переходных состояний при создании таблицы перехода, что значительно уменьшило размер таблицы. Таким образом, алгоритм Пейджера делает парсеры LR (1) конкурентоспособными с другими стратегиями синтаксического анализа с точки зрения эффективности пространства и времени. Фраза «минимальный парсер LR (1)» относится к минимальному размеру таблицы переходов, введенной алгоритмом Пейджера.

Ограничения алгоритма пейджера

Минимальные алгоритмы LR (1) создают таблицу переходов на основе конкретной входной грамматики для анализируемого языка. Разные грамматики могут создавать один и тот же язык. В самом деле, грамматика, не относящаяся к LR (1), может создать синтаксический язык LR (1). На практике генераторы синтаксического анализатора LR (1) принимают грамматики не-LR (1) со спецификацией для разрешения конфликтов между двумя возможными переходами состояний («конфликты сдвига-уменьшения»), чтобы учесть этот факт. Денни и Маллой обнаружили, что алгоритм Пейджера не может генерировать достаточно мощные синтаксические анализаторы для синтаксического анализа языков LR (1) при наличии определенных грамматик не-LR (1), хотя грамматика не-LR (1) генерирует язык LR (1).

Денни и Маллой показывают, что это ограничение не просто академическое, демонстрируя, что Gawk и Gpic, оба широко используемые, зрелые программы, выполняют некорректные действия парсера.

Улучшения IELR (1)

Денни и Маллой изучили источник недостатков алгоритма Пейджера, сравнив таблицу переходов, сгенерированную алгоритмом Пейджера, с таблицей переходов эквивалентной грамматики LR (1) и определили два источника, которые они называют неадекватностями, которые появляются в таблице переходов из таблицы Пейджера. алгоритм, но не в таблице переходов LR (1). Алгоритм Денни и Маллоя IELR (1) ( устранение неадекватности LR (1)) - это алгоритм, разработанный для устранения этих недостатков при создании таблицы переходов, размер которой практически идентичен размеру алгоритма Пейджера.

Роберт Якобсон
источник

Статья, которая претендует на введение: IELR (1): практические таблицы синтаксического анализа LR (1) для не-LR (1) грамматик с разрешением конфликтов (через archive.org). Автор - Джоэл Э. Денни и Брайан А. Маллой, Университет Клемсона. , свободно доступен с сайта Маллой.

Чего они стоят, я не могу ответить. (Лично я не понимаю необходимости такого урезанного разбора CFG - зачем ограничивать вашу выразительную силу, когда вы можете просто использовать GLR ? Что имеет для меня смысл, это что-то вроде TAG или PEG (они кажутся естественными и добавляют выразительную силу) или дерево грамматики (для языков, таких как XML, в которых распознавание деревьев разбора не вызывает затруднений).

reinierpost
источник

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

Бабу

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

FUZxxl

Я не понимаю, почему это будет проблемой.

reinierpost

@reinierpost Это линейное время против худшего случая-

O (n^{4})

$O(n^4)$ (GLR) или

O (n^{3})

$O(n^3)$ (GLL). Например, для компиляции больших исходных файлов это может занять много времени. Кроме того, отношение предпочтения выразительности над ограничением без поддержки пренебрегает потерей времени. Технически мы могли бы использовать сверхэкспрессивные формализмы sLMG и / или PMCFG, но тогда мы будем иметь дело с до

l i m_{x \to \infty} O (n^{x})

$lim_{x\rightarrow\infty} O(n^x)$ , Это может быть абсурдным примером, но мотивация - всегда время . Люди не живут вечно, и у них много дел. Тратить свое время, как правило, плохо.

пользователь

Я хотел бы отметить, что «Лично я не понимаю необходимости в таком искаженном разборе CFG - зачем ограничивать вашу выразительную силу, когда вы можете просто использовать GLR?» довольно ошибочно в этом контексте. IELR (1) используется для генерации более эффективных таблиц парсера LR (1), что позволяет создавать более эффективные парсеры GLR .

orlp