Бессканерный парсинг

В информатике синтаксический анализ без сканирования (также называемый синтаксическим анализом без лексера ) выполняет токенизацию (разбиение потока символов на слова) и синтаксический анализ (организацию слов в фразы) за один шаг, вместо того, чтобы разбивать его на конвейер лексера , за которым следуют парсер одновременно выполняющийся , . Грамматика языка не требует сканирования, если она использует единый формализм для выражения как лексической (на уровне слов), так и структуры языка на уровне фраз.

Разделение обработки на лексер, за которым следует синтаксический анализатор, является более модульным; Бессканерный анализ в основном используется, когда четкое различие между лексером и парсером не нужно или нежелательно. Примеры того, когда это уместно, включают TeX , большинство вики- грамматик, make-файлы , простые языки сценариев для конкретных приложений и Raku .

Преимущества

• только один метаязык Нужен
• Нерегулярная лексическая структура легко обрабатывается.
• «Классификация токенов» не требуется, что устраняет необходимость в конструктивных приспособлениях, таких как « лексер-хак » и зарезервированных словах языка (например, « while» в C ).
• Грамматики могут быть композиционными (можно объединять без вмешательства человека) ^[а]

Недостатки

• Поскольку лексическое сканирование и синтаксический анализ объединяются, результирующий анализатор обычно оказывается более сложным и, следовательно, труднее для понимания и отладки. То же самое будет справедливо и для связанной грамматики, если грамматика используется для генерации синтаксического анализатора.
• Получающийся в результате анализатор имеет тенденцию быть значительно менее эффективным, чем конвейер лексер-анализатор, как в отношении времени, так и в отношении памяти.

Реализации

• SGLR — это анализатор модульного формализма определения синтаксиса (SDF), который является частью ASF+SDF мета-среды и системы преобразования программ Stratego/XT .
• JSGLR — чистая Java-реализация SGLR, также основанная на SDF.
• TXL поддерживает синтаксический анализ на уровне символов.
• dparser генерирует код ANSI C для анализаторов GLR без сканирования .
• Spirit позволяет выполнять анализ как без сканирования, так и с использованием сканера.
• SBP — это анализатор логических грамматик без сканирования (расширение контекстно-свободных грамматик), написанный на Java.
• Laja — это двухфазный генератор синтаксического анализатора без сканера с поддержкой отображения правил грамматики в объекты, написанный на Java.
• Грамматики Raku — это особенность языка программирования общего назначения Raku .
• PyParsing — это парсер без сканера, написанный на чистом Python.
• META II Имеет встроенные функции парсера токенов.
• TREE-META Как и META II, он также не имеет сканера и имеет встроенные функции лексера.
• Компилятор CWIC для написания и реализации компиляторов. Имеет правила токенов как часть своего языка. Правила в CWIC были скомпилированы в логические функции, возвращающие успех или неудачу.

Примечания

• ^а Это связано с тем, что синтаксический анализ на уровне символов делает язык, распознаваемый анализатором, единым контекстно-свободным языком, определенным для символов, в отличие от контекстно-свободного языка последовательностей строк в обычных языках . Некоторые беслексерные парсеры обрабатывают весь класс контекстно-свободных языков, который закрыт при композиции.

Дальнейшее чтение

• Виссер, Э. (август 1997 г.). Обобщенный анализ LR без сканирования . Нидерланды: Амстердамский университет. CiteSeerX   10.1.1.37.7828 .