parsing compiler-theory lr1

parsing - LR1 Parser y Epsilon



compiler-theory (1)

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!


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