使用shift-reduce解析構建解析樹

Question

我正在嘗試解析我的空閒時間，並且我想實現一個非常簡單的語法的shift-reduce解析器。我讀過很多在線文章，但我仍然對如何創建分析樹感到困惑。下面是我想要做的一個例子：

---

語法：

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num 

以下範例輸入：

1 + 1 + 1 + 1 

也就是說，符號化後，就變成了：

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num 

---

我明白：

1. 移裝置推堆棧上的第一輸入令牌和從輸入
2. 減少裝置替換堆棧上的一個或多個元素與語法元素
除去它

所以，基本上，這應該發生：

Step 1: 
    Stack: 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num 
    What: Stack is empty. Shift. 

Step 2: 
    Stack: TKN_Num 
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num 
    What: TKN_Num can be reduced to Expr. Reduce. 

Step 3: 
    Stack: Expr 
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num 
    What: Cannot reduce. Shift. 

Step 4: 
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num 
    What: Cannot reduce. Shift. 

Step 5: 
    Stack: Expr TKN_Op TKN_Num 
    Input: TKN_Op TKN_Num TKN_Op TKN_Num 
    What: TKN_Num can be reduced to Expr. Reduce. 
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't 
    // reduce the top alone? 

Step 6: 
    Stack: Expr TKN_Op Expr 
    Input: TKN_Op TKN_Num TKN_Op TKN_Num 
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce. 

Step 7: 
    Stack: Expr 
    Input: TKN_Op TKN_Num TKN_Op TKN_Num 
    What: ... 
    // And so on... 

除了「要減少什麼？」懷疑，我不知道如何正確地構建一個分析樹。樹應該看起來像這樣：

1 + o 
      | 
    1 + o 
       | 
      1 + 1 

我應該創建一個新的節點嗎？

什麼時候我應該添加孩子到新創建的節點/何時應該創建一個新的根節點？

Answer 1

簡單而明顯的做法是在每次縮減時創建一個樹節點，並從減少到該樹節點的語法元素中添加樹節點。

這可以通過與原始解析器使用的「移位令牌」堆棧並行運行的節點堆棧輕鬆管理。對於長度爲N的規則的每個約簡，移位令牌堆棧被縮短N，並且非終結符令牌被推入移位堆棧。同時，通過刪除前N個節點來縮短節點堆棧，爲非終端創建節點，將刪除的N個節點作爲子節點，並將該節點推入節點堆棧。

該策略甚至適用於具有零長度右側的規則：創建樹節點並將空子集連接到它（例如，創建葉節點）。

如果您認爲終端節點上的「移位」是終端節點（形成終端的字符）的縮減，那麼終端節​​點將直接適配。爲終端創建節點並將其推入到堆棧上。

如果你這樣做，你會得到一個「語法/解析樹」，它與語法同構。 （我們爲此提供了一個商業工具）。有很多人不喜歡這種具體的樹，因爲它們包含關鍵字節點等，這些節點並沒有真正增加價值。確實，但是這樣的樹是極其容易構建的，並且極其容易理解，因爲樹結構是文法是。當你有2500條規則時（就像我們爲一個完整的COBOL解析器所做的那樣），這是重要的。這也很方便，因爲所有機制都可以完全構建到解析基礎結構中。語法工程師只是寫規則，解析器運行，瞧，一棵樹。改變語法也很容易：只要改變它，瞧，你仍然可以得到解析樹。然而，如果你不想要一個具體的樹，例如，你想要一個「抽象語法樹」，那麼你需要做的就是讓語法工程師控制哪些縮減生成節點;通常是將一些程序性附件（代碼）添加到要在縮小步驟中執行的每個語法規則。然後，如果任何此類程序性附件產生節點，則它將保留在節點堆棧上。任何生成節點的過程附件都必須附加由右手元素生成的節點。如果這是YACC/Bison/......大多數shift-reduce分析器引擎所做的。閱讀Yacc或Bison，並檢查語法。這個計劃給你很多控制權，但堅持要你控制這個控制權。 （對於我們所做的，我們不希望在構建語法方面做這麼多工程努力）。

在生成CST的情況下，從樹上刪除「無用的」節點在概念上很簡單;我們在我們的工具中這樣做。結果很像AST，沒有人工編寫所有這些程序附件。

Answer 2

你麻煩的原因是，你有一個轉變/減少衝突在你的語法：

expr: expr OP expr 
    | number 

您可以通過兩種方式解決此問題：對於左結合運營商

expr: expr OP number 
    | number 

，或者

expr: number OP expr 
    | number 

對於正確的關聯的。這也應該確定你的樹的形狀。

通常在檢測到一個子句完成時進行縮減。在正確的關聯情況下，您將從狀態1開始，期望一個數字，將其推入數值堆棧並切換到狀態2.在狀態2中，如果令牌不是OP，則可以將數字減少到expr 。否則，按下操作員並切換到狀態1.狀態1完成後，可以將數字，運算符和表達式減少到另一個表達式。請注意，您需要一種機制在減少後「返回」。然後整個解析器將以狀態0開始，比如立即進入狀態1並在縮減之後接受。

請注意，像yacc或bison這樣的工具使得這類東西變得更加容易，因爲它們帶來了所有低級別的機器和堆棧。