LR1 Parser y Epsilon

Question

Estoy tratando de entender cómo funcionan los analizadores LR1 pero se me ocurrió un problema extraño: ¿qué pasa si la gramática contiene Epsilons? Por ejemplo: si tengo la gramática:

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

Está claro cómo comenzar:

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

... y así sucesivamente

pero no sé cómo hacerlo para esa gramática:

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

¿Es correcto hacer:

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

¿Y luego hacer que este estado en el DFA acepte?

¡Cualquier ayuda sería realmente apreciada!

Answer 1

Sí, exactamente (piense en el épsilon como un espacio vacío, donde no hay dos lugares para el punto a los lados).

En un autómata LR (0), haría que el estado aceptara y redujera a A. Sin embargo, debido a la producción de A->a A a, habría un conflicto de cambio / reducción.

En un autómata LR (1), determinaría si cambiar o reducir usando lookahead (a - > shift, cualquier cosa en FOLLOW(A) - > reduce)

Vea el artículo de Wikipedia