Embed Size (px)
Citation preview
Clase 15: GLC’s limpias y bien formadas
Solicitado: Ejercicios 12: GLC’sLimpias y bien formadas
1M. en C. Edgardo Adrián Franco Martínez
http://computacion.cs.cinvestav.mx/~efranco
@efranco_escom
Contenido• Gramáticas limpias y bien formadas
• Reglas no deseadas
• Gramáticas sucias
• Gramáticas bien formadas
• Eliminación de las reglas no generativas
• Eliminación de las reglas de redenominación
• Limpieza de gramáticas
• Algoritmo para detectar símbolos muertos
• Algoritmo para detectar símbolos inaccesibles
• Ejemplo
• Ejercicios 12: GLC’s Limpias y bien formadas
Compiladores (Lenguajes y gramáticas - Edgardo A. Franco)
2
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Gramáticas limpias y bien formadas
• Una gramática limpia y 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 de las reglas de producción de
la gramática, así como su validez. 3
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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→ε, donde S es el símbolo
inicial.
• Sin Reglas de Redenominación: A → B es una
regla de redenominación. 4
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Reglas no deseadas
• 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 con 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 ya
que todas las reglas de A son no generativas.5
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• 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, debido a la existencia del
símbolo B no generativo en el lado derecho de
la producción.
«Identificar las reglas no generativas y de redenominación es
tarea fácil, mientras que ubicar las reglas innecesarias, con
símbolos no generativos o superfluas puede llegar a ser difícil si
el numero de producciones de una gramática es muy grande» 6
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Para identificar las reglas innecesarias, no
generativas o superfluas, puede realizarse la
búsqueda de símbolos llamados muertos e
inaccesibles en la gramática.
• Llamamos símbolo vivo al símbolo no
terminal a partir del cual se puede derivar una
cadena de terminales.
G = ( {a,b}, { S, A, B, C}, S, P)
P: {S → Ab, S → AB, A → Aa|a, B → Bb, C → abA} )
S, A y C son símbolos vivos 7
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Llamamos símbolo muerto a los símbolos no-vivos, no generan una cadena del lenguaje.
G = ( {a,b}, { S, A, B, C}, S, P)P: {S → Ab, S → AB, A → Aa|a, B → Bb, C → abA}
)
B es un símbolo muerto
• Como B es un símbolo muerto, las reglas dondeB aparecen del lado derecho únicamente sonReglas con Símbolos No Generativos.
• Las reglas donde B aparece del lado izquierdo,pasan ha ser Reglas Superfluas de la gramática.
8
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Llamamos símbolo inaccesible si nuncaaparece en la parte derecha de unaproducción.
G = ( {a,b}, { S, A, B, C}, S, P)
P: {S → Ab, S → AB, A → Aa|a, B → Bb, C → abA} )
C es un símbolo inaccesible
• Como C es un símbolo inaccesible, las reglasdonde B aparecen del lado derechoúnicamente son Reglas Innecesarias.
9
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• A las gramáticas que contienen símbolos
muertos e inaccesibles se les llama
gramáticas súcias.
«A las gramáticas que incluyen reglas con símbolos
no generativos, reglas superfluas e innecesarias, se
les conoce como gramáticas sucias»
10
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Gramáticas sucias
• Una gramática está bien formada si es
limpia y además no contiene
producciones A→ λ o A→ B.
«Las gramáticas bien formadas, además de ser
limpias no incluyen reglas no generativas ni reglas de
redenominación»
11
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Gramáticas bien formadas
• Para eliminar reglas no generativas, se
deberá de sustituir las eliminaciones no
generativas por aquellas que dejan la
gramática con el mismo sentido.
12
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
S → a A B | A b
A → c B d | λ
B → c B A
S → a A B | a B | b
A → c B d
B → c B A | cB
Eliminación de las reglas no generativas
• Para eliminar reglas de redenominación,
se deberá de sustituir las reglas de
redenominación por reglas que dejan la
gramática con el mismo sentido
13
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Eliminación de las reglas de redenominación
S → a A B | G | A
A → c B d | Bc
B → bbc | Abb | Ga
G →gAd | g
S → a A B | gAd | g | c B d | Bc
A → c B d | Bc
B → bbc | Abb | Ga
G →gAd | g
• Para realizar la limpieza de una gramática, seconsideran los siguiente principios.
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.
14
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Limpieza de gramáticas
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.
15
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
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.16
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
• Ejemplo: Limpiar y formar de manera correcta la
gramática siguiente:
Ejemplo:
17
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
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
1. Eliminación de reglas no generativas
18
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
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
S → a A B | aA | A | G
A → c B d | cd | H
B → e | f S
C → g D | h D t
D → x | y | z
E → AH | cB | c
F → AB | A | Ga
G → FG
H → Ha | bH | E
2. Eliminación de reglas de redenominación
19
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
S → a A B | aA | A | G
A → c B d | cd | H
B → e | f S
C → g D | h D t
D → x | y | z
E → AH | cB | c
F → AB | A | Ga
G → FG
H → Ha | bH | E
S → a A B | aA | c B d | cd | Ha | bH | AH | cB | c |FG
A → c B d | cd |Ha | bH | AH | cB | c
B → e | f S
C → g D | h D t
D → x | y | z
E → AH | cB | c
F → AB | c B d | cd |Ha | bH | AH | cB | c | Ga
G → FG
H → Ha | bH | AH | cB | c
3. Búsqueda de símbolos muertos
20
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
S → a A B | aA | c B d | cd | Ha | bH | AH | cB | c |FG
A → c B d | cd |Ha | bH | AH | cB | c
B → e | f S
C → g D | h D t
D → x | y | z
E → AH | cB | c
F → AB | c B d | cd |Ha | bH | AH | cB | c | Ga
G → FG
H → Ha | bH | AH | cB | c
Lista inicial {S,A,B,D,E,F,H} Lista final {S,A,B,D,E,F,H,C}
Símbolos fuera de la lista {G}
21
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Símbolos VIVOS Símbolos MUERTOS
B D A C E F H G
El símbolo muerto G aparecen en la parte derecha de
las reglas con símbolos no generativos y las reglas
donde aparecen G del lado izquierdo son reglas
superfluas en la gramática:
Reglas con símbolos no
generativos
S →FG
F →Ga
G→FG
Reglas superfluas
G→FG
4. Eliminación de reglas con símbolos no
generativos y reglas superfluas
22
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
S → a A B | aA | c B d | cd | Ha | bH | AH | cB | c
A → c B d | cd |Ha | bH | AH | cB | c
B → e | f S
C → g D | h D t
D → x | y | z
E → AH | cB | c
F → AB | c B d | cd |Ha | bH | AH | cB | c
H → Ha | bH | AH | cB | c
4. Búsqueda de símbolos inaccesibles
23
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
S → a A B | aA | c B d | cd | Ha | bH | AH | cB | c
A → c B d | cd |Ha | bH | AH | cB | c
B → e | f S
C → g D | h D t
D → x | y | z
E → AH | cB | c
F → AB | c B d | cd |Ha | bH | AH | cB | c
H → Ha | bH | AH | cB | c
Lista inicial {S,A,B,H} Lista final {S,A,B,H}
Símbolos fuera de la lista {C,D,E,F}
24
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
Símbolos ACCESIBLES Símbolos INACCESIBLES
S A B G H E C D F
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:
Reglas innecesarias
C → g D | h D t
D → x | y | z
F → AB | c B d | cd |Ha | bH | AH | cB | c
E → AH | cB | c
• Gramática limpia y bien formada
25
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
S → a A B | aA | c B d | cd | Ha | bH | AH | cB | c
A → c B d | cd |Ha | bH | AH | cB | c
B → e | f S
H → Ha | bH | AH | cB | c
• Realice la limpieza de las siguientes gramáticas:
*Se entregarán antes del día Martes 22 de Octubre de 2013(23:59:59 hora limite)
*Incluir la redacción de cada ejercicio
*Portada y encabezados de pagina
26
Ejercicios 12 “GLC’s limpias y bien formada”
1.-
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
2.-
<S>::= a <B> <A>| <C> | <H>
<A>::= c <G> d |<G>
<B>::= <E> | f <S> | λ
<C>::= g <D>| h <D> t
<D>::= x | y | z |<C>
<E>::= <A><H>| c<B> | λ
<F>::= <A><B> | <G>a
<G>::= <F><G> |G>H>
<H>::= <H>a | <b><H> | <E>
<J>::= <H>a | <B><E> | asa
Teo
ría
co
mp
uta
cio
na
l
Cla
se 1
5:
GLC
'sli
mp
ias
y b
ien
fo
rma
da
s
Pro
f. E
dga
rdo
Ad
riá
n F
ran
co M
art
íne
z
