Проекты растут. Кодовая база растёт. Время компиляции растёт вместе с ними и переходит все границы разумного.
В какой-то момент я решил: а что если попробовать написать свой компилятор? Пока только для разработки, не для прода. На замену Clang++/G++/CL.EXE.
Эта статья — о первом шаге на этом пути. О парсере C++, который я написал на своём DSL специально сделанном для этого изначально.
Инструменты
QapGen - генератор парсеров специально сделанный для того чтобы когда-то написать самый быстрый загрузчик CST(конкретное дерево разбора) С++.
QapDSLv2 - язык для QapGen-а на котором описываются грамматики языков программирования.
Про грамматику QapDSLv2
Грамматика — это ветка из лексеров. Лексер состоит из полей, к полям можно привязывать через "=" правила. Поля - это обычно тоже лексеры. Исключение - это деградировавшие до самого дна лексеры-терминалы которые либо пишут прямо в поля-строки лексера, либо вообще в никуда (когда их задача - это связаться с константной-зашитой последовательностью символов).
Пример фрагмента простой грамматики для javascript чтобы понять синтаксис QapDSLv2:
struct t_js_let_var_stat:i_stat{ // тут ключевое слово "struct" у лексеров можно не писать "let" // константная-зашитая последовательность символов " " //ещё одна, а можно было просто пробел выше зашить t_name type; // это поле структуры как в С++, только у лексера " " t_name var; // ещё одно поле лексера "=" t_js_expr expr; // ко всем трём полям неявно привязано правило "dev.go_auto" ";" // а ко всем зашитым константам неявно привязано правило "dev.go_const" }; // или можно вот так ещё: t_js_const_var_stat:i_stat{ // ещё одна структура-лексер для константной переменной. "const " t_name type; " " string var=str<t_name>();//привязаное к полю правило, парсит t_name и сохраняет в var. "=" // оно разворачивается в "dev.go_str<t_name>(this->var);" t_js_expr expr; ";" }
Во что это развернётся в С++: // надо ли раскрывать спойлеры???
Возможно тут будет немного больно, я предупредил:
struct t_js_let_var_stat:public i_stat{ #define DEF_PRO_STRUCT_INFO(NAME,PARENT,OWNER)NAME(t_js_let_var_stat)PARENT(i_stat) #define DEF_PRO_VARIABLE(ADDBEG,ADDVAR,ADDEND)\ ADDBEG()\ ADDVAR(t_name,type,DEF,$,$)\ ADDVAR(t_name,var,DEF,$,$)\ ADDVAR(t_js_expr,expr,DEF,$,$)\ ADDEND() //=====+>>>>>t_js_let_var_stat #include "QapGenStructNoTemplate.inl" //<<<<<+=====t_js_let_var_stat public: void Use(i_visitor&A){A.Do(*this);} static SelfClass*UberCast(ParentClass*ptr){return i_visitor::UberCast<SelfClass>(ptr);} public: bool go(i_dev&dev){ t_fallback $(dev,"t_js_let_var_stat",nullptr,this,__LINE__); auto&ok=$.ok;if(!ok)return ok; ok=dev.go_const("let");$(ok,",\"l\""); if(!ok)return ok; ok=dev.go_const(" ");$(ok,",\" \""); if(!ok)return ok; ok=dev.go_auto(type);$(ok,"t_name,\"c\""); if(!ok)return ok; ok=dev.go_const(" ");$(ok,",\" \""); if(!ok)return ok; ok=dev.go_auto(var);$(ok,"t_name,\"c\""); if(!ok)return ok; ok=dev.go_const("=");$(ok,",\"=\""); if(!ok)return ok; ok=dev.go_auto(expr);$(ok,"t_js_expr,\"\""); if(!ok)return ok; ok=dev.go_const(";");$(ok,",\";\""); if(!ok)return ok; return ok; } }; struct t_js_const_var_stat:public i_stat{ #define DEF_PRO_STRUCT_INFO(NAME,PARENT,OWNER)NAME(t_js_const_var_stat)PARENT(i_stat) #define DEF_PRO_VARIABLE(ADDBEG,ADDVAR,ADDEND)\ ADDBEG()\ ADDVAR(t_name,type,DEF,$,$)\ ADDVAR(string,var,DEF,$,$)\ ADDVAR(t_js_expr,expr,DEF,$,$)\ ADDEND() //=====+>>>>>t_js_const_var_stat #include "QapGenStructNoTemplate.inl" //<<<<<+=====t_js_const_var_stat public: void Use(i_visitor&A){A.Do(*this);} static SelfClass*UberCast(ParentClass*ptr){return i_visitor::UberCast<SelfClass>(ptr);} public: bool go(i_dev&dev){ t_fallback $(dev,"t_js_const_var_stat",nullptr,this,__LINE__); auto&ok=$.ok;if(!ok)return ok; ok=dev.go_const("const ");$(ok,",\"c\""); if(!ok)return ok; ok=dev.go_auto(type);$(ok,"t_name,\"c\""); if(!ok)return ok; ok=dev.go_const(" ");$(ok,",\" \""); if(!ok)return ok; ok=dev.go_str<t_name>(var);$(ok,"t_name,\"c\""); if(!ok)return ok; ok=dev.go_const("=");$(ok,",\"=\""); if(!ok)return ok; ok=dev.go_auto(expr);$(ok,"t_js_expr,\"\""); if(!ok)return ok; ok=dev.go_const(";");$(ok,",\";\""); if(!ok)return ok; return ok; } };
Настоящая грамматика для С++:
А вот как выглядит настоящий t_var_expr для С++: // много и сложно
// начнём с t_var_expr, т.к он требуется для реализации t_var_stat struct t_var_expr:i_expr{ TAutoPtr<t_global> global?; // "?" == опциональность t_part head; vector<t_step> arr?; }; struct t_global{"::"}; struct t_part{ " "? TAutoPtr<i_name> name; // ищите наследников i_name ниже " "? TAutoPtr<i_ext> ext?; // ищите наследников i_ext ниже " "? vector<t_arr_body> arr?; " "? }; struct t_arr_body{ " "? "[" " "? TAutoPtr<t_lev15> expr?; // t_lev15 - любое выражение С++, не ищите его тут нет " "? "]" " "? }; struct t_step{ " "? string oper=any_str_from_vec(split("->,.,::",",")); t_part part; //t_part объявлен выше }; struct t_arr_ext:i_ext{ t_arr_body body; //t_arr_body объявлен выше }; struct t_call_ext:i_ext{ TAutoPtr<t_concrete_params> concrete_params?; // t_concrete_params=="<" ... ">" " "? vector<t_call_params> arr; // t_call_params == "(" ... ")" }; struct t_tmpl_ext:i_ext{ TAutoPtr<t_concrete_params> concrete_params; // t_concrete_params == "<" ... ">" }; struct t_op_impl:i_name{ "operator" " "? string op=any_str_from_vec(split("=,+=,-=,*=,/=,%=,&=,^=,|=,<<=,>>=,итд",",")); " "? }; struct t_name_impl:i_name{string value=str<t_name>();}; // ...---===###[ T_VAR_STAT ]###===---... struct t_var_stat:i_stat{ TAutoPtr<i_var_impl> impl=diff<t_expr_stat>();// ищите наследников i_var_impl " "? }; struct t_typename{"typename" " "?}; struct t_var_case:i_var_impl{ // вот он - наследник i_var_impl TAutoPtr<t_typename> tn?; " "? t_var_expr expr; // реализован вначале этого фрагмента кода " "? TAutoPtr<i_form_init> init?; // i_form_init - это "("...")" или "{"..."}" " "? // ... - вражение(t_expr) }; struct t_func_case:i_var_impl{ // вот он - наследник i_var_impl t_fv_class_stat::t_type_expr::t_fv_stat body=diff<t_var_case>();// всё сложно };
Слишком сложно? Вот попроще t_enum_class_stat:
struct t_enum_class_stat:i_class_stat{ "enum" " "? t_name name?; // любое С++ имя, ну там типа "azAZ09"... " "? t_body body?; }; struct t_body{ TAutoPtr<i_body> body; // ищите наследников i_body }; struct t_empty_body:i_body{ // вот он - наследник i_body ";" }; struct t_impl_body:i_body{ // вот он - наследник i_body "{" vector<t_item> arr=vec(",")?; TAutoPtr<t_comma_with_sep> comma?; // struct t_comma_with_sep{"," " "?}; "}" }; struct t_item{ " "? t_name name; " "? TAutoPtr<t_value> value?; }; struct t_value{ "=" " "? t_expr expr; // почти любое С++ выражение " "? };
Ещё проще? Вот t_if_stat:
struct t_if_stat:i_stat{ "if" " "? "(" " "? TAutoPtr<i_if_cond> cond; // ищите наследников i_if_cond " "? ")" " "? TAutoPtr<i_stat> bef; // i_stat - любое утверждение в С++ " "? TAutoPtr<t_else> aft?; // "?" == опциональность " "? } struct t_init_cond:i_if_cond{ // вот он - наследник i_if_cond TAutoPtr<t_for_stat::i_for_init> body; // тут всё сложно, там 3 ветки вариантов }; struct t_expr_cond:i_if_cond{ // вот он - наследник i_if_cond t_expr body=diff<t_init_cond>(); // t_expr - любое выражение С++ }; struct t_else{ "else" " "? TAutoPtr<i_stat> body; // i_stat - любое утверждение в С++ };
Самый ад хотите? Их есть у меня: // (это объявление "либо функции либо переменной")
t_fv_class_stat:i_class_stat{ t_type_expr{ t_type_expr_with_sep_and_cv{ vector<t_const_with_sep> cvs?; " "? TAutoPtr<t_type_expr> body; } t_name_part{ TAutoPtr<i_name_part> body; } t_amp{ string body=any_str_from_vec(split("&,&&",",")); " "? } t_brackets_name_part:i_name_part{ t_amp_part:i_part{ t_amp body; " "? } t_star_part:i_part{ string stars=any("*"); " "? TAutoPtr<t_amp> amp?; " "? } "(" " "? TAutoPtr<i_part> stamp_part; " "? TAutoPtr<t_name_part> namepart?; ")" " "? TAutoPtr<t_arr_body> arrbody?; " "? } t_cv{string body=any_str_from_vec(split("const,volatile",",")); " "?} t_raw_name_part:i_name_part{ TAutoPtr<t_cv> cv?; string name=str<t_name>(); } t_ap_name_part:i_name_part{ TAutoPtr<t_cv> cv1?; string ap=any_str_from_vec(split("&,&&,*",",")); " "? TAutoPtr<t_cv> cv2?; t_name_part name; " "? } t_func_param{ " "? TAutoPtr<i_func_param> body; " "? TAutoPtr<i_init_body> value?; " "? } t_func_params{ " "? "(" " "? vector<t_func_param> arr=vec(",")?; " "? ")" " "? } t_pfunc{ t_addr{ t_type_expr_with_sep_and_cv type; " "? "::" " "? } t_type_expr_with_sep_and_cv type; "(" " "? t_addr addr?; "*" " "? string name=str<t_name>()?; " "? ")" " "? t_func_params params; " "? } t_pfunc_func_param:i_func_param{ t_pfunc value; } t_var_args_func_param:i_func_param{ "..." } t_type_func_param:i_func_param{ t_const{ "const" t_sep sep?; } t_type_expr_with_sep_and_cv type; t_sep sep?; TAutoPtr<t_const> cv?; TAutoPtr<t_name_part> namepart?; } t_expr_func_param:i_func_param{ t_expr body=minor<t_type_func_param>(); } t_fv_stat{ t_impl_func_body:i_fv_body{ t_sep sep?; t_raw_func_body body; } t_zero_func_body:i_fv_body{ "=" " "? "0" ";" " "? } t_delete_func_body:i_fv_body{ "=" " "? "delete" " "? ";" " "? } t_override{ string value=any_str_from_vec(split("override,final",",")); " "? } t_braxcept{ "(" " "? t_expr expr; " "? ")" " "? } t_noexcept{ "noexcept" " "? TAutoPtr<t_braxcept> expr?; } t_func_fv_end:i_fv_end{ TAutoPtr<t_func_params> params; TAutoPtr<t_const_with_sep> cv1?; " "? vector<t_override> overrides?; TAutoPtr<t_noexcept> noe?; TAutoPtr<i_fv_body> body?; } t_var_fv_end:i_fv_end{ t_func_fv_item:i_fv_item{ TAutoPtr<t_func_params> params; TAutoPtr<t_const_with_sep> cv1?; } t_var_fv_item:i_fv_item{ vector<t_arr_body> arrbody?; TAutoPtr<i_init_body> value?; } t_item{ "," t_sep sep0?; TAutoPtr<t_const_with_sep> cv?; t_sep sep1?; string name=str<t_name>(); t_sep sep2?; TAutoPtr<i_fv_item> body?; t_sep sep3?; } TAutoPtr<i_fv_item> body?; vector<t_item> arr?; ";" } " "? vector<t_keyword> keywords?; TAutoPtr<t_type_expr> type; TAutoPtr<t_const_with_sep> cv?; " "? TAutoPtr<t_func_path> path?; TAutoPtr<t_callconv> callconv?; t_name_part name; " "? TAutoPtr<i_fv_end> way; } t_impl_typeexpr:i_typeexpr{ t_global{ "::" } TAutoPtr<t_global> global?; t_sep sep?; t_scopes scopes; vector<t_ptr> ptrs?; TAutoPtr<t_ref> ref?; } t_decl_typeexpr:i_typeexpr{ "decltype" " "? "(" " "? t_expr expr; " "? ")" " "? } TAutoPtr<i_typeexpr> body; } t_type_expr::t_fv_stat body; }
Где можно почитать про QapDSLv2 и QapGen?
Грамматика С++
У меня она как-то неявно поделилась на несколько частей.
Часть 1: Стандартная С++ мелочь(string + char + t_sep + t_name)
Вот она полностью:
Так охота написать "не смотрите, т.к это скучно!", но на что тогда смотреть?:
typedef array<char,2> ARRAY2char; typedef array<char,4> ARRAY4char; t_str_item_raw:i_str_item{ string body=any(dip_inv("\"\\\n")); } t_str_item_hex:i_str_item{ "\\x" ARRAY2char body=any_arr_char(gen_dips("09afAF")); } t_str_item_num:i_str_item{ "\\u" ARRAY2char body=any_arr_char(gen_dips("09")); } t_str_item_fix:i_str_item{ "\\" char body=any_char("tfbrn\\\"\'"+gen_dips("07")); } t_str_item{ t_impl{ "\"" vector<TAutoPtr<i_str_item>> arr?; "\"" } string value=str<t_impl>(); } t_char_item_raw:i_char_item{ string body=any(dip_inv("'\\\n")); } t_char_item_hex:i_char_item{ "\\x" ARRAY2char body=any_arr_char(gen_dips("09afAF")); } t_char_item_num:i_char_item{ "\\u" ARRAY4char body=any_arr_char(gen_dips("09")); } t_char_item_fix:i_char_item{ "\\" char body=any_char("tfbrn\\\"\'"+gen_dips("07")); } t_char_item{ t_impl{ "'" TAutoPtr<i_char_item> body; "'" } string value=str<t_impl>(); } t_sep_seq:i_sep{ string body=any(" \t\r\n"); } t_c_comment:i_sep{ "/*" string body=end("*/"); } t_cpp_comment:i_sep{ "//" string body=any(dip_inv("\n"))?; } t_sep{ t_impl{ vector<TAutoPtr<i_sep>> arr; } string value=str<t_impl>(); } using " " as t_sep; t_name{ t_keyword{ string value=any_str_from_vec(split("new,delete,default,consteval,false,true,nullptr,this,struct,class,for,if,while,do,const,constexpr,else,operator,continue,break,return,goto,virtual,override,public,private,protected,friend,template,typedef,using,namespace,decltype,volatile,final,switch,case,catch,try",",")); } t_impl{ char A=any_char(gen_dips("azAZ")+"_$@"); string B=any(gen_dips("azAZ09")+"_$@")?; } t_impl_ex{ t_impl impl=diff<t_keyword>(); } string value=str<t_impl_ex>(); }
Часть 2: Не шаблонные уровни задающие приоритеты операций:
Лоза из 16 уровней за которую меня по делу ругают: // рекомендую открыть и промотать
t_lev00{ t_item:i_lev00_prefix{string oper=any_str_from_vec(split("*,+,-,++,--,!,~",","));" "?} t_cast:i_lev00_prefix{"(" " "? TAutoPtr<t_type_expr_proxy> type; " "? ")" " "?} t_call:i_lev00_postfix{"(" " "? TAutoPtr<t_lev15> body?; " "? ")" " "?} t_index:i_lev00_postfix{"[" " "? TAutoPtr<t_lev15> body; " "? "]" " "?} t_dot:i_lev00_postfix{"." " "? t_name name;" "?} t_arrow:i_lev00_postfix{"->" " "? t_name name;" "?} t_inc:i_lev00_postfix{"++" " "?} t_dec:i_lev00_postfix{"--" " "?} t_operator_call:i_lev00_postfix{ "operator" " "? string op = any_str_from_vec(split("=,+=,-=,*=,/=,%=,&=,^=,|=,<<=,>>=,||,&&,|,^,&,==,!=,<,<=,>,>=,<<,>>,+,-,*,/,%,++,--,~,!,(),[],->",",")); " "? TAutoPtr<t_call_params> params?; " "? } t_operator_cast_call:i_lev00_postfix{ "operator" " "? TAutoPtr<t_type_expr_proxy> type; " "? t_call_params params?; " "? } vector<TAutoPtr<i_lev00_prefix>> bef?; " "? TAutoPtr<i_expr> expr; " "? vector<TAutoPtr<i_lev00_postfix>> aft?; } t_lev01{ string oper=any_str_from_vec(split("&",","))?; " "? TAutoPtr<t_lev00> expr; " "? } t_lev02{ t_oper{string value=any_str_from_vec(split(".*,->*",","));} t_item{" "? t_oper oper;" "?t_lev01 expr;} t_lev01 expr; vector<t_item> arr?; " "? } t_lev03{ t_oper{string value=any_str_from_vec(split("*,/,%",","));} t_item{" "? t_oper oper;" "?t_lev02 expr;} t_lev02 expr; vector<t_item> arr?; " "? } t_lev04{ t_oper{string value=any_str_from_vec(split("+,-",","));} t_item{" "? t_oper oper;" "?t_lev03 expr;} t_lev03 expr; vector<t_item> arr?; " "? } t_lev05{ t_oper{string value=any_str_from_vec(split("<<,>>",","));} t_item{" "? t_oper oper;" "?t_lev04 expr;} t_lev04 expr; vector<t_item> arr?; " "? } t_lev06{ t_oper{string value=any_str_from_vec(split("<,<=,>,>=",","));} t_item{" "? t_oper oper;" "?t_lev05 expr;} t_lev05 expr; vector<t_item> arr?; " "? } t_lev07{ t_oper{string value=any_str_from_vec(split("==,!=",","));} t_item{" "? t_oper oper;" "?t_lev06 expr;} t_lev06 expr; vector<t_item> arr?; " "? } t_lev08{ t_oper{"&"[::]inline static const string value="&";} t_item{" "? t_oper oper;" "?t_lev07 expr;} t_lev07 expr; vector<t_item> arr?; " "? } t_lev09{ t_oper{"^"[::]inline static const string value="^";} t_item{" "? t_oper oper;" "?t_lev08 expr;} t_lev08 expr; vector<t_item> arr?; " "? } t_lev10{ t_oper{"|"[::]inline static const string value="|";} t_item{" "? t_oper oper;" "?t_lev09 expr;} t_lev09 expr; vector<t_item> arr?; " "? } t_lev11{ t_oper{"&&"[::]inline static const string value="&&";} t_item{" "? t_oper oper;" "?t_lev10 expr;} t_lev10 expr; vector<t_item> arr?; " "? } t_lev12{ t_oper{"||"[::]inline static const string value="||";} t_item{" "? t_oper oper;" "?t_lev11 expr;} t_lev11 expr; vector<t_item> arr?; " "? } t_lev13{ t_mega:i_mega{TAutoPtr<t_mega_expr> body;} t_pico:i_mega{TAutoPtr<t_lev13> body=diff<t_mega_expr>();} t_mega12:i_mega12{TAutoPtr<t_mega_expr> body;} t_pico12:i_mega12{TAutoPtr<t_lev12> body=diff<t_mega_expr>();} t_ter_op:i_ter_oper{ TAutoPtr<i_mega12> cond; " "? "?" " "? TAutoPtr<i_mega> true_expr; " "? ":" " "? TAutoPtr<i_mega> false_expr; } t_nop_op:i_ter_oper{ t_lev12 body; } TAutoPtr<i_ter_oper> body; " "? } t_lev14{ t_oper{string value=any_str_from_vec(split("=,+=,-=,*=,/=,%=,&=,^=,|=,<<=,>>=",","));} t_item{" "? t_oper oper;" "?t_lev13 expr;} t_lev13 expr; vector<t_item> arr?; " "? } t_lev15{ t_oper{","[::]inline static const string value=",";} t_item{" "? t_oper oper;" "?t_lev14 expr;} t_lev14 expr; vector<t_item> arr?; " "? } t_expr{ t_lev14 body; }
Часть 3: шаблонные уровни задающие приоритеты операций:
Это тоже самое только для шаблонов: // рекомендую открыть и сразу закрыть
t_tmpl_lev03{ string oper=any_str_from_vec(split("&,*,+,-,!,~",","))?; TAutoPtr<i_tmpl_expr> expr; } t_tmpl_lev05{ t_oper{ string value=any_str_from_vec(split("*,/,%",",")); } t_item{ t_oper oper; t_tmpl_lev03 expr; } t_tmpl_lev03 expr; vector<t_item> arr?; } t_tmpl_lev06{ t_oper{ string value=any_str_from_vec(split("+,-",",")); } t_item{ t_oper oper; t_tmpl_lev05 expr; } t_tmpl_lev05 expr; vector<t_item> arr?; } t_tmpl_lev09{ t_oper{ string value=any_str_from_vec(split("==,!=",",")); } t_item{ t_oper oper; t_tmpl_lev06 expr; } t_tmpl_lev06 expr; vector<t_item> arr?; } t_tmpl_lev10{ t_oper{ string value=any_str_from_vec(split("&",",")); } t_item{ t_oper oper; t_tmpl_lev09 expr; } t_tmpl_lev09 expr; vector<t_item> arr?; } t_tmpl_lev11{ t_oper{ string value=any_str_from_vec(split("^",",")); } t_item{ t_oper oper; t_tmpl_lev10 expr; } t_tmpl_lev10 expr; vector<t_item> arr?; } t_tmpl_lev12{ t_oper{ string value=any_str_from_vec(split("|",",")); } t_item{ t_oper oper; t_tmpl_lev11 expr; } t_tmpl_lev11 expr; vector<t_item> arr?; } t_tmpl_lev13{ t_oper{ string value=any_str_from_vec(split("&&",",")); } t_item{ t_oper oper; t_tmpl_lev12 expr; } t_tmpl_lev12 expr; vector<t_item> arr?; } t_tmpl_lev14{ t_oper{ string value=any_str_from_vec(split("||",",")); } t_item{ t_oper oper; t_tmpl_lev13 expr; } t_tmpl_lev13 expr; vector<t_item> arr?; } t_tmpl_expr{ t_tmpl_lev14 body; }
в них нет символов "больше"(>) и "меньше"(<) - вот для этого они и нужны, а так они полная старая копия из части 2 которую мне лень синхронизировать и поэтому она устарела и поэтому грамматика неполноценная, но я как-нибудь это исправлю.
Часть 4: Всякая мелочь, её очень много и поэтому не буду её показывать тут.
Часть 5: Наследники i_class_stat.
Это то что может встречаться на самом высоком уровне в С++ коде - их немало.
Покажу некоторые: // рекомендую открыть и сразу закрыть
t_dtor_class_stat:i_class_stat{ vector<t_kw_with_sep> kw?; TAutoPtr<t_callconv> callconv?; TAutoPtr<t_func_path> path?; "~" t_sep sep0?; string name=str<t_name>(); t_sep sep1?; t_fv_class_stat::t_type_expr::t_func_params params; TAutoPtr<i_func_body> body; } t_ctor_class_stat:i_class_stat{ t_impl{ t_explicit{ "explicit" t_sep sep; } vector<t_kw_with_sep> kw?; TAutoPtr<t_callconv> callconv?; TAutoPtr<t_explicit> prefix?; TAutoPtr<t_func_path> path?; string name=str<t_name>(); t_sep sep?; TAutoPtr<t_concrete_params> concrete_params?; t_fv_class_stat::t_type_expr::t_func_params params; TAutoPtr<i_func_body> body; } t_impl body; } t_oper_cast_class_stat:i_class_stat{ t_impl{ TAutoPtr<t_callconv> callconv?; TAutoPtr<t_func_path> path?; "operator" t_sep sep0?; t_fv_class_stat::t_type_expr type; t_sep sep1?; t_fv_class_stat::t_type_expr::t_func_params params; TAutoPtr<t_const_with_sep> cv?; TAutoPtr<i_func_body> body; } t_impl body; } t_common_oper_class_stat:i_class_stat{ t_impl{ vector<t_keyword> keywords?; t_fv_class_stat::t_type_expr type; TAutoPtr<t_const_with_sep> cv0?; t_sep sep0?; TAutoPtr<t_callconv> callconv?; TAutoPtr<t_func_path> path?; "operator" t_sep sep1?; string oper=any_str_from_vec(split("=,+=,-=,*=,/=,%=,|=,&=,^=,<<=,>>=,||,&&,|,^,&,==,!=,<,<=,>,>=,<<,>>,+,-,*,/,%,++,--,~,!,(),[],->",",")); t_fv_class_stat::t_type_expr::t_func_params params; TAutoPtr<t_const_with_sep> cv1?; TAutoPtr<i_func_body> body; } t_impl body; }
Часть 6: Наследники i_stat
Это то что может встречаться внутри методов/функций.
Покажу некоторые: // рекомендую открыть
t_sep_stat:i_stat{ " "? ";" " "? } t_while_stat:i_stat{ "while" " "? "(" " "? t_expr cond; " "? ")" " "? TAutoPtr<i_stat> body; " "? } t_do_while_stat:i_stat{ "do" " "? t_raw_func_body body; " "? "while" " "? "(" " "? t_expr cond; " "? ")" " "? ";" " "? } t_goto_stat:i_stat{ "goto" " "? t_name name; " "? ";" " "? } t_common_oper_stat:i_stat{t_common_oper_class_stat::t_impl body;} t_switch_stat:i_stat{ t_num_ce:i_case_expr{string value=any(gen_dips("09"));} t_char_ce:i_case_expr{string value=str<t_char_item::t_impl>();} t_name_ce:i_case_expr{t_name name;} t_case:i_case{ "case" " "? TAutoPtr<i_case_expr> expr; " "? ":" " "? vector<TAutoPtr<i_stat>> stat?; " "? } t_default:i_case{"default" " "? ":" " "? vector<TAutoPtr<i_stat>> arr?; " "?} "switch" " "? "(" " "? t_expr expr; " "? ")" " "? "{" " "? vector<TAutoPtr<i_case>> arr?; " "? "}" " "? } t_try_stat:i_stat{ "try" " "? t_raw_func_body body; " "? vector<t_catch_block> arr; " "? } t_return_stat:i_stat{ "return" " "? TAutoPtr<i_setter> expr?; " "? ";" " "? } t_break_stat:i_stat{"break" " "? ";" " "?} t_continue_stat:i_stat{"continue" " "? ";" " "?} t_expr_stat:i_stat{ t_lev15 body; " "? ";" " "? }
Часть 7: Нужное для реализации лямбд
Покажу некоторые: // рекомендую не открывать вообще
t_capture_default{ string value=any_str_from_vec(split("=,&",",")); " "? } t_capture_item{ t_main:i_capture_item{ string cr=any_str_from_vec(split("=,&",","))?; " "? t_name name; " "? TAutoPtr<t_set_init_body> value?; " "? } t_this:i_capture_item{ "this" " "? } t_var_args:i_capture_item{ "..." " "? } " "? vector<TAutoPtr<i_capture_item>> item; } t_template_params_for_lambda{ "<" " "? vector<t_template_class_stat::t_template_param> arr=vec(",")?; " "? ">" " "? } t_capture_list{ "[" " "? t_capture_default def?; " "? TAutoPtr<t_comma_with_sep> comma?; vector<t_capture_item> items=vec(",")?; " "? "]" " "? TAutoPtr<t_template_params_for_lambda> templ_params?; " "? } t_lambda_param{ t_auto_param:i_lambda_param{ "auto" " "? string refs=any_str_from_vec(split("&,&&,*",","))?; " "? t_name name?; " "? } t_type_param:i_lambda_param{ TAutoPtr<t_for_stat::i_decl> type; " "? TAutoPtr<t_ref> ref?; " "? t_fv_class_stat::t_type_expr::t_name_part name?; " "? } t_var_args:i_lambda_param{ "..." " "? } t_this_param:i_lambda_param{ // C++23 "this" " "? } " "? vector<TAutoPtr<i_lambda_param>> arr; " "? } t_lambda_params{ "(" " "? vector<t_lambda_param> params=vec(",")?; " "? ")" " "? } t_lambda_spec{ t_kw:i_lambda_spec_item{ " "? string kw=any_str_from_vec(split("mutable,constexpr,consteval,noexcept",",")); " "? } t_throw:i_lambda_spec_item{ " "? "throw" " "? "(" vector<t_fv_class_stat::t_type_expr> types=vec(",")?; ")" " "? } t_trailing_return{ "->" " "? t_fv_class_stat::t_type_expr type; " "? } " "? vector<TAutoPtr<i_lambda_spec_item>> arr?; " "? TAutoPtr<t_trailing_return> ret?; " "? } t_lambda_template{ "template" " "? t_template_params_for_lambda body; } t_lambda_expr:i_expr{ TAutoPtr<t_lambda_template> templ?; " "? t_capture_list cap; " "? TAutoPtr<t_lambda_params> params?; " "? t_lambda_spec spec?; " "? t_raw_func_body body; " "? }
Часть 8: Наследники i_expr
Покажу некоторые: // рекомендую открыть
t_initializer_list:i_expr{ t_item{ " "? TAutoPtr<i_setter> body; " "? } "{" " "? vector<t_item> arr=vec(",")?; " "? "}" " "? } t_block_expr:i_expr{ "(" " "? t_lev15 expr; " "? ")" " "? } t_this_expr:i_expr{"this"} t_bool_expr:i_expr{ string value=any_str_from_vec(split("false,true",",")); } t_string_expr:i_expr{ t_item{t_str_item::t_impl body;" "?} string prefix=any_str_from_vec(split("u8,L",","))?; vector<t_item> arr; string suffix=any_str_from_vec(split("s,sv,U",","))?; } t_raw_string_expr:i_expr{ string prefix=any_str_from_vec(split("u8,L",","))?; "R\"" string delimiter=any(gen_dips("azAZ09")+"_")?; "(" string body=end(")"+delimiter); "\"" string suffix=any_str_from_vec(split("s,sv,U",","))?; } t_char_expr:i_expr{ string value=str<t_char_item::t_impl>(); } t_num_expr:i_expr{ t_frac{ "." string frac = any(gen_dips("09"))?; } t_exp{ char e=any_char("eE"); string sign=any_str_from_vec(split("+,-",","))?; string exp=any(gen_dips("09")); } t_udl:i_num_expr_suffix{ "_" string value=str<t_name>(); } t_suffix:i_num_expr_suffix{ " "? string suffix=any_str_from_vec(split("u,U,l,L,ll,LL,ul,UL,ull,ULL,f,F,lf,LF,s,ms,us,ns,min,h",",")); } t_impl{ string whole=any(gen_dips("09")); TAutoPtr<t_frac> frac?; TAutoPtr<t_exp> exp?; } string value=str<t_impl>(); TAutoPtr<i_num_expr_suffix> suffix?; } t_nullptr_expr:i_expr{ "nullptr" } t_hex_expr:i_expr{t_impl{ "0" char x=any_char("xX"); string value=any(gen_dips("09afAF")); } string value=str<t_impl>(); }
Часть 9: t_for_stat - цикл for
Скрытый текст
t_for_stat:i_stat{ t_init_decl{ " "? t_fv_class_stat::t_type_expr::t_name_part name; " "? TAutoPtr<i_init_body> body?; " "? } t_cv{string body=any_str_from_vec(split("const,volatile,unsigned,signed,short,long",",")); " "?} t_cv2{string body=any_str_from_vec(split("const,volatile,unsigned,signed",",")); " "?} t_fulltype{ TAutoPtr<t_typename> tn1?; vector<t_cv> cv?; TAutoPtr<t_typename> tn2?; t_fv_class_stat::t_type_expr type; } t_type_decl:i_decl{ t_structbind:i_varname_or_structbind{ t_dots_item:i_structbind_item{" "? "..." " "?} t_name_item:i_structbind_item{" "? t_name name;" "?} "[" " "? vector<TAutoPtr<i_structbind_item>> arr=vec(","); " "? "]" } t_varname:i_varname_or_structbind{ t_fv_class_stat::t_type_expr::t_name_part name; } TAutoPtr<t_typename> tn1?; vector<t_cv> cv?; TAutoPtr<t_typename> tn2?; t_fv_class_stat::t_type_expr type; " "? TAutoPtr<i_varname_or_structbind> name; " "? } t_long_decl:i_decl{ vector<t_cv2> cv?;"long" " "? t_fv_class_stat::t_type_expr::t_name_part name; " "? } t_ll_decl:i_decl{ vector<t_cv2> cv?;"long" " "? "long" " "? t_fv_class_stat::t_type_expr::t_name_part name; " "? } t_decl_for_init:i_for_init{ t_item{"," " "? t_init_decl body;} TAutoPtr<i_decl> decl; TAutoPtr<i_init_body> body?; vector<t_item> arr?; } t_expr_for_init:i_for_init{ t_expr body=minor<t_decl_for_init>(); } t_init{TAutoPtr<i_for_init> body?;" "? ";" " "?} t_classic_header:i_for_header{ t_init init; TAutoPtr<t_expr> cond?; " "? ";" " "? TAutoPtr<t_lev15> inc?; } t_range_header:i_for_header{ TAutoPtr<t_init> init?; TAutoPtr<i_decl> decl; " "? ":" " "? t_expr range; } "for" " "? "(" " "? TAutoPtr<i_for_header> header; " "? ")" " "? TAutoPtr<i_stat> body; " "? }
Где всё посмотреть целиком: inp.qapdsl.h
Где выхлоп? — вот: QapCppFrontLexers.h
Что уже работает?
Поддерживается почти всё, но почему бы не перечислить ещё раз это всё:
Для тех не хочет читать код, но хочет увидеть что поддерживается:
Грамматика поддерживает основные конструкции C++:
Операторы:
Все приоритеты: от
::(глобальный доступ) до,(оператор запятая)Арифметика:
+,-,*,/,%Сравнение:
<,>,<=,>=,==,!=Логика:
&&,||,!Присваивание:
=,+=,-=, и т.д.Инкремент/декремент:
++,--
Литералы:
Числовые с суффиксами (
u,l,f,s,ms, и т.д.)Строковые
("...", R"delimiter(...)delimiter")Символьные (
'a')Логические (
true,false)
Шаблоны:
template <typename T>Параметры шаблонов
Вызовы шаблонов (
func<int>())
Лямбды:
Захваты:
[&],[=],[x],[&x]Параметры
Тело в фигурных скобках
Объявления:
Переменные:
int x = 5;Функции:
void foo(int a) { ... }Классы, структуры, объединения
Перечисления
Препроцессор: (частично)
#pragma,#include— проходятся, но не обрабатываются
Концепты: (частично)
Атрибуты: [[...]]— вроде бы поддерживаются
Структурное связывание: полностью
Что ещё не работает:
Скрытый текст
ссылка на файл где закомментировано всё нерабочее
Скорость парсинга:
127KB |
1.98 сек |
~64 KB/s |
|
127KB |
3.57 сек |
~35 KB/s |
|
153KB |
2.93 сек |
~52 KB/s |
|
547KB |
7.15 сек |
~76 KB/s |
|
121KB |
2.28 сек |
~53 KB/s |
Для сравнения: на моей машине cl.exe компилирует мой код со скоростью ~70KB/s
Файлы в которые специально добавлялись сложные конструкции:
contests.h attrs.h et_danger.cpp neo4evidno2.cpp neo4evidno.cpp
Особенности реализации C++ грамматики
Как решаются классические проблемы:
T<1>(2) — шаблон или сравнение? — всегда шаблон: подразумевается что на этапе семантического анализа будет костыль который при необходимости развернёт шаблон в цепочку сравнений.
struct S { int x; }; — объявление или выражение? — всегда t_class_stat, т.к внутри фигурных скобочек находиться выражение которое однозначно интерпретируется только в контексте t_class_stat, альтернатива t_uniform_init отваливается, т.к внутри не может распарсить int x;
AST ввиде JSON для "void foo(){struct S { int x; };}" // ничего интересно, не смотрите.
{ "arr": [ { "#": "t_fv_class_stat", "body": { "body": { "#": "t_keywords_uok", "keywords": [], "type": { "body": { "#": "t_impl_typeexpr", "global": null, "sep": { "value": "" }, "scopes": { "first": { "sep": { "value": "" }, "name": "void", "concrete_params": null }, "arr": [] }, "ptrs": [], "ref": null } }, "cv": null, "path": null, "callconv": null, "name": { "body": { "#": "t_raw_name_part", "cv": null, "name": "foo" } } }, "way": { "#": "t_func_fv_end", "params": { "arr": [] }, "cv1": null, "overrides": [], "noe": null, "body": { "#": "t_impl_func_body", "no_except": "", "init_list": null, "type": null, "body": { "arr": [ { "#": "t_class_stat", "body": { "attrs": [], "keyword": "struct", "attrs2": [], "name": "S", "fin": "", "parents": null, "body": { "arr": [ { "#": "t_fv_class_stat", "body": { "body": { "#": "t_keywords_uok", "keywords": [], "type": { "body": { "#": "t_impl_typeexpr", "global": null, "sep": { "value": "" }, "scopes": { "first": { "sep": { "value": "" }, "name": "int", "concrete_params": null }, "arr": [] }, "ptrs": [], "ref": null } }, "cv": null, "path": null, "callconv": null, "name": { "body": { "#": "t_raw_name_part", "cv": null, "name": "x" } } }, "way": { "#": "t_var_fv_end", "body": null, "arr": [] } } }, { "#": "t_sep_class_stat", "sep": { "value": " " } } ], "name": null } } } ] } } } } } ] }
Как решалась проблема с if (auto& [ok, value] = func(); ok && value > 0)
Тут ok && value жадно парсилось как тип + rvalue_ref + имя_переменной, а затем парсер падал, т.к не понимал что происходит "что ещё за >?" думал он. но я быстро понял, что это мой косяк и я забыл добавить альтернативу на t_expr или ещё что-то более забористое и всё сразу заработало.
Время
Оценка затраты времени на разработку парсера осложняется тем что сильно меньшая половина его писалась 11 лет назад и умело полноценно парсить только то что тогда было использовано мною в мои проектах и только заголовочная часть грамматики, то есть вся реализация всех методов/функций пожиралась одним(ну ладно семью) простейшим вот этим лексером(можете кстати оценить как грамматика выглядела на старте разработки в этом месяце — весь это файл до этого не менялся 11 лет). Доработка началась третьего числа этого месяца и заняла почти 10 дней примерно по десть часов в день. Оригинальная грамматика с которой я продолжил разработку в этом месяце тогда 11 лет назад заняла где-то пару недель в таком же режиме. Итого: порядка 200 часов. // А время разработки QapGen+QapDSLv2 — от трёх до девяти месяцев в том же режиме.
Что дальше?
Планы по развитию:
Никто ничего не заметит и не придумает — проект помрёт опять.
Почему проект должен помереть по мои прогнозам:
но проект — не главное, его не жалко. главное: кооп
Как развивать проект если компилятор вот вот откажется его компилировать? Дробить на файл? Грамматика очень плохо дробиться на файлы/модули как мне кажется.
Интересная статистика от QapGen-а про грамматику:
> QapGen.exe inp.qapdsl.h>out.h {"version":"1.0"} {"parse_ms":556.683} {"Do(tar) done in ":102.445} // первый проход по дереву для генерации ast2json {"parse_ms":572.304} {"Do(tar) done in ":11.0758} // второй проход по дереву для генерации пустого посетителя {"parse_ms":532.23} {"Do(tar) done in ":6.77717} // третий проход по дереву я не помню зачем он {"parse_ms":541.226} // основной парсин С++ грамматики QapGen-ом {"need_igrab done in ":1.08629} // сбор интерфэйсов {"need_grab done in ":0.661759} // сбор лексеров {"interface_autogen done in ":0.637013} // генераци интерфейсов {"lexers_grab done in ":12.7505} // ещё один сбор лексеров в другую струкутур {"Do(tar) done in ":494.345} // первый проход генерации кода {"buildLexerTree done in ":2.96149} // ещё один сбор лексров в третью струкуру {"pass_with_log_err_gen done in ":556.134} // генерим ошибки и код для них первый раз {"pass2_with_log_err_gen done in ":1104.39} //генерим ошибки и код для них второй раз {"poly_end done in ":391.131} // создаём код для полиморфных лексеров {"parse_ms":541.226,"total_ms":5166.62,"lexers":465,"fields":1176,"g_unique_pool_ptr_counter":101896} // Итого: 456 лексеров, 1176 полей-правил в них, 101К объектов в куче при парсинге создано. > wc inp.qapdsl.h 1894 3322 42664 inp.qapdsl.h // Итого: 1894 строки грамматики, 3322 связи, 42КБ плотного кода. > wc out.h 22421 34925 856731 out.h // Итого: 22421 строка генереного кода, 856КБ файл. "out.h" - зажимается 7zip-ом в 6% "inp.qapdsl.h" - зажимается 7zip-ом в 15%
Выводы:
пишите в комментариях.
Итог:
Парсер вроде работает. Строит CST для реальных файлов. Грамматика растёт.
Код открыт и доступен на GitHub: https://github.com/adler3d/QapCppFront
Финал
------------------------------------------------------------- // Матчинг запущен? Кооперация предложена? — нет? — Тогда мы идём к вам!
Рассказываю историю, услышанную на канале Homo Deus в видео про кооп и дилемму заключённого: короче, только самый важный момент-вывод: двое в агрессивной среде получают просто космическую выгоду если матчатся/кооперируются и единственное что их останавливает на какое-то время — это низкая вероятность встречи. Эти статьи и проекты которые я делаю/пишу/конструирую — это мои броски в этой игре, а ваши реакции/комментарии/действия — это ваши броски в этой игре. Среда невероятно агрессивная на первый взгляд, но я верю в кооп. Пусть он победит. Пусть из статьи выйдет что-то ещё кроме комментариев/реакций/действий. Пусть родится нечто новое — ваш ход: