|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Tolerant parsing using modified LR(1) and LL(1) algorithms with embedded “Any” symbol
[Толерантный синтаксический анализ с использованием модифицированных алгоритмов LL(1) и LR(1) со встроенной обработкой символа «Any»]
A. V. Goloveshkin Southern Federal University
Аннотация:
Толерантный синтаксический анализ используется для разбора структуры областей программы, представляющих интерес в контексте определённой задачи. В то время как эти области должны быть подробно описаны в толерантной грамматике языка, описание остальных частей программы может быть менее детальным, в результате парсер толерантен по отношению к возможным вариациям нерелевантных областей. Островные грамматики - один из основных способов реализации толерантного парсинга. Термином «остров» обозначаются релевантные области кода, нерелевантный код обозначается термином «вода». Предполагается, что на написание водных правил грамматики должно тратиться как можно меньше усилий. Ранее автором настоящей работы была введена формальная концепция упрощённой грамматики, расширяющая теорию островных грамматик. Данная концепция основана на идее устранения описаний воды в грамматике путём замены их на специальный символ «Any». Для работы с упрощёнными грамматиками был модифицирован стандартный LL(1) алгоритм синтаксического анализа и разработан генератор толерантных парсеров LanD. В настоящей статье модификация, встраивающая обработку «Any», описывается для LR(1) алгоритма синтаксического анализа. В сравнении с толерантными LL(1) грамматиками, толерантные LR(1) грамматики являются более простыми для разработки и исследования ввиду того, что в них каждый остров может быть описан одним непрерывным правилом. Предложены дополнительные механизмы обработки символа «Any», приводящие ряд интуитивно корректных сценариев его использования в соответствие с формальным определением упрощённой грамматики. Для LL и LR толерантного синтаксического анализа описаны специфические механизмы восстановления от ошибок, позволяющие ещё больше сократить количество водных правил, понизить их сложность и сделать толерантную грамматику расширяемой. В разделе экспериментов представлены результаты крупномасштабного тестирования толерантных LL и LR парсеров на 9 репозиториях крупных проектов с открытым исходным кодом.
Ключевые слова:
толерантный парсинг, устойчивый парсинг, легковесный парсинг, частичный парсинг, островная грамматика, упрощённая грамматика, генератор синтаксических анализаторов LanD.
Образец цитирования:
A. V. Goloveshkin, “Tolerant parsing using modified LR(1) and LL(1) algorithms with embedded “Any” symbol”, Труды ИСП РАН, 31:3 (2019), 7–28
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tisp418 https://www.mathnet.ru/rus/tisp/v31/i3/p7
|
Статистика просмотров: |
Страница аннотации: | 179 | PDF полного текста: | 277 | Список литературы: | 16 |
|