LR1解析器和Epsilon [英] LR1 Parser and Epsilon

问题描述

我试图了解LR1解析器的工作原理，但是我想到了一个奇怪的问题:如果语法中包含Epsilons，该怎么办?例如:如果我有语法:

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

很清楚如何开始:

S -> .A
A -> .a A 
A -> .B

...等等

但是我不知道怎么做这样的语法:

but I don't know how to do it for such a grammar:

S -> A
A -> a A a | \epsilon

这样做正确吗?

S -> .A
A -> .a A a
( A -> .\epsilon )

然后在DFA中接受该状态?

And then make this State in the DFA accepting?

任何帮助将不胜感激！

推荐答案

是的，完全正确(将epsilon视为空白，在侧面没有两个点的地方).

Yes, exactly (think of the epsilon as empty space, where there aren't two places for the dot at the sides).

在LR(0)自动机中，您将使状态接受并减少为A.但是，由于产生A->a A a，因此存在移位/减少冲突.

In an LR(0) automaton, you would make the state accepting and reduce to A. However, due to the A->a A a production, there'd be a shift/reduce conflict.

在LR(1)自动机中，您将确定是否使用先行移位(a->移位，FOLLOW(A)-> reduce中的任何内容)

In a LR(1) automaton, you would determine whether to shift or reduce using lookahead (a -> shift, anything in FOLLOW(A) -> reduce)

请参见维基百科文章

这篇关于LR1解析器和Epsilon的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！