Lenguajes: árbol de derivación PDF

Preview

Summary

Ejemplificación del mecanismo de derivación de una gramática para obtener el lenguaje correspondiente...

Description

Arbol de Derivación S abc S S S S S S Esta es una gramática libre de contexto: En la parte izquierda de las producciones solo aparece una variable. Al lenguage generado por esta gramática pertenece la palabra a b c . Solo hay que aplicar la siguiente cadena de producciones S a

S S b S

S S S a b c

a

S

S

Modelos de Computación I– p.1/5

Arbol de Derivación

Modelos de Computación I– p.2/5

Construcción Cada nodo del árbol va a contener un símbolo. En el nodo raíz se pone el símbolo inicial S. Se efectúa una ramificación del árbol por cada producción que se aplique: Si a la variable de un nodo, A, se le aplica una determinada regla A , entonces para cada símbolo que aparezca en se añade un hijo con el símbolo correspondiente, situados en el orden de izquierda a derecha. Este proceso se repite para todo paso de la derivación. Si la parte derecha es una cadena vacía, entonces se añade un solo hijo, etiquetado con . En cada momento, leyendo los nodos de izquierda a derecha se lee la palabra generada. Modelos de Computación I– p.3/5

Ejemplo S

aAS

S

a

A

SbA

A

SS

A

ba

La palabra aabbaa tiene asociado el árbol:

Modelos de Computación I– p.4/5

Árboles y Derivaciones Un árbol de derivación puede proceder de dos cadenas de derivación distintas. Se llama derivación por la izquierda asociada a un árbol a aquella en la que siempre se deriva primero la primera variable (más a la izquierda) que aparece en la palabra. Se llama derivación por la derecha asociada a un árbol a aquella en la que siempre se deriva primero la última variable (más a la derecha) que aparece en la palabra.

Modelos de Computación I– p.5/5

Ejemplo Dado el árbol de la palabra aabbaa

Derivación por la izquierda: S aAS aSbAS aabAS aabbaS aabbaa Derivación por la derecha: S aAS aAa aSbAa aSbbaa aabbaa Modelos de Computación I– p.6/5

Gramática Ambigua Una gramática se dice ambigua si existe una palabra con dos árboles de derivación distintos. Ejemplo: La gramática S AA A aSa A a es ambigua, ya que la palabra a tiene los dos árboles siguientes:

Modelos de Computación I– p.7/5

Lenguaje inherentemente ambiguo Un lenguaje de tipo 2 es inherentemente ambiguo si toda gramática que lo genera es ambigua. Ejemplo: El lenguaje generado por la gramática anterior S AA A aSa A a, no es inherentemente ambiguo. Este lenguaje es a i i y puede ser generado por la gramática: S aa S aaU U aaaU U aaa, que no es ambigua. Único árbol para a :

Modelos de Computación I– p.8/5

Ejemplo E

I

E

I

E

E

E

I

I

es ambigua, ya que la palabra a b de derivación distintos:

Eliminando la producción E ser ambigua.

I

abcd c admite dos árboles

E la gramática deja de Modelos de Computación I– p.9/54

Lenguaje inherentemente ambiguo Lenguaje: L an bn cm d m n Gramática:

m

an bm cm d n n

m

S AB A ab A aAb B cd B cBd S aCd C aCd C bDc C bc D bDc D La palabra aabbccdd tiene dos árboles de derivación distintos:

b

Modelos de Computación I– p.10/5

Símbolos y Producciones Inútiles Un símbolo X V T se dice útil si y solo si existe una cadena de derivaciones en G tal que S

X

w

T

Una producción se dice útil si y solo si todos sus símbolos son útiles. Esto es equivalente a que pueda usarse en la derivación de alguna palabra del lenguaje asociado a la gramática. Eliminando todos los símbolos y producciones inútiles el lenguaje generado por la gramática no cambia.

Modelos de Computación I– p.11/5

Algoritmo El algoritmo para eliminar los símbolos y producciones inútiles consta de dos pasos: 1.

Eliminar las variables desde las que no se puede llegar a una palabra de T y las producciones en las que aparezcan.

2.

Eliminar aquellos símbolos que no sean alcanzables desde el símbolo inicial, S, y las producciones en las que estos aparezcan.

Modelos de Computación I– p.12/5

Orden de los algoritmos Es importante aplicar los algoritmos anteriores en el orden especificado. S

AB

S

a

A

a

En el primer paso se elimina B y la producción S AB. Entonces en el segundo se elimina la variable A y la producción A a. Si aplicamos primero el segundo algoritmo, entonces no se elimina nada. Al aplicar despues el primero de los algoritmos se elimina B y la producción S AB. En definitiva, nos queda la gramática S a A a donde todavía nos queda la variable inútil A.

Modelos de Computación I– p.13/5

Primera Parte Se diseña un algoritmo calculando Vt , conjunto de variables que se pueden subtituir por símbolos terminales. Condición Básica: Si A

u

Condición Recursiva: Si A entonces A Vt .

u

T , entonces A k

y cada

j

Vt

está en T Vt ,

1. Vt 2. Para cada producción de la forma A w, A se introduce en Vt . 3. Mientras Vt cambie 4. Para cada producción B 5. Si todas las variables de pertenecen a Vt , B se introduce en Vt 6. Eliminar las variables que esten en V y no en Vt 7. Eliminar todas las producciones donde aparezca una Modelos de Computación I– p.14/54 variable de las eliminadas en el paso anterior

Ejemplo

Vt

S

gAe gAe

S

aY B

S

cY

A

bBY

A

ooC

B

dd

B

D

C

jV B

C

gi

D

n

U

kW

V

baXXX

V

oV

W

c

X

fV

Y

Y hm

BCDWAU S

V

Vt

V XY

S

gAe

A

ooC

B

dd

B

D

C

gi

D

n

U

kW

W

c Modelos de Computación I– p.15/5

Segunda Parte Realizamos una búsqueda recursiva a partir del símbolo inicial S de todos los símbolos que se pueden alcanzar a partir de el. S

aAd

S

fX

b

d

A

C

E

b

A

CEd

VS variables obtenidas TS símbolos terminales obtenid J variables por analizar

S

a

A

f

d

X

Modelos de Computación I– p.16/5

Segunda Parte – VS y J son conjuntos de variables. – TS es un conjunto de símbolos terminales S , TS S , VS 1. J 2. Mientras J 3. Extraer un elemento de J A, (J J A ). 4. Para cada produccion de la forma A 5.Para cada variable B en 6. Si B no est en VS añadir B a J y a VS 7. Poner todos los simbolos terminales de en TS 8. Eliminar todas las variables que no estén en VS y todos los simbolos terminales que no esten en TS . 9. Eliminar todas las producciones donde aparezca un simbolo o variable de los eliminados en el paso anterior Modelos de Computación I– p.17/5

Ejemplo S B D

gAe dd n

VS J TS

A B U

ooC D kW

C W

gi c

S AC SAC geoi

Variable analizada: S A C Única derivación posible: S gAe gooCe googie Lenguaje generado: googie .

Modelos de Computación I– p.18/54

Lenguaje Vacío Si el lenguaje generado por una gramática es vacío, esto se detecta en que la variable S resulta inútil en el primer algoritmo. En ese caso se pueden eliminar directamente todas las producciones, pero no el símbolo S. Ejemplo:

VT

FE

S

aSb

S

E

aDb

F

bcD

S

abc

E

cSE abF

L G Modelos de Computación I– p.19/5

Formas Normales Definen unas características que deben de verificar todas las producciones de una gramática. Producciones nulas Producciones unitarias Forma normal de Chomsky Forma normal de Greibach

Modelos de Computación I– p.20/5

Motivación: el problema de la pertenencia Problema: Dada una gramática independiente del contexto G y una palabra u, ¿pertenece u a L G ? S

Si la palabra es generada, nos sale en esta búsqueda. Si la palabra no es generada, ¿Hasta qué profundidad tenemos que generar para convencernos de que no se puede?

Modelos de Computación I– p.21/54

Producciones Nulas A

.

Algoritmo que dada una gramática G, construye una gramática Gn equivalente a la anterior sin producciones nulas y tal que L Gn . L G Si tenemos, A

D

aABc

D

aABc

aBc

Añadimos D aBc Si B , entonce habría que añadir D

aBc

D

aAc

D

ac Modelos de Computación I– p.22/5

Variables Anulables Si tenemos C AB A B al quitar las producciones nulas C

A

C

B

, habría que añadir,

C

Y después habría que eliminar C Nosotros vamos a calcular desde el principio todas las variables, E, tales que en algún momento aparece E Estas variables se dicen anulables. Son variables tales que E

.

Después vamos a eliminar todas las producciones nulas y a añadir las producciones que compensen esta eliminación. Modelos de Computación I– p.23/5

Algoritmo (I) H es el conjunto de las variables anulables Cálculo de Variables Anulables: 1. H 2. Para cada produccion A A , se hace H H 3. Mientras H cambie 4. Para cada produccion B A A An , donde Ai H para todo i n, se hace H H

B

Modelos de Computación I– p.24/5

Algoritmo (II) Eliminar y Añadir: 1. Se eliminan todas las producciones nulas de la gramatica 2. Para cada produccion de la gramatica de la forma donde i V T . A n 3. Se añaden todas las producciones de la forma A Hy n donde i i si i si H i i i y no todos los i puedan ser nulos al mismo tiempo

Modelos de Computación I– p.25/5

Palabra Vacía Si G generaba inicialmente la palabra nula, entonces la nueva gramática no la genera. Se puede saber si se pierde la palabra vacía comprobando si S H. Si tenemos una gramática G, podemos construir una gramática Gv con una sola producción nula y que genera el mismo lenguaje que G más la palabra vacía. Para ello se añade una nueva variable, S v , que pasa a ser el símbolo inicial de la nueva gramática, Gv . También se añaden dos producciones: Sv

S

Sv Modelos de Computación I– p.26/5

Ejemplo Eliminar las producciones nulas de la siguiente gramática: S B A Cálculo de H

ABb bB

S B C

ABC

C A

abC aA

AB

{A B C S

Al ser S anulable la palabra vacía puede generarse mediante esta gramática.

Modelos de Computación I– p.27/5

Ejemplo: Segunda Parte S A S S B

ABb aA bS AS bB

S C b S A S b A

ABC AB AB S AB BS B aA a

H

C S S S C

abC Ab S Ab AC S AC C S C BC B

B S S C C

bB Bb S BC S ab C AC

ABC S

Modelos de Computación I– p.28/5

Producciones Unitarias A

B

Si queremos eliminar A

V

B, perdemos la posibilidad de A

Para eliminar A A donde B

AB

B

B, añadimos todas las producciones es una producción.

Si tenemos B C introduciríamos una unitaria que habría que eliminar después. Para poder eliminar todas de una vez calculamos, H: conjunto de parejas A B tales que B derivable a partir de A.

Modelos de Computación I– p.29/54

Algoritmo Se supone que no hay transiciones nulas H conjunto de parejas A B tales que B derivable a partir de A. 1. H 2. Para toda produccion de la forma A B, la pareja A B se introduce en H . 3. Mientras H cambie 4. Para cada dos parejas A B B C H 5. Si la pareja A C no esta en H A C se introduce en H 6. Se eliman las producciones unitarias 7. Para cada pareja B A H 8. Para cada produccion A 9. Se añade una produccion B

Modelos de Computación I– p.30/54

Ejemplo (I) S A B Cálculo de H Cálculo de H Cálculo de H

aBc S B A dc SA SA SA

AB AB AB

A A cd B

aAb ccBS

SB

Modelos de Computación I– p.31/5

Ejemplo (II) S B S S

aBc ccBS cdS cd ccBSS ccBS

A B A S

aAb A S dc ccBSA ccBS A dcS dc

H

SA

AB

SB

H

SA

AB

SB

cd aAbS dcA

aAb dc

Modelos de Computación I– p.32/5

El problema de la pertenencia(II) Problema: Dada G sin producciones nulas ni unitarias y u de longitud n, ¿pertenece u a L G ? S

Si la palabra no es generada, ¿Hasta qué profundidad tenemos que generar para convencernos de que no se puede? n (en cada paso o sacamos al menos un nuevo símbolo terminal (n) o aumenta al menos en 1 la longitud (n

))

Modelos de Computación I– p.33/5

Forma Normal de Chomsky Todas las producciones tienen la forma A donde A B C

V, a

BC

A

a

T.

El algoritmo se aplica a gramáticas sin producciones nulas ni unitarias Hay dos operaciones básicas: Eliminar terminales en producciones que no sean A a: B E

aBc aBEd

Ca Cc Cd

a B c E d

Ca BCc Ca BECd

Modelos de Computación I– p.34/5

Bases (2) Eliminar producciones con una longitud en la parte derecha mayor de 2:

A

A

BEFG

BD

D

D

ED

EFG

D

FG

Modelos de Computación I– p.35/5

Algoritmo 1. Para cada producción A n 2. Para cada i , si i es terminal:

i i

a

V T

T n

3. Se añade la produccion Ca a 4. Se cambia i por Ca en A n 5. Para cada produccion de la forma A B Bm m Dm variables D D 6. Se añaden m (distintas para cada produccion) Bm se reemplaza por 7. La produccion A B A B D D B D Dm Bm Bm

Modelos de Computación I– p.36/5

Ejemplo S A

bA S a B

aB A aBB B

S Cb A S Ca B A A a B Ca BB B Ca a Cb b

bAA A bS B

Cb AA A Cb S B

AS b

AS b

Modelos de Computación I– p.37/5

Ejemplo (II) S Cb A S Ca B A A a B Ca BB B A Ca a Cb b

Cb AAA Cb S Cb D

Cb AA A B D

AS b AA

Modelos de Computación I– p.38/5

Ejemplo (II) S Cb A A a Ca a B Ca E

S Ca B B Ca BBB Cb b E BB

Ca BB B A

Cb S Cb D

A B D

A B D

AS b AA

AS b AA

Resultado: S Cb A A a Ca a B Ca E

S Cb E

Ca B b BB

B A

Cb S Cb D

Modelos de Computación I– p.39/5

Forma Normal de Greibach Todas las producciones tienen la forma A

a

a

T

V

Condiciones para aplicar el algoritmo Todas las producciones tienen la forma: – A – A

a

a

T V

V . .

Modelos de Computación I– p.40/5

Dos operaciones básicas: A B B B B Concentramos las dos reglas en una: A Pasamos a: A A B B

B

A B

ELIMINA (A B ) 1. Eliminar A B 2. Para cada produccion B 3. Añadir A Modelos de Computación I– p.41/5

Segunda Operación A

A A

A

A

A

A

A

A A

A A

BA

A

BA

A

Queda:

BA A A BA BA

BA BA

A A BA BA

BA BA

A A BA BA

BA BA

Modelos de Computación I– p.42/54

Segunda Operación: Algoritmo ELIMINA (A) 1. Añadir una nueva variable BA 2. Para cada produccion A A 3. Añadir BA y BA BA 4. Eliminar A A 5. Para cada produccion A , 6. Añadir A BA .

no empieza por A

Modelos de Computación I– p.43/5

Primera parte Objetivo: todas las producciones (Bk variable que se añade al eliminar Ak con ELIMINA (Ak ). – A

a

– Ai

Aj

– Bj

Ai

a

V .

T j

i

V .

V

m 1. Para cada k k 2. Para cada j Aj 3. Para cada produccion Ak 4. ELIMINA (Ak A j ) 5. Si existe alguna produccion de la forma A k 6. ELIMINA (Ak )

Ak

Modelos de Computación I– p.44/5

Segunda parte 1. Para cada i m 2. Para cada produccion de la forma Ai 3. ELIMINA (Ai A j ) 4. Para cada i m 5. Para cada produccion de la forma B j 6. ELIMINA (B j Ai )

Aj

j

i

Ai .

Modelos de Computación I– p.45/5

Ejemplo A

A A

A

A

A A

A A

A

A

a

b

A A Aplicamos ELIMINA a A Se elimina esta producción y se añade: A Queda: A

A A A

A a

A A A

A

A A A

b

A A A

Modelos de Computación I– p.46/5

Ejemplo A

A A A

A a

A A A

A

b

A A A

A A A Aplicamos ELIMINA a A Se elimina esta producción y se añaden: A A A A A A bA A Queda: A A

A A a

A

A

A A

A A A A

A A

b bA A

Modelos de Computación I– p.47/5

Ejemplo A A

A A A A A A

A A

A A bA A

Aplicamos ELIMINA a A Se añade B y las producciones B A A A B A A A B Se elimina A A A A A . Se añaden las producciones: A Queda: A A A

A A bA A bA A B

A B

A A A A A

A B

A

b

aB

A

b A A A B

A

a

bA A B

A A

a aB

Modelos de Computación I– p.48/5

Ejemplo A A A

A A bA A bA A B

A B

A A A A A

A B

b A A A B

A A

a aB

A A Se aplica ELIMINA a A Se elimina esta producción y se añaden: A

aA

A

aB A

A

bA A B A

A

bA A A

Modelos de Computación I– p.49/5

Ejemplo A

A A

A

b

A