¿Es la gramática del python LL (1)?

Posible duplicado para esta pregunta, sin embargo, para mí no es lo suficientemente específico.

Se dice que la gramática de python es LL (1) , pero he notado algunas expresiones en la gramática de Python que realmente me confunden, por ejemplo, los argumentos en la siguiente llamada de función:

foo(a) foo(a=a) 

Corresponde a la siguiente gramática:

 argument: ( test [comp_for] | test '=' test | '**' test | '*' test ) 

test aparece dos veces en la primera posición de la gramática. Significa que solo con mirar la test Python no puede determinar su test [comp_for] o test '=' test .

Más ejemplos:

 comp_op: ''|'=='|'>='|'<='|''|'!='|'in'|'not' 'in'|'is'|'is' 'not' 

Nota 'is' y 'is' 'not'

 subscript: test | [test] ':' [test] [sliceop] 

test también aparece dos veces.

¿Mi comprensión de LL (1) es incorrecta? ¿Hace Python alguna solución para la gramática durante el análisis o el análisis para que sea procesable LL (1)? Gracias a todos de antemano.

La gramática presentada en la documentación de Python (y utilizada para generar el analizador de Python) está escrita en una forma de BNF extendido que incluye “operadores” como la opcionalidad ( [a] ) y el cierre de Kleene ( (abc)* ). LL (1), sin embargo, es una categoría que se aplica solo a las gramáticas simples sin 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 debería transformarse en una simple gramática sin contexto. Esto es, por supuesto, posible, pero no hay 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 de Kleene puede llevar fácilmente a la ambigüedad, que es por definición no LL (k) para cualquier 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 para poder construir un analizador predictivo con una búsqueda de solo un token. Debido a que un analizador predictivo puede usar estructuras de control como sentencias condicionales y bucles, una transformación completa en una gramática libre de contexto es innecesaria. Por lo tanto, es posible utilizar producciones de EBNF, como con la gramática documentada, que no son totalmente de izquierda, e incluso producciones de 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 ir seguida de un ';' , lo que significa que un simple bucle while no representará correctamente la producción. No sé cómo esta producción es manejada por el generador de analizador de Python, pero es posible transformarla en CFG mediante la factorización a la izquierda después de expandir la repetición:

 simple_stmt: small_stmt rest_A rest_A : ';' ret_B | NEWLINE rest_B : small_stmt rest_A | NEWLINE 

De manera similar, todo el EBNF se puede transformar en una gramática LL (1). Esto no se hace porque el ejercicio no es útil para analizar o para explicar la syntax. Sería difícil de leer, y el EBNF se puede transformar directamente en un analizador.

Esto es ligeramente independiente de la pregunta de si Python es LL (1), porque un idioma es LL (1) precisamente si existe una gramática LL (1) para el idioma. Siempre habrá una infinidad de gramáticas posibles para un idioma, incluidas las gramáticas que no son LL (k) para cualquier k e incluso las gramáticas que no están libres de contexto, pero eso es irrelevante para la pregunta de si el idioma es LL (1 ): el idioma es LL (1) si existe una gramática LL (1). (Soy consciente de que esta no es la pregunta original, por lo que no continuaré con esto).

Eres correcto que construye como 'is' | 'is' 'not' 'is' | 'is' 'not' son LL (1). Pueden ser factorizados a la izquierda a LL (1) con bastante facilidad cambiándolo a 'is' notOpt where notOpt: 'not' | ϵ notOpt: 'not' | ϵ o, si permite la syntax EBNF, simplemente 'is' 'not'? (o 'is' ['not'] dependiendo del sabor de EBNF).

Entonces el lenguaje es LL (1), pero técnicamente la gramática no lo es. Supongo que los diseñadores de Python decidieron que esto estaba bien porque la versión del factor izquierdo sería más difícil de leer sin mucho beneficio y la versión actual aún puede usarse como la base para un analizador de LL (1) sin mucha dificultad.