簡單的數學表達式解析器

Question

我有一個簡單的數學表達式解析器，我想自己構建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 

我知道問題出在哪裏，這是因爲「添加」可以occour從未或infinitly（*），但我不知道如何解決這個問題。我認爲是這樣的：

「添加」 部分：

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  
    )? 
    ; 

但是，這會給我一個recoursion錯誤。有任何想法嗎？

Answer 1

我沒有完整的語法測試該解決方案，但是考慮更換這個（從問題的第一add規則）：

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

有了這個：

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

這每次通過('+' multiply)*迭代的方式延伸e而不是替換它。

它可能需要一點點玩弄才行，或者您可能需要在規則中臨時使用Expression以管理事物。只要確保循環創建的最後一個表達式位於=運算符的右側某處，如$e = new XYZ($e, $rhs.e);。