РВО анализатор (РВО стоя для «обобщенной LR», где L обозначает «влево-вправо» и R означает «крайний правый (вывод)») является расширением на LR синтаксического анализ алгоритма для обработки недетерминированных и неоднозначные грамматик . [1] Теоретическая основа была предоставлена в статье 1974 года [2] Бернарда Лэнга (наряду с другими общими контекстно-свободными синтаксическими анализаторами, такими как GLL). Он описывает систематический способ создания таких алгоритмов и предоставляет единообразные результаты в отношении доказательств правильности, сложности в отношении классов грамматики и методов оптимизации. Первая реальная реализация GLR была описана в статье 1984 года Масару Томита., его также называют «параллельным синтаксическим анализатором». Томита представил пять этапов в своей первоначальной работе [3], хотя на практике это второй этап, который распознается как синтаксический анализатор GLR.
Хотя алгоритм эволюционировал с момента его первоначальной формы, принципы остались неизменными. Как показано в более ранней публикации, [4] Лэнг в первую очередь интересовался более простыми в использовании и более гибкими синтаксическими анализаторами для расширяемых языков программирования . Целью Томиты было тщательное и эффективное разбор текста на естественном языке . Стандартные парсеры LR не могут приспособиться к недетерминированной и неоднозначной природе естественного языка , а алгоритм GLR может.
Алгоритм
Вкратце, алгоритм GLR работает аналогично алгоритму парсера LR , за исключением того, что с учетом конкретной грамматики парсер GLR будет обрабатывать все возможные интерпретации заданного ввода в поиске в ширину . Во внешнем интерфейсе генератор парсера GLR преобразует входную грамматику в таблицы парсера аналогично генератору LR. Однако там, где таблицы синтаксического анализа LR допускают только один переход состояния (с учетом состояния и входного токена), таблицы синтаксического анализа GLR допускают несколько переходов. Фактически, GLR позволяет сдвигать / уменьшать и уменьшать / уменьшать конфликты.
Когда встречается конфликтующий переход, стек синтаксического анализа разветвляется на два или более параллельных стека синтаксического анализа, где состояние, соответствующее каждому возможному переходу, находится наверху. Затем считывается следующий входной токен и используется для определения следующего перехода (переходов) для каждого из «верхних» состояний - и может произойти дальнейшее разветвление. Если какое-либо заданное верхнее состояние и входной токен не приводят хотя бы к одному переходу, то этот «путь» через таблицы синтаксического анализа недействителен и может быть отброшен.
Важная оптимизация позволяет использовать общие префиксы и суффиксы этих стеков, что ограничивает общее пространство поиска и использование памяти, необходимое для синтаксического анализа входящего текста. Сложные структуры, возникающие в результате этого улучшения, делают граф поиска ориентированным ациклическим графом (с дополнительными ограничениями на «глубины» различных узлов), а не деревом.
Преимущества
Распознавание с использованием алгоритма GLR имеет тот же самый худший случай времени сложность в качестве алгоритма CYK и алгоритма EARLEY : O ( п 3 ). [ необходима цитата ] Однако GLR имеет два дополнительных преимущества:
- Время, необходимое для запуска алгоритма, пропорционально степени недетерминизма в грамматике: на детерминированных грамматиках алгоритм GLR выполняется за время O ( n ) (это не относится к алгоритмам Эрли [ необходима ссылка ] и CYK, но к исходному Для этого можно изменить алгоритмы Эрли)
- Алгоритм GLR является «интерактивным», то есть он потребляет входные токены в определенном порядке и выполняет как можно больше работы после использования каждого токена.
На практике грамматики большинства языков программирования являются детерминированными или «почти детерминированными», что означает, что любой недетерминизм обычно разрешается в пределах небольшого (хотя, возможно, неограниченного) числа токенов [ необходима ссылка ] . По сравнению с другими алгоритмами, способными обрабатывать полный класс контекстно-свободных грамматик (например, Earley или CYK), алгоритм GLR дает лучшую производительность на этих «почти детерминированных» грамматиках, потому что только один стек будет активен в течение большей части процесс разбора.
GLR можно комбинировать с алгоритмом LALR (1) в гибридном анализаторе, что обеспечивает еще более высокую производительность. [5]
Смотрите также
- Сравнение генераторов парсеров
- Мета-среда ASF + SDF
- Набор инструментов для реинжиниринга программного обеспечения DMS
- GNU Bison , генератор парсеров, который может создавать парсеры LALR и GLR
Рекомендации
- ↑ Масару Томита (6 декабря 2012 г.). Обобщенный парсинг LR . Springer Science & Business Media. ISBN 978-1-4615-4034-2.
- ^ Ланг, Бернард (1974). Loeckx, J. (ред.). «Детерминированные методы для эффективных недетерминированных синтаксических анализаторов» . Автоматы, языки и программирование, 2-й коллоквиум . Конспект лекций по информатике. Саарбрюккен: Springer. 14 : 255–269. DOI : 10.1007 / 3-540-06841-4_65 . ISBN 978-3-540-06841-9. ISSN 0302-9743 .
- ↑ Масару Томита. Эффективный синтаксический анализ естественного языка. Kluwer Academic Publishers, Бостон, 1986.
- ^ Ланг, Бернард (декабрь 1971 г.). «Параллельный недетерминированный восходящий анализ» . Уведомления ACM SIGPLAN . Материалы международного симпозиума по расширяемым языкам. 6 (12): 56–57. DOI : 10.1145 / 942582.807982 .
- ^ "Elkhound, Elsa и Cqual ++: статический анализ с открытым исходным кодом для C ++" .
дальнейшее чтение
- Грун, Дик; Джейкобс, Сериэль JH (2008). Методы синтаксического анализа . Springer Science + Business Media. ISBN 978-0-387-20248-8.
- Томита, Масару (1984). «Парсеры LR для естественных языков». ОГРАНИЧЕНИЕ . 10-я Международная конференция по компьютерной лингвистике. С. 354–357.
- Томита, Масару (1985). «Эффективный контекстно-свободный алгоритм синтаксического анализа для естественных языков». IJCAI . Международная совместная конференция по искусственному интеллекту. С. 756–764.