3 - Lenguajes Independientes del Contexto y Autómatas de Pilla PDF

Preview

Summary

Tema 3 | Lenguajes Independientes del Contexto y Autómatas de PilaT e o r í a d e l a C o m p u t a c i ó nLENGUAJES INDEPENDIENTES DELCONTEXTO Y AUTÓMATAS DE PILAContenidos: Gramáticas regulares y lenguajes regulares. Gramáticas independientes del context. Árboles de derivación y ambigüedad. Simpli...

Description

Teoría de la Computación

LENGUAJES INDEPENDIENTES DEL CONTEXTO Y AUTÓMATAS DE PILA

Contenidos: 1. Gramáticas regulares y lenguajes regulares. 2. Gramáticas independientes del context. 3. Árboles de derivación y ambigüedad. 4. Simplificación de gramáticas independientes del context. 5. Propiedades de los lenguajes independientes del contexto. 6. Algoritmos de análisis sintáctico. 7. Autómatas de pila. 8. Forma normal de Greibach.

Tema 3 | Lenguajes Independientes del Contexto y Autómatas de Pila

Gramáticas regulares y lenguajes regulares

Nos centraremos ahora en una nueva clase de lenguajes llamados lenguajes independientes del contexto o LIC,s. Esta clase es más amplia que la de los lenguajes regulares y, de hecho, los incluye. Los LIC,s pueden especificarse mediante una notación natural y recursiva denominada gramática independiente del contexto o GIC. Los lenguajes regulares pueden denotarse también mediante un tipo de gramáticas, las gramáticas regulares, que, como veremos, son un caso particular de las GIC,s. Este capítulo introduce también la noción de árbol sintáctico, como representación gráfica de la estructura que la gramática aplica sobre las cadenas de su lenguaje. Veremos también una serie de propiedades específicas de los LIC,s entre las que destaca la posibilidad de resolver el problema de la pertenencia de una cadena de símbolos a un lenguaje de esta clase. Este problema puede abordarse mediante el diseño de algoritmos de análisis sintáctico o mediante el uso de los autómatas de pila o AP,s. Desde el punto de vista práctico, las GIC,s han desempeñado un papel primordial en el desarrollo de los ordenadores desde los años sesenta. Gracias a ellas, la implementación del analizador sintáctico de un compilador dejó de ser una tarea costosa y específica. Actualmente, las GIC,s se usan para la descripción de nuevos lenguajes de programación, de formatos de documentos que aseguran intercambios de información más fiables, o incluso de algunos de los aspectos más comunes de los lenguajes naturales.

Las ER,s y los AF,s permiten especificar lenguajes regulares. Las ER,s constituyen una plantilla o patrón generador de cadenas, mientras que los AF,s constituyen el mecanismo de reconocimiento. Sin embargo, el verdadero formalismo generador viene dado por las gramáticas regulares.

2

Una gramática regular es una colección de cuatro elementos G = (N, Σ, P, S), donde: •

N es un conjunto finito de símbolos no terminales o variables, estos símbolos no van a formar parte del lenguaje generado por la gramática, sino que son símbolos auxiliares que ayudan a definir el lenguaje.

•

Σ es un conjunto finito de símbolos terminales o alfabeto.

•

P es un conjunto finito de producciones o reglas de reescritura de la forma A → w, con A ∈ N y w ∈ (N ∪ Σ)* , pero con las siguientes condiciones: o La cadena w tiene como máximo un símbolo no terminal. o Si w tiene un símbolo no terminal, entonces dicho símbolo es el último de la cadena.

•

S es un símbolo destacado de N, denominado símbolo inicial o axioma de la gramática.

Por ejemplo, consideremos la gramática: G = (N = {S, A}, Σ = {a, b}, P = {S → bA, A → aaA | b | ϵ}, S = S) Las cadenas que forman parte del lenguaje generado por G son aquellas que están compuestas sólo por símbolos terminales y que se pueden obtener desde S aplicando reglas de P. En este caso, se trata de cadenas que comienzan por una b, seguida de un número par de aes, y que terminan con ϵ o con b: S ⇒ bA ⇒ baaA ⇒ baaaaA ⇒ · · · ⇒ baaaa . . . aa o bien baaaa . . . aab Por tanto, esto se puede escribir también como: S ⇒* b(aa)*(b ∪ ϵ)

3

4

Una gramática regular se dice que es: •

bien lineal por la izquierda si las reglas son de la forma A → w B.

•

bien lineal por la derecha si las reglas son de la forma A → B w.

Donde A, B ∈ N y w ∈ Σ+. Ambas definiciones son equivalentes, en el sentido de que se puede pasar de una a otra y viceversa.

5

Gramáticas independientes del contexto

Estas gramáticas a G = (N, Σ, P, S) nos dan libertad absoluta en la parte derecha de la flecha e P ⊆ N × (N ∪ Σ)*, es decir, que las partes derechas de las producciones puedan tener cualquier número de terminales y no terminales y en cualquier orden, eso es lo que se denomina una gramática independiente del contexto o GIC. E igual que antes, un lenguaje independiente del contexto, o LIC, será aquel conjunto de cadenas que se puedan obtener desde el símbolo inicial de la gramática mediante el uso de las reglas de la misma: L(G) = {w ∈ Σ* | S* ⇒ w} Por lo tanto, toda gramática regular es también una GIC y todo lenguaje regular es también un LIC. Y además, los lenguajes regulares están incluidos de manera estricta dentro de los LIC,s ya que existen LIC,s que no son lenguajes regulares. Por ejemplo, la gramática: S → aSb | ϵ Genera {anbn | n ≥ 0} que, como ya hemos visto, no es un lenguaje regular.

6

Árboles de derivación y ambigüedad

Dada la siguiente gramática, partimos del símbolo inicial y vamos aplicando reglas de varias maneras.

Podemos construir la cadena aabbb de varias maneras:

Pero todas ellas tendrán el mismo árbol de derivación.

7

Por tanto, dicho árbol puede verse como una especie de forma canónica de las derivaciones anteriores.

8

El problema de la ambigüedad es muy común en los lenguajes naturales. Por ejemplo, si consideramos aisladamente, es decir, fuera de todo contexto, la frase “Veo un hombre con un telescopio”, no es posible saber si el sintagma preposicional “con un telescopio” está complementando al sujeto o al objeto directo de dicha oración. Y la ambigüedad puede aparecer también en los lenguajes de programación, por ejemplo, con las estructuras if-then-else o con las expresiones aritméticas: A → I := E

I→a|b|c

E → E + E | E ∗ E | (E) | I

Como vemos la primera cadena puede ser ambigua puesto que se pueden construir dos árboles de derivación a partir de la gramática anterior.

En ambos casos es necesario definir más cosas, como por ejemplo las prioridades de los operadores, para eliminar estas ambigüedades, de tal forma que el compilador pueda siempre deducir cuál es el código ejecutable que debe generar.

9

Esto es lo que ocurre, por ejemplo, con el lenguaje {ai bj ck | i = j o bien j = k}. Hay un tipo de árboles que controlan que i = j con cualquier número de ces, y otro tipo de árboles que controlan que j = k con cualquier número de aes. Pero cuando la cadena en cuestión verifique que i = j = k, ambos tipos de árboles serán válidos, lo que implica que el lenguaje es inherentemente ambiguo.

10

Simplificación de gramáticas independientes del contexto

Las GIC,s en FNC son muy estructuradas y producen árboles de derivación siempre binarios. Además, el hecho de que cualquier GIC se pueda poner en FNC permitirá demostrar la existencia de un lema del bombeo para LIC,s y de los algoritmos de análisis sintáctico o parsing. El algoritmo de conversión a FNC es el siguiente. Suponemos G una gramática “limpia” (es decir, sin reglas-ϵ, ni unitarias, ni símbolos inútiles, ni no accesibles) y tal que ϵ ∉ L(G). Por tanto, las reglas son de la forma A → w, donde |w| ≥ 1. Así pues: •

Si |w| = 1, necesariamente w es un terminal y la regla se deja tal cual.

•

Si |w| > 1, entonces la regla es de la forma A → X1 X2 . . . Xn: o Si Xi es un no terminal, no se toca. o Si Xi es el terminal σ, lo cambiamos por un nuevo no terminal C σ y añadimos la regla Cσ → σ. o Por tanto, siempre podemos hacer que A → B1B2 . . . Bn, donde todos los Bi son no terminales. Y ahora, simplemente “binarizamos” la regla: A → B1D1

D1 → B2D2D2 → B3D3 . . .

Dn−2 → Bn−1 Bn

Y si ϵ ∈ L(G), igual que antes, simplemente añadimos la regla S → ϵ.

11

Propiedades de los lenguajes independientes del contexto

A partir de la FNC, introducimos ahora un razonamiento similar al lema del bombeo para los lenguajes regulares, que permitirá, en este caso, demostrar que algunos lenguajes no son LIC,s. Sea una GIC donde N = {S, A, B, C, D}, es decir, |N| = 5. En el camino más largo de un árbol de profundidad 6, habrá 7 símbolos, de los cuales sólo el último es un terminal. Así pues, hay al menos un símbolo no terminal que se repite en dicho camino. En este caso, consideremos, por ejemplo, el símbolo A.

12

La segunda aparición de A define entonces un punto en el que, en lugar de aplicar la reescritura mostrada en la figura para derivar la cadena a bb c b aa, podemos insertar de nuevo el primer subárbol encabezado por A para generar la cadena a bb bb c b b aa. Y además, esta operación de inserción podría repetirse cualquier número de veces, haciendo posible la generación de cualquier cadena de la forma a (bb) i c (b)i aa, donde i ≥ 0.

Ahora veremos un ejemplo de inserción:

13

14

15

16

Propiedades del cierre de los lenguajes independientes del contexto

17

Por tanto, tampoco van a ser cerrados para el complementario, porque la intersección se podría escribir como el complementario de la unión de complementarios:

No obstante, si intersecamos un LIC con un lenguaje regular, el resultado sí es un LIC, tal y como veremos más adelante.

Autómatas de pila

El formalismo algebraico que va a resolver el problema de la pertenencia de cadenas a los lenguajes independientes del contexto, esa estructura teórica es el autómata de pila. Es una estructura muy similar al autómata finito que ya conocemos pero tiene un elemento adicional una pila o stack, que le permitirá hacer una serie de comprobaciones adicionales y por tanto reconocer lenguajes del siguiente escalón de la jerarquía que estamos construyendo, es decir los lenguajes independientes del contexto.

18

Las configuraciones instantáneas serán ahora ternas de la forma (q, w, u), donde q es el estado actual, w es la cadena de símbolos que queda por procesar, y u es el contenido de la pila. Segín esto, el procesamiento de la cadena aabb podría describirse como sigue:

¿Cómo dada una gramática se puede construir un autómata de pila que acepte el lenguaje generado por la gramática?

19

La manera en que lo hace este algoritmo es construyendo siempre un autómata que va a tener 3 Estados (q1, q2, q3), va a haber una transición del q1 a q2 que lo único que hace es apilar el símbolo inicial de la gramática. Después habrá una serie de lazos en q2 algunos dependientes de las reglas de la gramática y otros dependientes de los símbolos no terminales, y finalmente pues va a haber una transición desde q2 etiquetado con épsilon hacia q3 que es el estado de aceptación, siempre y cuando pues volvamos a ver Z encima de la pila.

20

La gramática dada, está produciendo son palíndromos de aes y bes con un punto central c. El autómata de pila que podemos construir mediante el algoritmo anterior, tiene tres estados, la primera transición es siempre la misma (apilar el estado inicial) y la última también es siempre la misma (volver a poner el símbolo de inicio de la pila en la cima de esta). En los ciclos, tenemos un primer grupo de transiciones que dependen de las reglas de la gramática y que dicen que sin consumir nada de la entrada, si vemos un no terminal en la cima de la pila, podemos cambiarlo por las partes derechas de sus posibles reescrituras (aSa, bSb o c). Y después tenemos otro grupo de transiciones que nos dicen que si vemos un terminal en la cadena de entrada y ese mismo terminal en la cima de la pila, podemos desapilarlo. Coloquialmente solemos llamar a estos autómatas, autómatas margarita. Esta es una traza guiada que incluye sólo las configuraciones que llevan a la aceptación, y muestra que el orden de uso de las reglas en la pila es el mismo que en la derivación de la cadena. Si pudiéramos entonces recuperar las operaciones de la pila, obtendríamos la derivación completa. Esto podría hacerse mediante técnicas de programación dinámica. Y, en lugar de hacer backtracking o de explorar las configuraciones en anchura, sería cómodo también mirar la cadena hacia adelante utilizando lo que se denomina un look-ahead para seleccionar las reglas.

El paso inverso, es decir dado un autómata de pila, obtener la gramática independiente del contexto que genera el mismo lenguaje afectado por el autómata. Es un paso que también es posible y que cierra completamente la relación que hay entre los autómatas de pila. Es un paso que no vamos a ver debido a que es demasiado tedioso. El lenguaje que hemos visto anteriormente, los palíndromos de aes y bes con un punto central C, podría ser reconocido por este otro autómata:

21

Básicamente lo que está haciendo es que cada vez que llega una aplica siempre una a grande en la pila, si llega una b pues apila una b grande, si llega a una c no toca nada en la pila y simplemente cambia el estado. Y ahora admite una a pequeña siempre y siempre y cuando haya una a grande en la pila y la desapila, también acepta una b pequeña siempre y cuando haya una b grande en la pila y la desapila. Es decir, lo que está haciendo entonces es aceptar la secuencia inversa de aes y bes que han llegado previamente y si en algún momento no queda ningún símbolo por procesar y volvemos a ver el símbolo de inicio de pila en la cima de la pila entonces podemos aceptar. ¿Cuál es la diferencia entre este autómata y el que hemos visto en la transparencia anterior? La diferencia es que este autómata es determinista.

Sin embargo, si el lenguaje fuera este, palíndromos de aes y bes de longitud par, pero que no tienen ese punto central c, entonces para este otro lenguaje no podríamos construir un autómata de pila determinista esto está relacionado con la existencia de los lenguajes inherentemente ambiguos. ¿Por qué no se puede construir un autómata de pila determinista en este caso? Bueno pues porque cuando llega un símbolo e inmediatamente después llega el mismo símbolo pues yo tengo que prever los dos posibles casos, es decir, que esté en ese momento en el punto de doblaje y tenga que empezar a desapilar o que a lo mejor no estoy todavía en la mitad de la cadena y tengo que apilar ese símbolo y continuar escaneando el resto de la cadena. Por lo tanto, hay que preparar un autómata para que haga estas dos operaciones y por tanto va a ser un autómata no determinista.

Esto quiere decir que los autómatas de pila no deterministas aceptan más lenguajes independientes del contexto que los deterministas, o dicho de otra manera, los autómatas finitos se podían determinizar porque aceptaban los lenguajes, pero los autómatas de pila no se van a poder

22

determinizar, porque los no deterministas reconocen más lenguajes. Hemos alcanzado ya el siguiente grado de clasificación:

Forma normal de Greibach

La forma normal de Greibach es una forma normal en el sentido de que cada gramática independiente del contexto se va a poder escribir el formato que indica esta forma normal.

Obsérvese que la presencia de un símbolo terminal al principio de la parte derecha de cada regla evita la existencia de recursividades por la izquierda y de reglas ϵ (aunque siempre podremos incluir S → ϵ cuando ϵ pertenezca al lenguaje de la gramática). Para transformar cualquier gramática independiente del contexto en una gramática en forma normal de Greibach. Hay que hacer uso de 2 teoremas:

23

Lo que nos dice este teorema es que si tenemos un no terminal a que se puede reescribir de la manera αBγ, con las anteriores reescrituras de B, se podría cambiar por las anteriores. Simplemente es una aplicación directa de reglas.

Este teorema nos proporciona una forma para eliminar las recursividades izquierdas allí donde puedan aparecer. Sin embargo, esto no llega para transformar una GIC a forma normal de Greibach. Tendremos que combinar estos dos teoremas con un método de tres fases, que no veremos.

La forma normal de Greibach es interesante por varias razones: •

En primer lugar, dado que el uso de una producción introduce exactamente un solo símbolo terminal, una cadena de longitud n tiene una derivación de exactamente n pasos.

•

Además, al analizar sintácticamente una cadena, si la gramática correspondiente está en FNG, el parser puede guiarse comparando los símbolos de la cadena con los terminales que encabezan las reescrituras, eliminando así parcial o totalmente el no determinismo inherente a la tarea de análisis sintáctico.

24

•

De igual forma, si se construye un AP a partir de una gramática en FNG, este AP también podrá realizar procesos de reconocimiento guiados, comparando los símbolos de la cadena de entrada con los terminales que encabezan las etiquetas de las transiciones (es lo que se conoce como técnica de look-ahead).

•

Por último, queda garantizado también que dicho AP no tendrá ϵ-transiciones, lo que demuestra que siempre es posible eliminar este tipo de transiciones de cualquier autómata de pila.

25...