Determinar si una gramática puede convertirse a LL(1)/LL(k)

Question

(Este es un post cruzado de https://cstheory.stackexchange.com/questions/11676/determining-if-a-grammar-can-be-converted-to-ll1-llk con la esperanza de conseguir un público más amplio).

Me gustaría saber si hay una manera de determinar si una gramática libre de contexto se puede convertir en

• una gramática LL(1)
• una gramática LL(k), sea cual sea el valor de k (por lo que el algoritmo debe dar el valor de k)

Por "puede convertirse en", quiero decir que la nueva gramática (LL) debe generar el mismo lenguaje que la antigua gramática.

Si no se puede hacer, agradecería algunas referencias. También me interesan las formas de conseguir el mismo resultado en condiciones más restrictivas (por ejemplo, sólo para gramáticas libres de contexto no ambiguas).

Answer 1

Copiando esta respuesta del comentario de @AlextenBrink:

Prueba con Propiedades de las gramáticas deterministas descendentes por D.J. Rosenkrantz y R.E. Stearns. Demuestra que sus dos problemas son indecidibles en general, y demuestra que el segundo es decidible si su gramática es LR( $k'$ ) para algunos $k'$ .

Lamentablemente, no he podido encontrar una copia de este artículo que se pueda descargar gratuitamente en línea. (Los artículos de las revistas de la ACM suelen tener licencia para su distribución gratuita con fines académicos. Si sale a la luz una copia, la enlazaré aquí).

Aquí hay un hilo de se.cs posiblemente relevante: Comparación teórica de las gramáticas LL y LR

Answer 2

Posiblemente también sea interesante la presentación detallada de Peter Pepper sobre cómo realizar transformaciones simples en una CFG para terminar con una gramática LL (si el original era LR(k)). Análisis LR = Transformación gramatical + Análisis LL