Comments 20
Сравните пожалуйста с QapDSL на примере парсинага
"if(some_expr){some_stat();}else{some_stat2();}".
Мой вариант можно найти в комментарии:
с QapDSL я не знаком совсем, но по тому, что я вижу могу сказать следующее:
он достаточно низкоуровневый по сравнению с EBNF. Пример правила в ispa:
condition: // name "if" for rule is prohibited
'if' '(' @ expr ')' @ stmt 'else' @ stmt
@{expression, true_stmt, false_stmt}
;
expr:
logical
#logical:
@ compare (@ LOGICAL_OP @ compare)*
@{left, op, right}
;
#compare:
@ arithmetic (@ COMPARE_OP @ arithmetic)*
@{first, operators, sequence}
;
// ... see https://github.com/Sinfolke/ispa-parser/blob/main/parser/parser/cll.isc
#value:
@ group | _variable | function_call | method_call | rvalue
{@}
;
;
stmt:
( '{' @ #value '}' ) | @ #value
{@}
#value:
// here what stmt could contain
;
;Похоже на ANTRL.
Этот парсер генератор может генерировать LR парсеры. Конструкция дерева может не отличаться с LL парсером как только я реализую PLL алгоритм (мой собственный алгоритм который добавляет левую рекурсию в LL парсерах)
Все достаточно абстрактно, хотя вообще вы можете матчить текст самостоятельно в СLL. Достаточно просто добавить для этого возможность читать текущий символ и токен. То-есть абстракция есть, но можно делать что-то специфичное если нужно. Именно поэтому я хочу сделать возможность создавать свое дерево на конкретном языке (пункт 3 в посте).
В QapDSL похоже нету токенизации
ISPA как отдельный язык, в то время как QapDSL больше похож на утилиту для существующего языка
ISPA пока что поддерживает только C++, но его архитектура позволяет генерацию на несколько языков.
QapDSL как ассемблер, гибкий, низкоуровневый, но из-за этого сложный.
Bison как C с инлайн ассемблером - декларативный, с возможностью низкоуровневого контроля
ISPA, ANTRL как C++ - высокоуровневые, удобные, но не теряющие контроль
мне вот EBNF/BNF и подобное не нравиться из-за того что AST приходиться делать отдельно, если я ничего не путаю.
QapDSL как ассемблер, гибкий, низкоуровневый, но из-за этого сложный.
я уже поработал над этим и теперь в QapDSL v2 описание стало в два раза короче. осталось только написать статью про это.
вот как парсин условий выглядит в новой версии:
t_if_body_one=>i_if_body{
TAutoPtr<i_stat> stat;
}
t_if_body_two=>i_if_body{
t_block_stat bef;
"else"
TAutoPtr<i_stat> aft;
}
t_if_stat=>i_stat{
"if("
TAutoPtr<i_expr> cond;
")"
TAutoPtr<i_if_body> body;
}как вам такой новый синтаксис? неужели всё ещё сложно?
Сам принцип парсера - низкоуровненове взаимодействие (низкоуровневое в нашем случае будет означать прямое обьявление переменных, условий и т.д). ISPA парсер даёт этому абстракцию давая добавлять низкоуровневые елементы только когда это необходимо. Именно в этом и преимущество. Это не значит, что какой-то из вариантов лучше, просто каждый подходит больше под свою задачу. Например QapDSL лучше подходит для парсинга JSON, XML, INI, где прямое взаимодействие обычно необходимо, а EBNF для новых языков или других комплексных текстов.
Насчет самостотельного создания дерева, это правда для ANTRL, но не для ISPA. В ISPA вы просто выделяете что захватить, а далее определяете каким типом данных оно будет (int, bool, string, array, object) и что из захваченного туда поместить. Хотя можно и редактировать данные перед созданием дерева посредством CLL.
Ещё одна важная проблема для парсер генераторов это ошибки. Я стараюсь её решить посредством fail блоков. В QapDSL это опять же низкоуровневое (что вообще может быть и отлично)
В целом QapDSL имеет смысл и вам нужно над этим работать.
В ISPA вы просто выделяете что захватить, а далее определяете каким типом данных оно будет (int, bool, string, array, object) и что из захваченного туда поместить
Если я правильно понял то тогда у вас при обходе получившегося AST придётся вручную определять типы лексем(обычного разделения типов на array/object недостаточно) и имена полей/узлов по содержимому и его положения в дереве. А это всё лишняя работа, которую можно автоматизировать и потом наслаждаться всеми удобствами(посетителями/интерпретаторами/строителями) при обходе дерева. Не понимаю как от этого можно отказаться и ради собственно чего. Или я чего-то не замечаю, вроде скорости парсинга и компактности реализации? Кстати как у вас дела с исходниками генератора? У меня например всё open source.
Да, думаю переходить с этой структуры на другую (основанную на std::variant и структурах для каждого правила/токена) или возможно полностью на структуру из классов но она вроде бы считаеться устаревшой.
Вообще в своем проекте я сделал TreeAPI (сейчас AST.API), который определяет дерево в удобной, фиксированной структуре, которая не будет изменяться и конвертирует дерево из парсера в эту структуру. Это даёт возможность редактировать вывод дерева парсера с минимальными затратами т.к таких изменений будет много в будущем
У меня все также open source, проект на C++20/C++23 с использованием модулей
struct Array {
stdu::vector<CllExpr> value;
private:
friend struct ::uhash;
auto members() const {
return std::tie(value);
}
};
struct Object {
std::unordered_map<std::string, CllExpr> value;
private:
friend struct ::uhash;
auto members() const {
return std::tie(value);
}
};Вот тут у вас опять всё упрётся в неправильную архитектуру AST, т.к далее вы заворачиваете это в rvalue, а затем в CllExprValue. В итоге у вас будет только один вид объектов - Object и один вид массивов - Array. И если я всё правильно понял, и нигде не ошибся, то тогда вам(или пользователям вашего генератора парсеров) придётся всё равно вручную преобразовывать Object`ы в пользовательские типы объектов. А в QapDSL все пользовательские типы пробрасываются прямиком в С++ со всеми полями и даже с пользовательским кодом(последнее я не очень приветствую). Могу помочь переписать парсер вашего DSL на QapDSL v2 если вам интересно. QapDSL v2 уже почти полностью(95%) переписан/описан на QapDSL v2 и похоже может использоваться для чего угодно.
Мой парсер генератор использует также структуры а не обьекты если только пользователь самостоятельно не создаст обьект как тип данных:
some_rule:
@ key ';' @ value
$obj<str, var> obj;
$obj[@] = @;
{obj}
;Если сохранить это следующим образом то будет структура:
some_rule:
@ key ';' @ value
@{key, value}
;То-есть это создаёт структуру:
{
a: a
b: b
}Это создает обьект:
obj<str, str> obj
{obj}Переписывать мой парсер на QapDSL мне не поможет т.к я уже успешно сделал bootstrap своей грамматики.
плохо понимаю что у вас происходит в коде, но я попробовал перевести некоторые штуки на QapDSL v2:
t_group:i_val{
'('
vector<t_member> members;
')'
t_ast_node make_ast_node(){return ast_node(members);}
}
t_keyvalue:i_prefix{...}
t_value:i_prefix{...}
emit_polymorphic_type_foreach_pice(
arr=split("name | CSEQUENCE | STRING | HEX | BIN | NOSPACE | ESCAPED | DOT | OP | LINEAR_COMMENT | cll"," | "),
parent="i_val"
);
t_member{
TAutoPtr<i_prefix> prefix?;
" "?
TAutoPtr<i_val> val;
" "?
t_quantifier quantifier?;
" "?
t_ast_node make_ast_node(){return ast_node({make_ast_node(prefix),make_ast_node(val),make_ast_node(quantifier)});}
}не знаю насколько правильно я понял как у вас храниться AST.
что обычно или структура или прямой тип данных
ну тогда ваш генератор парсеров пока круче моего по количеству фич и мало в чём ему уступает, если вообще уступает хоть в чём-то.
могу посоветовать в следующей статье про ваши проекты указывать все 5 возможных хабов, так будет больше просмотров. а эту статью уже не спасти, слишком старая для таких оптимизаций просмотров.
Спасибо, мы кстати можем работать над этим генератором вместе. Мне хотелось бы найти команду т.к проект стает достаточно большим для реализации в одиночку. Тем не менее ваш генератор по описанию не плох как я упоминал для JSON, XML. Если бы мне нужно было парсить эти структуры, я бы либо писал парсер вручную либо использовал подобный вашему генератор.
Я думаю в следующей статье описать СLL подробно, укажу больше хабов (думал в начале здесь как на редите нельзя постить если пост не подходит под тему поэтому указал только подходящие хабы)
ваш генератор по описанию не плох как я упоминал для JSON, XML
с XML у меня проблемы - там есть тэги которые не закрываются из-за дизайна/ошибок, это приводит к тому что максимум что можно - это разбить всё на токены/плоские_лексемы. дерево построить очень сильно как не всегда получается. с JSON дела получше, но скорость парсинга пока конечно не такая крутая как у заточенных под это дело монстров подобных rapidjson.
я бы либо писал парсер вручную либо использовал подобный вашему генератор
а почему не своим собственным генератором? у вас же всё должно быть круто с производительностью, не понимаю.
мы кстати можем работать над этим генератором вместе. Мне хотелось бы найти команду т.к проект стает достаточно большим для реализации в одиночку.
интересно, но я не представляю чем могу помочь. показать как круто можно обходить строго типизированное AST? это можно посмотреть прямо сейчас в моих исходниках. могу даже дать прямую ссылку на QapGen:
вот от этой строки и дальше вся круто-та: посетители/строители/интерпретаторы в одном месте строят интерпретируют и посещают строго типизированное дерево. с небольшими костылями(для нескольких разнотипных обходов), но всё работает.
описывать ваш DSL на QapDSL v2 вам не очень интересно, как я понял. что ещё остаётся?
Мой генератор делает токенизацию, что в этом случае не всегда еффективно. Прямой матчинг может быть лучше чем использование DFA таблиц. Низкоуровневый контроль часто необходим чтобы построить лучшее дерево. А так да, можно
Помочь мне можно именно с backend, frontend уже сделан. Но для этого нужно разбирать мой код. Поэтому я просто предлагаю)
можете еще кстати почитать недавно опубликованную статью о CLL
а я правильно понимаю что вот это(это генерированный код вашим же генератором парсеров, если да то скажите сколько на это тратиться времени): https://github.com/Sinfolke/ispa-parser/blob/main/parser/Parser.cpp
Это старая реализация, но сгенерированная этим парсером и сейчас используеться для парсинга грамматики. Новая реализация использует DFA для лексера и парсера в месте опциональных правил
на генерацию старой версии уходило около 700 мс, на генерацию новой версии около 1с
крутой у вас генератор, таблицы переходов, круто всё. я до такой оптимизации ещё не дошёл. у меня пока генератор простой и со своей грамматикой справляется за 143.02 ms. выхлоп 5700 строк С++ кода(197kb). вот он:
https://github.com/adler3d/QapGen/blob/master/src/QapGenV2025/QapGen/meta_lexer.inl
а вот исходник(749 строк и 12.4кб):
ISPA Parser Generator