Парсер GLR - GLR parser

РВО анализатор (РВО стоя для «обобщенной LR», где L обозначает «влево-вправо» и R означает «крайний правый (вывод)») является расширением на LR синтаксического анализ алгоритма для обработки недетерминированных и неоднозначные грамматик . Теоретическая основа была предоставлена ​​в статье 1974 года Бернарда Лэнга (наряду с другими общими контекстно-свободными синтаксическими анализаторами, такими как GLL). Он описывает систематический способ создания таких алгоритмов и предоставляет единообразные результаты, касающиеся доказательств правильности, сложности по отношению к классам грамматики и методов оптимизации. Первая реальная реализация GLR была описана в 1984 году в статье Масару Томита , ее также называли «параллельным синтаксическим анализатором». Томита представил пять этапов в своей первоначальной работе, хотя на практике это второй этап, который распознается как синтаксический анализатор GLR.

Хотя алгоритм эволюционировал с момента его первоначальной формы, принципы остались неизменными. Как показано в более ранней публикации, Ланг в первую очередь интересовался более простыми в использовании и более гибкими синтаксическими анализаторами для расширяемых языков программирования . Целью Томиты было тщательное и эффективное разбор текста на естественном языке . Стандартные парсеры LR не могут приспособиться к недетерминированной и неоднозначной природе естественного языка , а алгоритм GLR может.

Алгоритм

Вкратце, алгоритм GLR работает аналогично алгоритму синтаксического анализатора LR , за исключением того, что, учитывая конкретную грамматику, синтаксический анализатор GLR будет обрабатывать все возможные интерпретации заданного ввода в поиске в ширину . Во внешнем интерфейсе генератор парсера GLR преобразует входную грамматику в таблицы парсера аналогично генератору LR. Однако там, где таблицы синтаксического анализа LR допускают только один переход состояния (с учетом состояния и входного токена), таблицы синтаксического анализа GLR допускают несколько переходов. Фактически, GLR позволяет сдвигать / уменьшать и уменьшать / уменьшать конфликты.

Когда встречается конфликтующий переход, стек синтаксического анализа разветвляется на два или более параллельных стека синтаксического анализа, где состояние, соответствующее каждому возможному переходу, находится наверху. Затем считывается следующий входной токен и используется для определения следующего перехода (переходов) для каждого из «верхних» состояний - и может произойти дальнейшее разветвление. Если какое-либо заданное верхнее состояние и входной токен не приводят хотя бы к одному переходу, то этот «путь» через таблицы синтаксического анализа недействителен и может быть отброшен.

Важная оптимизация позволяет использовать общие префиксы и суффиксы этих стеков, что ограничивает общее пространство поиска и использование памяти, необходимое для синтаксического анализа входящего текста. Сложные структуры, возникающие в результате этого улучшения, делают граф поиска ориентированным ациклическим графом (с дополнительными ограничениями на «глубины» различных узлов), а не деревом.

Преимущества

Распознавание с использованием алгоритма GLR имеет тот же самый худший случай времени сложность в качестве алгоритма CYK и алгоритма EARLEY : O ( п 3 ). Однако у GLR есть два дополнительных преимущества:

  • Время, необходимое для запуска алгоритма, пропорционально степени недетерминизма в грамматике: на детерминированных грамматиках алгоритм GLR выполняется за время O ( n ) (это не относится к алгоритмам Эрли и CYK, но исходные алгоритмы Эрли могут быть изменен, чтобы обеспечить это)
  • Алгоритм GLR является «интерактивным», то есть он потребляет входные токены в определенном порядке и выполняет как можно больше работы после использования каждого токена (также верно для Эрли).

На практике грамматики большинства языков программирования являются детерминированными или «почти детерминированными», что означает, что любой недетерминизм обычно разрешается в пределах небольшого (хотя, возможно, неограниченного) числа токенов. По сравнению с другими алгоритмами, способными обрабатывать полный класс контекстно-свободных грамматик (например, Earley или CYK), алгоритм GLR дает лучшую производительность на этих «почти детерминированных» грамматиках, потому что только один стек будет активен в течение большей части времени. процесс разбора.

GLR может быть объединен с алгоритмом LALR (1) в гибридном анализаторе, что обеспечивает еще более высокую производительность.

Смотрите также

использованная литература

дальнейшее чтение

  • Грун, Дик; Джейкобс, Сериэль JH (2008). Методы синтаксического анализа . Springer Science + Business Media. ISBN 978-0-387-20248-8.
  • Томита, Масару (1984). «Парсеры LR для естественных языков». ОГРАНИЧЕНИЕ . 10-я Международная конференция по компьютерной лингвистике. С. 354–357.
  • Томита, Масару (1985). «Эффективный контекстно-свободный алгоритм синтаксического анализа для естественных языков». IJCAI . Международная совместная конференция по искусственному интеллекту. С. 756–764.