lenguajes y compiladores aspectos formales (parte...

Facultad de Ingeniería de SistemasFacultad de Ingeniería de Sistemas

Lenguajes y Compiladores

Aspectos Formales (Parte 2)

Compiladores2007

1

DerivacionesDerivaciones

� El proceso de búsqueda de un árbol sintáctico para unacadena se llama análisis sintáctico.

� El lenguaje generado por una gramática es igual alconjunto de cadenas que pueden ser generadas por unárbol sintáctico a través del uso de las producciones deesa gramática..

Compiladores2007 2

esa gramática..� Se dice que una gramática es ambigua si para una

misma frase encontramos dos árboles sintácticosdiferentes. Por ejemplo la gramática G0 es ambigua yaque para la frase 6 + 9 - 5 podemos graficar dosárboles sintácticos diferentes. (¿Cuáles?)

DefinicionesDefiniciones

� Podemos definir un lenguaje L(G) como:

L(G) = {σ | S →* σ y σ ∈ T * }� Producciones libres de contexto: tienen la forma

v → σ con σ ∈ (N ∪ T) *

Expresa que un símbolo no terminal v puede sersustituido por σ sin importar el contexto donde

Compiladores2007 3

sustituido por σ sin importar el contexto dondeaparece v

� Derivaciones por la izquierda (derecha): siempre se reemplazael no terminal mas a la izquierda (o más a la derecha)

� Una gramática independiente del contexto es no ambigua si ysolo si existe una sola derivación por la izquierda (o por laderecha) y por ende un solo árbol de análisis sintáctico.

*

DefinicionesDefiniciones

� Si:

se dice que X es recursivo.

Si α = ε se dice que es recursivo por la izquierda.

“Si la gramática tiene un símbolo no terminal

X→* α X β

Compiladores2007 4

“Si la gramática tiene un símbolo no terminalrecursivo se dice que la gramática es recursiva”.

� La inversa de la derivación es la reducción:es equivalente

β puede derivarse directamente de α o

β puede reducirse directamente a α.

*

β ← αα → β

Jerarquía de gramáticasJerarquía de gramáticas

“Las gramáticas fueron clasificadas deacuerdo a su complejidad, y a esta

Compiladores2007 5

acuerdo a su complejidad, y a estaclasificación se le conoce con el nombre deJerarquía de Chomsky”

Jerarquía de gramáticasJerarquía de gramáticas

Tipo 0 : sin restricciones

Tipo 1 : sensibles al contexto α X β → α γγγγ β

Tipo 2 : independiente del contexto X → α

Tipo 3 : regulares

Compiladores2007 6

Tipo 3 : regulares

A → Ba o A → a oA → aB o A → a

Gramática de un Lenguaje (G)

G = ( N, T, P, S )

Es un cuarteto formado por:N = Vocabulario No Terminal : Son sentencias que no

Definición de CHOMSKY:

Compiladores2007 7

N = Vocabulario No Terminal : Son sentencias que nopertenecen al lenguaje, pueden ser variables ynombre de procedimientos, se representan conletra mayúscula.

A No Terminal<A> No Terminal[A] No Terminal

T = Vocabulario Terminal. sentencias que pertenecen al lenguaje, se representan con minúsculas.

<S> → if x then <B><B> → w z

P = Reglas de producción o Reglas de derivación.

Definición de CHOMSKY

Compiladores2007 8

P = Reglas de producción o Reglas de derivación.

<S> → do <A> while xProduce o deriva.

Axioma Principal.S = Es el axioma principal o símbolo distinguido.

<S> da inicio a las reglas de producción.<S> pertenece al vocabulario no terminal.

Si se tiene las siguientes reglas:R1 : <S> → w x do <A>

R2 : <A> → if z then <B> else <C>

R3 : <B> → x y z

Definición de CHOMSKY

Compiladores2007 9

R3 : <B> → x y z

R4 : <C> → a b c

Donde : N = {<S>, <A>, <B>, <C>}

T = {w, x, do, if …}

Definición Chomsky

G = ( N, T, P, S)

Gramática.- Se clasifica en 4 tipos.

Tipos de Gramática

Compiladores2007 10

A. Gramática Estructura de Base.B. Gramática Sensible al Contexto.C. Gramática de Contexto Libre.D. Gramática Regulares.

α → β Regla de Producción

A. Gramática Estructura de Base Tipo 0.- No existe restricción en las Reglas.

α → β donde : α ∈∈∈∈ ( N U T )+

β ∈∈∈∈ ( N U T )*

Tipos de Gramática

Compiladores2007 11

Ejemplos :

R1 : w x <A> → if x then <B>R2 : a b <S > → c d aR3 : w a <B> → ε

B. Gramática Sensible contexto Tipo 1.

donde :(NUT)*

α →→→→ β

θA ϒ →→→→ θ w ϒ

Tipos de Gramática

Compiladores2007 12

donde :ϒ θ ∈∈∈∈ (NUT)* → puede ser nulo.

W ∈∈∈∈ (NUT)+ → no puede ser nulo.

A ∈∈∈∈ NEjemplos :

R1: w <A> d → abcR2: <A> a → <B>c

θA ϒ →→→→ θ w ϒ

C. Gramática Tipo 2 contexto Libre.- En la parte izquierda tiene solo un símbolo del vocabulario no termina.

donde :α ∈ N β ∈ (NUT)*

Tipos de Gramática

αααα →→→→ ββββ

Compiladores2007 13

N β ∈ (NUT)*

Ejemplos :R1: <S> → w x d <B>R2: <B> → i x t <A>R3: <A> → s c x <c>R4: <C> → λ

D. Gramática Regular Tipo 3.- “En la parte izquierda y derecha debe existir un No Terminal como máximo”

I).Gramáticas regulares por la izquierda:

Se dice que G (T, N, P, S) es regular por la izquierda si cada producción P tiene la forma

Tipos de Gramática

Compiladores2007 14

si cada producción P tiene la forma

o bien

donde : <A> ∈∈∈∈ N

<B> ∈∈∈∈ N*

a ∈∈∈∈ T+

<A> → a <B> <A> → a

“Estas gramáticas también se conocen como regulares o de estado finito”.

II). Gramáticas regulares por la derecha:

Se dice que G (T, N, P, S) es regular por la derecha si cada producción P tiene la forma.

Tipos de Gramática

Compiladores2007 15

cada producción P tiene la forma.

o bien

donde : <A> ∈∈∈∈ N

<B> ∈∈∈∈ N*

a ∈∈∈∈ T+

<A> → <B> a <A> → a

� “En general los lenguajes de programación no se puedenexpresar totalmente con gramáticas regulares, peroestas gramáticas si definen la sintaxis de losidentificadores, números, cadenas, etc”.

S → aS bB b

B → cC

Tipos de Gramática

Compiladores2007 16

B → cC

C → aS

� En compiladores interesan las gramáticas tipo 2 y 3.

� Con las gramáticas tipo 2 se puede controlar lapresencia correcta de pares de símbolos como Begin,end o paréntesis.

� Sin embargo hay características que no puedenexpresarse a través de gramáticas tipo 2 o 3. Porejemplo, para que la instrucción X := B esté correctaes necesario:

� X y B estén declarados

X y B sean de tipos compatibles

Tipos de Gramática

Compiladores2007 17

� X y B sean de tipos compatibles

� B tenga un valor definido.

� Estas características se verifican con el analizadorsemántico usando la tabla de símbolos.

� Ejemplo :

S → abc aAbcAb → bAAc → BbccbB → Bb

EjemploEjemplo

Compiladores2007 18

bB → BbaB → aa aaA

Ejemplo de cadena: ?¿Qué tipo de cadenas genera este lenguaje?

*

En una gramática

α va producir β siempre que se transforme, cambie o sederive hasta llegar a ser igual a β a estos cambios se ledenomina derivación de longitud.

Lenguaje Definido por una Gramática

αααα →→→→ ββββ

α →→→→ ϒ0 →→→→ ϒ1 →→→→ ϒ2 ….. ϒn = β

Compiladores2007 19

Derivación de longitud n

→→→→ cambios

α →→→→ + β Derivación de Longitud transitiva

α →→→→ * β incluye el elemento nulo o Tira a Nulo.

α →→→→ ϒ0 →→→→ ϒ1 →→→→ ϒ2 ….. ϒn = β

Definición de un lenguaje

“Un lenguaje definido por una gramática G estácompuesto por símbolos x, tal que x es la tira desímbolos terminales o sentencia del lenguaje L(G) que

L(G)= { x / <S> →→→→ * x .and. x ∈ T* }

Lenguaje Definido por una Gramática

Compiladores2007 20

símbolos terminales o sentencia del lenguaje L(G) quese obtiene al seguir una serie de derivaciones directaspartiendo de <S>”

Ejemplo

Un lenguaje tiene las siguientes reglas.

R1: <S> → while <A> end

R2: <A> → while end

A. Determine si while while end end pertenece al lenguaje

L(G)= {x / <S> →→→→ * x .and. x ∈ T* }

X elemento terminal que se analiza

Solución. Se parte de L(G)

Lenguaje Definido por una Gramática

Compiladores2007 21

Solución. Se parte de L(G)

R1 <S> → while <A> end

xR2 <S> → while while end end

∴∴∴∴ while while end end ∈∈∈∈ L(G)

Ejercicio

1. Se tienen las siguientes reglas.

R1: <S> → a <B>

R2: <S> → b <A>

R3: <A> → a

R4: <A> → a <S>

Compiladores2007 22

R5: <A> → b <A> <A>

R6: <B> → b

R7: <B> → b <S>

R8: <B> → a <B> <B>

R9: < B> → λ

Determine si Pertenece L (G)

a) a b a a a b

b) b a a a a b b

Solución:

R1 : <S> → a <B>

XR7 : <S> → ab <S>

XR1 : <S> → aba <B>

XR8 : <S> → abaa <B> <B>

a. Determine si abaaab pertenece L(G)

Compiladores2007 23

XR8 : <S> → abaa <B> <B>

XR8 : <S> → abaaa <B> <B> <B>

XR6 : <S> → abaab <B> <B>

XR9 x R9 : <S> → abaaab λ λ

∴ abaaab ∈ L (G)

Solución:

xR2: <S> → b <A>

xR4: <S> → ba <S>

xR1: <S> → baa <B>

b. Determine si baaaabb pertenece L(G)

Compiladores2007 24

xR8: <S> → baaa <B> <B>

xR8: <S> → baaaa <B> <B> <B>

xR6 xR6xR9: <S> → baaaabb λ

∴ baaaabb ∈ L (G)

2. Se tienen las siguientes reglas

R1: <S> → w <A> <S>

R2: <S> → d

R3: <A> → w

Ejercicio

Compiladores2007 25

R4: <A> → d <S> <A>

a. Reconocer w d d w d

b. Reconocer w w w d d w d d

Solución:

xR1: <S> → w <A> <S>

xR4: <S> → wd <S> <A> <S>

xR2: <S> → wdd <A> <S>

a. Reconocer wddwd

Compiladores2007 26

xR2: <S> → wdd <A> <S>

xR3: <S> → wddw <S>

xR2: <S> → wddwd

∴ wddwd ∈ L(G)

L(G) = {x / <S> →→→→ * x .and. x ∈T* }

Solución:

xR1: <S> → w <A> <S>

xR3: <S> → w w <S>

b. Reconocer wwwddwdd

Compiladores2007 27

xR1: <S> → w w w <A> <S>

xR4: <S> → w w w d <A> <S>

xR2: <S> → w w w dd <A> <S>

xR3: <S> → w w wddw <S>

xR2: <S> → w w w d d w d

∴wwwddwdd ∉ L(G)

A. Tipos Gramática.

1. Estructura de Base Tipo 0 :

donde : α ∈∈∈∈ ( N U T )+ β ∈∈∈∈ ( N U T )*

2. Sensible Contexto Tipo 1:

α → β

Resumen

Compiladores2007 28

2. Sensible Contexto Tipo 1:

donde : ϒ θ ∈∈∈∈ (NUT)*

W ∈∈∈∈ (NUT)+

A ∈∈∈∈ N

α → β

θA ϒ →→→→ θ w ϒ

3. Contexto Libre Tipo 2

donde : αααα ∈∈∈∈ N ββββ ∈∈∈∈ (NUT)*

4. Regular Tipo 3

Acepta como máximo un noterminal en la izquierda y derecha.

α → β

<A> → a <B>

Resumen

Compiladores2007 29

Acepta como máximo un noterminal en la izquierda y derecha.

B. Lenguaje Reconocido por una Gramática.

Axioma Principal

<A> → a <B>

<A> → b

L (G) = { x / <S> →→→→ * x .and. x ∈ T *}

Técnicas de análisisTécnicas de análisis

� La tarea de un compilador no es generar frases, uncompilador debe verificar si una frase pertenece allenguaje o no.

� El análisis sintáctico es el proceso de búsqueda de unárbol sintáctico correspondiente a una frase.

Normalmente se usan dos métodos:

Compiladores2007 30

� Normalmente se usan dos métodos:

� Análisis sintáctico descendente: parte de la raíz ybaja hacia las hojas

� Análisis sintáctico ascendente: comienza por las hojase intenta llegar a la raíz

Representación Gráfica – Arbol Sintáctico

Implica usar un árbol ordenado, está formado por un Nudo (Elemento no Terminal parte Izquierda) y por ramas que serán la parte derecha de la regla.

<A> → a <B> b

Técnicas de análisisTécnicas de análisis

Compiladores2007 31

<A> → a <B> b

Nudo Ramas (derecha)

<A> nudo

a <B> b Ramas

Análisis descendenteAnálisis descendente

T = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}N = { Digito, Enn}P = { Enn → Digito | Enn Digito

Digito → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }S =

Compiladores2007 32

S = {Enn}Para analizar la frase 123, se comienza con la raíz

Enn que deriva a Enn Digito.Enn

Enn Digito

Análisis descendenteAnálisis descendente

Aplicando la misma producción:

Enn

Enn Digito

Compiladores2007 33

Enn Digito

Con la producción Enn → Digito seguimos construyendo el árbol

Análisis descendenteAnálisis descendente

Enn Digito

Enn Digito

Enn

Compiladores2007 34

Digito

Con la producción Digito → 1 seguimos construyendo el árbol y obtenemos

Análisis descendenteAnálisis descendente

Enn

Enn Digito

Enn Digito

Compiladores2007 35

Digito

1 2 3

Podemos ver que el árbol crece hacia abajo conforme se valeyendo la frase de izquierda a derecha.

Análisis ascendenteAnálisis ascendente

� Veremos como se realiza el análisis ascendente para la misma frase 123.

� Sólo conocemos la raíz y la frase.

� Con la reducción 1 ← Digito obtenemos

Compiladores2007 36

Digito

1 2 3

� Con la reducción Digito ← Enn llegamos a:

Análisis ascendenteAnálisis ascendente

Enn

Digito

1 2 3

Y luego

Compiladores2007 37

Y luegoEnn Digito

Digito

1 2 3

Análisis ascendenteAnálisis ascendente

Podemos usar la reducción Enn Digito ← Enn

Enn

Enn Digito

Compiladores2007 38

Digito

1 2 3

Repitiendo el uso de las mismas derivaciones llegamos a obtener:

Análisis ascendenteAnálisis ascendente

Enn

Enn Digito

Enn Digito

Compiladores2007 39

Digito

1 2 3

Análisis sintácticoAnálisis sintáctico

� En cualquiera de los métodos usados llegamos a lasolución porque se tenia conocimiento de la frasecompleta (conocer el programa completo?)

� Si no hay un preanálisis se podrían tomar decisionescomo (para un análisis descendente):

Compiladores2007 40

como (para un análisis descendente):

Enn

Digito

1

Lo que nos llevaría a una situaciónsin salida (deadlock) ya que llegamosde la hoja a la raíz y todavía noterminamos de recorrer la frase.

Análisis sintácticoAnálisis sintáctico

� Para resolver este problema se definen losconjuntos Primero y Siguiente que permitiránrealizar el análisis sintáctico sin bloqueos mutuos.

� La idea básica es que mirando un número fijo decaracteres hacia adelante se pueda determinar

Compiladores2007 41

caracteres hacia adelante se pueda determinarexactamente cual es el árbol que corresponde.

TareaTarea

� Seleccione una grafo sintáctico del Pascal y escribala producción correspondiente.

� Deberá tener por lo menos:� Alternativas ( | )� Una repetición de elementos ( { } )

Compiladores2007 42

� Una repetición de elementos ( { } )

� Un elemento opcional ( [ ] )

1. Se tienen las siguientes reglas.

R1: <S> → a

R2: <S> → a <A> a

R3: <A> → b

EjercicioEjercicio

Compiladores2007 43

R4: <A> → b <A>

Reconocer mediante el árbol sintáctico

a) a b b a

b) a b b b b a

c) a a a b b a

2. Se tienen las siguientes Reglas

R1: <S> → do <B>

R2: <S> → ; <A>

R3: <A> → do

R4: <A> → do <S>

Reconocer mediante el árbol sintáctico

EjercicioEjercicio

Compiladores2007 44

R4: <A> → do <S>

R5: <A> → ; <A> <A>

R6: <B> → ;

R7: <B> → ; <S>

R8: <B> → do <B> <B>

R9: <B> → λ

a) do ; do do do ;

b) do; do ; ; ; do do do ;

c) ; do do do ; do do ; do

“En un lenguaje, se utilizan más de un centenar de

reglas “Backus Normal Form” para describir la

gramática de un lenguaje por lo que se ha ido

Notación ampliada de las reglas EBNF

Compiladores2007 45

gramática de un lenguaje por lo que se ha ido

introduciendo simplificaciones o formas compactas

llamadas “Extended Backus Form” “

1. Alternativa de una regla.- Varias reglas tienen elmismo símbolo no terminal (N) en la parte izquierda,varias reglas pueden expresarse en una regla.

R1 : <S> →→→→ a <B> aR2 : <S> →→→→ b <A>

Notación ampliada de las reglas EBNF

Variantes

Compiladores2007 46

R2 : <S> →→→→ b <A>R3 : <S> →→→→ a <S> aR4 : <S> →→→→ bR5 : <S> →→→→ λ

< S > →→→→ a < B > a | b < A > | a < S > a | b | λR1 R2 R3 R4 R5

2. Uso de Llaves.- Las llaves nos indica que el símbolo que encierra se repite desde cero hasta un número arbitrario de veces

R1 : <S> →→→→ <A> a

Notación ampliada de las reglas EBNF

Compiladores2007 47

R1 : <S> <A> a

R2 : <A> →→→→ b <S> →→→→ <A> a

R3 : <A> →→→→ bb <A> →→→→ {b}5R4 : <A> →→→→ bbbR5 : <A> →→→→ bbbbR6 : <A> →→→→ bbbbb

1

3. Uso de paréntesis cuadrados (Corchetes).- Es un caso particular de las llaves.

0[ X ] = { X }1

Se puede usar o no se

Notación ampliada de las reglas EBNF

Compiladores2007 48

< S > →→→→ a < B > c < S > [ b < S > ]Se puede hacer 1 vezo ninguna vez

0

Se puede usar o no sepuede usar

1. Se tiene las siguientes reglas:

R1: <S> → <T> <F>

R2: <F> → + <T> <F> | λλλλ

R3: <T> → <E><L>

Reconocer con el árbol sintáctico

1) a*(a+a)

EjercicioEjercicio

Compiladores2007 49

R4: <L> → * <E><L>| λλλλ

R5: <E> → ( <S> ) | a

1) a*(a+a)

2) (a+a)*a*(a+a)

3) a+a+a+a+(a+a)*a

2. Se tiene las siguientes reglas

R1: <S> →→→→ ( <A> )

R2: <A> → <T> <F>

R3: <F> → + <A> | λλλλ

Reconocer con el árbol sintáctico

1) ((a) + (a) + a+a)

EjercicioEjercicio

Compiladores2007 50

R3: <F> → + <A> | λλλλ

R4: <T> → <S>| a 1) ((a) + (a) + a+a)

2) (a+a+(a)+a+(a))

3) (a+a+a+(a+a)+a)