escritura de gramática
Post on 08-Jul-2015
350 Views
Preview:
TRANSCRIPT
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 1/26
Escritura deEscritura deuna Gramáticauna Gramática
* 1
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 2/26
RECURSIVIDADRECURSIVIDAD
Concepto,Tipos, Eliminación
27/08/2011 2
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 3/26
RecursividadRecursividad
y La recursividad se define en unaproducción cuando el símbolo de laizquierda se encuentra también a la
derecha de la producción.y Existe recursividad por la izquierda y por
la derecha, dependiendo de la ubicación
del símbolo, ya sea al principio o final dela producción.
27/08/2011 3
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 4/26
RecursividadRecursividad
y Por la Derecha
y Por la izquierda
27/08/2011
ID ::= LETRA ID
Num ::= Num Dígito | Dígito
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 5/26
RecursividadRecursividad
y También se puede encontrarproducciones que tienen ambas clases derecursividad.
y Una gramática se considera recursiva si al
menos una de sus producciones esrecursiva.
27/08/2011
E ::= E + E
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 6/26
Eliminar la Recursividad DirectaEliminar la Recursividad Directa
y Se hace a través del uso de la siguientef orma
y Donde A es el símbolo No terminal conrecursividad por la izquierda
y Donde son la cadenas de símbolos que
siguen después del No terminal Ay Y es es cualquier otra producción
27/08/2011
A A |
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 7/26
Eliminar la Recursividad DirectaEliminar la Recursividad Directa
y Se substituye la f orma
Po
r la definición:
27/08/2011
A A |
A A¶
A¶ A¶ |
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 8/26
Eliminar la Recursividad DirectaEliminar la Recursividad Directa
Eliminando la recursividad por la izquierda
27/08/2011
A A | A
A¶ A¶ A¶ |
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 9/26
Eliminar la Recursividad DirectaEliminar la Recursividad Directa
Si existen más de dos producciones:
y Estratificación:
A
A
1|A
2
| «|A
m
| 1|
2|«|
ny Reescritura:
A 1A¶| 2A¶|«| nA¶
A·
1A¶|
2A¶|«|
mA¶ |
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 10/26
Eliminar la Recursividad IndirectaEliminar la Recursividad Indirecta
La recursividad indirecta se obtiene a travésde varias producciones:
G = (N,T,P,S) es sin producciones y sinciclos G· = (N,T·,P·,S) no recursiva,
con L(G) = L(G·)
27/08/2011
A B | ¶ B C | ¶ C A | ¶
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 11/26
Eliminar la Recursividad IndirectaEliminar la Recursividad Indirecta
Por medio de:For i = 0 to n do
For j = 0 to i-1 do
y substituir AiA j por las produccionesAi 1 | 2 | « | k donde sontodas las producciones actuales de A
y eliminar recursividad directa de Ai
27/08/2011 11
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 12/26
AMBIGÜEDADAMBIGÜEDAD
27/08/2011 12
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 13/26
Gramáticas AmbiguasGramáticas Ambiguas
y Una gramática G(N,T,P,S) se consideraambigua, si existen por lo menos dosárboles de derivación que la representen.
y Una gramática es ambigua si por lo menos posee una producción ambigua.
y La ambigüedad es una propiedad
indecidible
27/08/2011 13
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 14/26
AmbigüedadAmbigüedad
La ambigüedad surge de la derivación deuna cadena a través de una gramática, obteniendo dos o mas derivaciones.
Gexp = (N, {+, *, (, ), 1,«, 9}, P, S)donde P = {E E + E | E * E |1 |«| 9}y Una expresión ambigua: E + E * EObtiene dos derivaciones:y E E + E E + E * Ey E E * E E + E * E
27/08/2011 14
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 15/26
Gramáticas AmbiguasGramáticas Ambiguas
Otro ejemplo de este tipo de gramáticas, donde se reconoce la misma entrada aabb
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 16/26
Eliminar la AmbigüedadEliminar la Ambigüedad
Para eliminar la ambigüedad se puede:
y Establecer precedencia de operadores o asociatividad.
y Transf ormar la gramática
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 17/26
Precedencia de OperadoresPrecedencia de Operadores
Se puede transf ormar la gramáticaagrupando los operadores de igualprecedencia en grupos y asociando a cada
uno una regla, de f orma que los quetengan menor precedencia aparezcan máscercanos al símbolo de inicio, creando una
precedencia en cascada.
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 18/26
Precedencia de OperadoresPrecedencia de Operadores
Por ejemplo la gramática:E num | E + E | E - E | E * E | E / E
exp exp + term | exp - term | term
term term * factor | term / factor | factor
factor ( exp ) | num
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 19/26
Transf ormación de GramáticaTransf ormación de Gramática
y Si no se puede utilizar la precedencia deoperadores, puede transf ormarse lagramática de manera de eliminar la
ambigüedad.y Reestructurando para que al momento
del análisis se tenga una gramática mejor
estructurada.
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 20/26
FACTORIZACIÓNFACTORIZACIÓN
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 21/26
FactorizaciónFactorización
Se debe de factorizar cuando dos o másproducciones poseen un conjunto desímbolos iguales, por lo general por la
izquierda.Cuando se desea hacer el análisis de una
cadena, no se puede determinar cual es la
producción más adecuada para el análisis.
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 22/26
FactorizaciónFactorización
Se pueden reescribir, permitiendo retrasarla selección de una producción hastatener más símbolos de entradas para la
decisión correcta.Este proceso permite evaluar de manera
adecuada una entrada, optimizando el
análisis.
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 23/26
FactorizaciónFactorización
Para factorizar se debe de substituir através del siguiente esquema:
Solo si después de hay un No Terminal y
�
27/08/2011
A
B1| B2
|
A
A¶|
A¶ B1
| B2
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 24/26
FactorizaciónFactorización
Por ejemplo P ¶if · <exp> ¶then· <prop>
| ¶if · <exp> ¶then· <prop> ¶else· <prop>
Se transf orma factorizando por la izq:P ¶if · <exp> ¶then· <prop> P·
P· ¶else· <prop>|
27/08/2011
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 25/26
FIN DE LA PRESENTACIÓNFIN DE LA PRESENTACIÓN
GRACIAS POR SU ATENCIÓN!!GRACIAS POR SU ATENCIÓN!!
INTEGRANTES:INTEGRANTES:
ISAAC BALDEONISAAC BALDEONEDUARDO MORENOEDUARDO MORENO
VERÓNICA GUTIÉRREZVERÓNICA GUTIÉRREZ
MANUEL GARC
IAMANUEL GARC
IA
ANÁLISIS DE COMPILADORESANÁLISIS DE COMPILADORESS7KS7K27/08/2011 25
5/9/2018 Escritura de Gram tica - slidepdf.com
http://slidepdf.com/reader/full/escritura-de-gramatica 26/26
LECCIÓNLECCIÓN
y Con sus propias palabras indique que es unagramática ambigua
y Eliminar la recursión por la izquierda:x E E + T I T
x T T * F I F
x F ( E) I id
y Factorizar lo siguiente:x P iEtP I iEtPeP I a
x E b
27/08/2011
top related