formales2

Facultad de Ingeniera de SistemasFacultad de Ingeniera de Sistemas

Lenguajes y Compiladores

Aspectos Formales (Parte 2)

Compiladores2007

1

DerivacionesDerivaciones

El proceso de bsqueda de un rbol sintctico para unacadena se llama anlisis sintctico.

El lenguaje generado por una gramtica es igual alconjunto de cadenas que pueden ser generadas por unrbol sintctico a travs del uso de las producciones deesa gramtica..

Compiladores2007 2

esa gramtica.. Se dice que una gramtica es ambigua si para una

misma frase encontramos dos rboles sintcticosdiferentes. Por ejemplo la gramtica G0 es ambigua yaque para la frase 6 + 9 - 5 podemos graficar dosrboles sintcticos diferentes. (Cules?)

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 smbolo 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 ms a la derecha)

Una gramtica independiente del contexto es no ambigua si ysolo si existe una sola derivacin por la izquierda (o por laderecha) y por ende un solo rbol de anlisis sintctico.

*

DefinicionesDefiniciones

Si:

se dice que X es recursivo.

Si = se dice que es recursivo por la izquierda.

Si la gramtica tiene un smbolo no terminal

X* X

Compiladores2007 4

Si la gramtica tiene un smbolo no terminalrecursivo se dice que la gramtica es recursiva.

La inversa de la derivacin es la reduccin:es equivalente

puede derivarse directamente de o puede reducirse directamente a .

*

Jerarqua de gramticasJerarqua de gramticas

Las gramticas fueron clasificadas deacuerdo a su complejidad, y a esta

Compiladores2007 5

acuerdo a su complejidad, y a estaclasificacin se le conoce con el nombre deJerarqua de Chomsky

Jerarqua de gramticasJerarqua de gramticas

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

Gramtica de un Lenguaje (G)

G = ( N, T, P, S )

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

Definicin de CHOMSKY:

Compiladores2007 7

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

A No Terminal No Terminal[A] No Terminal

T = Vocabulario Terminal. sentencias que pertenecen al lenguaje, se representan con minsculas.

if x then w z

P = Reglas de produccin o Reglas de derivacin.

Definicin de CHOMSKY

Compiladores2007 8

P = Reglas de produccin o Reglas de derivacin.

do while xProduce o deriva.

Axioma Principal.S = Es el axioma principal o smbolo distinguido.

da inicio a las reglas de produccin. pertenece al vocabulario no terminal.

Si se tiene las siguientes reglas:R1 : w x do

R2 : if z then else

R3 : x y z

Definicin de CHOMSKY

Compiladores2007 9

R3 : x y z

R4 : a b c

Donde : N = {, , , }

T = {w, x, do, if }

Definicin Chomsky

G = ( N, T, P, S)

Gramtica.- Se clasifica en 4 tipos.

Tipos de Gramtica

Compiladores2007 10

A. Gramtica Estructura de Base.B. Gramtica Sensible al Contexto.C. Gramtica de Contexto Libre.D. Gramtica Regulares.

Regla de Produccin

A. Gramtica Estructura de Base Tipo 0.- No existe restriccin en las Reglas.

donde : ( N U T )+ ( N U T )*

Tipos de Gramtica

Compiladores2007 11

Ejemplos :

R1 : w x if x then R2 : a b c d aR3 : w a

B. Gramtica Sensible contexto Tipo 1.

donde :(NUT)*

A w

Tipos de Gramtica

Compiladores2007 12

donde : (NUT)* puede ser nulo.W (NUT)+ no puede ser nulo.

A NEjemplos :

R1: w d abcR2: a c

A w

C. Gramtica Tipo 2 contexto Libre.- En la parte izquierda tiene solo un smbolo del vocabulario no termina.

donde : N (NUT)*

Tipos de Gramtica

Compiladores2007 13

N (NUT)*

Ejemplos :R1: w x d R2: i x t R3: s c x R4:

D. Gramtica Regular Tipo 3.- En la parte izquierda y derecha debe existir un No Terminal como mximo

I).Gramticas regulares por la izquierda:

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

Tipos de Gramtica

Compiladores2007 14

si cada produccin P tiene la forma

o bien

donde : N

N*

a T+

a a

Estas gramticas tambin se conocen como regulares o de estado finito.

II). Gramticas regulares por la derecha:

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

Tipos de Gramtica

Compiladores2007 15

cada produccin P tiene la forma.

o bien

donde : N

N*

a T+

a a

En general los lenguajes de programacin no se puedenexpresar totalmente con gramticas regulares, peroestas gramticas si definen la sintaxis de losidentificadores, nmeros, cadenas, etc.

S aS bB bB cC

Tipos de Gramtica

Compiladores2007 16

B cC

C aS

En compiladores interesan las gramticas tipo 2 y 3.

Con las gramticas tipo 2 se puede controlar lapresencia correcta de pares de smbolos como Begin,end o parntesis.

Sin embargo hay caractersticas que no puedenexpresarse a travs de gramticas tipo 2 o 3. Porejemplo, para que la instruccin X := B est correctaes necesario:

X y B estn declarados

X y B sean de tipos compatibles

Tipos de Gramtica

Compiladores2007 17

X y B sean de tipos compatibles

B tenga un valor definido.

Estas caractersticas se verifican con el analizadorsemntico usando la tabla de smbolos.

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 gramtica

va producir siempre que se transforme, cambie o sederive hasta llegar a ser igual a a estos cambios se ledenomina derivacin de longitud.

Lenguaje Definido por una Gramtica

0 1 2 .. n =

Compiladores2007 19

Derivacin de longitud n

cambios

+ Derivacin de Longitud transitiva * incluye el elemento nulo o Tira a Nulo.

0 1 2 .. n =

Definicin de un lenguaje

Un lenguaje definido por una gramtica G estcompuesto por smbolos x, tal que x es la tira desmbolos terminales o sentencia del lenguaje L(G) que

L(G)= { x / * x .and. x T* }


Compiladores2007 20

smbolos terminales o sentencia del lenguaje L(G) quese obtiene al seguir una serie de derivaciones directaspartiendo de

Ejemplo

Un lenguaje tiene las siguientes reglas.

R1: while end

R2: while end

A. Determine si while while end end pertenece al lenguaje

L(G)= {x / * x .and. x T* }

X elemento terminal que se analiza

Solucin. Se parte de L(G)


Compiladores2007 21

Solucin. Se parte de L(G)

R1 while end

xR2 while while end end

while while end end L(G)

Ejercicio

1. Se tienen las siguientes reglas.

R1: a

R2: b

R3: a

R4: a

Compiladores2007 22

R5: b

R6: b

R7: b

R8: a

R9: < B>

Determine si Pertenece L (G)

a) a b a a a b

b) b a a a a b b

Solucin:

R1 : a

XR7 : ab

XR1 : aba

XR8 : abaa

a. Determine si abaaab pertenece L(G)

Compiladores2007 23

XR8 : abaa

XR8 : abaaa

XR6 : abaab

XR9 x R9 : abaaab

abaaab L (G)

Solucin:

xR2: b

xR4: ba

xR1: baa

b. Determine si baaaabb pertenece L(G)

Compiladores2007 24

xR8: baaa

xR8: baaaa

xR6 xR6xR9: baaaabb

baaaabb L (G)

2. Se tienen las siguientes reglas

R1: w

R2: d

R3: w

Ejercicio

Compiladores2007 25

R4: d

a. Reconocer w d d w d

b. Reconocer w w w d d w d d

Solucin:

xR1: w

xR4: wd

xR2: wdd

a. Reconocer wddwd

Compiladores2007 26

xR2: wdd

xR3: wddw

xR2: wddwd

wddwd L(G)

L(G) = {x / * x .and. x T* }

Solucin:

xR1: w

xR3: w w

b. Reconocer wwwddwdd

Compiladores2007 27

xR1: w w w

xR4: w w w d

xR2: w w w dd

xR3: w w wddw

xR2: w w w d d w d

wwwddwdd L(G)

A. Tipos Gramtica.

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 mximo un noterminal en la izquierda y derecha.

a

Resumen

Compiladores2007 29

Acepta como mximo un noterminal en la izquierda y derecha.

B. Lenguaje Reconocido por una Gramtica.

Axioma Principal

a

b

L (G) = { x / * x .and. x T *}

Tcnicas de anlisisTcnicas de anlisis

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

El anlisis sintctico es el proceso de bsqueda de unrbol sintctico correspondiente a una frase.

Normalmente se usan dos mtodos:

Compiladores2007 30

Normalmente se usan dos mtodos:

Anlisis sintctico descendente: parte de la raz ybaja hacia las hojas

Anlisis sintctico ascendente: comienza por las hojase intenta llegar a la raz

Representacin Grfica Arbol Sintctico

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

a b

Tcnicas de anlisisTcnicas de anlisis

Compiladores2007 31

a b

Nudo Ramas (derecha)

nudo

a b Ramas

Anlisis descendenteAnlisis 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 raz

Enn que deriva a Enn Digito.Enn

Enn Digito


Aplicando la misma produccin:

Enn

Enn Digito

Compiladores2007 33

Enn Digito

Con la produccin Enn Digito seguimos construyendo el rbol


Enn Digito

Enn Digito

Enn

Compiladores2007 34

Digito

Con la produccin Digito 1 seguimos construyendo el rbol y obtenemos


Enn

Enn Digito

Enn Digito

Compiladores2007 35

Digito

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

Anlisis ascendenteAnlisis ascendente

Veremos como se realiza el anlisis ascendente para la misma frase 123.

Slo conocemos la raz y la frase.

Con la reduccin 1 Digito obtenemos

Compiladores2007 36

Digito

1 2 3

Con la reduccin Digito Enn llegamos a:


Enn

Digito

1 2 3

Y luego

Compiladores2007 37

Y luegoEnn Digito

Digito

1 2 3


Podemos usar la reduccin Enn Digito EnnEnn

Enn Digito

Compiladores2007 38

Digito

1 2 3Repitiendo el uso de las mismas derivaciones llegamos a obtener:


Enn

Enn Digito

Enn Digito

Compiladores2007 39

Digito

1 2 3

Anlisis sintcticoAnlisis sintctico

En cualquiera de los mtodos usados llegamos a lasolucin porque se tenia conocimiento de la frasecompleta (conocer el programa completo?)

Si no hay un preanlisis se podran tomar decisionescomo (para un anlisis descendente):

Compiladores2007 40

como (para un anlisis descendente):

Enn

Digito

1

Lo que nos llevara a una situacinsin salida (deadlock) ya que llegamosde la hoja a la raz y todava noterminamos de recorrer la frase.

Anlisis sintcticoAnlisis sintctico

Para resolver este problema se definen losconjuntos Primero y Siguiente que permitirnrealizar el anlisis sintctico sin bloqueos mutuos.

La idea bsica es que mirando un nmero 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 sintctico del Pascal y escribala produccin correspondiente.

Deber tener por lo menos: Alternativas ( | ) Una repeticin de elementos ( { } )

Compiladores2007 42

Una repeticin de elementos ( { } ) Un elemento opcional ( [ ] )

1. Se tienen las siguientes reglas.

R1: a

R2: a a

R3: b

EjercicioEjercicio

Compiladores2007 43

R4: b

Reconocer mediante el rbol sintctico

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: do

R2: ;

R3: do

R4: do

Reconocer mediante el rbol sintctico

EjercicioEjercicio

Compiladores2007 44

R4: do

R5: ;

R6: ;

R7: ;

R8: do

R9:

a) do ; do do do ;

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

c) ; do do do ; do do ; do

En un lenguaje, se utilizan ms de un centenar de

reglas Backus Normal Form para describir la

gramtica de un lenguaje por lo que se ha ido

Notacin ampliada de las reglas EBNF

Compiladores2007 45

gramtica 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 smbolo no terminal (N) en la parte izquierda,varias reglas pueden expresarse en una regla.

R1 : a aR2 : b


Variantes

Compiladores2007 46

R2 : b R3 : a aR4 : bR5 :

< 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 smbolo que encierra se repite desde cero hasta un nmero arbitrario de veces

R1 : a


Compiladores2007 47

R1 : a

R2 : b a

R3 : bb {b}5R4 : bbbR5 : bbbbR6 : bbbbb

1

3. Uso de parntesis cuadrados (Corchetes).- Es un caso particular de las llaves.

0[ X ] = { X }1

Se puede usar o no se


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:

R2: + | R3:

Reconocer con el rbol sintctico

1) a*(a+a)

EjercicioEjercicio

Compiladores2007 49

R4: * | R5: ( ) | 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: ( )

R2:

R3: + | Reconocer con el rbol

sintctico

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

EjercicioEjercicio

Compiladores2007 50

R3: + | R4: | a 1) ((a) + (a) + a+a)

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

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

formales2

Documents