No he sido capaz de encontrar una respuesta a esto todavía. ¿Existen gramáticas que son independientes del contexto y no ambiguas que no se pueden convertir a LL(1)?
Encontré una producción que no pude averiguar cómo convertir en LL (1): la producción parameter-type-list en C99:
parameter-type-list: parameter-list parameter-list , ...¿Es este un ejemplo de una gramática LR(k) que no tiene un equivalente LL(1) o estoy haciendo algo mal?
editar: copié el nombre incorrecto, quise copiar la declaración de parámetros:
parameter-declaration: declaration-specifiers declarator declaration-specifiers abstract-declarator(opt)el problema es que el declarador y el declarador abstracto tienen ( en su primer conjunto, pero también se quedan recursivos.
En general, las gramáticas LR(k) son más poderosas que las LL(k) . Eso significa que hay lenguajes con LR(k) , pero no LL(k) .
Uno de los ejemplos es el lenguaje definido con la gramática:
S -> a SS -> P P -> a P b P -> \epsilon O, en otras palabras, una cadena de a , seguida por el mismo o menor número de b . Eso se deriva del hecho de que el LL(k) debe tomar una decisión sobre cada a encontrado, si está emparejado con algún b , mirando hacia adelante no más de k símbolos de entrada, pero también pueden ser a 's, sin dar información útil . Para una prueba estricta, mire la segunda parte de la respuesta aceptada aquí https://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable
Su ejemplo, sin embargo, puede simplemente dejarse factorizado en la gramática LL (1) para ser
parameter-type-list -> parameter-list optional-ellipsis optional-ellipsis -> \epsilon optional-ellipsis -> , ... Una nota de que el conjunto FOLLOW para parameter-list contendrá , carácter, y esto puede causar un conflicto FIRST-FOLLOW . Si es el caso, entonces también necesitamos ver la definición de parameter-list para solucionar este conflicto.
Editar: la regla parameter-declaration parece muy complicada de responder de inmediato. Puede intentar realizar la factorización izquierda a mano para todas las alternativas en conflicto, o con alguna herramienta de asistencia, como ANTLR .