Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
В информатике , scannerless синтаксического анализа (также называемый lexerless синтаксического анализа ) выполняет токенизации (разрушающее поток символов в слова) и синтаксического анализа (располагая слова в фразы) в одну стадию, а не нарушая его в трубопровод из в лексером с последующим анализатор , выполняя одновременно . Язык грамматика является scannerless , если он использует единый формализм , чтобы выразить как лексические (уровень слова) и уровневую структуру фразы языка.
Разделение обработки на лексер, за которым следует синтаксический анализатор, является более модульным; Разбор без сканирования в основном используется, когда четкое различие лексера и парсера не нужно или нежелательно. Примеры того, когда это уместно, включают TeX , большинство грамматик вики , make-файлы , простые языки сценариев для конкретных приложений и Raku .
Преимущества [ править ]
- Нужен только один метаязык
- Нерегулярная лексическая структура обрабатывается легко
- «Классификация токенов» не требуется, что устраняет необходимость в конструктивных приспособлениях, таких как « взлом лексера » и зарезервированные слова языка (например, «while» в C ).
- Грамматики могут быть композиционными (могут быть объединены без вмешательства человека) [1]
Недостатки [ править ]
- Поскольку лексическое сканирование и синтаксический синтаксический анализ объединены, результирующий синтаксический анализатор имеет тенденцию быть более сложным и, следовательно, более сложным для понимания и отладки . То же самое будет справедливо для связанной грамматики, если грамматика используется для создания синтаксического анализатора.
- Результирующий синтаксический анализатор имеет тенденцию быть значительно менее эффективным, чем конвейер лексического анализатора, как в отношении времени, так и в отношении памяти . [1]
Реализации [ править ]
- SGLR - это синтаксический анализатор для модульного SDF формализма определения синтаксиса , который является частью метасреды ASF + SDF и системы преобразования программ Stratego / XT .
- JSGLR , чистая реализация SGLR на Java, также основанная на SDF .
- TXL поддерживает синтаксический анализ на уровне символов.
- dparser генерирует код ANSI C для безсканирующих парсеров GLR .
- Spirit допускает синтаксический анализ как без сканирования, так и на основе сканера.
- SBP - это анализатор без сканирования логических грамматик (надмножество контекстно-свободных грамматик), написанный на Java.
- Laja - это двухфазный генератор синтаксического анализатора без сканирования с поддержкой отображения правил грамматики в объекты, написанные на Java.
- В Раке грамматик имеет общего язык программирования цели Рака .
- PyParsing - это парсер без сканирования, написанный на чистом Python.
- META II Имеет встроенные функции парсеров токенов.
- TREE-META, как и META II, также не требует сканирования и имеет встроенные функции лексера.
- Компилятор CWIC для написания и реализации компиляторов. Имеет правила токена как часть своего языка. Правила в CWIC были скомпилированы в логические функции, возвращающие успех или неудачу.
Заметки [ править ]
- ^ Это связано с тем, что синтаксический анализ на уровне символов делает язык, распознаваемый синтаксическим анализатором, единымконтекстно-свободным языком,определенным для символов, в отличие от контекстно-свободного языка последовательностей строк вобычных языках. Некоторые лексерные парсеры обрабатывают весь класс контекстно-свободных языков, который закрывается композицией.
Ссылки [ править ]
- ^ Экономопулос, Джорджиос; Клинт, Пол; Винджу, Юрген (2009). «Ускоренный анализ GLR без сканирования» (PDF) . Конструкция компилятора . 5501 : 126–141. DOI : 10.1007 / 978-3-642-00722-4_10 .
Дальнейшее чтение [ править ]
- Виссер, Э. (август 1997 г.). Бесканерный разбор Generalized-LR . Нидерланды: Амстердамский университет. CiteSeerX 10.1.1.37.7828 .