¿Ejemplo de una gramática LR que LL no puede representar?

Question

Todas las gramáticas LL son gramáticas LR, pero no al revés, pero todavía me cuesta lidiar con la distinción. Tengo curiosidad por los pequeños ejemplos, si existen, 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 izquierda es LR (probablemente LR (1)) y no LL. Entonces una gramática de la lista como:

list ::= list ',' element | element

es LR (1) (suponiendo que la producción para el elemento sea) pero no LL. Dichas gramáticas pueden convertirse bastante fácilmente en gramáticas LL mediante factor de izquierda y demás, por lo que esto no es demasiado interesante.

De más interés son los idiomas que son LR pero no LL, ese es un idioma para el que existe una gramática LR (1) pero no LL (k) gramática para ninguna k. Un ejemplo son las cosas que necesitan coincidencias posteriores opcionales. Por ejemplo, el lenguaje de cualquier número de a símbolos seguidos del mismo número o menos b símbolos, pero no más bS - {a^ib^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 debe decidir si coincidir con un par A+B o una ADA A cuando mira una A, mientras que la gramática LR puede diferir esa decisión hasta que vea el B o el final de la entrada.

Esta publicación en cs.stackechange.com tiene muchas referencias sobre esto