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