c++ - Boost spirit 需要永远解析表达式

Question

我是新来的，工作 spirit 振奋

阅读了很多关于 boost spirit 的非常好的文章，我决定制作一个自己的解析器并遇到像这样解析表达式的问题

1+(2+(3+(4+(5+(6+(7+(8)))))))

在运行时需要很长时间.. 使它更简单 1+(2+(3)) 工作正常。我看起来解析器的回溯是活跃的。请给我提示如何修改语法或行为以使其及时运行。

这是来自语法的位代码。我使用“iter_pos”来跟踪位置。

问候 马库斯

  primary            = functioncall 
                     | constant_double   
                     | constant_integer 
                     | name 
                     | string;

  constant_double   = real_parser< double, strict_ureal_policies<double> >()                    [_val = construct<common_node>(type_const_double, key_value, _1)];
  name              = name_pure_location                                                        [_val = construct<common_node>(type_name, phoenix::bind(&getLocation, _1),key_value, phoenix::bind(&getString, _1))];
  string            = (lexeme[L'"' >> +(boost::spirit::standard_wide::char_ - L'"') >> L'"'])   [_val = construct<common_node>(type_const_string, key_value,phoenix::bind(&makeString, _1))];
  constant_integer  = int_                                                                      [_val = construct<common_node>(type_const_int, key_value, construct<int>(_1))];

  parenthetical =
              lit('(') >> expression >> lit(')')
              | primary;

  unary =
     (iter_pos >> unary_op >> unary >> iter_pos)                            [_val = construct<common_node>(
                                                                                 type_cmd_member_call,
                                                                                 LOCATION(_1,_4),
                                                                                 key_callname, construct<std::wstring>(_2),
                                                                                 key_this,construct<common_node>(_3)
                                                                            )]
    | parenthetical[_val = _1]
    ;

  multiplicative =

    (iter_pos >> unary >> (multiply_op | divide_op | modulo_op) >> multiplicative >> iter_pos)    [_val = construct<common_node>(
                                                                            type_cmd_member_call,
                                                                            LOCATION(_1, _5),
                                                                            key_callname, construct<std::wstring>(_3),
                                                                            key_this, construct<common_node>(_2),
                                                                            key_parameter, construct<common_node>(_4)
                                                                            )]
    | unary[_val = _1];

  additive =

    (iter_pos >> multiplicative >> (add_op | subtract_op) >> additive >> iter_pos) [_val = construct<common_node>(
                                                                                type_cmd_member_call,
                                                                                LOCATION(_1, _5),
                                                                                key_callname, construct<std::wstring>(_3),
                                                                                key_this, construct<common_node>(_2),
                                                                                key_parameter, construct<common_node>(_4)
                                                                              )]
    | multiplicative[_val = _1]
    ;

  compares =

    (iter_pos >> additive >> (compare_op) >> compares >> iter_pos)      [_val = construct<common_node>(
                                                                            type_cmd_member_call,
                                                                            LOCATION(_1, _5),
                                                                            key_callname, construct<std::wstring>(_3),
                                                                            key_this, construct<common_node>(_2),
                                                                            key_parameter, construct<common_node>(_4)
                                                                          )]
    | additive[_val = _1]
    ;

  expression = compares[_val = _1];

Answer 1

您正确地确定了问题的根源:规则是“延迟”指定的(因为它们 - 正如它们应该 - 描述性地给出规则的产生式)。

如您所见，在 PEG 语法中，如果有大量回溯，这会很快导致性能不佳。

我已经展示了非常相似的表达式的优化。总结是这样的:与其“期待”一个二进制表达式并在结果不满足时回溯，不如“贪婪地”解析第一个操作数并根据后面的内容组成不同的 AST 表达式节点。

• Boost spirit poor perfomance with Alternative parser

• 类似的处理方式和更直观的解释 Boost::Spirit : Optimizing an expression parser

也许很有趣:

• Optimizing a boost::spirit::qi parser
• https://stackoverflow.com/a/20387628/85371