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

Scannerless parsing

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

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

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

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

Недостатки

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

Реализации

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

Примечания

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

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

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