Cada LR (0) gramática es SLR (1), pero al revés no tiene por qué ser necesariamente cierto, ¿por qué?

Question

Cada LR (0) gramática es SLR (1), pero al revés no tiene por qué ser necesariamente cierto, ¿por qué?

Answer 1

Básicamente, un SLR (1) gramática puede resolver de cambio-reducir los conflictos que existen en un LR correspondiente (0) gramática. Tomemos el ejemplo de la gramática href="http://en.wikipedia.org/wiki/Simple_LR_parser" rel="nofollow"> SLR analizador de páginas de Wikipedia (lo que explica esto en un nivel más bajo, más riguroso) :

1. S ? E
2. E ? E 1
3. E ? 1

Cuando un (0) analizador sintáctico LR es analizar un E y un "1" es el siguiente símbolo de entrada, se podría reconocer E y reducir (regla 3) o que podría cambiar con el fin de analizar una siguiente E (regla 2). Porque no puede mirar hacia el futuro, un LR (0) no puede determinar qué hacer. Esto se hace más evidente si nos fijamos en la la LR (0) podría ser el proceso cuando se encuentra con un "1" (el símbolo de final de cadena se ha añadido):

• E ? E • 1 $
• E ? 1 • $

La primera requeriría un cambio, la segunda requiere una Reducir.

Con la gramática anterior, una SLR (1) gramática puede mirar hacia adelante un símbolo y determinar qué acción tomar. E sólo puede ser seguido por $, por lo que un reducen acción sólo es válida en el final de la cadena. Esto se corresponde con el segundo punto, donde se puede ver el símbolo es un "$".

Para otro ejemplo gramática que es SLR (1) y no LR (0), ver Fegaras' notas para CSE 5317/4305 en la Universidad de Texas.