Download Parte 3 - Angelfire

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,m0}.
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.
| n0} 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 km 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| AWi1}
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  ABC 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 | n0}, 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 Kxx, 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  +, mn }
{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 Kxx, 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