Анализ без сканера

Алгоритм, который выполняет токенизацию и анализ за один шаг

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

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

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

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

Недостатки

• Поскольку лексическое сканирование и синтаксический разбор объединены, результирующий парсер, как правило, более сложен и, следовательно, его сложнее понять и отладить. То же самое будет справедливо и для связанной грамматики, если грамматика используется для генерации парсера.
• Полученный парсер, как правило, значительно менее эффективен, чем конвейер лексер-парсер с точки зрения как времени, так и памяти. ^[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 были скомпилированы в булевы функции, возвращающие успех или неудачу.

Примечания

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

Ссылки

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

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

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