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

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

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

Преимущества [ править ]

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

Недостатки [ править ]

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

Реализации [ править ]

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 были скомпилированы в логические функции, возвращающие успех или неудачу.

Примечания [ править ]

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

Ссылки [ править ]

^ Экономопулос, Джорджиос; Клинт, Пол; Винью, Юрген (2009). «Быстрый анализ GLR без сканирования» (PDF) . Конструкция компилятора . Конспекты лекций по информатике. Том. 5501. стр. 126–141. дои : 10.1007/978-3-642-00722-4_10 . ISBN 978-3-642-00721-7 .

Дальнейшее чтение [ править ]

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

[1] Экономопулос, Джорджиос; Клинт, Пол; Винью, Юрген (2009). «Быстрый анализ GLR без сканирования» (PDF) . Конструкция компилятора . Конспекты лекций по информатике. Том. 5501. стр. 126–141. дои : 10.1007/978-3-642-00722-4_10 . ISBN 978-3-642-00721-7 .

[1]

v т Это Алгоритмы разбора
Top-down	Earley LL Recursive descent Tail recursive
Bottom-up	Precedence Simple Operator Shunting-yard LR Simple Look-ahead Canonical Generalized CYK Recursive ascent Shift-reduce
Mixed, other	Combinator Chart Left corner Statistical
Related topics	PEG Definite clause grammar Deterministic parsing Dynamic programming Memoization Parser generator LALR Parse tree AST Scannerless parsing History of compiler construction Comparison of parser generators Operator-precedence grammar