一个LR(1)分析器能否解析这种类型的语法?
S -> SA | A
A -> aSb | ab
我正在尝试编写一个Java程序来实现这种类型的解析器,但是只有在没有左递归的语法中才能得到正确的结果。
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)文法(除非我在某个地方出错了!)
希望这可以帮到你!
(1)
S' -> .S S => (Go to 2)
S -> .SA A => (Go to 3)
S -> .A a => (Shift and go to 4)
A -> .aSb
A -> .ab
(2)
S' -> S. $ => (Accept on $)
S -> S.A A => (Go to 5)
A -> .aSb a => (Shift and go to 6)
A -> .ab
(3)
S -> A. [$b] => (reduce on $ or b)
(4)
A -> a.Sb S => (Go to 7)
A -> a.b A => (Go to 9)
S -> .SA a => (Shift and go to 6)
S -> .A b => (Shift and go to 8)
A -> .aSb
A -> .ab
(5)
S -> SA. [$b] => (reduce on $ or b)
(6)
A -> a.Sb S => (Go to 7)
A -> a.b A => (Go to 3)
S -> .SA a => (Shift and go to 4)
S -> .A b => (Shift and go to 8)
A -> .aSb
A -> .ab
(7)
A -> aS.b A => (Go to 5)
S -> S.A a => (Shift and go to 6)
A -> .aSb b => (Shift and go to 10)
A -> .ab
(8)
A -> ab. [$b] => (reduce on $ or b)
(9)
S -> A. [$b] => (reduce on $ or b)
(10)
A -> aSb. [$b] => (reduce on $ or b)