如何使用解析樹來解析表達式？

Question

嗨，我一直在解析一些基本的教程，我已經能夠理解CFG和解析樹的基礎知識。

採取以下語法基本公式：

term 
    : INTEGER 
    | '(' expression ')' 
    ; 

mult 
    : term ('*' term)* 
    ; 

add 
    : mult ('+' mult)* 
    ; 

expression 
    : add 
    ; 

我想知道那是什麼，它是如何幫助我們解決方程？所有的教程最後都是通過製作一個解析樹或者像預測解析器一樣編寫一個解析器來完成的，但是所有的解析器校驗是，如果該表達式符合語法，但是它不評估它。

任何人都可以幫助我嗎？

Answer 1

如果您只是試圖直接評估由一堆整數組成的數學表達式，那麼解析以形成AST可能是矯枉過正的。您可以使用像Dijkstra's shunting-yard algorithm這樣的標準評估算法來評估表達式並對其進行處理。但是，如果您打算對錶達式做其他事情 - 比如說，它們中有變量，並且您正在嘗試繪製圖形或採用衍生工具 - 因爲它們具有分析樹是非常有價值的，因爲它們自然地表示表達式的層次結構，並且可以很容易地在表達式上實現（遞歸）很多轉換。例如，如果您的表達式是布爾公式，則可以使用解析樹爲公式創建真值表，方法是給出如何評估所有不同連接詞的規則，然後根據不同的真值對多次計算公式。如果在電子表格中使用公式，則將公式的分析樹存儲在單元格中可以提出問題，例如「這個單元格引用的單元格是什麼」（您可以遞歸地遍歷樹來收集依賴關係），或者「根據當前電子表格內容評估單元格」（再次使用遞歸步驟）。