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 более производительный на таких «почти детерминированных» грамматиках, так как в течение почти всего разбора остается активной только одна ветвь стека.

Ссылки

• Анна Пентус, Мати Пентус, [www.intuit.ru/studies/courses/1064/170/lecture/2444?page=5 Курс «Математическая теория формальных языков» Лекция 13: «Синтаксический разбор»] // Интуит.ру, 09.07.2007

Отрывок, характеризующий GLR-парсер

Одни из них копали лопатами гору, другие возили по доскам землю в тачках, третьи стояли, ничего не делая.
Два офицера стояли на кургане, распоряжаясь ими. Увидав этих мужиков, очевидно, забавляющихся еще своим новым, военным положением, Пьер опять вспомнил раненых солдат в Можайске, и ему понятно стало то, что хотел выразить солдат, говоривший о том, что всем народом навалиться хотят. Вид этих работающих на поле сражения бородатых мужиков с их странными неуклюжими сапогами, с их потными шеями и кое у кого расстегнутыми косыми воротами рубах, из под которых виднелись загорелые кости ключиц, подействовал на Пьера сильнее всего того, что он видел и слышал до сих пор о торжественности и значительности настоящей минуты.


Пьер вышел из экипажа и мимо работающих ополченцев взошел на тот курган, с которого, как сказал ему доктор, было видно поле сражения.
Было часов одиннадцать утра. Солнце стояло несколько влево и сзади Пьера и ярко освещало сквозь чистый, редкий воздух огромную, амфитеатром по поднимающейся местности открывшуюся перед ним панораму.
Вверх и влево по этому амфитеатру, разрезывая его, вилась большая Смоленская дорога, шедшая через село с белой церковью, лежавшее в пятистах шагах впереди кургана и ниже его (это было Бородино). Дорога переходила под деревней через мост и через спуски и подъемы вилась все выше и выше к видневшемуся верст за шесть селению Валуеву (в нем стоял теперь Наполеон). За Валуевым дорога скрывалась в желтевшем лесу на горизонте. В лесу этом, березовом и еловом, вправо от направления дороги, блестел на солнце дальний крест и колокольня Колоцкого монастыря. По всей этой синей дали, вправо и влево от леса и дороги, в разных местах виднелись дымящиеся костры и неопределенные массы войск наших и неприятельских. Направо, по течению рек Колочи и Москвы, местность была ущелиста и гориста. Между ущельями их вдали виднелись деревни Беззубово, Захарьино. Налево местность была ровнее, были поля с хлебом, и виднелась одна дымящаяся, сожженная деревня – Семеновская.
Все, что видел Пьер направо и налево, было так неопределенно, что ни левая, ни правая сторона поля не удовлетворяла вполне его представлению. Везде было не доле сражения, которое он ожидал видеть, а поля, поляны, войска, леса, дымы костров, деревни, курганы, ручьи; и сколько ни разбирал Пьер, он в этой живой местности не мог найти позиции и не мог даже отличить ваших войск от неприятельских.
«Надо спросить у знающего», – подумал он и обратился к офицеру, с любопытством смотревшему на его невоенную огромную фигуру.
– Позвольте спросить, – обратился Пьер к офицеру, – это какая деревня впереди?
– Бурдино или как? – сказал офицер, с вопросом обращаясь к своему товарищу.
– Бородино, – поправляя, отвечал другой.
Офицер, видимо, довольный случаем поговорить, подвинулся к Пьеру.
– Там наши? – спросил Пьер.
– Да, а вон подальше и французы, – сказал офицер. – Вон они, вон видны.
– Где? где? – спросил Пьер.
– Простым глазом видно. Да вот, вот! – Офицер показал рукой на дымы, видневшиеся влево за рекой, и на лице его показалось то строгое и серьезное выражение, которое Пьер видел на многих лицах, встречавшихся ему.
– Ах, это французы! А там?.. – Пьер показал влево на курган, около которого виднелись войска.
– Это наши.
– Ах, наши! А там?.. – Пьер показал на другой далекий курган с большим деревом, подле деревни, видневшейся в ущелье, у которой тоже дымились костры и чернелось что то.
– Это опять он, – сказал офицер. (Это был Шевардинский редут.) – Вчера было наше, а теперь его.
– Так как же наша позиция?