LR1 Parser e Epsilon

Question

Eu estou tentando entender como LR1 Analisadores trabalho, mas eu vim com um problema estranho: E se a gramática contém Epsilons? Por exemplo: se eu tiver a gramática:

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

É claro como começar:

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

... e assim por diante

mas eu não sei como fazê-lo para tal gramática a:

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

É correto fazer:

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

E, em seguida, fazer este Estado no DFA aceitar?

Qualquer ajuda seria muito apreciada!

Answer 1

Sim, exatamente (pense na epsilon como espaço vazio, onde não há dois lugares para o ponto nas laterais).

Em um LR (0) autômato, você faria o estado de aceitação e reduzir a A. No entanto, devido à produção A->a A a, haveria uma mudança / reduzir os conflitos.

Em um LR (1) autômato, você iria determinar se a mudança ou reduzir usando lookahead (a -> mudança, nada em FOLLOW(A) -> reduzir a)

Veja o artigo Wikipedia