增强精神永远要解析表情 [英] Boost spirit takes for ever to parse expressions
问题描述
我在这里工作，在提升精神上
阅读很多非常好的内容，以促进精神我决定制作一个自己的解析器，遇到问题解析表达式如下
1+（2+（3+（4+（5+（6+（7 +（8））））））） >
永远在运行时..使它更简单1+（2+（3））工作正常。我看起来像是解析器的回溯是活跃的。请给我一个提示，如何修改语法或行为，以便及时运行。
这是一个来自语法的一个代码。我使用iter_pos来跟踪职位。
认罪
Markus
primary = functioncall
| constant_double
| constant_integer
|名称
|串;
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 = 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））]
括号=
lit（'（'）>>表达式>>点亮（'）'
| primary;
unary =
（iter_pos>> unary_op>> unary>> iter_pos）[_val =构造< common_node>（
type_cmd_member_call，
LOCATION（_1，_4），
key_callname，构造< std :: wstring>（_ 2），
key_this，构造< common_node>（_ 3）
）]
|括号[_val = _1]
;
multiplicative =
（iter_pos>> unary>>（multiply_op | divide_op | modulo_op）>>乘法>> iter_pos）[_val =构造< common_node>（
type_cmd_member_call，
LOCATION（_1，_5），
key_callname，construct< std :: wstring>（_ 3），
key_this，construct< common_node& _2），
key_parameter，构造< common_node>（_ 4）
）]
|一元[_val = _1];
添加=
（iter_pos>>乘法>>（add_op | subtract_op）>>>>> iter_pos） common_node>（
type_cmd_member_call，
LOCATION（_1，_5），
key_callname，construct< std :: wstring>（_ 3），
key_this，construct< common_node& ，
key_parameter，构造< common_node>（_ 4）
）]
|乘法[_val = _1]
;
compare =
（iter_pos>>>>>（compare_op）>比较>> （
type_cmd_member_call，
LOCATION（_1，_5），
key_callname，construct< std :: wstring>（_ 3），
key_this，construct< common_node& b $ b key_parameter，构造< common_node>（_ 4）
）]
|加法[_val = _1]
;
表达式=比较[_val = _1];
你正确地确定了麻烦的根源：规则被指定为懒惰（因为他们应该 - 描述性地给出规则的制作）。
如您所见，在PEG语法中，这很快导致如果有很多回溯，表现不佳。
我已经显示了非常类似的表达式的优化。总结如下：代替预期二进制表达式和回溯（如果事实证明不满足），请根据以下内容解析第一个操作数grelyily并构成不同的AST表达式节点。
-
使用更多视觉说明进行类似的治疗 Boost :: Spirit：优化表达式解析器
可能有趣：
i am new here working with boost spirit
Reading alot of very good articels for boost Spirit i decide to make an own Parser and run into the Problem that parsing an Expression like this
1+(2+(3+(4+(5+(6+(7+(8)))))))
takes forever on runtime.. making it more simple 1+(2+(3)) works fine. I Looks like the backtracking of the Parser is active. Please give me a hint how to modify the grammer or behaviour to make this run in time.
Here is a bit code from the grammer. I use the "iter_pos" for tracking the Position.
regards Markus
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];
You correctly identified the source of the trouble: the rules are specified "lazily" (in that they - as they should - descriptively give the productions for the rule).
As you can see, in a PEG grammar this quickly leads to a bad performance if there's a lot of backtracking.
I've already shown optimization of very similar expressions. The summary is this: instead of "expecting" a binary expression and backtracking if it turns out not to be satisfied, parse the first operand "greedily" and compose different AST expression nodes depending on what follows.
Similar treatment with more visual explanation Boost::Spirit : Optimizing an expression parser
Perhaps interesting:
这篇关于增强精神永远要解析表情的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
