假設你有一個文法 G，我們為它找到一個 LR(1) 自動機。我們可以通過執行狀態合并和轉換規則將其轉換為 LALR(1) 或 SLR(1) 決議器，但可能會出現沖突。
我的問題如下：所有問題都必須出現在合并狀態中嗎？未合并的非沖突 LR(1) 狀態是否可能在 LALR(1) 或 SLR(1) 自動機中發生沖突？
uj5u.com熱心網友回復：
有趣的問題！答案是
- 如果語法是 LR(1)，則 LALR(1) 決議器中的任何沖突都必須發生在合并狀態中，但是
- 如果語法是 LR(1)，則沖突可能出現在未合并的 LR(1) 狀態中。
對于第一點，假設你有一個 LR(1) 的語法，所以你可以形成它的 LR(1) 決議器。我們可以通過將具有相同產生式的所有狀態合并在一起，將其轉換為 LALR(1) 決議器，忽略前瞻。如果你的 LR(1) 狀態沒有與任何東西合并，那么 LR(1) 狀態會逐字出現在 LALR(1) 決議器中。并且由于 LR(1) 狀態沒有移位/歸約或歸約/歸約沖突，相應的 LALR(1) 決議器狀態不會有任何沖突。
在 SLR(1) 方面，您最終可能會遇到不會發生 LR(1) 狀態合并的狀態，但存在減少/減少沖突。這背后的直覺是，您可以在 LR(1) 決議器中擁有一個沒有減少/減少沖突的狀態，因為前瞻有足夠的細節來解決沖突，但是當從 LR(1) 切換到 SLR(1) 并擴展時我們不小心引入了減少/減少沖突的前瞻集。這是發生這種情況的語法示例：
- S → aTb | 阿爾| cT
- T → d
- R → d
這是 LR(1) 配置集：
(1)
S' -> .S [$]
S -> .aTb [$]
S -> .aR [$]
S -> .cT [$]
(2)
S' -> S. [$]
(3)
S -> a.Tb [$]
S -> a.R [$]
T -> .d [b]
R -> .d [$]
(4)
T -> d. [b]
R -> d. [$]
(5)
S -> aT.b [$]
(6)
S -> aTb. [$]
(7)
S -> aR. [$]
(8)
S -> c.T [$]
T -> .d [$]
(9)
T -> d. [$]
(10)
S -> cT. [$]
這些項集與您在 SLR(1) 決議器中的項集相同。另請注意，FOLLOW(T) = {$, b}。這意味著 LR(1) 狀態
(4)
T -> d. [b]
R -> d. [$]
轉換為 SLR(1) 狀態
(4)
T -> d. [b, $]
R -> d. [$]
它對 $ 有減少/減少沖突。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/484545.html
上一篇：識別符號中的有效字符是什么？