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 в худшем случае имеет такую же сложность, как алгоритм Кока — Янгера — Касами и алгоритм Эрли — O(n³). Однако, у GLR-алгоритма имеется два преимущества:

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

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

Ссылки

• Анна Пентус, Мати Пентус, Курс «Математическая теория формальных языков» // Интуит.ру, 09.07.2007