Разбор без сканирования

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

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

• 1 Преимущества
• 2 Недостатки
• 3 Реализации
• 4 Примечания
• 5 Дополнительная литература

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

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

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

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

• Visser, E. (август 1997). Бесканерный разбор Generalized-LR. Нидерланды: Амстердамский университет. CiteSeerX 10.1.1.37.7828.

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