亲爱的灵气专家。
我玩过 Spirit Qi 中的 MiniC 示例,并注意到表达式语法中“空”AST 节点的问题。它将再次生成只包含一个“表达式”类型的操作数的“表达式”节点。
我认为问题是由于运算符优先级的递归规则定义:
// expression.hpp
qi::rule<Iterator, ast::expression(), skipper<Iterator> >
expr, equality_expr, relational_expr,
logical_or_expr, logical_and_expr,
additive_expr, multiplicative_expr
;
// expression_def.hpp
expr =
logical_or_expr.alias()
;
logical_or_expr =
logical_and_expr
>> *(logical_or_op > logical_and_expr)
;
logical_and_expr =
equality_expr
>> *(logical_and_op > equality_expr)
;
// ast.hpp
typedef boost::variant<
nil
, bool
, unsigned int
, identifier
, boost::recursive_wrapper<unary>
, boost::recursive_wrapper<function_call>
, boost::recursive_wrapper<expression>
>
operand;
/*...*/
struct expression
{
operand first;
std::list<operation> rest;
};
当logical_or_expr 递归到logical_and_expr 时,logical_and_expr 将返回一个表达式()。由于属性传播是 Spirit,logical_or_expr 然后将此表达式分配给它的表达式的“第一个”成员。
我认为这就是生成所有这些“空”表达式节点的原因。然而,我觉得这很讨厌,并想摆脱它们,但尚未成功。以前有没有人找到一个不错的解决方案?
我认为如果表达式由二元操作和一元操作组成,那将是可能的。这也将具有将操作和操作数保持在相同结构(伪代码)中的优点:
struct binary_op
{
optype type;
operand op1;
operand op2;
}
struct unary_op
{
optype type;
operand op1;
}
struct eval_op
{
operand op1;
}
typedef boost::variant<binary_op,
unary_op,
eval_op>
expression;
typedef boost::variant<int,
bool,
boost::recursive_wrapper<expression> >
operand;
但是,我相信在纸上播放后我仍然会遇到这个“空节点”问题。我好像在追自己的尾巴。
有谁知道如何解决这个问题?
编辑
a > b
将解析为:
expression (from logical_or_op) // Empty expression (forward only)
(rest) -/ \- (first) expression (from logical_and_op) // Empty expression (forward only)
(rest) -/ \- (first) expression (from equality_op) // Empty expression (forward only)
(rest) -/ \- (first) expression (from relational_op) // "Correct" expression
(first) a -/ \- (rest)
[0] operator_: op_greater
operand_: b
所需的输出将是:
expression (from relational_op)
(first) a -/ \- (rest)
[0] operator_: op_greater
operand_: b
编辑2
我上传了一个修改过的 mini-c 版本,它打印了一个表达式的生成表达式树:
如果您查看包含的 A.avxh 文件,它包含要解析的表达式。在 main.cpp 的第 67 行设置断点,并观察它在此处递归执行的频率。