¿Busca un idioma que no sea LL (1)?

Question

He estado jugando con muchas gramáticas que no son LL (1) recientemente, y muchas de ellas se pueden transformar en gramáticas LL (1).

Sin embargo, nunca he visto un ejemplo de un idioma inequívoco que no sea LL (1). En otras palabras, un lenguaje para el cual cualquier gramática no ambigua para el lenguaje no es LL (1)), ni tengo idea de cómo podría probar que encontré uno si accidentalmente tropecé con uno.

¿Alguien sabe cómo probar que un lenguaje inequívoco particular no es LL (1)?

Answer 1

Estaba pensando en la pregunta un tiempo y luego encontraron esta lengua en Wikipedia:

S -> A | B 
A -> 'a' A 'b' | ε 
B -> 'a' B 'b' 'b' | ε 

Afirman que el lenguaje descrito por la gramática anterior no puede ser descrito por la gramática LL (k). Usted preguntó acerca de LL (1) solamente y esto es bastante sencillo. Teniendo solo el primer símbolo, no sabes si la secuencia es 'ab' o 'aab' (o más recursiva) y por lo tanto no puedes elegir la regla correcta. Entonces el lenguaje definitivamente no es LL (1).

También para cada secuencia generada por esta gramática solo hay un árbol de derivación. Entonces el lenguaje no es ambiguo.

La segunda parte de su pregunta es un poco más difícil. Es mucho más fácil probar que el lenguaje es LL (1), que lo contrario (no hay una gramática LL (1) que describa el idioma). Creo que solo creas una gramática que describe el idioma, luego tratas de hacerlo LL (1). Después de descubrir un conflicto que no se puede resolver, de alguna manera tiene que aprovecharlo y crear una prueba.