Download Parte 3 - Angelfire
Document related concepts
Transcript
CAPÍTULO 3. LENGUAJES Y GRAMÁTICAS LIBRES DE CONTEXTO 3.1 Aplicaciones de los Lenguaje Formales Uno de los usos más importantes de la teoría formal de lenguajes es en la definición de lenguajes de programación y en la construcción de intérpretes y compiladores para ellos. El problema básico es definir un lenguaje de programación preciso y usar esta definición como el punto de comienzo para escribir la traslación de programas en forma eficiente y confiable. Ambos, los lenguajes regulares y libres de contexto son importantes para lograr este objetivo. Los lenguajes regulares son usados en el reconocimiento de ciertos patrones que ocurren en los lenguajes de programación, pero necesitamos lenguajes libres de contexto para modelar aspectos más complicados. Como muchos lenguajes, podemos definir un lenguaje de programación por una gramática. Es tradicional en la escritura de un lenguaje de programación usar una convención para especificar gramáticas en forma de Backus-Naur o BNF. En esta forma las variables son encerradas en paréntesis triangulares. Los símbolos terminales están escritos sin una forma especial. BNF usa símbolos auxiliares como |. Así, podemos mostrar la siguiente gramática en BNF: <expresión> ::= <término> | <expresión> + <término>, <término> ::= <factor> | <término> * <factor>, etc. Los símbolos + y * son terminales. El símbolo | es usado como un alternador en nuestra notación, pero ::= es usado en lugar de . Las descripciones en BNF de los lenguajes de programación tienden a usar más variables de identificación explícita para intentar una producción explícita. De otra forma no habría diferencias entre las dos notaciones. Muchas partes de los lenguajes de programación tal como el Pascal son susceptibles a la definición por formas restrictivas de las gramáticas libres de contexto. Por ejemplo, un if-then-else puede definirse así <if_statement> ::= if <expression> <then_clause> <else_clause>. Aquí, la palabra if es un símbolo terminal. Los otros términos son variables que tendrán que definirse. La variable <if_statement> está asociada con if de la parte derecha. Por esta razón, tal oración es eficientemente parseada. Vemos aquí el porqué usamos palabras 29 reservadas en los lenguajes de programación. Las palabras reservadas no solo proveen una estructura visual que puede guiar al lector del programa, sino que además hace el trabajo de un compilador más fácil. Desafortunadamente, no todas las características de un lenguaje de programación pueden ser expresados por una gramática simple. Las reglas para <expression> no son de este tipo, de manera que el parseo comienza a ser menos obvio. La pregunta entonces es porqué las reglas gramaticales pueden permitir un parseo eficiente. En los compiladores, el uso extensivo ha sido hecho de las gramáticas regulares y libres de contexto, las cuales tienen la habilidad de expresar las características menos obvias de un lenguaje de programación, y todavía permitir usar un parser en tiempo lineal. En relación con esto, el aspecto de ambigüedad toma un significado especial. La especificación de un lenguaje de programación no debe ser ambiguo, de otra manera podría dar resultados diferentes cuando son procesados por otros compiladores o corridos en diferentes sistemas. Para evitar esos errores debemos ser capaces de reconocer y eliminar ambigüedades. Una pregunta relacionada es si el lenguaje es inherentemente ambiguo. Lo que necesitamos para este propósito es el uso de algoritmos para detectar y eliminar ambigüedades en gramáticas libres de contexto y para decidir si dicho lenguaje es inherentemente ambiguo. Los aspectos de un lenguaje de programación, los cuales pueden ser modelados por una gramática libre de contexto es referida como sintaxis. Sin embargo, es normal el caso en que no todos los programas sintácticamente correctos son programas aceptables. En Pascal, se permite construir el siguiente código: var x,y: real; x,y: integer O bien var x: integer; x:= 3.2. Ninguna de esas construcciones es aceptada por el compilador Pascal, debido a que se violan otras condiciones, tales como que una variable entera no puede asignársele un valor real. Esta regla es parte de la semántica del lenguaje, debido a que se interpreta el significado particular de la expresión. 30 La semántica de un lenguaje de programación es un tema complicado. Nada mas elegante y conciso como las gramáticas libres de contexto para la especificación semántica de un lenguaje. Este es un resultado que concierne tanto a lenguajes de programación como a la teoría de lenguajes formales para encontrar métodos efectivos para definir la semántica de los lenguajes de programación. Varios métodos han sido propuestos, pero ninguno de ellos han sido aceptados universalmente y tan maravillosos como la definición de semánticas por los lenguajes libres de contexto. El tema de los Lenguajes Libres de Contexto (LLC) es el aspecto más importante de la teoría formal de lenguajes así como su aplicación en los lenguajes de programación. Lo que la teoría formal de lenguajes dice acerca de los LLC tiene importantes aplicaciones en el diseño de lenguajes de programación, así como en la construcción de compiladores eficientes. 3.2 Gramáticas Libres de Contexto Las producciones en una GR están restringidas en dos formas: el lado izquierdo debe ser una sola variable, mientras que el lado derecho tiene una forma especial. Para crear gramáticas más poderosas, debemos hacer flexibles estas restricciones. Mantenemos la restricción del lado izquierdo, pero permitimos cualquier cosa en el lado derecho, y entonces obtenemos una Gramática Libre de Contexto. En las Gramáticas Libres de Contexto (GLC), las reglas son de la forma (V-)xV*, en donde V es el vocabulario (símbolos terminales y no terminales) es el conjunto de símbolos terminales Entonces V- es el conjunto de no terminales y están en la parte izquierda de las producciones, mientras que en el lado derecho está V*, que significa que puede ser cualquier cadena formada de símbolo terminales y no terminales. Una gramática regular es libre de contexto, de modo que un lenguaje regular es libre de contexto. Los Lenguajes Libres de Contexto(LLC) son aquellos que pueden ser generados por una GLC, en donde las reglas son de la forma A , donde A es un No Terminal, y 31 es una cadena compuesta de Terminales y de No Terminales, en cualquier orden. Ejemplo. La siguiente gramática genera el lenguaje de los paréntesis bien balanceados. V={S,(,)} R 1. S (S) 2. S SS S () ={(,)} El lenguaje generado por esta gramática no es regular. Derivaciones por la izquierda y por la derecha En las GLC, una derivación puede involucrar ciertas formas con más de una variable. En tales casos, tenemos una opción en el orden en el que las variables son reemplazadas. Tomemos como ejemplo la gramática G = ({A,B,S}, {a,b}, S, P) con las producciones 1. S AB 2. A aaA 3. A 4. B Bb 5. B Esta gramática genera el lenguaje L(G) = {a2nbm Consideremos ahora las dos derivaciones siguientes: | n,m0}. S 1 AB 2 aaAB 3 aaB 4 aaBb 5 aab y S 1 AB 4 ABb 2 aaABb 5 aaAb 3 aab Observamos que las dos derivaciones generan la misma palabra y utilizan las mismas producciones. La diferencia está en el orden en que son aplicadas. Para eliminar estos factores irrelevantes, necesitaremos que las variables sean reemplazadas en un orden específico. Se dice que una derivación se realiza por la izquierda si en cada paso, la variable más a la izquierda de la forma generada es reemplazada. Si en cada paso, la variable que está más a la derecha es 32 reemplazada, entonces estamos realizando una derivación por la derecha. 3.3 Arboles de derivación Una segunda forma de mostrar derivaciones, independientemente del orden en el que son usadas, es usando un árbol de derivación. Un Arbol de Derivación es un grafo arborescente definido de la siguiente manera: Sea G=(V, ,R,S) una GLC. Entonces un árbol de derivación cumple las siguientes propiedades: 1 Cada nodo tiene una etiqueta 2 La raíz tiene etiqueta S 3 La etiqueta de los nodos que no son hojas deben estar en V- 4 Si un nodo tiene etiqueta A, y los nodos n1,…, nm son sus hijos ( de izquierda a derecha) con etiquetas A1, …,Am, entonces A A1…Am R. 5 Si un nodo tiene etiqueta , entonces es un nodo hoja, y es el único hijo de su nodo padre. En un árbol de derivación, un nodo etiquetado con una variable que está en el lado izquierdo de la producción tiene hijos que consisten de símbolos en el lado derecho de dicha producción. Comenzando en la raíz, etiquetada con el símbolo inicial y terminando en las hojas que son los terminales, un árbol de derivación muestra cómo una variable es reemplazada en la derivación. Consideremos la gramática G con producciones S aAB, A bBb, B A|. El árbol de la siguiente figura muestra una derivación parcial de G, genera la cadena abBbB. 33 El árbol de la siguiente figura es un árbol de derivación de G que genera la cadena abbbb. Los árboles de derivación dan una descripción explícita y fácil de una derivación. Similar a los grafos de transición para AF, esta explicación es de gran ayuda en la realización de argumentos. Es conveniente establecer la relación entre las derivaciones y los árboles de derivación con el siguiente teorema: Teorema. Sea G = (V,T,S,P) una GLC. Entonces para cada w L(G), existe un árbol de derivación de G cuya cadena generada es w. Inversamente, una cadena de cualquier árbol de derivación está en L(G). También, si tG es cualquier derivación parcial del árbol para G cuya raíz está etiquetada con S, entonces la cadena de tG es una forma sentencial de G. 34 Los árboles de derivación muestran cuáles producciones son usadas para obtener una cadena, pero no dicen el orden de aplicación. Estos árboles son capaces de representar cualquier derivación, reflejando el hecho de que este orden es irrelevante. Por definición, cualquier w L(G) tiene una derivación, pero no dice si es una derivación por la izquierda o por la derecha Ambigüedad en Gramáticas y Lenguajes Una GLC G se dice que es ambigua si existe alguna w L(G) que tiene al menos dos árboles de derivación. Alternativamente, la ambigüedad implica la existencia de dos o más derivaciones por la izquierda o por la derecha. La ambigüedad es una característica común de los lenguajes naturales, donde ésta es tolerada y tratada con una variedad de formas. En los Lenguajes de Programación, en donde debería haber una interpretación para cada cadena, la ambigüedad debe ser eliminada cuando sea posible. Siempre podemos lograrlo reescribiendo la gramática en una forma no ambigua. Consideremos la gramática G = (V,T,E,P) con V = {E,I}, T = {a,b,c,+,*,(,)}, y las producciones E I, E E + E, E E * E, E (E), I a|b|c. Las cadenas (a+b)*c y a*b+c están en L(G). Es fácil ver que esta gramática genera un subconjunto de expresiones aritméticas para lenguajes de programación como C o Pascal. La gramática es ambigua. Por ejemplo, la cadena a+b*c tiene dos árboles de derivación, tal y como se muestra en la siguiente figura: 35 Una forma de resolver la ambigüedad es asociar reglas de precedencia con los operadores + y *. Debido a que * normalmente tiene una precedencia mayor que +, tomaremos como parseo correcto el del primer árbol de la figura anterior, el cual indica que b*c es una subexpresión a ser evaluada antes de ejecutar la adición. Sin embargo, esta resolución está completamente fuera de la gramática. Es mejor volver a escribir la gramática de modo que solo un parser sea posible. Al re-escribir esta gramática introducimos nuevas variables, tomando V como {E,T,F,I} y reemplazamos las producciones con E T, T F, F I, E E + T, T T * F, F (E), I a|b|c. Un árbol de derivación de la sentencia a+b*c se muestra en la siguiente figura: 36 Ningún otro árbol de derivación es posible para esta cadena, es decir, la gramática no es ambigua. No hay un procedimiento general para eliminar la ambigüedad en una gramática. 3.4 Propiedades de cerradura de las GLC Las propiedades de cerradura de las GLC son operaciones que se pueden realizar entre ellas, considerando que el resultado será siempre una GLC. Estas propiedades son la unión, concatenación y cerradura de kleen. Teorema. Los LLC son cerrados con respecto a la Unión Concatenación Cerradura de kleene Prueba. Sean L1 y L2 dos LLC generados por las GLC G1 = (V1,T1,S1,P1) y G2 = (V2,T2,S2,P2), respectivamente. Podemos suponer sin pérdida de generalidad que los conjuntos V1 y V2 son disjuntos. 37 Consideremos ahora el lenguaje L(G3), generado por la gramática G3 = (V1 V2 {S3}, T1 T2, S3, P3 ), En donde S3 no está en V1 V2. Las producciones de G3 son todas las producciones de G1 y G2, juntas con un inicio alternativo que nos permite usar alguna de las gramáticas. Es decir, P3 = P1 P2 {S3 S1|S2}. Obviamente G3 es una GLC, de modo que L(G3) es un LLC, pero es fácil ver que L(G3) = L1 L2. Supongamos que w L1. Entonces S3 S1 * w Es una derivación posible en G3. Un argumento similar puede realizarse para w L2. También, si w L(G3) entonces S3 S1, o bien S3 S2 deben ser el primer paso de la derivación. Supongamos que S3 S1 es usado. Debido a que las sentencias derivadas de S1 tienen variables en V1, y V1 y V2 son disjuntos, la derivación S1 * w puede involucrar producciones en P1 únicamente. Aquí w debe estar en L1. Alternativamente si S3 S2 es usado primero, entonces w debe estar en L2 y de aquí se sigue que L(G3) es la unión de L1 y L2. Ahora consideremos G4 = (V1 V2 {s4}, T1 T2, S4,P4). Aquí otra vez S4 es una nueva variable y P4 = P1 P2 {S4 S1S2}. Entonces 38 L(G4) = L(G1)L(G2). Finalmente, consideremos L(G5) con G5 = (V1 {s5}, T1, S5, P5), en donde S5 es una nueva variable y P5 = P1 {S5 S1S2|}. Entonces L(G5) = L(G1)*. Una GLC puede expresarse como una serie de producciones en las que se generan dos no terminales o un terminal, de manera que se eliminan las producciones que generan la cadena vacía y otras mas. Para hacer esto se deben agregar no terminales que generen cada terminal y luego hacer las sustituciones respectivas. Es conveniente que una GLC esté en Forma Normal de Chomski (FNC) para facilitar su uso en el uso de compiladores. Teorema. Si L es un LLC que no contiene la cadena vacía, entonces existe una gramática G tal que L(G)=L y el lado derecho de cualquier regla de reescritura en G consiste en un solo Terminal o exactamente dos No Terminales. 39 3.5 Teorema de Bombeo para Lenguajes Libres de Contexto Una manera para determinar si un lenguaje es libre de contexto es utilizando el Teorema de Bombeo para LLC. Este teorema es análogo al utilizado para lenguajes regulares ya que consta de ciclos en su definición. Básicamente lo que dice es que dado un lenguaje infinito, éste será LC si se puede dividir en 5 partes, dos de las cuales se pueden ciclar indefinidamente y la palabra formada seguirá siendo parte del lenguaje. Sea L un Lenguaje Libre de Contexto que no contiene . Entonces existe un entero k para el cual, si z L y |z|>k, entonces z se puede escribir como z=uvwxy con las propiedades siguientes: 1. |vwx| k 2. al menos o v o x no es 3. uvwxy L para todo i 0 Ejemplo. Mostrar que el lenguaje L = {anbncn contexto. | n0} no es libre de Elegimos el entero m, entonces analizamos la cadena ambmcm, la cual está en L. Si escogemos vxy que contiene únicamente a´s, entonces la cadena bombeada obviamente no estará en L. Si escogemos una cadena que contiene un número igual de a´s que de b´s, entonces la cadena bombeada akbkcm con km puede ser generada, y otra vez hemos generado una cadena que no está en L. De hecho, la única forma en que la cadena puede cumplir es escoger una cadena vxy tal que vy tenga el mismo número de a’s, b’s y c’s. Pero este no es posible de restringir. Ejercicio. Verifica si la gramática L = {ww | w {a,b}*} es libre de contexto. Existen métodos para determinar si una palabra proviene de una gramática; uno de estos métodos es el algoritmo de CYK (Cing, Young, Kasami), que básicamente consiste en la formación de conjuntos de elementos no terminales que se van agregando para decidir al final si el elemento inicial se encuentra. A continuación se presenta el algoritmo de CYK. 40 1. FOR i=1,n Ni,1= {A| AWi1} 2. FOR j=2,n FOR i=1,n-j+1 Ni,J= FOR K=1,J-1 Adicionar a Ni,J los NT A ABC con B Ni,k C Ni+k,J-k 3. Si S Ni,n entonces x L(G) Este algoritmo requiere que se tenga una GLC en FNC. 3.6 Autómatas de Pila Los AF no pueden reconocer a todos los lenguajes libres de contexto, debido a que tienen memorias finitas, mientras que los LLC pueden requerir almacenamiento de una cantidad de información ilimitada. Por ejemplo, en el lenguajes L = {anbn | n0}, debemos revisar el número de a´s que preceden a las b’s. Debido a que n es ilimitado, esta cuenta no puede realizarse con una memoria finita. Queremos una máquina que pueda contar sin límite. Esto sugiere tratar con una pila como un mecanismo de almacenamiento, permitiendo un almacenamiento ilimitado. Esto lo permite una clase de máquinas llamadas Autómatas de Pila (AP). Los autómatas de pila (AP) son autómatas utilizados para representar LLC. Para ello utilizan símbolos de entrada y salida que van usando la pila, tratando de que al final se llegue a la pila vacía, es decir, que se reconozca el lenguaje. Si permitimos que un AP actúe en forma no determinista, conseguiríamos una clase de AP que acepte exactamente la familia de LLC. No existe una equivalencia entre los AP deterministas y no deterministas. Nos enfocaremos a los AP no deterministas. Un Autómata de Pila (AP) es un séxtuplo = (K, , , ,s, F) donde 41 K es un conjunto de identificadores de estados es el alfabeto de entrada es el alfabeto de la pila s K es el estado inicial F K es un conjunto de estados finales (K x *x *) x (K x *)es la relación de transición Si tenemos una transición (p, u, )(q, ) , el AP hace lo siguiente : Estando en el estado p, Consume u de la entrada Saca de la pila Llega a un estado q Mete en la pila PUSH : (p, u, ) (q, ) POP : (p, u, ) (q, ) Una configuración es un elemento de K x *x *. Por ejemplo [q, abbab, #$aa] Sea M=(K, , , ,s, F ) un AP, entonces [p,ux,] M [q,x,] ssi (p,u,)(q,) Un AP acepta una palabra w * ssi [s, w, ] *M [p, , ] donde p F. (p,x,y) en Kxx, existe una y solo una transición en de la forma Hacer los AP para los siguientes lenguajes libres de contexto {wcwR} w {a,b} {wwR} w {a,b} {xmyn | m,n +, mn } {w {a,b}* #a = #b } 42 En esta parte se explicará que existen AP no determinísticos y que son una analogía a los AFN. Se demostrarán algunos teoremas básicos para que se formalice el concepto que tiene de AP. Teorema. Todo lenguaje aceptado por un AF es también aceptado por un AP. Teorema. Si L es un LLC entonces hay un AP M tal que L(M)=L De la construcción del AP descrito anteriormente, concluimos la siguiente proposición: S*w ssi [p,w,] * [q,,] Si L1 y L2 son LLC entonces existe un AP que acepta L1 L2 Definición. UN AP determinista se define como el AP (K,,,,s,F) tal que para cada tripleta (p,x,y) en Kxx, existe una y solo una transición en de la forma (p,u,v;q,z), donde (u,v) { (x,y),(x, ),(,y),(,) }, q K, z Teorema. Si L1 es un LLC y L2 es un LR, entonces L1 L2 es un LLC. El siguiente AP representa el lenguaje L = {wcwI| w {a,b}*} El AP acepta la cadena con w= abcba. Con este capítulo finalizamos el material del curso de Teoría de Lenguajes y Autómatas. Hay temas muy interesantes que no se ven en este curso, pero que son de gran utilidad, entre estos temas tenemos a las Máquinas de Turing, los Autómatas Finitos con Salida y el análisis de 43 la complejidad de los Algoritmos. Estamos listos pues para entrar de lleno a la materia de compiladores, el cual tiene como base esta materia. Solo me queda desearte suerte en el campo de la Teoría Computacional y aconsejarte que hagas muchos ejercicios para dominar los temas. BIBLIOGRAFÍA 44 1. Hopcroftt, John; Ullman Jeffrey. Introduction to Automata Theory languajes, and Computaction. Addison Wesley. 1993. Capítulos 1,2,3,4,5,6,9,10 2. Brena, Ramón. Lenguajes Formales y Autómatas Centro de Inteligencia Artificial, Instituto Tecnológico y de Estudios Superiores de Monterrey, Campus Monterrey. 1997. Capítulos 2,3,4,6,7. 3. Brookshear, J. Glenn. Teoría de la Computación, Lenguajes formales, Autómatas y Complejidad Addison Wesley Iberoamericana. 1993. Capítulos 1,2,3. 4. Sanchez, Jesús; Quintana, Maricela. Material del curso Teoría de la Computación, impartida en el ITESM campus Estado de México. 1998. 5. Martin, J.C. Introduction to Languajes and Theory of Computation McGraw-Hill Series in Computer Science. 1996. 6. Kelley, Dean. Teoría de Autómatas y Lenguajes Formales Prentice-Hall. 1995. 7. Caroll, J. ; Long, D. Theory of finite automata with an introduction Prentice-Hall. 1989 8. Linz, Peter.. An Introduction to Formal Languajes and Automata Jones and Bartlett. 2001 45