語法LALR？

Question

假設同樣的語法不是LR（1），我們可以放心地說語法不是LALR嗎？

如果不是，語法爲LALR的條件是什麼？ （或使語法不成LALR的條件是什麼）

感謝您的幫助！

Answer 1

LALR（1）⊂LR（1），是的，我們可以假設。這兩個語法以類似的方式表示語言，但是LR（1）跟蹤比LALR（1）更多的左邊狀態。參看These lecture notes，其中討論了兩種表示之間的狀態差異。

通常，解析器生成器將處理爲您創建shift-reduce步驟的所有細節;不同之處在於，基於較大文法的生成器更有可能找到無衝突的解析策略。

Answer 2

This document比較兩者。

Answer 3

下面是一個簡單的語法是LR（1），但不LALR（1）：

G -> S 
S -> c X t 
    -> c Y n 
    -> r Y t 
    -> r X n 
X -> a 
Y -> a 

的LALR（1）解析器生成給你一個LR（0）的狀態機。一個LR（1）解析器生成器爲您提供一個LR（1）狀態機。 （1）狀態機比LR（0）狀態機多一個狀態 。

的LR（0）狀態機包含此狀態：

X -> a . 
Y -> a . 

的LR（1）狀態機包含的這兩種狀態而不是 上面顯示的一個：

X -> a . { t } 
Y -> a . { n } 

X -> a . { n } 
Y -> a . { t } 

問題與LALR是國家是第一個 沒有任何知識的頭看。然後，在創建狀態之後檢查或創建外觀 。然後LALR 有這樣一個狀態和外觀-A-頭，這通常是後來添加的， 看起來就像這樣：

X -> a . { t, n } 
Y -> a . { n, t } 

任何人可以在這裏看到了問題？如果預見是't'，你選擇哪種減少方式？ ？它含糊不清！因此，LALR（1）解析器生成器會爲您提供減少 - 減少衝突報告，這可能會使作者無經驗的語法 混淆。

很少有現實世界的計算機語言，它們的LALR（1）衝突可以用LR（1）解析器生成器來解決。 但是，這些衝突通常可以使用LALR（2） 解析器生成器來解決。

這就是爲什麼我使LRSTAR爲LALR（k）解析器生成器。它可以通過在 運行時使用前面的2來處理上述語法。如果有人向我展示LR（1）但不是 LALR（1）的現實世界語法，它將來可能會成爲LR（k）解析器生成器， 。