LR1 Parser and Epsilon

Question

I’m trying to understand how LR1 Parsers work, but I got a strange problem: what if the grammar contains Epsilons? For example: if I have a grammar:

S -> A A -> a A | B B -> a 

It is clear how to start:

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

... etc.

but I don’t know how to do this for such a grammar:

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

Is it right to do this:

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

And then get this state into the DFA to accept?

Any help would be really appreciated!

Answer 1

Yes, for sure (think of epsilon as an empty space where there are no two points for a point on the sides).

In the LR (0) machine, you must accept the state and reduce it to A. However, due to A->a A a production, a change / decrease conflict has arisen.

In the LR (1) machine, you must determine whether to shift or reduce using lookahead (shift a →, something in FOLLOW(A) → decrease)

See Wikipedia article