• Author / Uploaded
• SaulAzul_19

• Categories
• Lenguaje de programación
• Compilador
• Gramática
• Informática teórica
• Informática

Citation preview

Autómatas y Lenguajes - Año 2007 ´ Teor´ıa 4: Lenguajes Libres del Contexto - Gramaticas Libres del Contexto ´ Automatas Push-Down

´ Departamento de Informatica ´ Facultad de Cs. Fco. Matematicas y Naturales

Universidad Nacional de San Luis San Luis - Argentina

´ ˜ 2007– p.1/32 Automatas y Lenguajes - Ano

Lenguajes Tipo 2 o Independientes del contexto La principal característica de este tipo de lenguajes es la de generar cadenas en modalidad espejo, aunque también engloba las características Tipo 3 (L3 ⊂ L2 ). Su importancia radica en que permiten describir los aspectos sintácticos de los lenguajes de programación. Es decir, como debe escribirse correctamente un programa, por lo tanto tienen un rol central en el contexto de compiladores. Sin embargo tienen sus limitaciones desde el punto de vista semántico (declaración y uso de identificadores en Pascal) Ejemplos: Uso de paréntesis en expresiones aritméticas: (3 × x) + (z/(x + y)) Delimitación de bloques a través de begin y end en lenguajes estructurados a bloque (Pascal).

´ ˜ 2007– p.2/32 Automatas y Lenguajes - Ano

Dispositivos descriptores asociados a los lenguajes tipo 2. Generadores: Gramáticas Libres de Contexto (GLC). Reconocedores: Autómatas Push-Down (a pila).

´ ˜ 2007– p.3/32 Automatas y Lenguajes - Ano

Gramáticas Libres de Contexto (GLC) Definición: Una gramática G = (N, Σ, P, S) es libre de contexto, si sus producciones en P tienen la siguiente forma: A → α, con A ∈ N y α ∈ (N ∪ Σ)∗ . Con N , Σ y S somo se definieron en el contexto general de gramáticas. El nombre “libre de contexto” se debe a que cada una de las producciones pueden ser aplicadas independientemente del contexto en donde aparezca un no terminal en una forma sentencial. Ejemplo: Analicemos como construir una GLC para generar expresiones aritméticas que incluyan los símbolos + y ∗ y los identificadores que pueden estar formados por las letras a y b y los números 0 y 1, pero que comienzan con letra:

´ ˜ 2007– p.4/32 Automatas y Lenguajes - Ano

P :

E→I E →E+E E →E∗E E → (E) I →a I →b I → Ia I → Ib I → I0 I → I1

´ ˜ 2007– p.5/32 Automatas y Lenguajes - Ano

Derivaciones en una GLC Las producciones de una gramática se utilizan para inferir que ciertas cadenas están en el lenguaje generado por dicha gramática. Hay dos aproximaciones para esta inferencia: inferencia recursiva, que es una aproximación convencional y las más comúnmente usada denominada derivación, que es con la que trabajaremos en la materia. Como ya vimos, el proceso de derivar cadenas requiere de la definición de la relación deriva ⇒, recordemos: Sean α, β, γ ∈ (Σ ∪ N )∗ y A ∈ N , definimos la relación deriva (⇒) sobre (Σ ∪ N )∗ como sigue: αAβ ⇒ αγβ sii existe A → γ ∈ P Esto significa que αγβ es obtenida a partir de αAβ por la aplicación de la regla o producción A → γ ∈ P.

´ ˜ 2007– p.6/32 Automatas y Lenguajes - Ano

∗

Podemos extender la relación ⇒ (como ya vimos) para representar cero, una o más derivaciones (⇒), tal como extendimos δ, la función de transición de un AF a δ ∗ , lo hacemos de la siguiente manera: ∗

Base: para cualquier cadena α de terminales y no terminales, decimos que α ⇒ α. ∗

∗

Induccción: si α ⇒ β y β ⇒ γ, entonces α ⇒ γ. Ejemplo: Apliquemos esta definición para derivar la cadena b ∗ (b + a00), usando la gramática de las expresiones aritméticas: E ⇒ E ∗ E ⇒ I ∗ E ⇒ b ∗ E ⇒ b ∗ (E) ⇒ b ∗ (E + E) ⇒ b ∗ (I + E) ⇒ b ∗ (b + E) ⇒ b ∗ (b + I) ⇒ b ∗ (b + I0) ⇒ b ∗ (b + I00) ⇒ b ∗ (b + a00)

´ ˜ 2007– p.7/32 Automatas y Lenguajes - Ano

Derivaciones de más a la izquierda y más a la derecha La forma de aplicar las producciones en una secuencia de derivación puede ser arbitraria, en el sentido que cualquier símbolo no terminal de una forma sentencial puede ser escogido para reemplazarlo por su parte derecha. Sin embargo, es posible establecer algún criterio de selección del no terminal a expandir, con la idea de restringir el número de elecciones que se tienen para derivar una cadena. Tales criterios son: Elegir siempre el no terminal de más a la izquierda. Tal derivación se denomina derivación de más ∗

a la izquierda, y se usan las relaciones ⇒lm ⇒lm . Elegir siempre el no terminal de más a la derecha. Tal derivación se denomina derivación de más ∗

a la derecha, y se usan las relaciones ⇒rm ⇒rm .

´ ˜ 2007– p.8/32 Automatas y Lenguajes - Ano

Ejemplo: E ⇒lm E ∗ E ⇒lm I ∗ E ⇒lm b ∗ E ⇒lm b ∗ (E) ⇒lm b ∗ (E + E) ⇒ b ∗ (I + E)lm ⇒lm b ∗ (b + E) ⇒lm b ∗ (b + I) ⇒lm b ∗ (b + I0) ⇒lm b ∗ (b + I00) ⇒lm b ∗ (b + a00) Inferir la misma cadena utilizando derivaciones de más a la derecha. Lenguaje generado por una GLC ∗

El lenguaje generado por una gramática G (denotado L(G)) es: L(G) = {w ∈ Σ∗ /S ⇒ w}.

´ ˜ 2007– p.9/32 Automatas y Lenguajes - Ano

Árbol de derivación o de parser Es un recurso alternativo para mostrar derivaciones en una gramática Tipo 2. Este es un concepto muy importante en el contexto de análisis sintáctico (etapa importante en el proceso de compilación) de lenguajes de programación. Definición: Sea G = (N, Σ, P, S) una GLC, luego un árbol es un Árbol de Derivación para G si: 1. Cada vértice está rotulado por un símbolo de (N ∪ Σ) ∪ {λ}. 2. El rótulo de la raíz del árbol es S, el símbolo distinguido. 3. Si un vértice es un nodo interior con rótulo A, luego A ∈ N . 4. Si n tiene rótulo A y los vértices n1 , n2 , ..., nk son los descendientes de n, de izquierda a derecha, con rótulos X1 , X2 , ..., Xk respectivamente, luego A → X1 X2 ...Xk ∈ P 5. Si el vértice n tiene rótulo λ, luego n es una hoja y es el único descendiente de su padre. (Para las producciones del tipo A → λ).

´ ˜ 2007– p.10/32 Automatas y Lenguajes - Ano

Ejemplo: A partir de la gramática que genera expresiones aritméticas dada previamente y la cadena w = b ∗ (b + a00) obtenemos el siguiente Árbol de Derivación:

E E

*

E

I

(

E

)

b

E

+

E

I

I I

b I

0 0

a

´ ˜ 2007– p.11/32 Automatas y Lenguajes - Ano

´ ´ Frontera de un Arbol de Derivacion.

Dado un Árbol de Derivación para una gramática G. Si los rótulos de las hojas del árbol son leídos de izquierda a derecha, tenemos una forma sentencial. La cadena formada por la concatenación de tales rótulos es denominada frontera del árbol. Por ejemplo, para el árbol previamente mostrado, la frontera es w = b ∗ (b + a00).

´ ˜ 2007– p.12/32 Automatas y Lenguajes - Ano

Ambigüedad. Definición: Una gramática G, libre de contexto es ambigüa si existe al menos una cadena w en L(G) para la cual existe más de un Árbol de Derivación con frontera w. La existencia de esta condición, impediría en principio, implementar un reconocedor determinístico. Teorema 1: para cada gramática G = (N, Σ, P, S) y la cadena w ∈ Σ, w tiene dos árboles de parser distintos sí y sólo sí tiene dos derivaciones de más a la izquierda distintas, partiendo de S.

Ejemplo: conjunto de producciones que generan la construcción if-the-else al estilo del lenguaje ’C’: Introducimos la notación especial para los no terminales usando corchetes angulares para diferenciarlos de los terminales (BNF).

´ ˜ 2007– p.13/32 Automatas y Lenguajes - Ano

hsentenciai →

if(

hexpresioni )hsentenciai

if(hexpresioni)hsentenciai elsehsentenciai

hotrasentenciai

Consideremos la cadena “if ( expr1 ) if ( expr2 ) f() else g()”. Puede comprobarse que para ella existen dos árboles de derivación distintos, dado que es ambigüa la correspondencia de la parte “else” de la sentencia. Es decir, ¿cierra el primer “if” o el segundo?.

´ ˜ 2007– p.14/32 Automatas y Lenguajes - Ano

Removiendo ambigüedad de las gramáticas Así como es posible eliminar estados inaccesibles desde un AF, sería útil poder eliminar la ambigüedad en una gramática de manera algorítmica. Sin embargo, el hecho es que no hay un algoritmo para determinar si una gramática es ambigüa y que a veces resulta imposible eliminar la ambigüedad (gramáticas inherentemente ambigüas). Es decir, no xiste un algoritmo práctico que permita eliminar la ambigüedad en una gramática.

´ ˜ 2007– p.15/32 Automatas y Lenguajes - Ano

Reconocimiento de lenguajes Tipo 2. ¿Cómo podríamos extender el AF para que pueda reconocer lenguajes en modalidad espejo?. Agregamos una Memoria Auxiliar (pila).

...

Cinta

Cabeza Lectora (mov. a derecha implicito)

UC

Pila

Autómata Push-Down (APD)

´ ˜ 2007– p.16/32 Automatas y Lenguajes - Ano

Características del APD: Cinta de entrada de sólo lectura. Pila, acepta lectura y escritura (pop y push). Cabeza lectora, se mueve a derecha (movimiento implícito).

El APD es esencialmente un AFND-ǫ con el agregado de una pila.

´ ˜ 2007– p.17/32 Automatas y Lenguajes - Ano

Autómata Push-Down. ´ Definicion:

Un APD es una 7-upla P = (Q, Σ, Γ, δ, q0 , Z0 , F ), donde:

Q : es el conjunto de estados, Σ : Alfabeto de entrada, Γ : Alfabeto de la Memoria Auxiliar (pila), q0 : el estado inicial, Z0 : símbolo inicial de la pila, F : Conjunto de estados finales (puede ser vacío), ∗

La función de transición es, δ : Q × (Σ ∪ {λ}) × Γ → 2Q×Γ , analicemos el dominio y el rango de esta función:

´ ˜ 2007– p.18/32 Automatas y Lenguajes - Ano

Dominio:

1. Q: estado actual. 2. (Σ ∪ {λ}): símbolo corriente en la entrada. Aquí, λ significa movimiento independiente de la entrada (explicado más adelante). 3. Γ: representa el símbolo corriente en el tope de la pila. O sea que δ toma como argumento una triupla: δ(q, a, X). Rango:

Conjunto de posibles estados (no determinismo) con el correspondiente cambio del símbolo en el tope de la pila. Observe que el tope (un símbolo) puede ser reemplazado por una cadena, incluyendo a la cadena de longitud nula o λ. Es decir que el rango de δ es un conjunto del tipo: {(q, γ)|q ∈ Q ∧ γ ∈ Γ∗ }, si γ = λ entonces se hace pop en la pila. Si γ = Y Z, entonces X es reemplazado por Z e Y es puesto en la pila. Si γ = X, entonces la pila no se modifica.

´ ˜ 2007– p.19/32 Automatas y Lenguajes - Ano

Un APD es por definición no determinístico. Antes de ver un ejemplo, veamos en detalle los tipos de movimientos que un APD puede realizar.

Movimiento Dependiente de la entrada

Tiene en cuenta el símbolo corriente en la cinta de entrada. Luego, una transición de este tipo tendría la siguiente forma: δ(q, a, Z) = {(p1 , γ1 ), (p2 , γ2 ), ..., (pn , γn )} donde q ∈ Q, a ∈ Σ es el símbolo de la entrada, Z ∈ Γ es el tope de la pila y finalmente, pi ∈ Q, γi ∈ Γ∗ con i = 1, 2, ..., n. ¿Cómo se interpreta?

´ ˜ 2007– p.20/32 Automatas y Lenguajes - Ano

Movimiento Independiente de la entrada

No se tiene en cuenta el símbolo corriente en la entrada. δ(q, λ, Z) = {(p1 , γ1 ), (p2 , γ2 ), ..., (pn , γn )} Interpretación: igual a la anterior, excepto que no miramos el símbolo de la entrada para tomar una decisión. ¿Qué pasa cuando γ = λ? - En este caso se reemplaza el tope de la pila por la cadena de longitud nula, es decir se realiza la operación pop sobre la pila. Esto vale para cualquier tipo de movimiento.

´ ˜ 2007– p.21/32 Automatas y Lenguajes - Ano

Ejemplo: Construir un APD P , tal que L(P ) = {0n 12n |n > 1}. Un APD puede ser caracterizado por la especificación completa de la función de transición.

δ(q0 , 0, Z0 ) = {(q1 , 00Z0 )}

δ(q2 , 1, 0) = {(q2 , λ)}

δ(q1 , 0, 0) = {(q1 , 000)}

δ(q2 , λ, Z0 ) = {(q3 , λ)}

δ(q1 , 1, 0) = {(q2 , λ)} Sin embargo, como lo hacíamos con un AF, podemos representar gráficamente cada una de las transiciones y estados del APD.

´ ˜ 2007– p.22/32 Automatas y Lenguajes - Ano

0,0 000

q0

0,Z0 00Z0

q1

1, 0 1,0

q3

q2 λ, Z 0

´ ˜ 2007– p.23/32 Automatas y Lenguajes - Ano

Lenguaje reconocido por un APD. ´ : Configuracion

es una notación especial para describir el estado actual del autómata (una descripción

instantánea). Una configuración de un APD es una triupla (q, w, γ) ∈ Q × Σ∗ × Γ∗ donde: q es el estado actual, w es la cadena remanente en la entrada (aun no analizada), γ es el contenido de la pila, luego, un movimiento de un APD se representa relacionando dos configuraciones de la siguiente manera: (q, aw, Zα) ⊢ (p, w, γα) si δ(q, a, Z) contiene a (p, γ) Estando en el estado q, consumiendo a (el cual puede ser λ) de la entrada, reemplazamos Z por γ y se mueve al estado p.

´ ˜ 2007– p.24/32 Automatas y Lenguajes - Ano

En forma similar a la relación deriva, definimos: i

⊢: movimiento en i pasos. +

⊢: movimiento en uno o más pasos (clausura transitiva). ∗

⊢: movimiento en cero o más pasos (clausura reflexo- transitiva). Configuraciones especiales: Configuración Inicial: (q0 , w, Z0 ) con w ∈ Σ∗ . Configuración Final: (q, λ, α), con q ∈ F y α ∈ Γ∗ . ∗

Una cadena w ∈ Σ∗ es aceptada por un APD P , si (q0 , w, Z0 ) ⊢ (q, λ, α) y q ∈ F . Es decir, partiendo de una configuración inicial y con la aplicación de sucesivos movimientos legales, llegamos a una configuración final.

´ ˜ 2007– p.25/32 Automatas y Lenguajes - Ano

∗

Teorema 2: Si P = (Q, Σ, Γ, δ, q0 , Z0 , F ) es un APD, y (q, x, α) ⊢ (p, y, β), entonces para cualquier cadena w ∈ Σ∗ y γ ∈ Γ∗ , es también verdad que: ∗

(q, xw, αγ) ⊢ (p, yw, β, γ) Lenguaje aceptado por un APD. Existen dos maneras de aceptar un lenguaje. Una es por estado final (forma clásica de un autómata) y la otra, relacionada con un APD, es por pila vacía. A continuación definimos cada una de ellas: Lenguaje aceptado por estado final. ∗

L(P ) = {w ∈ Σ∗ |(q0 , w, Z0 ) ⊢ (p, λ, α), p ∈ F y α ∈ Γ∗ } Lenguaje aceptado por pila vacía. ∗

N (P ) = {w ∈ Σ∗ |(q0 , w, Z0 ) ⊢ (p, λ, λ), p ∈ Q}

´ ˜ 2007– p.26/32 Automatas y Lenguajes - Ano

Se puede demostrar que los lenguajes aceptados por APDs por pila vacía son exactamente los mismos que los aceptados por APDs por estado final. Pila vacía a estado final Mostramos que las clases de lenguajes que son L(P ) para algún APD P es lo mismo que la clase de lenguajes que son N (P ) para algún APD P . Es decir que, mostraremos como a partir de un APD PN que acepta el lenguaje L por pila vacía construímos un APD PF que acepta L por estado final. Teorema 3: si L = N (PN ) para algún APD PN = (Q, Σ, Γ, δN , q0 , Z0 ), entonces hay un APD PF tal que L = L(PF ). Demostración: usamos un nuevo símbolo X0 , que cumple la función de símbolo de comienzo de PF y de marcador sobre el fin de la pila cuando PN llega a pila vacía. Podemos observar en la figura, en la próxima página, cual es la idea de la prueba de este teorema:

´ ˜ 2007– p.27/32 Automatas y Lenguajes - Ano

λ ,X 0 / λ λ ,X 0 / λ

p

λ ,X 0 /Z 0 X 0 0

q0

p

f

λ ,X 0 / λ

λ ,X 0 / λ

También necesitamos un nuevo símbolo de comienzo p0 . Entonces PF simula PN , hasta que la pila de PN está vacía, lo cual PF lo detecta porque ve X0 en el tope. Además necesiat un estado más, pf , el cual es el estado final de PF . La especificación de PF es como sigue: PF = (Q ∪ {p0 , pf }, Σ, Γ, δf , p0 , X0 , {pf }) donde δf se define así:

´ ˜ 2007– p.28/32 Automatas y Lenguajes - Ano

1. δf (p0 , λ, X0 ) = {(q0 , Z0 , X0 )} 2. Para todo estado q ∈ Q, las entradas a ∈ Σ o a = λ, y los símbolos de la pila Y ∈ Γ, δ(q, a, Y ) contiene todos los pares en δN (q, a, Y ). 3. Además de la regla 2., δF (q, λ, X0 ) contiene (pf , λ) para todo estado q ∈ Q. Ahora debemos probar que w ∈ L(PF ) sí y sólo sí w ∈ N (PN ). ∗

(Sí) Tenemos que (q0 , w, Z0 ) ⊢PN (q, λ, λ). ∗

Por teorema 2 podemos insertar X0 y concluímos que (q0 , w, Z0 X0 ) ⊢PN (q, λ, X0 ). ∗

Por la regla 2., PF tiene todos los movimientos de PN , concluímos que (q0 , w, Z0 X0 ) ⊢PF (q, λ, X0 ). Si ponemos todo junto, desde la regal 1. a la 3., tenemos: ∗

(p0 , w, X0 ) ⊢PF (q0 , w, Z0 X0 ) ⊢PF (q, λ, X0 ) ⊢PF (pf , λ, lambda) (3.1) Por lo tanto PF acepta w por estado final.

´ ˜ 2007– p.29/32 Automatas y Lenguajes - Ano

(Sólo Sí) Basta observar las transiciones adicionales de las reglas 1. a 3. Cualquier computación de PF que acepta w debe ser como (3.1). Excepto por el primer y último paso PF no puede usar otras transiciones que no sean también transiciones de PN . Por lo tanto w ∈ N (PN ). Estado final a pila vacía Se puede también demostrar que dado un APD PF que acepta un lenguaje L por estado final, se puede construir otro APD PN que acepta L por pila vacía. Teorema 4: sea L = L(PF ) para algún APD PF = (Q, Σ, Γ, δF , q0 , Z0 , F ), entonces hay un APD PN tal que L = N (PN ). Ver demostración en la bibliografía (página 235).

´ ˜ 2007– p.30/32 Automatas y Lenguajes - Ano

Autómata Push-Down Determinístico ´ Definicion:

Un APD P = (Q, Σ, Γ, δ, q0 , Z0 , F ) es determinístico, si la función de transición satisface las

siguientes restricciones: ∀q ∈ Q ∧ Z ∈ Γ siempre que δ(q, λ, Z) esté definida, luego δ(q, a, Z) está indefinida ∀a ∈ Σ. No permite simultáneamente movimientos independientes y dependientes de la entrada para un mismo q y Z. Para ningún q ∈ Q, Z ∈ Γ, a ∈ (Σ ∪ {λ}); δ(q, a, Z) no contiene más de un elemento. La cardinalidad del conjunto de posibles acciones puede ser uno o cero.

´ ˜ 2007– p.31/32 Automatas y Lenguajes - Ano

Sin embargo, la familia de lenguajes reconocidos por APDs no determinísticos (LAP D−nodet ) no es equivalente a la reconocida por los APD Determinísticos (LAP D−det ). En particular se cumple que LAP D−det ⊂ LAP D−nodet . Veamos esto planteando el siguiente problema: Diseñar un APD Determin´ıstico que reconozca el lenguaje L = {xxt |x ∈ {a, b}∗ }. ¿Es esto posible de realizar? (Ejercicio)

´ ˜ 2007– p.32/32 Automatas y Lenguajes - Ano