LR1 Parser ed Epsilon

Question

Sto cercando di capire come funzionano i parser LR1 ma ho riscontrato uno strano problema: cosa succede se la grammatica contiene Epsilon? Ad esempio: se ho la grammatica:

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

È chiaro come iniziare:

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

... e così via

ma non so come farlo per una tale grammatica:

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

È corretto fare:

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

E quindi accettare questo stato nel DFA?

Qualsiasi aiuto sarebbe davvero apprezzato!

Answer 1

Sì, esattamente (pensa a epsilon come spazio vuoto, dove non ci sono due punti per il punto ai lati).

In un automa LR (0), faresti accettare lo stato e ridurlo ad A. Tuttavia, a causa della A->a A a produzione, ci sarebbe uno spostamento / riduzione del conflitto.

In un automa LR (1), determineresti se spostare o ridurre usando lookahead (a - > shift, qualsiasi cosa in FOLLOW(A) - > riduci)

Vedi articolo di Wikipedia