LR1 解析器和 Epsilon
我试图了解 LR1 解析器是如何工作的，但我遇到了一个奇怪的问题：如果语法包含 Epsilons 怎么办？ 例如：如果我有语法：
S -> A
A -> a A | B
B -> a
很清楚如何开始：
S -> .A
A -> .a A
A -> .B
...等等，
但我不知道如何执行这样的语法：
S -> A
A -> a A a | \epsilon
这样做是否正确：
S -> .A
A -> .a A a
( A -> .\epsilon )
然后在 DFA 中设置此状态接受？
任何帮助将不胜感激！
I'm trying to understand how LR1 Parsers work but I came up with a strange problem: What if the grammar contains Epsilons? For instance: if I have the grammar:
S -> A
A -> a A | B
B -> a
It's clear how to start:
S -> .A
A -> .a A
A -> .B
... and so on
but I don't know how to do it for such a grammar:
S -> A
A -> a A a | \epsilon
Is it correct to do:
S -> .A
A -> .a A a
( A -> .\epsilon )
And then make this State in the DFA accepting?
Any help would really be appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，确实如此（将 epsilon 视为空白空间，其两侧没有两个点可以放置）。
在 LR(0) 自动机中，您可以使状态接受并归约到 A。但是，由于
A->a A a产生式，会出现移位/归约冲突。在 LR(1) 自动机中，您可以使用前瞻来确定是移位还是归约（
a-> 移位，FOLLOW(A)中的任何内容 -> 归约）请参阅维基百科文章
Yes, exactly (think of the epsilon as empty space, where there aren't two places for the dot at the sides).
In an LR(0) automaton, you would make the state accepting and reduce to A. However, due to the
A->a A aproduction, there'd be a shift/reduce conflict.In a LR(1) automaton, you would determine whether to shift or reduce using lookahead (
a-> shift, anything inFOLLOW(A)-> reduce)See the Wikipedia article
您可以使用此站点来计算：
https://cyberzhg.github.io/toolbox/lr1
查看结果：
You can use this site to compute this:
https://cyberzhg.github.io/toolbox/lr1
See the results: