Войти
A Парсер GLR (GLR означает «Generalized LR», где L означает «слева направо», а R означает «крайний правый (вывод)») является расширением алгоритма парсера LR для обработки недетерминированных и неоднозначных грамматик. Теоретическая основа была предоставлена в статье 1974 года Бернарда Лэнга (наряду с другими общими контекстно-свободными парсерами, такими как GLL). Он описывает систематический способ создания таких алгоритмов и предоставляет единообразные результаты в отношении доказательств правильности, сложности в отношении классов грамматики и методов оптимизации. Первая реальная реализация GLR была описана в 1984 г. в статье Масару Томита, она также упоминалась как «параллельный синтаксический анализатор». Томита представил пять этапов в своей первоначальной работе, хотя на практике это второй этап, который распознается как синтаксический анализатор GLR.
Хотя алгоритм эволюционировал с момента его первоначальной формы, принципы остались нетронутыми. Как показано в более ранней публикации, Ланг в первую очередь интересовался более простыми в использовании и более гибкими синтаксическими анализаторами для расширяемых языков программирования. Целью Томиты было тщательно и эффективно разобрать текст на естественном языке. Стандартные парсеры LR не могут приспособиться к недетерминированной и неоднозначной природе естественного языка, а алгоритм GLR может.
Вкратце, алгоритм GLR работает следующим образом аналогичен алгоритму парсера LR, за исключением того, что с учетом конкретной грамматики парсер GLR будет обрабатывать все возможные интерпретации заданного ввода в поиске в ширину. Во внешнем интерфейсе генератор синтаксического анализа GLR преобразует входную грамматику в таблицы синтаксического анализатора аналогично генератору LR. Однако если таблицы синтаксического анализа LR допускают только один переход состояния (с учетом состояния и входного токена), таблицы синтаксического анализа GLR допускают несколько переходов. Фактически, GLR позволяет сдвигать / уменьшать и уменьшать / уменьшать конфликты.
Когда встречается конфликтующий переход, стек синтаксического анализа разветвляется на два или более параллельных стека синтаксического анализа, где состояние, соответствующее каждому возможному переходу, находится наверху. Затем считывается следующий входной токен и используется для определения следующего перехода (переходов) для каждого из «верхних» состояний - и может произойти дальнейшее разветвление. Если какое-либо заданное верхнее состояние и входной токен не приводят хотя бы к одному переходу, тогда этот «путь» через таблицы синтаксического анализа недействителен и может быть отброшен.
Важная оптимизация позволяет использовать общие префиксы и суффиксы этих стеков, что ограничивает общее пространство поиска и использование памяти, необходимое для синтаксического анализа входящего текста. Сложные структуры, которые возникают в результате этого улучшения, делают поисковый граф направленным ациклическим графом (с дополнительными ограничениями на «глубины» различных узлов), а не деревом.
Распознавание с использованием алгоритма GLR имеет ту же временную сложность в наихудшем случае, что и алгоритм CYK и алгоритм Эрли : O (n). Однако у GLR есть два дополнительных преимущества:
На практике грамматики большинства языков программирования являются детерминированными или «почти детерминированными», что означает, что любой недетерминизм обычно разрешается в пределах небольшого (хотя, возможно, неограниченного) числа токенов. По сравнению с другими алгоритмами, способными обрабатывать полный класс контекстно-свободных грамматик (например, Earley или CYK), алгоритм GLR дает лучшую производительность на этих «почти детерминированных» грамматиках, потому что только один стек будет активен в течение большей части процесс разбора.
GLR можно комбинировать с алгоритмом LALR (1) в гибридном анализаторе, что обеспечивает еще более высокую производительность.
