GLR-парсер
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
( Синтаксический анализатор 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 имеет два дополнительных преимущества:
- Время, необходимое для запуска алгоритма, пропорционально степени недетерминированности грамматики: на детерминированных грамматиках алгоритм GLR выполняется за время O ( n ) (это не относится к алгоритму Эрли [ нужна ссылка ] и CYK, но оригинальные алгоритмы Эрли могут быть модифицированы для обеспечения этого)
- Алгоритм GLR является « онлайновым » — то есть он потребляет входные токены в определенном порядке и выполняет как можно больше работы после потребления каждого токена (это также верно для Эрли).
На практике грамматики большинства языков программирования являются детерминированными или «почти детерминированными», что означает, что любой недетерминизм обычно разрешается в пределах небольшого (хотя, возможно, неограниченного) числа токенов. [ нужна ссылка ] . По сравнению с другими алгоритмами, способными обрабатывать полный класс контекстно-свободных грамматик (такими как анализатор Earley или алгоритм CYK ), алгоритм GLR обеспечивает лучшую производительность при обработке этих «почти детерминированных» грамматик, поскольку в течение большинства из них будет активен только один стек. процесса разбора.
GLR можно комбинировать с алгоритмом LALR (1) в гибридном анализаторе, что обеспечивает еще большую производительность. [5]
См. также
[ редактировать ]- Сравнение генераторов парсеров
- Набор инструментов для реинжиниринга программного обеспечения DMS
- GNU Bison — генератор парсеров, который может создавать парсеры LALR и GLR.
- Парсер Packrat , еще один парсер, который может анализировать неоднозначные и недетерминированные языки.
Ссылки
[ редактировать ]- ^ Масару Томита (6 декабря 2012 г.). Обобщенный парсинг LR . Springer Science & Business Media. ISBN 978-1-4615-4034-2 .
- ^ Ланг, Бернард (1974). «Детерминированные методы для эффективных недетерминированных парсеров». В Лёкксе, Дж. (ред.). Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 14. Саарбрюккен: Шпрингер. стр. 255–269. дои : 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. дои : 10.1145/942582.807982 .
- ^ «Элкхаунд, Эльза и Cqual++: статический анализ с открытым исходным кодом для C++» . Ютуб . Архивировано из оригинала 21 декабря 2021 г.
Дальнейшее чтение
[ редактировать ]- Грюн, Дик; Джейкобс, Сериэль Дж. Х. (2008). Техники разбора . Springer Science + Business Media. ISBN 978-0-387-20248-8 .
- Томита, Масару (1984). «LR-парсеры для естественных языков». ОХЛАЖДЕНИЕ . 10-я Международная конференция по компьютерной лингвистике. стр. 354–357.
- Томита, Масару (1985). «Эффективный алгоритм контекстно-свободного анализа естественных языков». ИДЖКАИ . Международная совместная конференция по искусственному интеллекту. стр. 756–764.