Después de mirar en diferentes repositorios y foros de internet al final hemos descubierto la respuesta que te enseñamos más adelante.
Solución:
La gramática presentada en la documentación de Python (y utilizada para generar el analizador de Python) está escrita en forma de BNF extendido que incluye “operadores” como opcionalidad ([a]) y cierre Kleene ((a b c)*). LL(1), sin embargo, es una categoría que se aplica solo a gramáticas simples libres de contexto, que no tienen tales operadores. Entonces preguntar si esa gramática en particular es LL(1) o no es un error de categoría.
Para que la pregunta tenga sentido, la gramática tendría que transformarse en una gramática simple libre de contexto. Por supuesto, esto es posible, pero no existe una transformación canónica y la documentación de Python no explica la transformación precisa utilizada. Algunas transformaciones pueden producir gramáticas LL(1) y otras no. (De hecho, la traducción ingenua de la estrella Kleene puede llevar fácilmente a la ambigüedad, que por definición no es LL(k) para ninguna k).
En la práctica, el aparato de análisis de Python transforma la gramática en un analizador ejecutable, no en una gramática libre de contexto. Para los propósitos pragmáticos de Python, es suficiente poder construir un analizador predictivo con una anticipación de solo un token. Debido a que un analizador predictivo puede usar estructuras de control como declaraciones condicionales y bucles, no es necesaria una transformación completa en una gramática libre de contexto. Por lo tanto, es posible usar producciones EBNF, como con la gramática documentada, que no están completamente factorizadas por la izquierda, e incluso producciones EBNF cuya transformación a LL (1) no es trivial:
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
En la producción anterior, la repetición de (';' small_stmt)* puede ser seguido por un ';'lo que significa que un simple while loop no representará correctamente la producción. No sé cómo el generador de analizador de Python maneja esta producción, pero es posible transformarla en CFG factorizando a la izquierda después de expandir la repetición:
simple_stmt: small_stmt rest_A
rest_A : ';' rest_B
| NEWLINE
rest_B : small_stmt rest_A
| NEWLINE
De manera similar, todo el EBNF se puede transformar en una gramática LL(1). Eso no se hace porque el ejercicio no es útil para analizar o para explicar la sintaxis. Sería difícil de leer y el EBNF se puede transformar directamente en un analizador.
Esto es ligeramente independiente de la cuestión de si Python es LL(1), porque un lenguaje es LL(1) precisamente si existe una gramática LL(1) para el lenguaje. Siempre habrá una infinidad de gramáticas posibles para una lengua, incluidas gramáticas que no son LL(k) para cualquier k e incluso gramáticas que no están libres de contexto, pero eso es irrelevante para la cuestión de si el idioma es LL(1): el lenguaje es LL(1) si existe al menos una gramática LL(1). (Soy consciente de que esta no es la pregunta original, por lo que no continuaré con esto).
Tienes razón en que construye como 'is' | 'is' 'not' no son LL(1). Se pueden factorizar a la izquierda a LL(1) con bastante facilidad cambiándolo a 'is' notOpt dónde notOpt: 'not' | ϵ o, si permite la sintaxis EBNF, simplemente 'is' 'not'? (o 'is' ['not'] dependiendo del sabor de EBNF).
Así que el idioma es LL(1), pero la gramática técnicamente no lo es. Supongo que los diseñadores de Python decidieron que esto estaba bien porque la versión factorizada a la izquierda sería más difícil de leer sin mucho beneficio y la versión actual todavía se puede usar como base para un analizador LL(1) sin mucha dificultad.
Si te ha sido de ayuda este artículo, sería de mucha ayuda si lo compartieras con otros entusiastas de la programación así nos ayudas a difundir nuestro contenido.