LR1 Parser and Epsilon

Question

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!

No way. Still don't believe I found this question on Stack Overflow ;) So the next time you apply the `Goto` function, will you do `Goto(Io, \epsilon)` where `Io` is that first state? — Oscar Mederos, Jun 28 '11 at 03:39

score 5 · Accepted Answer · answered Jan 28 '09 at 12:44

5

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 a production, 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 in FOLLOW(A) -> reduce)

See the Wikipedia article

answered Jan 28 '09 at 12:44

jpalecek

47,058
7
102
144

1

Do you say `A->.\epsilon` is not in `I0`? – alhelal Apr 07 '18 at 11:44

score 1 · Answer 2 · answered Feb 04 '21 at 12:28

1

You can use this site to compute this: https://cyberzhg.github.io/toolbox/lr1

See the results:

answered Feb 04 '21 at 12:28

Rea Haas

2,018
1
16
18

LR1 Parser and Epsilon

2 Answers2

Linked