11 gramaticas no ambiguas limpias y bien formadas

11 Gramáticas no ambiguas, limpias y bien formadas Ejercicios 04 "Derivaciones y limpieza de gramáticas"

1 Prof. Edgardo Adrián Franco Martínez http://computacion.cs.cinvestav.mx/~efranco @efranco_escom [email protected]

http://computacion.cs.cinvestav.mx/~efranco

http://twitter.com/intent/user?screen_name=efranco_escom

Contenido • Ambigüedad en gramáticas • Gramáticas limpias y bien formadas

• Algoritmo para detectar símbolos muertos • Algoritmo para detectar símbolos inaccesibles

• Ejemplo de limpieza de gramáticas • Ejercicios 04

Compiladores (Lenguajes y gramáticas - Edgardo A. Franco)

2

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ambigüedad en gramáticas Considérese la gramática:

S → SbS S → ScS S → a

Derivar la palabra abaca

3

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ambigüedad en gramáticas S → SbS | ScS | a

1. S => SbS => SbScS => SbSca => Sbaca => abaca 2. S => ScS => SbScS => abScS => abacS => abaca

S

S S

c a

a

b

S S

a

Derivación 1 S

S S

b a

a

c

S S

a

Derivación 2 Para una misma cadena, se obtuvieron árboles de derivación distintos

4

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ambigüedad en gramáticas • Una gramática es ambigua cuando para una

determinada cadena, se produce más de un árbol de derivación.

5

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

S

S S

c a

a

b

S S

a

S

S S

b a

a

c

S S

a

S → SbS | ScS | a

Ambigüedad en gramáticas (Definición formal)

• Una gramática es ambigua si existe una cadena w ∈ L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más árboles de derivación. • En caso de que toda cadena w ∈ L(G) tenga un único árbol de

derivación, la gramática es no ambigua.

• P.g: La gramática S → aS | Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda

S ⇒ aS ⇒ aa S ⇒ Sa ⇒ aa

S

a S

a

S

S a

a

6

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ambigüedad en gramáticas • Una gramática que refleja mejor el problema de

ambigüedad es la que valida expresiones aritméticas sobre id y num.

7

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ambigüedad en gramáticas • En la gramática para expresiones aritméticas sobre id y num:

• E → E + E • E → E ∗ E • E → id • E → num • E → -E • E → (E)

• Es ambigua porque la cadena id + num ∗ id tiene dos árboles de derivación:

• Árbol izquierdo representa (id + num) ∗ id • Árbol de la derecha representa id + (num ∗ id).

E

E E ∗

id + num id

E

E E +

num * id id

8

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

La ambigüedad puede producir serios problemas en lenguajes cuyo significado depende, en parte, de su estructura, como es el caso de los lenguajes naturales y los de programación.

Ambigüedad en gramáticas (Eliminación)

• Eliminar la ambigüedad en una gramática requiere de un proceso de análisis propio de cada gramática que verifique que para ninguna palabra que esta genera se puedan generar más de un árbol de derivación.

• En algunos casos, la ambigüedad de una gramática se puede eliminar utilizando nuevas variables que eliminen los árboles de derivación no deseados.

• También existen los lenguajes inherentemente ambiguos para los que no existe una gramática no ambigua equivalente.

9

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ambigüedad en gramáticas (Eliminación)

• En el ejemplo de los operadores aritméticos, además de la variable E, que representa expresiones, también se utilizan las variables F para factores y T para términos y se tienen las siguientes reglas:

• E → E + T E → T • T → T * F T → F • F → (E) T → -F • F → id F → num

10

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Gramáticas limpias y bien formadas

• Una gramática bien formada facilita el correcto tratamiento y detección a la hora de ser impuesta en algún lenguaje.

• Para poder construir una gramática adecuada se debe verificar la correcta escritura y reglas de producción de la gramática. 11

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez


• Sin Reglas Innecesarias: A → b, es una regla innecesaria si A no hace parte del lado derecho de otra regla. A es un símbolo inaccesible.

• Sin Reglas Superfluas: Dada la gramática G = ( {a,b}, { S, A, B}, S, {S → AB, A → Aa|a, B → Bb} ), la regla B →Bb es superflua porque no puede derivar una cadena que solo contenga símbolos terminales.

12

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez


• Sin Símbolos No Generativos: Dada la gramática G= (N, Σ, S, P), para cada símbolo A de N se construye la gramática G(A)=(NA, ΣA, A, PA), si L(G(A)) es vacío, entonces A es un símbolo no generativo.

13

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez


• Sin Reglas No Generativas: U → ε, es una regla no generativa. Si el lenguaje representado por la gramática no contiene la palabra vacía es posible eliminar todas las reglas no generativas, de lo contrario se debe admitir la regla S→ε.

• Sin Reglas de Redenominación: A → B es una regla de redenominación.

14

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez


• Llamamos símbolo vivo al símbolo a partir del cual se puede derivar una cadena de terminales. Llamamos símbolo muerto a los símbolos no-vivos, no generan una cadena del lenguaje. Llamamos símbolo inaccesible si nunca aparece en la parte derecha de una producción. A las gramáticas que contienen estos tipos de símbolos se les llama gramáticas súcias. 15

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez


• Teorema 1: si todos los símbolos de la parte derecha de una producción son símbolos vivos, entonces el símbolo de la parte izquierda también lo es.

• Teorema 2: si el símbolo no-terminal de la parte izquierda de una producción es accesible, entonces todos los símbolos de la parte derecha también lo son. 16

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez


• Para limpiar una gramática primero se eliminan los símbolos muertos y después los símbolos inaccesibles.

• Una gramática está bien formada si es limpia y además no contiene producciones →

17

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

ε

Algoritmo para detectar símbolos muertos

1. Hacer una lista de no-terminales que tengan al menos una producción con sólo símbolos terminales en la parte derecha.

2. Dada una producción, si todos los no-terminales de la parte derecha pertenecen a la lista, entonces podemos incluir en la lista al no-terminal de la parte izquierda de la producción.

3. Cuando ya no se puedan incluir más símbolos en la lista mediante la aplicación del paso 2, la lista contendrá los símbolos no-terminales vivos y el resto serán símbolos muertos.

18

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Algoritmo para detectar símbolos inaccesibles

1. Se inicializa una lista de no-terminales que sabemos que son accesibles con el axioma.

2. Si la parte izquierda de una producción está en la lista, entonces se incluye en la misma al no-terminal que aparece en la parte derecha de la producción.

3. Cuando ya no se pueden incluir más símbolos a la lista mediante la aplicación del paso 2, entonces la lista contendrá todos los símbolos accesibles y el resto de los no-terminales serán inaccesibles.

19

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ejemplo de limpieza de gramáticas • Ejemplo: limpiar la gramática

20

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

S → a A B | A | G A → c B d | H B → e | f S C → g D | h D t D → x | y | z E → AH | cB F → AB | Ga G → FG H → Ha | bH | E

Ejemplo de limpieza de gramáticas

21

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Símbolos VIVOS

Símbolos MUERTOS

B D A C E F H G

Los símbolos muertos aparecen en la parte derecha de las reglas superfluas lo que indica que las siguientes reglas son superfluas en la gramática: S →G F →Ga G →FG

Ejemplo de limpieza de gramáticas

22

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Símbolos ACCESIBLES

Símbolos INACCESIBLES

S A B G H F E C D

Los símbolos inaccesibles aparecen en la parte izquierda de las reglas innecesarias lo que indica que las siguientes reglas son innecesarias en la gramática: C → g D C → h D t D → x D → y D → z

Ejemplo de limpieza de gramáticas • Gramática limpia

23

Teor

ía co

mpu

taci

onal

11

Gra

mát

icas

no

ambi

guas

, lim

pias

y b

ien

form

adas

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

S → a A B | A A → c B d | H B → e | f S E → AH | cB F → AB H → Ha | bH | E

Ejercicios 04 "Derivaciones y limpieza de gramáticas" 1. Considere la siguiente gramática:

y la cadena a) Proporcione una derivación por la izquierda para la

cadena b) Proporcione una derivación por la derecha para la

cadena c) Proporcione un árbol de derivación para la cadena d) ¿La gramática es ambigua o no? Justifique su

respuesta

24

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

*aaa +aSSSSS |*|+→





respuesta

25

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

01|10SS →

000111





respuesta

26

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

ε|)( SSSS →(()())





respuesta

27

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

aaa *)( +

aSSSSSSS |*|)(||+→





respuesta

28

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

ε|| bSaSaSbSS →

aabbab

Ejercicios 04 "Derivaciones y limpieza de gramáticas" • Diseñe gramáticas para los siguientes lenguajes: 6. El conjunto de todas las cadenas de 0’s y 1’s , de

tal forma que justo antes de cada 0 vaya por lo menos un 1.

7. El conjunto de todas las cadenas de 0’s y 1’s que sean palíndromos; es decir, que la cadena se lea igual al derecho y al revés.

8. El conjunto de todas las cadenas de 0’s y 1’s en donde 011 no aparece como subcadena.

29

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Ejercicios 04 "Derivaciones y limpieza de gramáticas" • Realice la limpieza de las siguientes gramáticas

30

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

9. . E → a F B | F | C | D a A → g D | h D t B → e | F e | J C → C b| G b| J e a c D → x | y| z| J a F → c G d | C a G → R e a | e a R M → c F a | a B a N → M e a | J a c | N a R → C e

10. . <S>:: a <A>| <C> | <H> <A>:: c <G> d |<G> :: <E> | f <S> <C>:: g <D>| h <D> t <D>:: x | y | z |<C> <E>:: <A><H>| c <F>:: <A> | <G>a <G>:: <F><G> |G>H> <H>:: <H>a | <H> | <E> <J>:: <H>a | <E> | asa

Ejercicios 04 • La fecha máxima de entrega de los ejercicios

es el viernes 04 de mayo de 2012 a las 23:59:59 horas, vía web. (Ejercicios Individuales)

• El documento incluirá portada, la redacción y respuesta en

formato digital de los ejercicios (no escaneados).

• Se deberá de incluir encabezados en cada página.

• Enviar con el nombre: Ejercicios04_NombreAlumno.*

• Se deberán de describir todos los procedimientos

necesarios

31

Teor

ía co

mpu

taci

onal

09

Con

vers

ión

de A

FN a

AFD

Pr

of. E

dgar

do A

driá

n Fr

anco

Mar

tínez

Grupo Contraseña 2CM1 teoria2cm1

2CM4 teoria2cm4

2CM5 teoria2cm5

11 gramaticas no ambiguas limpias y bien formadas

Documents