View
956
Download
2
Category
Preview:
DESCRIPTION
Un algoritmo sobre la simplificación de gramáticas independientes de contexto
Citation preview
Simplificación de Gramáticas
Independientes de Contexto
• Escaso control sobre las producciones.
• Árboles tupidos
• S → abcdefgS |
abcdefg
• Árboles profundos e inútiles
S → A
A → B
B → C
C → D
D → a | A
Eliminación de terminaes nulas
1. Inicializar N’ con todos los no terminales A para los que A → w, es una producción de G, con w €
’.
2. Inicializar P’ con todas las producciones A → w para las cuales A € N’ y w € ’.
3. Repetir hasta que no se puedan añadir mas no terminales
Añadir a N’ todos los no terminales A para los cuales a → w, para algún w € (N’ U ’) que sea una producción de P y añadirla a P’.
• El bucle del paso 3 es finito.
• Todo no terminal que no aparezca en N’, no formara una subcadena de cualquier cadena final
• Se permiten producciones a la derecha.
• Toma el como una cadena de un terminal, llamadas producciones épsilon.
Ejemplos
Tenemos la siguiente GIC, G:
= { a,b,d}
N = { A, B, C, D, S}
S = S
P=
S → Aa | B | D
A → aA | bA | B
B → b
C → abd
1.- Inicializamos N’ con los no terminales (N) que produzcan (→) un terminal (w) que pertenece a
N’ = { B, C}
2.- Inicializamos P’ con las producciones (P) de N’
P’ =
B → b
C → abd
G:
= { a,b,d}
N = { A, B, C, D, S}
S = S
P=
S → Aa | B | D
A → aA | bA | B
B → b
C → abd
3.- Ahora agregamos a N’ los N que contengan un terminal y/o un miembro de N’
N’ = {B, S, C, A}
Y generamos sus producciones
P’ =
S → Aa|B
A → aA|bA|B
B → b
C → abd
G:
= { a,b,d}
N = { A, B, C, D, S}
S = S
P=
S → Aa | B | D
A → aA | bA | B
B → b
C → abd
El resultado final podríamos escribirlo como G’:
‘ = { a,b,d}
N’ = { A, B, C, S}
S’ = S
P’=
S → Aa | B
A → aA | bA | B
B → b
C → abd
Si nos damos cuenta, el no terminal D se elimino.
Simplifique la GIC G
una GIC cuyas
producciones son:
S → aB
A → bcCCC | dA
B → e
C → fA
D → Dgh
Ejemplos
La respuesta debe
de ser:
S → aB
A → bcCCC | dA
B → e
C → fA
Simplifique la GIC G una GIC cuyas producciones son:
S → aAb | cEB | CE
A → dBE | eeC
B → ff | D
C → gFB | ae
D → h
La respuesta debe
de ser:
S → aAb
A → eeC
B → ff | D
C → ae
D → h
Simplifique la GIC G una GIC cuyas producciones son:
S → a | aA | B | C
A → aB |
B → Aa
C → bCD
D → ccc
La respuesta debe
de ser:
S → a | aA | B
A → aB |
B → Aa
D → ccc
Recommended