GLR-парсер

GLR парсер (от англ. Generalized Left-to-right Rightmost derivation parser — Обобщенный восходящий магазинный анализатор) — в информатике расширенный алгоритм LR-парсера, предназначенный для разбора по недетерменированным и неоднозначным грамматикам. Впервые описанный Масару Томита (англ. Masaru Tomita) в 1984 году, его также называют «параллельным парсером».

Поскольку этот алгоритм является производным от LR парсера, принципы его работы остались прежними: Томита ставил перед собой цель добиться быстрого и эффективного распознавания текстов написанных на естественном языке. Обычный LR парсер не способен разрешать недетерменированность и неоднозначность естественных языков, тогда как GLR алгоритм может.

Алгоритм

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

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

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

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

Алгоритм GLR в худшем случае имеет такую же сложность как алгоритм CYK (англ.) и алгоритм Эрли (англ.) — O(n³). Однако у GLR-алгоритма имеется два преимущества:

• Время необходимое для выполнения алгоритма пропорционально степени недетерминированности исходной грамматики — при полностью детерминированной грамматике GLR алгоритм работает за O(n). (Для Earley и CYK алгоритмов это не так, хотя оригинальный алгоритм Earley может быть модифицирован для получения такого же преимущества).
• Алгоритм GLR «оперативный» (it is on-line) — считывая каждый символ из входного буфера он производит как можно больше работы по анализу доступной по прочнению данной входной последовательности.

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

Ссылки

• Лекция «Синтаксический разбор»