c++ - Spirit Qi MiniC 示例的语法树空节点问题

Question

尊敬的灵气专家们。

我试过 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 将返回一个expression()。由于属性传播是 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 

EDIT2

我已经上传了一个修改过的 mini-c 版本，它打印了一个表达式生成的表达式树:

Link

如果您查看包含的 A.avxh 文件，它包含一个要解析的表达式。在 main.cpp 的第 67 行设置一个断点，并观察它递归进入那里的频率。

Answer 1

这是因为所有规则都公开了一个“原始”ast::expression这是固定类型。

在这个示例中显然是为了简化而选择的:好处是

• 通过使所有表达式节点的类型相同，树访问代码可以简单统一。
• 所有规则都具有相同的“签名”并遵循相同的模式。这很容易推理。
• 在此特定示例 (mini_c) 中，代码生成阶段通过继承相同的简单性而受益。

要使 AST 更灵活更紧密地遵循语义，通常的方法是制作 expression一个变体代替:这样每个表达式都可以直接包含实际的“具体”子表达式类型，而不是通过节点类型的中间级别“涉水”，只是为了模仿语法结构而不是< em>语义。

I think I have several examples of such asts and corresponding grammars on this site, will see if I can link one later.

^{In fact, I think the typedef variant<...> statement in the same example (ast.hpp) is not a bad example of this approach.}

Relevant links:

• Boost::Spirit Expression Parser

• Boost::spirit how to parse and call c++ function-like expressions this being a question which I answered by providing a fully featured expression parser (with 'builtin function' evaluation), in two ways:

  • A 'bells and whistles' approach with a full AST (resembling what we're doing here with the mini_c sample expressions)
  • A 'pragmatic' approach which evaluates on-the-fly using just semantic actions - note this is optimal for storage, but has some downsides, which I address in that post

现在，如果您不想改变语法(以免“失去”简单性)，您可以改为对 AST 进行转换(可以说是对表达式的“简化”传递) .

我将看看在接下来的一个小时内我能想出什么。

我刚刚重构了语法，因此它不会导致如此深的嵌套。

1. 首先，让我们将测试缩减为一个独立的测试台，它只解析表达式并展示一个简单的表达式 ("42") 如何解析为一个深度嵌套的 AST:http://coliru.stacked-crooked.com/a/5467ca41b0ac1d03

   <expr>
     ...
     <success></success>
     <attributes>[[[[[[[42, []], []], []], []], []], []]]</attributes>
   </expr>
   

2. 接下来，让我们解决根本问题:语法返回一个不变类型 ( ast::expression )，这在很多情况下都太重了。相反，我们想返回一个 ast::operand (这是变体，可以包含相同的 ast::expression 节点):http://coliru.stacked-crooked.com/a/00e43b1f61db018c

3. 最后，我们希望所有规则也变成变体，并返回任一个 expression iff 有尾部操作，或者只是一个单独的 operand在另一种情况下，在伪代码中:

   logical_or_expr = 
         (logical_and_expr >> +(logical_or_op > logical_and_expr)
       | logical_and_expr
       ;
   

   _{注意 if +(...) 的微妙用法而不是 *(...)强制执行至少一个尾随 logical_or 操作}

   现在，必须告诉 Spirit 如何将第一个分支分配给 operand。属性。 qi::attr_cast<ast::expression>(...)应该是这里的修复，但遗憾的是我遇到了未定义的行为(这花费了最多的时间)。我选择了一个更详细的解决方案:

   _logical_or_expr = logical_and_expr    >> +(logical_or_op     > logical_and_expr) ;
   logical_or_expr  = _logical_or_expr | logical_and_expr;
   

   正如您可能看到的，它是一样的，但是第一个分支被提取到一个单独的规则中，所以我们可以只声明规则来公开所需的属性:

   qi::rule<It, ast::operand(),    Skipper> logical_or_expr;
   qi::rule<It, ast::expression(), Skipper> _logical_or_expr;
   

   确实对子表达式的每个优先级执行此操作，结果如下:

   _logical_or_expr     = logical_and_expr    >> +(logical_or_op     > logical_and_expr) ;
   _multiplicative_expr = unary_expr          >> *(multiplicative_op > unary_expr) ;
   _additive_expr       = multiplicative_expr >> +(additive_op       > multiplicative_expr) ;
   _relational_expr     = additive_expr       >> +(relational_op     > additive_expr) ;
   _equality_expr       = relational_expr     >> +(equality_op       > relational_expr) ;
   _logical_and_expr    = equality_expr       >> +(logical_and_op    > equality_expr) ;
   
   logical_or_expr     = _logical_or_expr     | logical_and_expr        ;
   logical_and_expr    = _logical_and_expr    | equality_expr           ;
   equality_expr       = _equality_expr       | relational_expr         ;
   relational_expr     = _relational_expr     | additive_expr           ;
   additive_expr       = _additive_expr       | multiplicative_expr     ;
   multiplicative_expr = _multiplicative_expr | attr_cast<ast::operand, ast::operand> (unary_expr) ;
   

最终结果在这里:http://coliru.stacked-crooked.com/a/8539757bb02fca34 (遗憾的是，这对 Coliru 来说太多了)，并打印:

<expr>
  ...
  </logical_or_expr>
  <success></success>
  <attributes>[[42, []]]</attributes>
</expr>

注意 请注意，这种调整不会使解析器更高效!事实上，它只会导致大量回溯(调试输出计数为 925 行，而不是 第 1 步 (!!) 中的 45 行)。

现在，使用前瞻断言和/或语义操作将有一些优化空间，但通常您将不得不考虑优化 AST 存储将花费 CPU 时间。