LL (1) no puede ser ambiguo

Question

¿Cómo se puede demostrar que ninguna gramática LL (1) puede ser ambigua?

Sé lo que es la gramática ambigua, pero no pude probar el teorema/lema anterior.

Answer 1

Creo que es casi un resultado directo de la definición de LL (1). Prueba la prueba por contradicción; suponga que tiene una gramática LL (1) que es ambigua y busca algo que pueda mostrar como verdadero y no verdadero. Como punto de partida "¿qué es lo que siempre sabes al procesar la entrada?"

Como parece un problema de tarea y realmente no he terminado el problema más de lo que esbocé anteriormente, me detendré allí.

Answer 2

Demostrar que ninguna gramática ambigua puede ser una gramática LL (1). Para sugerencias, vea http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf, diapositivas 18-20. También vea http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, pg. 11 y precedentes.

Answer 3

Aquí está mi primer borrador en una prueba. Puede necesitar un ajuste fino, pero creo que cubre todos los casos. Creo que muchas soluciones son posibles. Esta es una prueba directa.

(Nota al pie: es una lástima SO no soporta matemáticas, tal como en LaTeX.)

Prueba

Sea T y N el conjuntos de terminales y no terminales símbolos .

Vamos a la siguiente bodega

MaybeEmpty(s) = true <=> s ->* empty 
First(s) = X containing all x for which there exists Y such that s ->* xY 
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ 

Tenga en cuenta que una gramática es LL (1) si se cumple lo siguiente para cada par de producciones A -> B y A -> C:

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C)) 
2. (First(B) intersect First(C)) = empty 
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty 

Considere un lenguaje con LL (1), con A -> B y A -> C. Es decir, hay una cadena de terminales TZ que admite derivaciones múltiples por distintos árboles de análisis.

Suponga que la derivación izquierda llega a S ->* TAY ->* TZ. El siguiente paso puede ser TAY -> TBY o TAY -> TCY. Por lo tanto, el lenguaje es ambiguo si ambos BY ->* Z y CY ->* Z. (Tenga en cuenta que dado que A es un arbitrarias no terminales, si no existe tal caso, el lenguaje no es ambigua.)

Caso 1:

Por regla 1 de LL (1) gramáticas Z = vacía , a lo sumo, uno de B y C puede derivar vacío (caso no ambiguo).

Caso 2: Z no vacío, y ni B ni C derivan vacío

Por regla 2 de LL (1) gramáticas, a lo sumo uno de B y C pueden permitir más derivación debido a que el líder de terminal de Z no puede estar en ambos First(B) y First(C) (caso no ambiguo).

Caso 3: Z no vacía, y, o bien MaybeEmpty(B) o MaybeEmpty(C)

Nota el por regla 1 de LL (1) gramáticas, B y C pueden no ambos derivar vacía. Supongamos, por lo tanto, que MaybeEmpty(C) es verdadero.

Esto da dos sub-casos.

Caso 3a: CY -> Y; y Caso 3b: CY ->* DY, donde D no está vacío.

En 3a debemos elegir entre BY ->* Z y CY -> Y ->* Z, pero tenga en cuenta que First(Y) subset-of Follow(A). Como Follow(A) no se cruza con First(B), solo puede proceder una derivación (no ambigua).

En 3b debemos elegir entre BY ->* Z y CY ->* DY ->* Z, pero tenga en cuenta que First(D) subset-of First(C). Como First(C) no se cruza con First(B), solo puede proceder una derivación (no ambigua).

Por lo tanto, en todos los casos, la derivación solo se puede ampliar con una de las producciones disponibles. Por lo tanto, la gramática no es ambigua.