TEMA 5.Anlisis semntico y
generacin de cdigo intermedio
Traduccin dirigida por la sintaxis. Comprobacin de tipos. Lenguajes Intermedios.
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I. - Diap. 1
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 2
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Autmata a pilao
Gramtica independientedel contexto
Acciones semnticas
+
Traductordirigido por
sintaxis
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 3
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Notaciones: Definicin dirigida por la sintaxis (DDS). Esquema de traduccin (EDT).
Evaluacin de una accin: Generacin de cdigo. Guardar/Consultar informacin en la TS. Notificacin de mensajes de error.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 4
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Cada smbolo tiene un conjunto de atributosasociados. Referencia a un atributo de un smbolo:
NombreSmbolo.NombreAtributo Cada produccin A::= tiene asociadas un conjunto de acciones semnticas.
X.atr = f(Y1.atr, ..., Yn.atr)
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 5
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Tipos de atributos: Sintetizados. Su valor se calcula en funcin de atributos de nodos hijosEjemplo:
L ::= E\nE ::= E+T | TT ::= T*F | FF ::= (E) | cte
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 6
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Tipos de atributos: Heredados. Su valor se calcula en funcin de atributos de nodos hermanos y/o padreEjemplo:
D ::= TLT ::= entero | real | boolL ::= L , id | id
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 7
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Orden de evaluacin:Para cualquier accin semntica de la forma:
X.atr = f(Y1.atr, ..., Yn.atr)Los valores de los atributos Y1.atr, ..., Yn.atrdeben estar disponibles antes de ejecutarlaMtodos de ordenacin:
Con rbol sintctico: compilacin Basados en reglas: desarrollo
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 8
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Definicin dirigida por la sintaxis
Evaluacin ascendente de DDS con atributos sintetizados:
Slo existen atributos sintetizados Utiliza analizadores LR Valores de atributos sintetizados dnde?
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 9
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Esquemas de traduccin
Cada smbolo tiene un conjunto de atributosasociados. Referencia a un atributo de un smbolo:
NombreSmbolo.NombreAtributo Las acciones semnticas se encuentran intercaladas con los smbolos del consecuente
X ::= ab{accion();}b Orden de evaluacin fijo: profundidad
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 10
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Esquemas de traduccin
EDT slo con atributos sintetizados Acciones al final de la produccin
EDT con atributos sintetizados y heredados Atributos heredados de un smbolo del consecuente Atributos sintetizados utilizados en acciones Atributos sintetizados del antecedente
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 11
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Esquemas de traduccinEjemplo 1:S ::= A1A2{A1.h = 1; A2.h = 2;}A ::= a {imprime(A.h);}
Ejemplo 2:S ::= TLT ::= real | boolL ::= id | id, L
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 12
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
Utilizacin de analizadores descendentes.
Utilizacin de esquemas de traduccin.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 13
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
Eliminacin de la recursividad por la izquierda.
L ::= E\n{imprime(E.v)}E ::= E1+T {E.v = E1.v+T.v}E ::= E1-T {E.v = E1.v-T.v}E ::= T {E.v = T.v}T ::= (E) {T.v = E.v}T ::= cte {T.v = cte.valex}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 14
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 15
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
GramticaA ::= XRR ::= YR1R ::=
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 16
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
GramticaA ::= XRR ::= YR1R ::=
EDTA ::= X{R.h=f(X.x)}R
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 17
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
GramticaA ::= XRR ::= YR1R ::=
EDTA ::= X{R.h=f(X.x)}RR ::= Y{R1.h=g(R.h, Y.y)}R1
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 18
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
GramticaA ::= XRR ::= YR1R ::=
EDTA ::= X{R.h=f(X.x)}RR ::= Y{R1.h=g(R.h, Y.y)}R1R ::= {R.s=R.h}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 19
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
GramticaA ::= XRR ::= YR1R ::=
EDTA ::= X{R.h=f(X.x)}RR ::= Y{R1.h=g(R.h,Y.y)}
R1{R.s= R1.s}R ::= {R.s=R.h}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 20
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteGeneralizacin de la eliminacin de la recursividad por la izquierda.
A ::= A1Y {A.a = g(A1.a, Y.y)}A ::= X {A.a = f(X.x)}
GramticaA ::= XRR ::= YR1R ::=
EDTA ::= X{R.h=f(X.x)}R{A.a=R.s}R ::= Y{R1.h=g(R.h,Y.y)}
R1{R.s= R1.s}R ::= {R.s=R.h}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 21
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
Ejercicio: Eliminar de la recursividad a izquierdas.L ::= E\n{imprime(E.v)}E ::= E1+T {E.v = E1.v+T.v}E ::= E1-T {E.v = E1.v-T.v}E ::= T {E.v = T.v}T ::= (E) {T.v = E.v}T ::= cte {T.v = cte.valex}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 22
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteConstruccin de traductores recursivos
Similar los analizadores descendentes recursivos:
Sintetizados de NT = Heredados de NT = At.Terminales = Acciones semnticas =
Valor devuelto funcin NT.Parmetro de la funcin NT.Variable para su valor.Sentencias de cdigo.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 23
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
S ::= aBbB ::= aBb | c
void S(void){
cmp(a);B();cmp(b);
}
void B(void){
if(entrada == a){cmp(a);B();cmp(b);
} else if(entrada == c)
cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 24
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
S ::= {B.h=1;}aBb{imprime(B.s);}B ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 25
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
S ::= {B.h=1;}aBb{imprime(B.s);}
void S(void){
cmp(a);B();cmp(b);}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 26
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
S ::= {B.h=1;}aBb{imprime(B.s);}void S(void){
int B_h;B_h=1;cmp(a);B();cmp(b);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 27
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteS ::= {B.h=1;}aBb{imprime(B.s);}B ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}void S(void){
int B_h;B_h=1; cmp(a);B();cmp(b);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 28
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteS ::= {B.h=1;}aBb{imprime(B.s);}B ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}void S(void){
int B_h;B_h=1; cmp(a);B(B_h);cmp(b);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 29
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
void B(int B_h){
if(entrada == a){cmp(a);B();cmp(b);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 30
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
void B(int B_h){
if(entrada == a){cmp(a);B();cmp(b);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 31
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
void B(int B_h){
int B1_h;if(entrada == a){
cmp(a);B(B1_h);cmp(b);} else if(entrada == c) cmp(c);
else error();}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 32
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
void B(int B_h){
int B1_h;if(entrada == a){
cmp(a); B1_h=B_h+1;B(B1_h);cmp(b);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 33
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
void B(int B_h){
int B1_h;if(entrada == a){
cmp(a); B1_h=B_h+1;B(B1_h);cmp(b);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 34
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
int B(int B_h){
int B1_h;if(entrada == a){
cmp(a); B1_h=B_h+1;B(B1_h);cmp(b);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 35
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
int B(int B_h){
int B1_h, B1_s;if(entrada == a){
cmp(a); B1_h=B_h+1;B1_s=B(B1_h);cmp(b);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 36
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
int B(int B_h){
int B1_h, B1_s;if(entrada == a){
cmp(a); B1_h=B_h+1;B1_s=B(B1_h);cmp(b);return(B1_s);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 37
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}
int B(int B_h){
int B1_h, B1_s;if(entrada == a){
cmp(a); B1_h=B_h+1;B1_s=B(B1_h);cmp(b);return(B1_s);
} else if(entrada == c) cmp(c);else error();
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 38
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}int B(int B_h){
int B1_h, B1_s, c_lex;if(entrada == a){
cmp(a); B1_h=B_h+1;B1_s=B(B1_h);cmp(b);return(B1_s);
} else if(entrada == c){ cmp(c);return(B_h*c_lex);
} else error();}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 39
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteS ::= {B.h=1;}aBb{imprime(B.s);}B ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}void S(void){
int B_h;B_h=1; cmp(a);B(B_h);cmp(b);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 40
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteS ::= {B.h=1;}aBb{imprime(B.s);}B ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}void S(void){
int B_h, B_s;B_h=1; cmp(a);B_s=B(B_h);cmp(b);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 41
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteS ::= {B.h=1;}aBb{imprime(B.s);}B ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}void S(void){
int B_h, B_s;B_h=1; cmp(a);B_s=B(B_h);cmp(b);imprime(B_s);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 42
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteS ::= {B.h=1;}aBb{imprime(B.s);}
void S(void){
int B_h, B_s;B_h=1; cmp(a);B_s=B(B_h);cmp(b);imprime(B.s);
}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 43
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendenteB ::= a{B1.h=B.h+1;}B1{B.s=B1.s}b |
c{B.s=B.h*c.lex;}int B(int B_h){
int B1_h, B1_s, c_lex;if(entrada == a){
cmp(a); B1_h=B_h+1;B1_s=B(B1_h);cmp(b);return(B1_s);
} else if(entrada == c){ cmp(c);return(B_h*c_lex);
} else error();}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 44
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin descendente
L ::= E\n {imprime(E.v);}E ::= T {R.h=T.v;} R {E.v=R.v;}R ::= +T {R1.h=R.h+T.v;} R1 {R.v=R1.v;}R ::= -T {R1.h=R.h-T.v;} R1 {R.v=R1.v;}R ::= {R.v=R.h;}T ::= (E) {T.v=E.v;}T ::= cte {T.v=cte.valex;}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 45
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendente
Utilizacin de analizadores ascendentes.Funcionamiento por reducciones.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 46
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendente
Utilizacin de analizadores ascendentes.Funcionamiento por reducciones.Problemas:
- Todas LL(1) y no todas LR(1).- Tratamiento de atributos heredados.- Acciones intercaladas en consecuentes.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 47
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendente
Acciones intercaladas en el consecuente. Pasar acciones al final de un consecuente. Convertir toda produccin de la forma:A ::= {accion();}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 48
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendente
Acciones intercaladas en el consecuente. Pasar acciones al final de un consecuente. Convertir toda produccin de la forma:A ::= {accion();}
En otras dos de la forma:A ::= XX ::= {accion();}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 49
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendenteTratamiento de atributos heredados.
Las definiciones utilizadas son:con atributos por la izquierda.
Se utiliza la idea de la pila de atributos. El smbolo del que se hereda el atributo se encuentra en la pila.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 50
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendenteTratamiento de atributos heredados.
Ejemplo: bool id, idD ::= T {L.h=T.t;} LT ::= real {T.t=r;}T ::= bool {T.t=b;}L ::= id {aadetipo(id.ent, L.h);}L ::= {L1.h=L.h;} L1,id
{aadetipo(id.ent, L.h);}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 51
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendenteTratamiento de atributos heredados.
Problema: Localizar el smbolo del que se hereda Ejemplo:
S ::= aAC {C.h=A.s;}S ::= bABC {C.h=A.s;}C ::= c {C.s=f(C.h);}
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 52
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendenteTratamiento de atributos heredados.
Problema: Localizar el smbolo del que se hereda Ejemplo:
S ::= aAC {C.h=A.s;}S ::= bABC {C.h=A.s;}C ::= c {C.s=f(C.h);}
Conseguir que A y C estn siempre a la misma distancia, mediante la insercin de no terminales.
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 53
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendenteTratamiento de atributos heredados.
Problema: Localizar el smbolo del que se hereda Ejemplo:
S ::= aAC {C.h=A.s;}S ::= bABC {C.h=A.s;}C ::= c {C.s=f(C.h);}
Conseguir que el valor de A.s y C estn siempre a la misma distancia...
Traduccin dirigida por sintaxisPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 54
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin ascendente
Tratamiento de atributos heredados. Conversin de atributos heredados en sintetizados. Cambio en la gramtica. Ejemplo:
D ::= L:TT ::= integer | charL ::= L, id | id
Comprobacin de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 55
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Comprobacin dinmica. (Ejecucin)Comprobacin esttica. (Compilacin)
de tipos de flujo de control de unicidad de nombres
Uso de la informacin de tipos:
Comprobacin de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 56
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Comprobacin dinmica. (Ejecucin)Comprobacin esttica. (Compilacin)
de tipos de flujo de control de unicidad de nombres
Uso de la informacin de tipos: sobrecarga y polimorfismo
Comprobacin de tiposPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 57
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Sistemas de tipos
Diseado segn: Construcciones sintcticas Tipos bsicos Reglas de asignacin de tipos a construcciones sintcticas
Compuesto por reglas de asignacin de expresiones de tipos a las distintas partes de un programa
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 58
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Expresiones de tipos:Tipo bsico:
char, int, float, tipo_error, void
Nombre del tipoConstructores:
Matrices: array(tamao, tipo de los elementos) Productos de tipos: tipo1 x ... x tipon
Comprobacin de tiposSistemas de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 59
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Expresiones de tipos ... :Constructores ... :
Registros: struct((elemento1) x ... x (elementon))
Punteros: pointer(tipo) Funcin: tipo_parmetros tipo_devuelto(tipo1 x ... x tipon) tipo
Variables de tipo: su valor es un tipo
Comprobacin de tiposSistemas de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 60
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Comprobador de tipos seguro:Durante la compilacin (c. esttica) detecta todos los posibles errores de tipos
Lenguaje fuertemente tipado:Si un fragmento de cdigo compila es que nose van a producir errores de tipo
Comprobacin de tiposSistemas de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 61
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
S ::= TIPO LIST_ID; | TIPO LIST_ID; S | DEST = ORIG; | DEST = ORIG; STIPO ::= TBAS | TBAS *TBAS ::= char | int | floatLIST_ID ::= id | id, LIST_ID | id[cte] | id[cte], LIST_ID
Comprobacin de tiposEjemplo de comprobador de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 62
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
S ::= TIPO LIST_ID; {LIST_ID.tipo = TIPO.tipo;}
S ::= TIPO LIST_ID; S{LIST_ID.tipo = TIPO.tipo;}
TIPO ::= TBAS{TIPO.tipo = TBAS.tipo;}
TIPO ::= TBAS *{TIPO.tipo = pointer(TBAS.tipo);}
TBAS ::= char {TBAS.tipo = char;}TBAS ::= int {TBAS.tipo = int;}TBAS ::= float {TBAS.tipo = float;}
Comprobacin de tiposEjemplo de comprobador de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 63
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
LIST_ID ::= id{InsertaTipo(id.ts, LIST_ID.tipo);}
LIST_ID ::= id, LIST_ID1{InsertaTipo(id.ts, LIST_ID.tipo);LIST_ID1.tipo = LIST_ID.tipo}
LIST_ID ::= id[cte]{InsertaTipo(id.ts,array(cte.valex,
LIST_ID.tipo));}LIST_ID ::= id[cte], LIST_ID1
{InsertaTipo(id.ts,array(cte.valex, LIST_ID.tipo));
LIST_ID1.tipo = LIST_ID.tipo}
Comprobacin de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 64
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
S ::= DEST = ORIG; | DEST = ORIG; SDEST ::= id | id[cte] | id[id]
| *(DEST)ORIG ::= ORIG OP1 T | TT ::= DEST OP2 DEST | DESTOP1 ::= +|-OP2 ::= *|/|%
Comprobacin de expresiones
Comprobacin de tiposEjemplo de comprobador de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 65
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
CMP ::= CMP1 NR CMP2 | !(CMP) | (CMP)| DEST OPR DEST
OPR ::= == | != | < | | >=NR ::= && | ||DEST ::= id | id[cte] | id[id] | *(DEST)(* TBAS ::= bool *)
Comprobacin de expresiones booleanas
Comprobacin de tiposEjemplo de comprobador de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 66
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
S ::= while(CMP){S1}S ::= do{S1}while(CMP);S ::= if(CMP){S1}
Comprobacin de proposiciones
Comprobacin de tiposEjemplo de comprobador de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 67
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
S ::= TIPO id(LPARAM){S1}LPARAM ::= TIPO idLPARAM ::= TIPO id[cte]LPARAM ::= TIPO id, LPARAM1LPARAM ::= TIPO id[cte], LPARAM1
PARAM ::= idPARAM ::= PARAM, idS ::= id(PARAM)
Comprobacin de llamadas a funciones
Comprobacin de tiposEjemplo de comprobador de tipos
Comprobacin de tiposPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 68
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Equivalencia de expresiones de tipos
Cundo dos expresiones de tipos son equivalentes?Representacin en rbol:
Hojas: tipos bsicos + nombres de tipos Nodos interiores: constructores
float funcin (int a, char b)
int char
x
float
typedef tamao int;tamao a[256];
256
array
tamao
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 69
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Equivalencia estructural:Dos expresiones de tipos son equivalentes si:
1. Son el mismo tipo bsico2. Son el mismo constructor aplicado a tipos estructuralmente equivalentes
Se sustituyen los nombres por su expresin de tipo,Demasiado estricta
Comprobacin de tiposEquivalencia de expresiones de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 70
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Equivalencia de nombres:Expresiones idnticasComo la estructural pero sin sustituir los nombres por la expresin de tipo
typedef entero int;
Entero *a; pointer(entero)int *b; pointer(int)
Comprobacin de tiposEquivalencia de expresiones de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 71
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Distintos tipos Distintas instrucciones Distinta representacin en
memoriaConversin implcita (coercin):
Se realizan automticamente No se puede perder informacin Coercin de constantes
Conversin explcita: Especificada por el programador Como llamadas a funciones
Comprobacin de tiposConversin de tipos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 72
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Sobre funciones y operadores Distintos significados para una funcin u operador
Resolucin de la sobrecarga = identificacin del significado
Uso del tipo de los operandos o los parmetros
Comprobacin de tiposSobrecarga
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 73
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Ambigedad de tipo en subexpresiones.Una sub expresin con varios tipos posiblesLos operandos no bastan, hay que utilizar el contexto
Ejemplo:real operator *(int x,int y);int a, b, c;real d;(a*b)+c (a*b)+d
Comprobacin de tiposSobrecarga
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 74
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Reduccin de los conjuntos de tipos posibles.1. Se elige un tipo para la expresin2. Para cada subexpresin se elige el tipo en funcin de la expresin3. Si alguna subexpresin tiene varios tipos posibles, existe un error de tipos
Comprobacin de tiposSobrecarga
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 75
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Comprobacin de tiposSobrecarga
int a,b,c;real d;
(a*b)+cNueva definicin del operador +int operator +(real x, int y);a = (a*c)+b; d = a+(b*c);
+:int x int intreal x real real
*:int x int intreal x real realint x int real
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 76
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
En tiempo de compilacin no es necesario especificar el tipo de los parmetros Utilizan variables de tipo
Variable de tipo = expresin de tipo Comprobacin de tipos:
InferenciaUnificacin
Comprobacin de tiposFunciones polimrficas
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 77
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Sistema inferencia de tipos Sistema de demostracin de tipos Similar a un sistema axiomtico:
Conjunto de asignaciones de tipo + Reglas de inferencia de tipos
Comprobacin de tiposFunciones polimrficas
Condicional
:)'e' else e' then e (if -|A :'e' -|A :e' -|A :e -|A truval
Aplicacin
:)e' (e -|A :e' -|A :e -|A
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 78
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Unificacin Buscar una posible equivalencia estructural entre expresiones de tipos Sustitucin: lista de una o varias parejas de la forma:
(vble de tipo , exp de tipo) Proceso de unificacin de dos expresiones t1 y t2: encontrar una sustitucin tal que S(t1) = S(t2)
Comprobacin de tiposFunciones polimrficas
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 79
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Unificacin Elementos de una sustitucin:
Variable de tipoExpresin de tipo
Aplicacin de una sustitucin S a una expresin t S(t)
Expresin donde las variables de tipo se han transformado en las expresiones detalladas en la sustitucin S
Comprobacin de tiposFunciones polimrficas
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 80
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
UnificacinEjemplos de sustitucin:
1. t = pointer() S={(, integer)}S(t) = pointer(integer) integer
2. t = (pointer(1)) 1S={(1, pointer(2))}S(t) = pointer(pointer(2)) pointer(2)
S={2 , pointer(2)} SUST. RECURSIVAS !!!
Comprobacin de tiposFunciones polimrficas
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 81
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Algoritmo de unificacinRecorrido paralelo en profundidad, por cada nodo:
Si son iguales continuar con el siguiente.Si son distintos:
Si uno de ellos es una variable:Aplicar sustitucin (variable, otra expresin)
Si no Expresiones no unificables.Completado el recorrido:
Expresiones unificables segn las sustituciones.
Comprobacin de tiposFunciones polimrficas
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 82
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
UnificacinEjemplos de unificacin:
array(int)array(int) || array(1)array(1) pointer() || pointer(char)
pointer(int) 1 || 2 3pointer(1) 1 || 2 int
1 (2 1) || array(3) (pointer(3) 4)(pointer(1)) x (2 3) || 2 x (3 4)(pointer(1)) x (2 3) || 2 x (3 1)
Comprobacin de tiposFunciones polimrficas
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 83
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Una vez terminado el anlisis Traduccin a cdigo intermedio (CI) Representacin intermedia entre el anlisis y la generacin de cdigo final Ventajas:
1. Creacin de compiladores para distintasmquinas finales2. Optimizacin independiente de la mquina
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 84
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Representaciones intermedias:1. rbol semntico2. Notacin postfija, polaca inversa o RPN3. Cdigo de tres direcciones
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 85
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosRepresentacin grfica.Estructura jerrquica natural.Ej. DDS que genera la estructura de rbol.node* nodo(etiqueta, node*, node*)node* hoja(etiqueta)S ::= id=E;E ::= E+T | TT ::= T*F | FF ::= (E) | id
rbol semntico
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 86
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 87
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 88
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 89
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 90
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 91
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
(b)
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 92
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
(b)
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 93
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
(b) (c)
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 94
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
(b) (c)
(*, , )
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 95
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id(a)
(b) (c)
(*, , )
(+, , )
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 96
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
rbol semnticoS
id = E ;
E + T
T
F
id
T * F
F
id
id
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , )
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 97
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Notacin postfija
Basada en el rbol semntico. Recorrido en profundidad. No se representa un nodo mientras no se hayan representado todos sus hijos
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 98
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 99
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z a
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 100
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z a b
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 101
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z a b c
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 102
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z a b c *
Operandos
Operador
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 103
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z a b c * +
Operandos
Operador
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 104
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
z = a + b * c;
Notacin postfija
(=, , )(z)
(a)
(b) (c)
(*, , )
(+, , ) z a b c * + =
Operandos
Operador
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 105
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Representaciones intermedias:1. rbol semntico2. Notacin postfija, polaca inversa o RPN3. Cdigo de tres direcciones:
Cuartetos Tercetos Tercetos indirectos
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 106
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes Intermedios
Dos direcciones para los operandosUna direccin para el resultado
x = y op zx, y, z : nombres, constantes y variables temporales.No se permiten expresiones compuestas
Cdigo de tres direcciones
a=b+c*d-e;tmp1=c*dtmp2=b+tmp1tmp3=tmp2-ea=tmp3
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 107
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Proposiciones de cdigo de 3 direcciones: x = y op z x = op y x = y Etiq: goto E if x oprel y goto E param x call proc, num return x x = y[i] x[i] = y x = &y x = *y *x = y
Lenguajes IntermediosCdigo de tres direcciones
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 108
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosCdigo de tres direcciones
Ej. DDS que genera el cdigo de tres direcciones.nuevoTemp() Creacin de proposiciones de cdigo: gen(lista_de_literales_y_valores) Concatenacin de proposiciones: ||cdigo, lugar
S ::= id=E;E ::= E+T | TT ::= T*F | FF ::= (E) | id
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 109
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosCdigo de tres direcciones
Ej. DDS que genera el cdigo de tres direcciones.nuevaEtiq()gen(lista_de_literales_y_valores)||cdigo, lugar
S ::= do S1 until E;
(* Si despus de ejecutar S1 la expresin E tiene valor distinto de 0 se sale del bucle *)
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 110
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Cdigo de tres direcciones
Implementacin: Cuartetos Tercetos Tercetos indirectos.
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 111
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Cdigo de tres direcciones
Cuartetos:Cada proposicin consta de 4 elementos
(operador, arg1, arg2, resultado)arg1, arg2 y resultado suelen ser entradas de la TS
Ej. a + b * c
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 112
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Cdigo de tres direcciones
Tercetos: como los cuartetosEliminando el campo de resultadoSustituyendo las variables temporales por la referencia a las proposiciones que las calculan
Ej. a + b * c
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 113
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Cdigo de tres direcciones
Tercetos indirectos: como los tercetosManteniendo un vector de punteros a proposiciones del cdigo
Ej. a + b * cEj. (b*c)*(a + (b*c))/a
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 114
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosCdigo de tres direcciones
Cuartetos: Direccin de las variables temporales directamente accesibles Reubicacin del cdigo fcil Tabla de smbolos grande
Tercetos: Tabla de smbolos pequea Reubicacin ms difcil
PROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 115
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosCdigo de tres direcciones
Tercetos indirectos: Reubicacin fcil Uso eficiente de memoria Tabla de smbolos pequea
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 116
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin de declaraciones
Insertar identificadores.(lexema, tipo, direccin relativa)
Comprobacin de declaracin mltiple. Comprobacin de tipos.A ::= SS ::= T LiD ; | T LiD ; S1T ::= bool | real | int | charLiD ::= ID | ID , LiD1ID ::= id | * id | id[cte]
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 117
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin de declaraciones
Insertar identificadores.(lexema, tipo, direccin relativa)
Comprobacin de declaracin multiple. Comprobacin de tipos.
A ::= SS ::= T LiD ; | T LiD ; S1T ::= bool | real | int | charLiD ::= ID | ID , LiD1ID ::= id | * id | id[cte]
A
S
T LiD ; S
T LiD ;
ID
idbool
real ID , LiD
ID
id
id
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 118
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= SS ::= T {LiD.tipo = T.tipo;} LiD;S ::= T {LiD.tipo = T.tipo;} LiD; S1T ::= bool {T.tipo = b;}T ::= real {T.tipo = r;}T ::= int {T.tipo = i;}T ::= char {T.tipo = c;}LiD ::= {ID.tipo=LiD.tipo;}IDLiD ::= {ID.tipo=LiD.tipo;} ID {LiD1.tipo=LiD.tipo;}, LiD1 ID ::= id {id.ts=insert(id, id.tipo, ID.dh);
if(id.ts
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 119
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= SS ::= T {LiD.tipo = T.tipo;} LiD;S ::= T {LiD.tipo = T.tipo;} LiD; S1T ::= bool {T.tipo = b;}T ::= real {T.tipo = r;}T ::= int {T.tipo = i;}T ::= char {T.tipo = c;}LiD ::= {ID.tipo=LiD.tipo;}IDLiD ::= {ID.tipo=LiD.tipo;} ID {LiD1.tipo=LiD.tipo;}, LiD1 ID ::= id {id.ts=insert(id, id.tipo, ??);
if(id.ts
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 120
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= SS ::= T {LiD.tipo = T.tipo;} LiD;S ::= T {LiD.tipo = T.tipo;} LiD; S1T ::= bool {T.tipo = b;}T ::= real {T.tipo = r;}T ::= int {T.tipo = i;}T ::= char {T.tipo = c;}LiD ::= {ID.tipo=LiD.tipo;}IDLiD ::= {ID.tipo=LiD.tipo;} ID {LiD1.tipo=LiD.tipo;}, LiD1 ID ::= id {id.ts=insert(id, id.tipo, ??);
if(id.ts
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 121
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= SS ::= T {LiD.tipo = T.tipo;} LiD;S ::= T {LiD.tipo = T.tipo;} LiD; S1T ::= bool {T.tipo = b;}T ::= real {T.tipo = r;}T ::= int {T.tipo = i;}T ::= char {T.tipo = c;}LiD ::= {ID.tipo=LiD.tipo;}IDLiD ::= {ID.tipo=LiD.tipo;} ID {LiD1.tipo=LiD.tipo;}, LiD1 ID ::= id {id.ts=insert(id, id.tipo, ??);
if(id.ts
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 122
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= SS ::= T {LiD.tipo = T.tipo;} LiD;S ::= T {LiD.tipo = T.tipo;} LiD; S1T ::= bool {T.tipo = b;}T ::= real {T.tipo = r;}T ::= int {T.tipo = i;}T ::= char {T.tipo = c;}LiD ::= {ID.tipo=LiD.tipo;}IDLiD ::= {ID.tipo=LiD.tipo;} ID {LiD1.tipo=LiD.tipo;}, LiD1 ID ::= id {id.ts=insert(id, id.tipo, ??);
if(id.ts
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 123
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= S
S ::= T {...; LiD.tam = T.tam;}LiD;S ::= T {...; LiD.tam = T.tam;}LiD; S1T ::= bool {T.tipo = b; T.tam = 1;}T ::= real {T.tipo = r; T.tam = 8;}T ::= int {T.tipo = i; T.tam = 4;}T ::= char {T.tipo = c; T.tam = 1;}LiD ::= {...; ID.tam = LiD.tam;}IDLiD ::= {...; ID.tam = LiD.tam;} ID {...;LiD1.tam=LiD.tam;}, LiD1ID ::= id {ref = BuscaId (id.lexem); ...}ID ::= * id {ref = BuscaId (id.lexem); ...}ID ::= id[cte] {ref = BuscaId (id.lexem); ...}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 124
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= S
S ::= T {...; LiD.tam = T.tam;}LiD;S ::= T {...; LiD.tam = T.tam;}LiD; S1T ::= bool {T.tipo = b; T.tam = 1;}T ::= real {T.tipo = r; T.tam = 8;}T ::= int {T.tipo = i; T.tam = 4;}T ::= char {T.tipo = c; T.tam = 1;}LiD ::= {...; ID.tam = LiD.tam;}IDLiD ::= {...; ID.tam = LiD.tam;} ID {...;LiD1.tam=LiD.tam;}, LiD1ID ::= id {ref = BuscaId (id.lexem); ...}ID ::= * id {ref = BuscaId (id.lexem); ...}ID ::= id[cte] {ref = BuscaId (id.lexem); ...}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 125
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= S
S ::= T {...; LiD.tam = T.tam;}LiD;S ::= T {...; LiD.tam = T.tam;}LiD; S1T ::= bool {T.tipo = b; T.tam = 1;}T ::= real {T.tipo = r; T.tam = 8;}T ::= int {T.tipo = i; T.tam = 4;}T ::= char {T.tipo = c; T.tam = 1;}LiD ::= {...; ID.tam = LiD.tam;}IDLiD ::= {...; ID.tam = LiD.tam;} ID {...;LiD1.tam=LiD.tam;}, LiD1ID ::= id {ref = BuscaId (id.lexem); ...}ID ::= * id {ref = BuscaId (id.lexem); ...}ID ::= id[cte] {ref = BuscaId (id.lexem); ...}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 126
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= S
S ::= T {...; LiD.tam = T.tam;}LiD;S ::= T {...; LiD.tam = T.tam;}LiD; S1T ::= bool {T.tipo = b; T.tam = 1;}T ::= real {T.tipo = r; T.tam = 8;}T ::= int {T.tipo = i; T.tam = 4;}T ::= char {T.tipo = c; T.tam = 1;}LiD ::= {...; ID.tam = LiD.tam;}IDLiD ::= {...; ID.tam = LiD.tam;} ID {...;LiD1.tam=LiD.tam;}, LiD1ID ::= id {ref = BuscaId (id.lexem); ...}ID ::= * id {ref = BuscaId (id.lexem); ...}ID ::= id[cte] {ref = BuscaId (id.lexem); ...}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 127
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= S
S ::= T {...; LiD.tam = T.tam;}LiD;S ::= T {...; LiD.tam = T.tam;}LiD; S1T ::= bool {T.tipo = b; T.tam = 1;}T ::= real {T.tipo = r; T.tam = 8;}T ::= int {T.tipo = i; T.tam = 4;}T ::= char {T.tipo = c; T.tam = 1;}LiD ::= {...; ID.tam = LiD.tam;}IDLiD ::= {...; ID.tam = LiD.tam;} ID {...;LiD1.tam=LiD.tam;}, LiD1ID ::= id {ref = BuscaId (id.lexem); ...}ID ::= * id {ref = BuscaId (id.lexem); ...}ID ::= id[cte] {ref = BuscaId (id.lexem); ...}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 128
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 129
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 130
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 131
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 132
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 133
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 134
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;}T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 135
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DEL LENGUAJE A. SEMNTICO Y G.C.I.- Diap. 136
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
A ::= {S.dh = 0;} S {A.ds = S.ds;}S ::= T {...;...;LiD.dh=S.dh;}LiD {S.ds=LiD.ds;};S ::= T {...;...;LiD.dh=S.dh;}LiD {S1.dh=LiD.ds;};
S1{S.ds=S1.ds;} T ::= bool {...;} | real {...;} | int {...;}| char {...;}LiD ::= {...;...; ID.dh=LiD.dh;}ID {LiD.ds = ID.ds;}LiD ::= {...;...; ID.dh=LiD.dh;} ID {...;...; LiD1.dh=ID.ds;}
, LiD1 {LiD.ds=LiD1.ds;}ID ::= id {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam;InsertaDirMem(ref, ID.dh);}}
ID ::= * id {...; if(ref=null){ID.ds = ID.dh; error();}else{ ID.ds = ID.dh + 4;
InsertaDirMem(ref, ID.dh);}}ID ::= id[cte] {...; if(ref=null){ID.ds = ID.dh; error();}
else{ ID.ds = ID.dh + ID.tam * cte.val;InsertaDirMem(ref, ID.dh);}}
Lenguajes IntermediosPROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 137
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin de expresiones booleanas
Dos formas de traducir: Clculo del valor de verdad de la expresin.
Generar clculo del valor. Clculo del flujo de control.
Generar clculo de la direccin se salto.
E ::= E or T | TT ::= T and F | F F ::= not F | true | false | id oprel id1 |(E)
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 138
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del valor de verdad de la expresin.
E ::= T {E.lugar = T.lugar; E.cod = T.cod}
T ::= F {T.lugar = F.lugar;T.cod = F.cod}
F ::= (E) {F.lugar = E.lugar;F.cod = E.cod}
Lenguajes IntermediosTraduccin de expresiones booleanas
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 139
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del valor de verdad de la expresin.
E ::= E1 or T {E.lugar = nuevoTemp();E.cod = E1.cod || T.cod|| gen(E.lugar,=,E1.lugar
,or,T.lugar);}T ::= T1 and F {T.lugar = nuevoTemp();
T.cod = T1.cod || F.cod|| gen(T.lugar,=,T1.lugar
,and,F.lugar);}
Lenguajes IntermediosTraduccin de expresiones booleanas
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 140
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del valor de verdad de la expresin.
F ::= not F1 {F.lugar = nuevoTemp(); F.cod = F1.cod || gen(F.lugar,= not,F1.lugar);}
F ::= true {F.lugar = nuevoTemp(); F.cod = gen(F.lugar,=,1);}
F ::= false {F.lugar = nuevoTemp(); F.cod = gen(F.lugar,=,0);}
Lenguajes IntermediosTraduccin de expresiones booleanas
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 141
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del valor de verdad de la expresin.
Lenguajes IntermediosTraduccin de expresiones booleanas
F ::= id oprel id1 {F.lugar = nuevoTemp(); F.cod = gen(if,id.lexem,oprel,
id1.lugar,goto,+3)|| gen(F.lugar,=,0) || gen(goto,+2)|| gen(F.lugar,=,1);}
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 142
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del flujo de control.
Lenguajes IntermediosTraduccin de expresiones booleanas
F ::= id oprel id1 {F.cod = gen(if,id.lexem,oprel
,id1.lugar,goto,F.v)|| gen(goto,F.f);
}
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 143
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del flujo de control.
Lenguajes IntermediosTraduccin de expresiones booleanas
E ::= {T.v = E.v; T.f = E.f;}T {E.cod = T.cod;}
T ::= {F.v = T.v; F.f = T.f;} F{T.cod = F.cod;}
F ::= not {F1.v = F.f; F1.f = F.v;}F1 {F.cod = F1.cod;}
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 144
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del flujo de control.
Lenguajes IntermediosTraduccin de expresiones booleanas
F ::= true {F.cod = gen(goto, F.v);}F ::= false {F.cod = gen(goto, F.f);}F ::= ({E.v = F.v; E.f = F.f;}
E) {F.cod = E.cod;}
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 145
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Clculo del flujo de control.
Lenguajes IntermediosTraduccin de expresiones booleanas
E ::= {E1.v = E.v; E1.f = nuevaEtiq();T.v = E.v; T.f = E.f;}
E1 or T{E.cod = E1.cod || gen(E1.f,:) || T.cod;}
T ::= {T1.f = T.f; T1.v = nuevaEtiq();F.v = T.v; F.f = T.f;}
T1 and F{T.cod = T1.cod || gen(T1.v,:) || F.cod;}
Lenguajes IntermediosPROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 146
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin de llamadas a funciones
Pasar parmetros.Generar llamada.
S ::= id(); | id(L);L ::= id | id, L
Lenguajes IntermediosPROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 147
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin de llamadas a funciones
L ::= id{L.ps = L.ph + 1;gen(param(,id.lexem,));}
L ::= id {L1.ph = L.ph + 1; gen(param(,id.lexem,));}, L1 {L.ps = L1.ps;}
Lenguajes IntermediosPROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 148
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Traduccin de llamadas a funciones
S ::= id();
{gen(call,id.lexem,,,0);}S ::= id({L.ph = 0;}
L);
{gen(call,id.lexem,,,L.ps);}
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 149
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
S ::= id();{...;}
S ::= id( {L.ph = 0;...;}
L);{... ;}
L ::= id{L.ps = L.ph + 1;...;}
L ::= id{L1.ph = L.ph + 1;... ;}
,L1 {L.ps = L1.ps;... ;}
Lenguajes IntermediosTraduccin de llamadas a funciones
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 150
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosTraduccin de llamadas a funciones
S ::= id();{...;}S ::= id( {...;L.th = void;}L);{...}L ::= id{ ...;if(L.th=void) L.ts=id.t;
else L.ts=(L.th x id.t);...;}
L ::= id {...;if(L.th=void)L1.th=id.t;else L1.th=(id.t x L.th);
...;},L1 {...; L.ts = L1.ts;}
PROCESADORES DE LENGUAJES A. SEMNTICO Y G.C.I.- Diap. 151
Universidad Rey Juan Carlos, rea de Lenguajes y Sistemas. Jaime Urquiza Fuentes. Curso 2010-2011
Lenguajes IntermediosTraduccin de llamadas a funciones
S ::= id();{if(cmpTipo(id.ts, voidvoid))..;else error();}
S ::= id( {...;L.th = void;}L);{
if(cmpTipo(id.ts,L.ts void)){..}else error();}