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