Boost :: Parser per l’espressione dello spirito

Ho un altro problema con il mio boost: parser spirit.

template struct expression: qi::grammar { expression() : expression::base_type(expr) { number %= lexeme[double_]; varname %= lexeme[alpha >> *(alnum | '_')]; binop = (expr >> '+' >> expr)[_val = construct<ast::binary_op>(_1,_2)] | (expr >> '-' >> expr)[_val = construct<ast::binary_op>(_1,_2)] | (expr >> '*' >> expr)[_val = construct<ast::binary_op>(_1,_2)] | (expr >> '/' >> expr)[_val = construct<ast::binary_op>(_1,_2)] ; expr %= number | varname | binop; } qi::rule expr; qi::rule binop; qi::rule varname; qi::rule number; }; 

Questo era il mio parser. Ha analizzato "3.1415" e "var" bene, ma quando ho provato ad analizzare "1+2" mi dice che l’ parse failed . Ho quindi provato a cambiare la regola binop in

  binop = expr >> (('+' >> expr)[_val = construct<ast::binary_op>(_1, _2)] | ('-' >> expr)[_val = construct<ast::binary_op>(_1, _2)] | ('*' >> expr)[_val = construct<ast::binary_op>(_1, _2)] | ('/' >> expr)[_val = construct<ast::binary_op>(_1, _2)]); 

Ma ora ovviamente non è ansible creare l’AST, perché _1 e _2 sono impostati in modo diverso. Ho visto solo qualcosa di simile a _r1 menzionato, ma come _r1 -boost non riesco a capire bene come boost::phoenix e boost::spirit interagiscono.

Come risolvere questo?

Non mi è del tutto chiaro cosa stai cercando di ottenere. Soprattutto, non sei preoccupato per l’associatività dell’operatore? Mostrerò solo risposte semplici basate sull’uso della ricorsione a destra – questo fa sì che gli operatori associativi a sinistra vengano analizzati.

La risposta diretta alla tua domanda visibile sarebbe quella di manipolare una fusion::vector2 – che non è affatto divertente, specialmente nelle azioni semantiche di Phoenix lambda . (Mostrerò qui di seguito, che aspetto ha).

Nel frattempo penso che dovresti leggere i documenti dello Spirito

  • qui nei vecchi documenti dello Spirito (eliminando la ricorsione a sinistra); Sebbene la syntax non si applichi più, Spirit continua a generare parser di discesa ricorsivi di LL, quindi il concetto alla base della ricorsione a sinistra si applica ancora. Il codice qui sotto mostra questo applicato a Spirit Qi
  • qui : gli esempi di Qi contengono tre campioni di calculator , che dovrebbero fornire un suggerimento sul perché l’associatività dell’operatore è importante e su come esprimere una grammatica che catturi l’associatività degli operatori binari. Ovviamente, mostra anche come supportare le espressioni parentesi per sovrascrivere l’ordine di valutazione predefinito.

Codice:

Ho tre versioni di codice che funzionano, analizzando l’input come:

 std::string input("1/2+3-4*5"); 

in un ast::expression raggruppata come (usando BOOST_SPIRIT_DEBUG):

  ....  [[1, [2, [3, [4, 5]]]]]  

I collegamenti al codice sono qui:

  • step_ # 1_reduce_semantic_actions.cpp
  • step_ # 2_drop_rule.cpp
  • step_ # 0_vector2.cpp

Passaggio 1: ridurre le azioni semantiche

Per prima cosa, mi libererei delle espressioni di analisi alternative per operatore; questo porta a un backtracking eccessivo 1 . Inoltre, come hai scoperto, rende la grammatica difficile da mantenere. Quindi, ecco una variante più semplice che utilizza una funzione per l’azione semantica:

1 controlla che utilizzi BOOST_SPIRIT_DEBUG!

 static ast::expression make_binop(char discriminant, const ast::expression& left, const ast::expression& right) { switch(discriminant) { case '+': return ast::binary_op(left, right); case '-': return ast::binary_op(left, right); case '/': return ast::binary_op(left, right); case '*': return ast::binary_op(left, right); } throw std::runtime_error("unreachable in make_binop"); } // rules: number %= lexeme[double_]; varname %= lexeme[alpha >> *(alnum | '_')]; simple = varname | number; binop = (simple >> char_("-+*/") >> expr) [ _val = phx::bind(make_binop, qi::_2, qi::_1, qi::_3) ]; expr = binop | simple; 

Passaggio 2: rimuovere le regole ridondanti, utilizzare _val

Come puoi vedere, questo ha il potenziale per ridurre la complessità. È solo un piccolo passo ora, per rimuovere l’intermedia binop (che è diventata abbastanza ridondante):

 number %= lexeme[double_]; varname %= lexeme[alpha >> *(alnum | '_')]; simple = varname | number; expr = simple [ _val = _1 ] > *(char_("-+*/") > expr) [ _val = phx::bind(make_binop, qi::_1, _val, qi::_2) ] > eoi; 

Come potete vedere,

  • all’interno della regola expr , il segnaposto pigro _val viene utilizzato come variabile pseudo-locale che accumula i binops. Tra le regole, dovresti usare qi::locals per un simile approccio. (Questa era la tua domanda riguardo a _r1 ).
  • ci sono ora dei punti di aspettazione espliciti, rendendo la grammatica più solida
  • la regola expr non deve più essere una regola automatica ( expr = invece di expr %= )

Passaggio 0: tipi di fusione Wrestle direttamente

Infine, per divertimento e tristezza, lasciami mostrare come potresti aver gestito il tuo codice suggerito, insieme alle associazioni di spostamento di _1, _2 ecc .:

 static ast::expression make_binop( const ast::expression& left, const boost::fusion::vector2& op_right) { switch(boost::fusion::get<0>(op_right)) { case '+': return ast::binary_op(left, boost::fusion::get<1>(op_right)); case '-': return ast::binary_op(left, boost::fusion::get<1>(op_right)); case '/': return ast::binary_op(left, boost::fusion::get<1>(op_right)); case '*': return ast::binary_op(left, boost::fusion::get<1>(op_right)); } throw std::runtime_error("unreachable in make_op"); } // rules: expression::base_type(expr) { number %= lexeme[double_]; varname %= lexeme[alpha >> *(alnum | '_')]; simple = varname | number; binop %= (simple >> (char_("-+*/") > expr)) [ _val = phx::bind(make_binop, qi::_1, qi::_2) ]; // note _2!!! expr %= binop | simple; 

Come puoi vedere, non è altrettanto divertente scrivere la funzione make_binop questo modo!