yacc/bison LALR（1）算法如何處理「空」規則？

Question

在LALR（1）語法分析器中，語法中的規則被轉換爲一個分析表，它有效地表示「如果你有這個輸入，並且前瞻記號是X，那麼轉移到狀態Y或者按規則減少R」。

我已經成功構建瞭解釋語言（ruby）中的LALR（1）解析器，不使用生成器，但在運行時計算解析表並使用該解析表評估輸入。這種方式出人意料地出色，表格生成相當簡單（這讓我感到很吃驚），支持自我引用規則和左/右關聯。

但是，我有一點難以理解的是yacc/bison在概念上如何處理空白規則定義。我的解析器無法處理它們，因爲在生成表格時，它會遞歸地查看每個規則中的每個符號，而「空白」不是來自詞法分析器的東西，也不會被規則所減少。那麼，LALR（1）解析器如何處理空的規則呢？他們是專門對待它，還是一個有效的算法應該適用的「自然」概念，甚至不需要特別意識到這樣的概念？

比方說，一個規則可以與任何中間匹配任意數量成對的括號：

expr: /* empty */ 
     | '(' expr ')' 
     ; 

輸入類似下面將匹配這條規則：

((((())))) 

這意味着在閱讀'（'和'看'）'，在分析器選擇：解析器選擇：

1. 移動'）'（不可能）
2. 根據一些規則（不可能）
3. 別的東西減少輸入...

不太適合「移」或「減少」的核心算法。解析器實際上不需要將任何東西移到堆棧上，將「無」減少到expr，然後移動下一個標記')'，給出'(' expr ')'，當然這減少到expr，依此類推。

這是「沒有任何變化」，令我困惑。分析表如何傳達這樣的概念？還要考慮到應該可以調用一些語義操作，該操作返回值爲$$以減少空值，因此，從分析表跳過該操作並且在堆棧中指示'('和')'處於前瞻狀態的相當簡單的視圖應該是隻是簡單地轉換爲轉換，不會真正產生序列'(' expr ')'，但只會產生序列'(' ')'。

Answer 1

儘管想了很多天，但在寫這個問題時以及在接下來的幾分鐘裏思考這個問題，有些事情讓我覺得非常明顯和簡單。

減少所有規則總是：從堆棧中彈出X個輸入，其中X是規則中組件的數量，然後將結果移回堆棧並轉到該表中給出的任何狀態。

在空規則的情況下，您不需要考慮「空」甚至是一個概念。解析表只需要包含一個轉換，它表示「在堆棧上給出'('和'在前瞻中不是'('的任何東西，減少'空'規則」。現在由於空規則的大小爲零，從堆棧中彈出零意味着堆棧不會改變，那麼當沒有減少任何東西的結果轉移到堆棧上時，您正在查看確實出現在堆棧中的東西語法，一切都變得清晰。

Stack  Lookahead Remaining Input  Action 
-------------------------------------------------------------- 
$   (   ())$     Shift '(' 
$(   (   ))$     Shift '(' 
$((  )   )$     Reduce by /* empty */ 
$((expr )   )$     Shift ')' 
$((expr) )   $     Reduce by '(' expr ')' 
$(expr  )   $     Shift ')' 
$(expr)  $         Reduce by '(' expr ')' 
$expr           Accept 

它「正常工作」的原因是因爲爲了減少空規則，您只需從堆棧中彈出零項。

Answer 2

另一種觀點來也許圓了d11wtq最偉大的回答，如果可能的話：

的可空規則（一個派生ε）下的功能FOLLOW(X)和FIRST(X)解析器建設過程中考慮。例如，如果您有A -> B x，並且B可以導出ε，那麼我們必須在由FIRST(A)計算的集合中包含x。並在設置FOLLOW(B)。

此外，空規則很容易在規範LR(1)項目集中表示。

一個有用的事情是想象有一個額外的非終結符號$它代表文件的結尾。

讓我們的語法：

S -> X | ϵ 
X -> id 

對於第一個規範LR(1)項集，我們可以採取先LR(0)項目設置與符號「$」添加前瞻：

S -> . X , '$' 
S -> .  , '$' 
X -> . id , '$' 

然後我們有一個用於預測的是id：

S -> . X , 'id' 
S -> .  , 'id 
X -> . id , 'id' 

現在讓我們來看看FIRST和FOLLOW集：

S -> . X , '$' 

這是不是「最後點」項目，所以這裏要調換，但前提是一套FIRST(X)包含我們向前看符號$。這是錯誤的，所以我們不填寫表格條目。

下一頁：

S -> .  , '$' 

這是一個 「點最終」 項目，所以想減少。爲了驗證上下文的縮減，我們看看FOLLOW(S)：我們希望減少的語法符號可以跟在前面的內容之後嗎？完全同意。 $始終在FOLLOW(S)之間，因爲開始符號在定義之後是輸入的結尾。所以是的，我們可以減少。並且由於我們正在減少符號S，因此reduce實際上是一個accept操作：解析結束。我們使用accept操作填寫表格條目。

同樣，我們可以重複下一個項目集，向前看id。讓我們跳到S-獲得空規則：

S -> .  , 'id' 

可以S跟着id？幾乎不。所以這種減少是不合適的。我們不填充解析器表項。

所以你可以看到一個空的規則沒有問題。它立即變成點最後的LR(0)或LR(1)項目（取決於解析器構造方法），並且在考慮前瞻性和填充表格方面與其他任何點最終項目相同。