Practica de talf

Departamento de Estad´stica, ı ´ ´ Investigacion Operativa y Computacion

Computabilidad y Algoritmia
´ ETS Ingenier´a Informatica ı
http://www.etsii.ull.es http://www.campusvirtual.ull.es

´ Practicas

´ ´ Analisis Sintactico
´ 1. Introduccion
´ ´ El objetivo de esta practica es aprender a procesar Gramaticas Independientes del Contexto (Context Free Grammar, CFG) utilizando laherramienta JFLAP (disponible en http://www.jflap.org y en el portal de la asignatura). Obtendremos su forma normal de Chomsky y comprobaremos ´ si una cadena w pertenece al lenguage generado por esta gramatica utilizando el algoritmo de Cocke, Younger y Kasami (CYK). ´ El algoritmo CYK es uno de los algoritmos mas famosos que se utilizan para resolver el ´ ´ ´ problema del analisis sintactico: dada unacadena w ∈ Σ∗ y una gramatica independiente del contexto, G ≡ (V, Σ, S, P ) ¿w ∈ L(G)?. ´ ´ La sintaxis de todo lenguaje de programacion viene especificada por una gramatica indepen´ ´ diente del contexto. El problema del analisis sintactico lo resuelve el compilador de cualquier ´ ´ lenguaje cuando analiza el codigo fuente: si el codigo fuente (programa en lenguaje de alto nivel) ´ contiene erroressintacticos, el compilador indica un error puesto que la cadena analizada (el ´ programa) no cumple las reglas gramaticales del correspondiente lenguaje de programacion. ´ ´ ´ El algoritmo CYK utiliza un metodo de analisis ascendente y es un algoritmo de programacion ´ ´ ´ dinamica. Para poder utilizar el algoritmo, es preciso que la gramatica este escrita en forma nor´ mal de Chomsky (FNC), perocualquier gramatica independiente del contexto puede ser escrita en FNC. En computabilidad, la importancia del algoritmo CYK reside en el hecho de que demuestra ´ ´ de forma constructiva la decibilidad del problema del analisis sintactico, y del hecho de que lo ´ hace de forma bastante eficiente. El tiempo de ejecucion en el caso peor para el algoritmo CYK ´ ´ es Θ(n3 ), siendo n la longitud de lacadena analizada. Los algoritmos de analisis sintacticos que utilizan los compiladores tienen tiempos lineales con respecto al programa compilado, lo cual hace que no utilicen habitualmente el algoritmo CYK.

´ ´ 2. Analisis Sintactico
´ ´ Sea G ≡ (V, Σ, S, P ) una CFG. Sea w ∈ Σ∗ . El problema del analisis sintactico es: ¿w ∈ L(G)? Sea G ≡ (V, Σ, S, P ) una CFG en FN de Chomsky Sea x ∈ Σ∗Lema: ∀A ∈ V y ∀w, subcadena de x se puede determinar si A ⇒∗ w Sea n = |x|
˜ Avda Astrofisico Francisco Sanchez s/n 38271–La Laguna. S/C de Tenerife. Espana.
TEL. 922 318 169 – FAX 922 318 170 http://www.deioc.ull.es email: estinv@ull.es

Departamento de Estad´stica, ı ´ ´ Investigacion Operativa y Computacion

´ Sea wij la subcadena de x que comienza en la posicion i y tiene longitud j ´Demostraremos que el lema se cumple ∀wij por induccion sobre la longitud de la cadena, j ´ Si j = 1 (base de la induccion) entonces |wij | = 1, wij ∈ Σ (es un terminal) y tenemos que: A ⇒∗ wij ⇔ (A → wij ) ∈ P ´ Pero esto se puede determinar puesto que P (las producciones de la gramatica) es un conjunto finito ´ ´ Supongamos ahora (hipotesis de induccion, HI) que el lema se cumple ∀wih tal que |wih | =h < j (siendo j > 1) ´ Consideremos ahora la derivacion de una cadena wij de longitud j: A ⇒∗ wij ⇔ A → BC| B ⇒∗ wik C ⇒∗ wi+k,j−k para algun 1 ≤ k ≤ j − 1 ´ Pero wik y wi+k,j−k tienen longitud menor que j, y por HI se puede determinar si ´ B ⇒∗ wik y tambien si C ⇒∗ wi+k,j−k As´ pues podemos determinar si A ⇒∗ wij con ı 1 ≤ i ≤ n, 1 ≤ j ≤ n − i + 1 Particularizando este lema para A = S ∈ V yconsiderando la cadena w1n = x El lema indica que es posible determinar si S ⇒∗ w1n = x Dicho de otro modo, indica que es posible determinar si x ∈ L(G), o lo que es lo mismo, ´ ´ que es posible resolver el problema del analisis sintactico

3. Algoritmo de Cocke, Younger y Kasami (CYK)
El algoritmo calcula los conjuntos Vij = {A ∈ V |A ⇒∗ wij } Entrada: una cadena w = a1 a2 . . . an y una CFG...