0

我有一个简单的数学表达式解析器，我想自己构建 AST（意味着没有 ast 解析器）。但是每个节点只能保存两个操作数。所以 2+3+4 会产生这样的树：

        +
       / \
      2   +
         / \
        3   4

问题是，我无法让我的语法师进行递归，这里只是“添加”部分：

add returns [Expression e]
  : op1=multiply { $e = $op1.e; Print.ln($op1.text); } 
    ( '+' op2=multiply   { $e = new AddOperator($op1.e, $op2.e); Print.ln($op1.e.getClass(), $op1.text, "+", $op2.e.getClass(), $op2.text); }
    | '-' op2=multiply   { $e = null; } // new MinusOperator    
    )*
  ;

但在一天结束时，这将产生一棵树，如：

     +
    / \
   2   4

我知道问题出在哪里，这是因为“添加”可能永远不会或无限地发生（*），但我不知道如何解决这个问题。我想到了类似的东西：

“添加”部分：

add returns [Expression e]
  : op1=multiply { $e = $op1.e; Print.ln($op1.text); } 
    ( '+' op2=(multiply|add)   { $e = new AddOperator($op1.e, $op2.e); Print.ln($op1.e.getClass(), $op1.text, "+", $op2.e.getClass(), $op2.text); }
    | '-' op2=multiply   { $e = null; } // new MinusOperator    
    )?
  ;

但这会给我一个递归错误。有任何想法吗？

4

1 回答 1

1

我没有完整的语法来测试这个解决方案，但考虑替换它（来自add问题中的第一条规则）：

$e = new AddOperator($op1.e, $op2.e);

有了这个：

$e = new AddOperator($e, $op2.e);  //$e instead of $op1.e

This way each iteration over ('+' multiply)* extends e rather than replaces it.

It may require a little playing around to get it right, or you may need a temporary Expression in the rule to keep things managed. Just make sure that the last expression created by the loop is somewhere on the right-hand side of the = operator, as in $e = new XYZ($e, $rhs.e);.

于 2012-11-29T16:57:43.073 回答