LR(1) 解析器可以解析这种类型的语法吗？
S -> SA | A
A -> aSb | ab
我正在尝试编写一个实现此类解析器的 Java 程序，但我只能在没有左递归的语法上获得正确的结果。
最佳答案
LR(1) 解析器可以处理某些类型的左递归，但并非所有左递归语法都是 LR(1)。
让我们看看您的特定语法是否是 LR(1)。增强语法给出
S' → S
S → SA | A
A → aSb | ab
因此我们的配置集是
(1)
S' -> .S [$] (Go to 2)
S -> .SA [$a] (Go to 2)
S -> .A [$a] (Go to 3)
A -> .aSb [$a] (Shift on a and go to 4)
A -> .ab [$a] (Shift on a and go to 4)
(2)
S' -> S. [$] (Accept on $)
S -> S.A [$a] (Go to 3)
A -> .aSb [$a] (Shift on a and go to 4)
A -> .ab [$a] (Shift on a and go to 4)
(3)
S -> A. [$a] (reduce on $ or a)
(4)
A -> a.Sb [$a] (Go to 6)
A -> a.b [$a] (Shift on b and go to 10)
S -> .SA [ab] (Go to 11)
S -> .A [ab] (Go to 12)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(5)
A -> ab. [$a] (Reduce on a or $)
(6)
A -> aS.b [$a] (Shift on b and go to 7)
S -> S.A [ab] (Go to 13)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(7)
A -> aSb. [$a] (Reduce on a or $)
(8)
A -> a.Sb [ab] (Go to 14)
A -> a.b [ab] (Shift on b and go to 16)
S -> .SA [ab] (Go to 11)
S -> .A [ab] (Go to 12)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(9)
S -> SA. [$a] (Reduce on a or $)
(10)
A -> ab. [$a] (Reduce on a or b)
(11)
S -> S.A [ab] (Go to 13)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(12)
S -> A. [ab] (Reduce on a or b)
(13)
S -> SA. [ab] (Reduce on a or b)
(14)
A -> aS.b [ab] (Shift on b and go to 15)
S -> S.A [ab] (Go to 13)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(15)
A -> aSb. [ab] (Reduce on a or b)
(16)
A -> ab. [ab] (Reduce on a or b)
这个语法中没有移位/归约或归约/归约冲突，所以它应该是LR(1)(除非我在某个地方犯了错误!)
希望这有帮助!
关于parsing - LR(1) 解析器中的左递归，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21461974/