QapDSL — декларативное описание AST и парсеров для C++
QapDSL — это специализированный язык (DSL), который позволяет описывать абстрактные синтаксические деревья (AST) и правила их разбора для языков программирования, прежде всего C++. Такая формализация помогает автоматизировать построение парсеров, генерацию кода, анализ исходников и даже рефакторинг.
Зачем нужен QapDSL?
- Компактно и наглядно описывать структуру и грамматику языка.
- Автоматически генерировать C++-структуры, парсеры, сериализаторы и визиторы.
- Ускорять эксперименты с языками, создавая прототипы компиляторов и анализаторов.
- Упрощать анализ и рефакторинг сложных языков, в т.ч. C++.
Пример QapDSL-описания
Рассмотрим, как описывается объявление класса C++ на QapDSL:
t_class{
string keyword;
t_sep sep0;
string name;
t_sep sep1;
TAutoPtr<t_parents> parents;
t_sep sep2;
TAutoPtr<t_class_body> body;
t_sep sep3;
{
M+=go_any_str_from_vec(keyword,split("struct,class,union",","));
O+=go_auto(sep0);
M+=go_str<t_name>(name);
O+=go_auto(sep1);
O+=go_auto(parents);
O+=go_auto(sep2);
O+=go_auto(body);
O+=go_auto(sep3);
M+=go_const(";");
}
}
-
Поле
keyword— ключевое слово (struct,class,union). - name — имя класса, parents — список базовых классов.
- В фигурных скобках — правила разбора для каждого поля («M+=» — обязательное правило. «O+=» — опциональное, делее тип парсинга).
Пример сгенерированного C++-кода
Вот пример C++-структуры, которую может сгенерировать QapGen по приведённому выше QapDSL-описанию:
class t_class{
#define DEF_PRO_STRUCT_INFO(NAME,PARENT,OWNER)NAME(t_class)OWNER(t_inl_file)
#define DEF_PRO_VARIABLE(ADDBEG,ADDVAR,ADDEND)\
ADDBEG()\
ADDVAR(string,keyword,DEF,$,$)\
ADDVAR(t_sep,sep0,DEF,$,$)\
ADDVAR(string,name,DEF,$,$)\
ADDVAR(t_sep,sep1,DEF,$,$)\
ADDVAR(TAutoPtr<t_parents>,parents,DEF,$,$)\
ADDVAR(t_sep,sep2,DEF,$,$)\
ADDVAR(TAutoPtr<t_class_body>,body,DEF,$,$)\
ADDVAR(t_sep,sep3,DEF,$,$)\
ADDEND()
//=====+>>>>>t_class
#include "QapGenStructNoTemplate.inl"
//<<<<<+=====t_class
public:
bool go(i_dev&dev){
t_fallback scope(dev,__FUNCTION__);
auto&ok=scope.ok;
auto&D=scope.mandatory;
auto&M=scope.mandatory;
auto&O=scope.optional;
static const auto g_static_var_0=QapStrFinder::fromArr(split("struct,class,union",","));
M+=dev.go_any_str_from_vec(keyword,g_static_var_0);
if(!ok)return ok;
O+=dev.go_auto(sep0);
if(!ok)return ok;
M+=dev.go_str<t_name>(name);
if(!ok)return ok;
O+=dev.go_auto(sep1);
if(!ok)return ok;
O+=dev.go_auto(parents);
if(!ok)return ok;
O+=dev.go_auto(sep2);
if(!ok)return ok;
O+=dev.go_auto(body);
if(!ok)return ok;
O+=dev.go_auto(sep3);
if(!ok)return ok;
M+=dev.go_const(";");
if(!ok)return ok;
return ok;
}
};
- Структура полностью повторяет схему из QapDSL и содержит макросы для генерации кода и сериализации.
- Метод
goреализует правила разбора для каждого поля — как и в QapDSL. - Включение
QapGenStructNoTemplate.inlдобавляет автогенерированные методы для RTTI/визиторов/сериализации.
QapDSL в действии: как это работает?
- Пишем QapDSL-описание грамматики.
- Автогенератор создает C++-структуры и код парсера.
- Получаем AST, по которому можно строить анализаторы, рефактореры, сериализаторы и т.д.
В проекте Sgon можно встретить QapDSL-описание, закодированное в base64 или encodeURIComponent внутри комментария — это целостная схема AST и грамматики.
Пример живого проекта: cpp_ast_scheme.cpp в QapGen и репозиторий QapGen.
Сравнение с аналогами
| QapDSL | ANTLR | Yacc/Bison | protobuf | |
|---|---|---|---|---|
| Тип | DSL для AST+грамматики | Генератор парсеров | Генератор парсеров | DSL для сериализации |
| AST | Автоматически | Через actions | Ручное | Только структуры данных |
| Язык генерации | C++ | Java, C++, Python и др. | C/C++ | C++, Python и др. |
| Поддержка C++-синтаксиса | Глубокая | Возможно | Возможно | Нет |
| Порог вхождения | Средний | Средний/Высокий | Средний/Высокий | Низкий |
QapDSL: плюсы и минусы
- + Одна схема — и AST, и парсер.
- + Просто расширять и поддерживать новые конструкции C++ (шаблоны, пространства имён, препроцессор).
- + Автоматическая генерация кода, сериализация, визиторы.
- – Меньше документации и сообщества, чем у ANTLR/Yacc.
- – Ориентация прежде всего на C++ и AST-heavy задачи.
Где посмотреть/попробовать?
- Репозиторий: Adler3d/QapGen
- Пример AST для C++: samples/cpp_ast_scheme.cpp
- Демо-примеры: samples в репозитории
Заключение
QapDSL — мощный инструмент для тех, кто работает с AST, парсерами и анализом кода C++. Он позволяет компактно описывать самые сложные конструкции C++ и автоматизировать рутинные задачи, связанные с синтаксисом. Если вы любите декларативные подходы и часто пишете компиляторы или анализаторы — обязательно попробуйте QapDSL!
upd:
QapDSL:
t_var_decl{
string type_name;
string var_name;
{
M+=go_str<t_type>(type_name);
M+=go_const(" ");
M+=go_str<t_name>(var_name);
M+=go_const(";");
}
}
Что даётся на вход Лексеру:
Строка программы, например:
int x;
Лексер разбивает текст на лексемы (токены):
int // лексема типа
// пробел (разделитель)
x // идентификатор (имя переменной)
; // символ конца объявления
Какой AST получается на выходе:
После разбора получится структура:
t_var_decl{
type_name = "int"
var_name = "x"
}
То есть, поле type_name содержит строку «int», а var_name — строку «x».
Автор: Adler3d. Статья подготовлена при поддержке GitHub Copilot.
Комментарии (42)
simplepersonru
05.06.2025 14:29Чем это лучше, чем clang libtool (примерно так)? В общем инструментарий фронтенда компилятора кланг. Там на входе может быть не какой-то специальный dsl который нужно изучить/понимать, а вполне себе c++ код. Там вполне себе документированные и понятные инструменты для работы с AST C++.
И этот инструмент гарантированно работает, т.к. является неотъемлемой частью полного цикла работы компилятора, ну т.е. серьезные требования к работоспособности и корректности
Как следствие, clang будет поддерживать код из нужного стандарта c++. Например, пришла бы вам в голову идея поддержать ключевое слово trivially_relocatable_if_eligible, которое скоро https://habr.com/ru/companies/yandex/articles/882518/ станет частью разбора структуры/класса и между вашими name и parents встроится? Пример только для иллюстрации того что всегда поддерживать актуальный разбор AST c++ это быть в роли догоняющего за компиляторами
Adler3D Автор
05.06.2025 14:29Кратко:
Clang LibTooling — промышленный стандарт, максимальная совместимость, высокая сложность.
QapDSL/QapGen — компактность, простота, гибкость и скорость прототипирования.
Adler3D Автор
05.06.2025 14:29Спасибо за подробный вопрос!
Сравнивать QapGen/QapDSL и Clang LibTooling — это сравнивать профессиональный компиляторский фронтенд и инструмент для быстрой генерации AST+парсеров под свои задачи.
Они действительно решают похожие задачи, но в разном масштабе и с разной философией.Ваши аргументы про Clang LibTooling абсолютно справедливы:
Это промышленный инструмент, часть реального компилятора, всегда поддерживает последние стандарты и фичи C++.
На входе — настоящий C++ (а не DSL), и результат — максимально корректный и совместимый AST.
Есть документация, поддержка и большая экосистема.
Когда и зачем может быть удобнее QapDSL/QapGen:
1. Быстрый прототипинг, эксперименты, свои языки
Если вы хотите быстро описать свой AST (например, для языка, похожего на C++ или с кастомным синтаксисом), или сделать экспериментальный парсер/анализатор — QapDSL позволяет сделать это реально в разы быстрее и компактнее, чем через clang.
Не нужно разбираться с тяжёлым API, собирать clang, тащить зависимости — написал схему, сгенерировал C++-код, всё работает.
2. Кастомизация и расширяемость
В QapDSL можно под свои нужды менять/расширять грамматику на лету, добавлять как угодно странные конструкции, которые clang не примет вообще.
Когда нужен не 100% C++, а "почти C++" (например, язык для скриптов, шаблонов, метапрограммирования, или своя надстройка над C++), clang будет мешать, а QapDSL — нет.
3. Автоматизация и генерация кода
Автоматически генерируются не только структуры AST, но и сериализация, визиторы, парсер и часто даже рефлексия.
Для больших проектов с частыми изменениями структуры AST это экономит массу времени (clang такого не даст — там AST фиксирован).
4. Простота изучения и экспериментов
Для обучения, хобби, pet-проектов, QapDSL проще и прозрачнее: вся грамматика и правила разбора — в одном месте.
Нет необходимости разбираться в тонкостях clang AST, его версиях, баг-репортах и пр.
Минусы QapDSL по сравнению с clang
Да, это всегда догоняющий: поддержка нового синтаксиса C++ ложится на автора схемы. Если завтра в язык добавят новый синтаксис — его надо вручную добавить в схему.
Нет гарантии 100% соответствия: QapGen не заменяет компилятор. Отлично подходит для задач, где нужна своя грамматика или лёгкий парсер, но не для полного компилирования современного C++.
Меньше документации и комьюнити.
Когда использовать clang LibTooling обязательно:
Когда критична совместимость с последним стандартом и "боевым" C++.
Когда вы делаете промышленный инструмент, форматтер, IDE-фичи, рефакторинг для больших проектов.
Когда нужен гарантированный, максимально совместимый AST.
Итог:
Clang — для промышленного C++ и "догонять компилятор".
QapDSL/QapGen — для быстрых прототипов, своих языков, экспериментов, “почти C++”, генерации AST и инструментов, где важна скорость и гибкость, а не полная совместимость.
Adler3D Автор
05.06.2025 14:29t_class{ string keyword; t_sep sep0; string name; TAutoPtr<t_trivially_relocatable_if_eligible> tri_rel_if_eligible; t_sep sep2; TAutoPtr<t_parents> parents; t_sep sep3; TAutoPtr<t_class_body> body; t_sep sep4; { M+=go_any_str_from_vec(keyword,split("struct,class,union",",")); O+=go_auto(sep0); M+=go_str<t_name>(name); O+=go_auto(tri_rel_if_eligible); O+=go_auto(sep2); O+=go_auto(parents); O+=go_auto(sep3); O+=go_auto(body); O+=go_auto(sep4); M+=go_const(";"); } } t_trivially_relocatable_if_eligible{ { M+=go_const("trivially_relocatable_if_eligible"); } }
MaxAkaAltmer
05.06.2025 14:29Стесняюсь спросить, в каком месте проще стало?
Adler3D Автор
05.06.2025 14:29Проще становится тогда, когда тебе нужно быстро и компактно описывать AST + сразу получать рабочий парсер и сериализацию, не утопая в ручном C++-коде и поддержке большого количества boilerplate.
MaxAkaAltmer
05.06.2025 14:29У меня был проект на работе, там я делал синтаксический анализатор для вспомогательных скриптов, синтаксис настраивался примерно так (и это имхо действительно проще и вообще понятней):
....
pushLit("plus","+");
pushLit("minus","-");
.....
pushGram("ADDSUB","MULDIV {(plus | minus) MULDIV}");
pushGram("MULDIV","UNAR {(div | mul) OPERAND}");
pushGram("UNAR","[+ | minus | not] OPERAND");
....Adler3D Автор
05.06.2025 14:29Похоже у вас потом ещё придётся делать код для превращения распарсеного в AST. Тоесть вручную на С++/другом_языке описывать AST и обвязку которая это AST строит. Или вам не нужно AST?
MaxAkaAltmer
05.06.2025 14:29Зачем вручную? У вас есть грамматика, по ней и строится дерево.
Вручную только интерпретатор под конкретный скрипт делался. И то, большая часть реализаций в базовом классе.
Adler3D Автор
05.06.2025 14:29Круто конечно, но у вас в AST будут строки типа
ADDSUB/MULDIV/UNAR, а не С++ структуры. Это не удобно, т.к по С++ структурам потом можно ходить черз шаблоны/посетители, а с вашим подходом придётся сравнивать строки, что чревато опечатками. Поэтому мой подход круче/удобнее/практичнее вашего, как мне кажется.MaxAkaAltmer
05.06.2025 14:29На самом деле кодогенерацию никто не отменял (если боитесь опечаток, которые элементарно и единожды отлаживаются), поэтому вы ошибаетесь. В нашем варианте на написание интерпретатора уходил вполне спокойный день. Посторонний человек легко может разобраться что к чему. А в вашем случае я вижу лишь портянки каких-то конструкций и не понимаю общей картины (понять я ее конечно могу, но это потребует лишних ложек сахара в мой чай, а лично я люблю чай без сахара).
Adler3D Автор
05.06.2025 14:29А в вашем случае я вижу лишь портянки каких-то конструкций и не понимаю общей картины
Это почти обычный С++ код загрузки/сохранения AST из/в устройства ввода/вывода. Просто немного упрощённый(без лишних префиксов типа "dev."/"struct", а также заголовка метода go и его внутренней начинки(за исключением всего кроме вызовов go_*). Как его можно не понять?
В нашем варианте на написание интерпретатора уходил вполне спокойный день
У меня на простой интерпретатор уходит 2 часа, не знаю что там делать так долго.
MaxAkaAltmer
05.06.2025 14:29Ничего там просто взглянув и не залезая в ваши реализации понять нельзя, оно и близко не так читабельно как грамматики.
Простой в нашем случае за чашку чая делается, а решающий нужную задачу вот как-то так.Adler3D Автор
05.06.2025 14:29Ничего там просто взглянув и не залезая в ваши реализации понять нельзя
Github copilot(GPT4.1) неплохо разобрался в QapDSL коде даже не видя реализацию методов "go_*", единственное он затупил с понимание gen_dips/go_any/M+=/O+=/=>. Он например сам понял как работает go_auto/go_const.
оно и близко не так читабельно как грамматики.
Возможно вы правы(кстати, можно ТОП3 вещей из того что вы не поняли), но грамматики не позволяют описывать дружелюбное к C++ структуры AST в том же месте(рядом) где описана грамматика, а это не удобно. Кроме того делать Visitor`ов узлов AST придётся вручную(либо ещё одним внешним кодогенератором). А QapGen/QapDSL делает это всё "изкоробки".
Mingun
05.06.2025 14:29А что же не упомянули, что идея идет и Rust и его библиотеки syn (которая вроде и самим компилятором используется)?
Adler3D Автор
05.06.2025 14:29Спасибо за замечание!
Вы абсолютно правы — подходы к парсингу, использующие генерацию AST и лексико-синтаксический разбор, действительно очень популярны в экосистеме Rust.
Библиотека syn — отличный пример современного парсера, который широко применяется не только в procedural macros, но и реально используется в инфраструктуре языка.Кстати, моему QapDSL уже более 10 лет, и при разработке я не заимствовал идеи из Rust или библиотеки syn — всё придумывалось и реализовывалось самостоятельно, исходя из собственных задач и опыта.
Статью, возможно, дополнять не буду — с html-оформлением мне просто лень возиться, но спасибо за интересную ремарку!
Jijiki
05.06.2025 14:29извините не понял, но ведь, кланг на АСТ и пример калейдоскопа на АСТ на сколько помню, тогда надо упоминать что у Раста зависимость от кланга и гцц
Adler3D Автор
05.06.2025 14:29Решил добавить простой пример.QapDSL: t_var_decl{ string type_name; string var_name; { M+=go_str<t_type>(type_name); M+=go_const(" "); M+=go_str<t_name>(var_name); M+=go_const(";"); } } Что даётся на вход Лексеру: Строка программы, например: int x; Лексер разбивает текст на лексемы (токены): int // лексема типа // пробел (разделитель) x // идентификатор (имя переменной) ; // символ конца объявления Какой AST получается на выходе: После разбора получится структура: t_var_decl{ type_name = "int" var_name = "x" } То есть, поле type_name содержит строку "int", а var_name — строку "x".Adler3D Автор
05.06.2025 14:29Добавил в статью. Теперь комментарий можно удалить что-ли. Чтобы дублирования не было.
allex
05.06.2025 14:29Давным-давно в далёкой галактике ... :)
https://treedl.sourceforge.net/about.html
Adler3D Автор
05.06.2025 14:29По фичам из описания на главной страниц очень похоже на моё изобретение. Но не ясно умеет ли оно работать в обратную сторону(сохранять AST обратно в код с проверками) ?
Adler3D Автор
05.06.2025 14:29TreeDL — формальный, декларативный, заточен под описание структуры и автоматическую генерацию кода, не затрагивает саму грамматику или правила разбора.
QapDSL-подход — объединяет описание структуры, грамматики и действий (генерация кода, обработка лексем) в одном месте, ближе к концепции парсер-комбинаторов, где грамматика и действия неразделимы.
Когда что удобнее?
TreeDL лучше, когда нужно только формально описать дерево и автоматизировать генерацию кода для него, а грамматика и парсер будут отдельно.
QapDSL удобнее, когда важно определить, как из текста получается дерево, какие действия выполнять сразу при разборе, и хочется быстро экспериментировать с грамматикой и обработкой.
Adler3D Автор
05.06.2025 14:29Вы только посмотрите на это: abstract node TokenRangeNode : BaseNode { attribute <antlr.Token> startToken; attribute <antlr.Token> endToken; attribute custom late noset <com.unitesk.atp.text.location.Position> startPosition get { startPosition = TokenUtils.getPosition( startToken ); }; attribute custom late noset <com.unitesk.atp.text.location.Position> endPosition get { endPosition = TokenUtils.getEndPosition( endToken ); }; } Очень мало что понятно, куча лишнего, моя штука на порядок круче как мне кажется.
impwx
05.06.2025 14:29Имхо вы поторопились с созданием собственного решения, не разобравшись как следует в теории и существующих инструментах. Поэтому предложенный DSL воспринимается как велосипед, а статья вызывает гораздо больше вопросов, чем ответов. Например:
Как разобрать конструкцию вида
if(...) { ... } else { ... }, гдеelseи блок после него опциональны?Как разобрать конструкцию вида
1 + (2 - (3 * 4 / 5) + 6 + 7)), где есть вложенность и цикл?Зачем такое количество синтаксического шума в DSL, например всякие
M+=,O+=,split,go_autoи т.д., если всё это можно вывести автоматически из списка полей выше и не заставлять разработчика писать еще раз вручную?Используете ли вы ваш парсер, чтобы разобрать его собственную грамматику, и возможно ли это сделать вообще?
Заодно ради интереса сравните, как выглядит реализация пунктов 1 и 2 на вашем DSL и на, например, PEG или комбинаторах парсеров.
Jijiki
05.06.2025 14:29что мне в своё время поломало мозг (+ (+a b) (- a b)), но теперь простой оператор * но с операторами вроде всё попроще прыгаем по адресам и владениям, если левый аргумент имеет оператор то он у него, если внешний, то 2 адреса берем и возращаем конструктор, а это более просто чем раскручивать стек ), но всё равно ломает голову (
1 поидее по словам, но я наверно не прав, сначала играем в игру количество {
потом где-то потихоньку добавляем к игре счет if - else и их комбинациимы же не в асемблер вроде гоним конструкции
тоесть это задача поидее близка как разукрасить текст по словам-токенам
а значит нужен заветный запрос:
(?U)(?<=\s)(?=\S)|(?<=\S)(?=\s)|(?<=\w)(?=\W)|(?<=\W)
microengine parser по словам, но тут надо дополнять, но по словам разобьёт поидее, но наверно можно и получше поправить запрос
вообще вопросы просты самое сложное это ловить
(1) - {}, (2) - "", (3) - '', (4) - ;//1 - просто
2 - не тривиально3 - как 2
4 - фантастика )
Jijiki
05.06.2025 14:29Скрытый текст
else if(ExtFile.equals("Java")) { String s1 = t.getText(); //(?<=\s)(?=\S)|(?<=\S)(?=\s)|(?<=\w)(?=\W)|(?<=\W)(?=\w) t.setText(""); //"((?= )|(?=\t)|(?<=\n))"(?=\\w) String parts[] = s1.split("(?U)(?<=\\s)(?=\\S)|(?<=\\S)(?=\\s)|(?<=\\w)(?=\\W)|(?<=\\W)"); List<String> list = new ArrayList<String>(); for(String r: parts)list.add(r); final Iterator<String> it = list.iterator(); for(String next = (it.hasNext() ? it.next() : null), current = null; next != null;) { String previous = current; current = next; next = it.hasNext() ? it.next() : null; if(current.equals("import")){ ;} else if(current.equals("return")){ ;} else if(current.equals("int")){ ;} else if(current.equals("char")){ ;} else if(current.equals("double")){ ;} else if(current.equals("boolean")){ ;} else if(current.equals("unsigned")){ ;} else if(current.equals("long")){ ;} else if(current.equals("class")){ ;} else if(current.equals("static")){ ;} else if(current.equals("protected")){ ;} else if(current.equals("throws")){ ;} else if(current.equals("final")){ ;} else if(current.equals("public")){ ;} else if(current.equals("private")){ ;} else if(current.equals("void")){ ;} else if(current.equals("new")){ ;} else if(current.equals("break")){ ;} else if(current.equals("continue")){ ;} else if(current.equals("do")){ ;} else if(current.equals("for")){ ;} else if(current.equals("while")){ ;} else if(current.equals("if")){ ;} else if(current.equals("else")){ ;} else if(current.equals("switch")){ ;} else if(current.equals("try")){ ;} else if(current.equals("catch")){ ;} else if(current.equals("extends")){ ;} else if(current.equals("implements")){ ;} else if(current.equals("/")&&next.equals("/")){ ; ; for(next = (it.hasNext() ? it.next() : null), current = null; next != null;) { previous = current; current = next; next = it.hasNext() ? it.next() : null; if(next.equals("\n")){ ; break; } else ; } } else if(current.equals("/")&&next.equals("*")){ ; ; for(next = (it.hasNext() ? it.next() : null), current = null; next != null;) { previous = current; current = next; next = it.hasNext() ? it.next() : null; if(current.equals("*")&&next.equals("/")){ ; ;previous = current;current = next;next = it.hasNext() ? it.next() : null; break; } else ; } } else if(current.equals("(")){ ;} else if(current.equals(")")){ ;} else if(current.equals("[")){ ;} else if(current.equals("]")){ ;} else if(current.equals("{")){ ;} else if(current.equals("}")){ ;} else if(current.equals("main")){ ;} else if(current.equals("\"")){ if(current.equals("\"")&&next.equals("\"")){ appendToPane(t,current,tBody); previous = current; current = next; next = it.hasNext() ? it.next() : null; ; } else { ; ; for(next = (it.hasNext() ? it.next() : null), current = null; next != null;) { previous = current; current = next; next = it.hasNext() ? it.next() : null; if(current.equals("\"")) { if(next.equals("\"")) { ; previous = current; current = next; next = it.hasNext() ? it.next() : null; ; } else { ; } break; } else ; } }
Adler3D Автор
05.06.2025 14:29Используете ли вы ваш парсер, чтобы разобрать его собственную грамматику, и возможно ли это сделать вообще?
Да, вот первая/тупая/простая версия используюая go_end(костыль):t_struct_field{ string type; t_name name; string value; { M+=go_const(" "); M+=go_end(type," "); M+=go_auto(name); O+=go_const("="); M+=go_end(value,";\n"); } } t_struct_cmd_mode{ char body='M'; { M+=go_any_char(body,"MO"); M+=go_const("+="); } } t_struct_cmd{ TAutoPtr<t_struct_cmd_mode> mode; string code; { M+=go_const(" "); O+=go_auto(mode); M+=go_end(code,";\n"); } } t_struct_body{ vector<t_struct_field> arr; vector<t_struct_cmd> cmds; { M+=go_const("{\n"); O+=go_auto(arr); M+=go_const(" {\n"); M+=go_auto(cmds); M+=go_const(" }\n}"); } } t_class_def=>i_def{ t_name name; t_name parent; { M+=go_auto(name); M+=go_const("=>"); M+=go_auto(parent); } } t_struct_def=>i_def{ t_name name; { M+=go_auto(name); } } t_target_item{ string sep; TAutoPtr<i_def> def; t_struct_body body; { O+=go_any(sep," \n"); M+=go_auto(def); M+=go_auto(body); } } t_target{ vector<t_target_item> arr; { M+=go_auto(arr); } }Более крутую версию парсера/"загрузчика AST QapDSL" на QapDSL можно посмотреть вот тут:
Adler3D Автор
05.06.2025 14:29t_if_body_one=>i_if_body{ TAutoPtr<i_stat> stat; { M+=go_auto(stat); } } t_if_body_two=>i_if_body{ t_block_stat bef; TAutoPtr<i_stat> aft; { M+=go_auto(bef); M+=go_const("else"); M+=go_auto(aft); } } t_if_stat=>i_stat{ TAutoPtr<i_expr> cond; TAutoPtr<i_if_body> body; { M+=go_const("if"); M+=go_const("("); M+=go_auto(cond); M+=go_const(")"); M+=go_auto(body); } } t_for_stat=>i_stat{ t_var_stat init; TAutoPtr<i_expr> cond; TAutoPtr<i_expr> loop; TAutoPtr<i_stat> body; { go_const("for("); go_auto(init); go_auto(cond); go_const(";"); go_auto(loop); go_const(")"); go_auto(body); } }t_simple_calc{ t_term{ TAutoPtr<i_term> value; { go_auto(value); } } t_number=>i_term{ t_ext{ string v; { go_const("."); go_any(v,gen_dips("09")); } } t_impl{ string bef; TAutoPtr<t_ext> ext; { M+=go_any(bef,gen_dips("09")); O+=go_auto(ext); } } string value; { go_str<t_impl>(value); } } t_divmul{ t_elem{ string oper; t_term expr; { go_any_str_from_vec(oper,split("/,*",",")); go_auto(expr); } } t_term first; vector<t_elem> arr; { M+=go_auto(first); O+=go_auto(arr); } } t_addsub{ t_elem{ string oper; t_divmul expr; { go_any_str_from_vec(oper,split("+,-",",")); go_auto(expr); } } t_divmul first; vector<t_elem> arr; { M+=go_auto(first); O+=go_auto(arr); } } t_scope=>i_term{ t_addsub value; { go_const("("); go_auto(value); go_const(")"); } } t_addsub value; { go_auto(value); } }// Зачем такое количество синтаксического шума в DSL, // например всякие M+=, O+=, split, go_auto "M+=" - обязательное правило. "O+=" - опциональное. "split" - первое что в голову пришло то сделал. "go_auto" - это шаболнный метод из С++, его нельзя подставить автоматически из-за go_const, который не связан со список полей лексера. // и т.д., если всё это можно вывести автоматически из списка полей" // выше и не заставлять разработчика писать еще раз вручную? а что тогда делать с string? в него может писать: go_str<T> - чтобы сохранить тип Т в AST в виде строки. go_any - который сохроняет в строку последовательность разрешонных символов? К тому же я просто люблю когда код выглядит как С++, а не странный DSL.// Используете ли вы ваш парсер, чтобы разобрать его собственную грамматику, // и возможно ли это сделать вообще? Да парсер после разрешения проблеммы курицы и яйца был на 80% переписан на QapDSL.// Peg.js IfStatement = "if" _ "(" _ condition:Expression _ ")" _ "{" _ ifBlock:Block _ "}" _ elseBlock:ElseBlock? ElseBlock = "else" _ "{" _ elseBlock:Block _ "}" Block = statement:Statement* _ "whitespace" = [ \t\n\r]* Statement = ... // другие виды statement'ов Expression = ... // выражение//Парсер-комбинаторы (на Python с parsita, псевдокод): from parsita import * class MyParser(TextParsers, whitespace=r'\s*'): lbrace = lit('{') rbrace = lit('}') lparen = lit('(') rparen = lit(')') if_kw = lit('if') else_kw = lit('else') expr = reg(r'\w+') # для примера statement = reg(r'\w+') # для примера block = lbrace >> rep(statement) << rbrace if_stmt = (if_kw >> lparen >> expr << rparen >> block >> opt(else_kw >> block) )// PEG.js Expression = head:Term tail:(_ ("+" / "-") _ Term)* { return tail.reduce( (acc, [_, op, _, term]) => ({type: "binop", op, left: acc, right: term}), head ); } Term = head:Factor tail:(_ ("*" / "/") _ Factor)* { return tail.reduce( (acc, [_, op, _, factor]) => ({type: "binop", op, left: acc, right: factor}), head ); } Factor = number:Number / "(" _ expr:Expression _ ")" { return expr; } Number = digits:[0-9]+ { return parseInt(digits.join(""), 10); } _ "whitespace" = [ \t\n\r]*// Парсер-комбинаторы (Python, parsita): from parsita import * class ExprParser(TextParsers, whitespace=r'\s*'): number = reg(r'\d+') > int lparen = lit('(') rparen = lit(')') @staticmethod def binop(op_parser, next_parser): return next_parser & rep(op_parser & next_parser) > ( lambda t: ExprParser.foldl(t[0], t[1]) ) @staticmethod def foldl(first, rest): result = first for op, val in rest: result = (op, result, val) return result factor = number | (lparen >> lazy(lambda: ExprParser.expr) << rparen) term = binop(lit('*') | lit('/'), factor) expr = binop(lit('+') | lit('-'), term)// Спасибо github copilot за помощь.Мне мой код нравиться больше, т.к в нём меньше магии(он проще)
domix32
05.06.2025 14:29Какой-то сложный способ использовать комбинируемые парсеры. Лучше б подсмотрели у какого-нибудь winnow или nom. Ну или чего там protobuf/flatbuffers спавнят хотя бы. Пояснений, почему иногда
M+=а иногдаO+=и для чего это вообще в статье так и не описано.Adler3D Автор
05.06.2025 14:29"M+=" - обязательное правило."O+=" - опциональное.Спасибо. Добавил в статью.// Лучше б подсмотрели у какого-нибуд Хотелось сделать своё, чтобы было похоже на С++ и генерировало AST+посетителей.Adler3D Автор
05.06.2025 14:29// Лучше б подсмотрели у какого-нибудКто-то добавил в мой комментарий свой комментарий, так что отвечаю:
По моему у меня хорошо получилось, нисколько не жалею потраченное время.
Вам так сильно не поранилось моё решение?
Panzerschrek
05.06.2025 14:29Из своего опыта могу сказать, что все эти генераторы парсеров не очень то нужны. Руками написать парсер обычно не так проще, чем заморачиваться с каким-нибудь генератором. Ведь там надо изучать, как этот генератор работает, это ведь по сути отдельный язык.
Adler3D Автор
05.06.2025 14:29Привет :)
Ну ты крутой, тебе не нужны, да, спору нет(или есть). Но я вот например токены не перевариваю(мне надо сразу AST+Visitor`ы). Вот я смотрю на то как ты с ними мучаешься в своём U и мне больно становиться: https://github.com/Panzerschrek/U-00DC-Sprache/blob/master/source/compiler1/src/lex_synt_lib/lexical_analyzer.u
Я не понимаю как ты не допускаешь ошибок в этом своём коде без кодогенерации.
Вот посмотри как я гуляю по своему AST и сравни со своим кодом(смотри на методы use ниже по коду, они принимают на вход узлы AST вместо токенов): https://github.com/adler3d/unordered/blob/b1fdf85967c5ccb6f974addc2411765b2ac4be53/code/DemoMashkod/321/V2/Sgon/main_2016_03_29.cpp#L668
Panzerschrek
05.06.2025 14:29я смотрю на то как ты с ними мучаешься
Я бы не назвал код из ссылки выше мучительным. Да, он не очень компактный, но свою задачу решает и в целом то он не сильно сложный. Объём достигается лишь за счёт многообразия токенов - идентификаторы разных видов, строки с их экранированными последовательностями, числа различных форматов.
Аналогично с синтаксическим разбором. Да, код весьма объёмный, но этот объём достигается за счёт многообразия конструкций языка.
Писать всё вышеописанное было несложно, ибо каждый отдельный лексический/синтаксический элемент с другими не сильно связан. Писалось это не за один присест, а за множество итераций, так что я даже не заметил, что столько кода написал.
С тестированием всего этого дела проблем нету. Достаточно писать юнит-тесты, покрывающие какую-либо конструкцию языка. Ошибки в коде синтаксического анализа наверное могут быть, но я не припомню случаев, чтобы я их там находил, ибо в целом то код весьма прямолинейный, чтобы при его написании было просто ошибиться. И даже если предположить, что ошибки возможны, то нельзя исключить их и при описании грамматики каким-либо иным способом, вроде изложенного в этой статье.Вот посмотри как я гуляю по своему AST и сравни со своим кодом
Ты видимо не туда смотришь. После лексического анализа у меня запускается синтаксический разбор, порождающий привычное дерево. После этого, на следующем этапе компиляции, это дерево обходится. При этом используется что-то вроде паттерна visitor. Для узлов дерева запускаются методы, которые строят код по ним.
Adler3D Автор
05.06.2025 14:29После лексического анализа у меня запускается синтаксический разбор, порождающий привычное дерево
Вот, ты всё дерево строишь ручками, а его можно было описать на QapDSL прямо рядом с тем место где грамматика описывается. У тебя что на этапе токенизации, что на этапе строительства дерева одна сплошная боль и ручная копипаста. Токены дожили до самого кодогена и сидят в AST мешая работать Visitor`ам. Вместо посетителей+перегруженных_методов_codegenerator`а у тебя сплошные if/else_if/while/NextLexem/IsKeyword. На это невозможно смотреть и скорее всего никто не захочет такой код поддерживать/разбираться_в_нём.
После этого, на следующем этапе компиляции, это дерево обходится. При этом используется что-то вроде паттерна visitor
Не вижу, где у тебя visitor`ы?
С тестированием всего этого дела проблем нету. Достаточно писать юнит-тесты, покрывающие какую-либо конструкцию языка.
Вот, а у меня не надо юнит-тестов(я так считаю), т.к AST умеет сохраняться обратно в код(не теряя пробелы/комментарии), а также в свой бинарный формат(бесполезная фича)+в отладочный proto-формат(чтобы можно было посмотреть текстовую распечатку дерева(тоже сомнительная/редко_используемая фича). Сохранение в код позволяет делать проверку корректности загрузки/строительства AST одной/двумя строчками кода. Просто сохраняешь загруженное дерево обратно в код, проверяешь что получилось тоже самое что было на входе, если разницы нет, значит всё работает как надо.
И даже если предположить, что ошибки возможны, то нельзя исключить их и при описании грамматики каким-либо иным способом, вроде изложенного в этой статье.
У меня ошибки при описании грамматики проверяются С++ компилятором и описанным выше механизмом. Ещё в загрузчике дерева есть код который следит чтобы при конфликтах(два лексера или больше смогли успешно загрузить лексему) загрузки лексем всегда побеждала та которая съела из потока байтов больше других.
Panzerschrek
05.06.2025 14:29сплошные if/else_if/while/NextLexem/IsKeyword
Не вижу в этом особой проблемы. Код достаточно прямолинейный, пусть и не очень компактный.
никто не захочет такой код поддерживать/разбираться_в_нём
Сильное утверждение. Я бы сказал обратное - обычный код на знакомом языке программирования модифицировать проще, чем разбираться с незнакомым генератором парсера.
Не вижу, где у тебя visitor`ы?
Вот например. Данный код вызовет соответствующую реализацию функции
BuildExpressionCodeImplдля текущего хранимого типа. Да, это не классический visitor с отдельным классом, реализующим только visit методы, но по сути это то же самое.Вот, а у меня не надо юнит-тестов(я так считаю)
Это заблуждение. Юнит-тесты необходимы, чтобы удостовериться, что описание грамматики соответствует задуманному. Использование специализированного языка для этого не устраняет такой необходимости.
У меня ошибки при описании грамматики проверяются С++ компилятором
Таким образом все ошибки обнаружить нельзя. Например банальные опечатки, когда вместо
rteurnдолжен бытьreturnили вместо+должен быть*.Adler3D Автор
05.06.2025 14:29Это заблуждение. Юнит-тесты необходимы, чтобы удостовериться, что описание грамматики соответствует задуманному. Использование специализированного языка для этого не устраняет такой необходимости.
Я просто не понимаю, как можно ошибаться с грамматикой в QapDSL, если там всё очевидно. Всё выглядит как обычный С++ код, просто немного укороченный/оптимизированный/упрощённый. Я как раз считаю что устраняет необходимость в юнит-тестах.
Таким образом все ошибки обнаружить нельзя. Например банальные опечатки, когда вместо
rteurnдолжен бытьreturnили вместо+должен быть*С такой же вероятностью такие же ошибки могут быть и в юнит-тестах. И ещё:
return`а в QapDSL нет(только если внутри строки запихать).
Adler3D Автор
Тема на gamedev.ru про эту штуку: https://gamedev.ru/flame/forum/?id=290586&m=6061253