parsing - LR1 Parser y Epsilon

compiler-theory

Question

Intento entender cómo funciona LR1 Parsers, pero surgió un problema extraño: ¿y si la gramática contiene Epsilon? 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í

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

S -> A
A -> a A a | /epsilon

¿Es correcto hacerlo?

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

¿Y luego aceptar este estado en el DFA?

¡Cualquier ayuda realmente sería apreciada!

Answer 1

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

En un autómata LR (0), usted haría que el estado acepte y reduzca 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), usted determinaría si cambiar o reducir el uso de anticipación ( a -> shift, cualquier cosa en FOLLOW(A) -> reducir)

Ver el artículo de Wikipedia