Adler3D Jul 9 at 09:01

QapGen: Создаём мощные парсеры на C++

36 min

4.1K

Programming * Popular scienceC * Compilers * Open source *

Review

Comments 6

Kealon Jul 11 at 05:30

Не вдавался в сорцы.

Главный вопрос: поддерживает все регулярные грамматики или это аналог PEG-а?

Adler3D Jul 11 at 06:34

Да, QapDSLv2 полностью поддерживает все регулярные грамматики, поскольку регулярные грамматики — это самый простой класс формальных грамматик, и их поддержка — базовая возможность любого генератора парсеров.

QapDSLv2+QapGen — это гораздо более мощный и гибкий инструмент, чем PEG. В отличие от PEG, который вроде является формализмом для однозначного синтаксического анализа с приоритетным выбором, QapDSLv2 позволяет описывать сложные контекстно-свободные конструкции, интегрируя грамматику с построением AST, сериализацией и трансформациями.

Kealon Jul 11 at 07:12

Вы не поняли вопрос. Всё что можно описать в ANTL4

Можно описать в этом?
Оно будет асимптотически так же эффективно по разбору?

Adler3D Jul 11 at 07:37

Да, всё, что можно описать в ANTLR, можно описать и в QapDSLv2.

По производительности оба инструмента примерно сопоставимы, но в моих тестах с парсингом JSON`а QapDSLv2 быстрее чем ANTLR в 3.52 раза.

cpud47 Aug 18 at 12:14

Сравнивать на json-е скучно. Возьмите хотя бы парсер выражений на 10-15 уровней приоритетов.

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

cpud47 Aug 18 at 12:09

Не очень понятно, а какую проблему Ваша система пытается решить. Contextual keywords, language embedding, что-то ещё?

Сам синтаксис всё ещё довольно сложный и шумный (сравните с условными antlr и tree sitter). Встраивания фрагментов на C++ являются скорее недостатком, чем преимуществом: если уж мы полезли в генератор, то хочется в нём и оставаться.

Также, пример с выражениями Вам не просто так привели. Разумеется, есть классические примеры, как делать грамматику выражений с приоритетами. Но это довольно плохой подход. Хочется видеть хотя бы shunting yard/pratt parsing. Тут же вопрос: а какой parse tree Вы для этих выражений строите?... Помниться была статья, где паркинг питона ускоряли в 300 раз, просто устраняя вот эту лозу из дерева разбора.