Ejemplo de una gramática LR que no puede ser representada por LL?

Question

Todas las gramáticas LL son gramáticas LR, pero no al revés, pero aún me cuesta lidiar con la distinción. Tengo curiosidad acerca de pequeños ejemplos, si los hay, de gramáticas LR que no tienen una representación LL equivalente.

Answer 1

Bueno, en lo que respecta a las gramáticas, es fácil: cualquier gramática simple recursiva a la izquierda es LR (probablemente LR (1)) y no LL. Por lo tanto la gramática como una lista:

list ::= list ',' element | element 

es LR (1) (suponiendo que la producción para el elemento es) pero no LL. Tales gramáticas se pueden convertir con bastante facilidad en gramáticas LL mediante factorización de la izquierda y tal, por lo que esto no es demasiado interesante.

De más interés son los IDIOMAS que son LR pero no LL - es un lenguaje para el cual existe una gramática LR (1) pero ninguna gramática LL (k) para cualquier k. Un ejemplo es cosas que necesitan coincidencias finales opcionales. Por ejemplo, el idioma de cualquier número de símbolos a seguido del mismo número o menos de símbolos b, pero no más b s - {a^i b^j | i> = j}. Hay una gramática LR (1) trivial:

S ::= a S | P 
P ::= a P b | \epsilon 

pero no LL (k) gramática. La razón es que una gramática LL necesita decidir si hace coincidir un par a + b o una impar al mirar una a, mientras que la gramática LR puede diferir esa decisión hasta después de que ve el b o el final de la entrada.

This post en cs.stackechange.com tiene un montón de evaluaciones de esta