LALR解析器生成器實現問題

我目前正在嘗試按照「編譯器原理技巧和工具」（也稱爲「龍書」）中所述實現LALR解析器生成器。LALR解析器生成器實現問題

很多已經工作。解析器生成器當前能夠生成完整的goto-graph。

Example Grammar: 
        S' --> S 
        S --> C C 
        C --> c C 
        C --> d 

Nonterminals: S', S, C 
Terminals: c, d 
Start: S'

的後藤圖：

I[0]---------------+  I[1]-------------+ 
| S' --> . S , $ |--S-->| S' --> S . , $ | 
| S --> . C C , $ |  +----------------+ 
| C --> . c C , c | 
| C --> . c C , d |  I[2]--------------+ 
| C --> . d , c |  | S --> C . C , $ |  I[3]--------------+ 
| C --> . d , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ | 
+------------------+  | C --> . d , $ |  +-----------------+ 
    | |     +-----------------+ 
    | |   +--c--+ |  | 
    | |   |  | c  | 
    | |   |  v v  | 
    | |  I[4]--------------+ | 
    | c  | C --> c . C , c | | 
    | |  | C --> c . C , d | | 
    | |  | C --> c . C , $ | d 
    | |  | C --> . c C , c | | 
    | +---->| C --> . c C , d | | 
    |  | C --> . c C , $ | | 
    d  | C --> . d , c |--+ | 
    | +-----| C --> . d , d | | | 
    | |  | C --> . d , $ | | | 
    | |  +-----------------+ | | 
    | C       | | 
    | |  I[6]--------------+ | | 
    | |  | C --> c C . , c | d | 
    | +---->| C --> c C . , d | | | 
    |  | C --> c C . , $ | | | 
    |  +-----------------+ | | 
    |        | | 
    |  I[5]------------+ | | 
    |  | C --> d . , c |<---+ | 
    +------->| C --> d . , d |  | 
      | C --> d . , $ |<-----+ 
      +---------------+

我有實現算法生成的動作表trubbles！我的算法計算以下的輸出：

state | action  
     | c | d | $ 
------------------------ 
    0 | s4 | s5 | 
------------------------ 
    1 |  |  | acc 
------------------------ 
    2 | s4 | s5 | 
------------------------ 
    3 |  |  | r? 
------------------------ 
    4 | s4 | s5 | 
------------------------ 
    5 | r? | r? | r? 
------------------------ 
    6 | r? | r? | r?

SX ...轉移到狀態X
RX ...減少狀態X

將R？意味着我不知道如何獲得解析器應該減少的狀態（？）。有誰知道算法得到？使用上面的goto-graph？

如果有任何描述不夠清楚，請問，我會盡力解釋它！感謝您的幫助！

來源

2010-08-02 raisyn

換檔條目歸因於下一個狀態，但減少條目表示生產。

當你轉移時，你將一個狀態參考推入你的堆棧並進入下一個狀態。

當您減少時，這是針對特定的生產。生產負責將n個狀態轉移到您的堆棧上，其中n是該生產中的符號數。例如。一個用於S'，兩個用於S，並且兩個或一個用於C（即，用於C的第一或第二替代）。

當n個條目從堆棧中彈出後，您將返回到開始處理該生產的狀態。對於該狀態和由生產產生的非終結符，您可以查找goto表以找到下一個狀態，然後將其推送。

因此，減少條目標識生產。事實上，知道產生的非終結符號以及要彈出的符號數量就足夠了。因此

你的表應該讀

state | action  | goto 
     | c | d | $ | C | S 
------------------------------------ 
    0 | s4 | s5 |  | 2 | 1 
------------------------------------ 
    1 |  |  | acc |  | 
------------------------------------ 
    2 | s4 | s5 |  | 3 | 
------------------------------------ 
    3 |  |  | r0 |  | 
------------------------------------ 
    4 | s4 | s5 |  |  | 6 
------------------------------------ 
    5 | r3 | r3 | r3 |  | 
------------------------------------ 
    6 | r2 | r2 | r2 |  |

其中，Rx表示通過產生X減少。

來源

2010-08-02 20:48:16 Gunther

非常感謝！ – raisyn 2010-08-10 15:47:03

您需要彈出堆棧並從中找到下一個狀態。

來源

2010-08-02 19:40:11

所以我不需要知道rx？只是我必須減少？這本書說，第一個r值？ = r1;接下來的三個= r4;最後三位= r2;任何想法這是什麼意思，如果你是對的？ – raisyn 2010-08-02 19:50:43

rx表示：使用數字x減少生產量！
然後一切都變得清晰！簡單地彈出生產的主體，並將頭部移回頂部！

來源

2010-08-02 20:42:04 raisyn

LALR解析器生成器實現問題

回答

相關問題