Semántica
y Análisis de Tipos.
Un compilador no solo tiene
que revisar la corrección sintáctica del código
fuente, si no también si la semántica corresponde
a la del lenguaje de programación. Esto significa que
el análisis semántica debe garantizar que se consideren
todas las reglas dependientes del contexto del lenguaje de programación.
Las tablas de símbolos
se emplean para revisar si un identificador ya ha sido declarado,
y su uso pueden considerarse como parte del proceso de análisis
semántico y el análisis semántico puede
efectuarse en paralelo con el análisis sintáctico.
El análisis semántico
de un compilador usa la información del análisis
sintáctico en cambio con las reglas semánticas
del lenguaje de programación para generar una representación
interna del código fuente que se va a compilar. Esta
generación de una representación del código
fuente y portan, que el compilador analice semánticamente
las estructuras sintácticas del código fuente
al ser reconocidas por el analizador léxico y el analizador
sintáctico. La representación interna es un código
intermedio que será enviado al generador de código.
5.1 Código
intermedio.
Nos referimos a una
estructura de código cuya complejidad esta entre el código
fuente en lenguaje de alto nivel y el código maquina;
los códigos intermedios se pueden considerar como una
interfaz entre el generador de código y las fases previas
el compilador. El uso de este nivel de maquina abstracta tuene
las siguientes ventajas:
-
El propio compilador
es independiente de la maquina destino y por tanto es mas
transportable, ya que todas las características del
hardware destino están consideradas en el genero
de código.
-
Es mas fácil llevar
a cabo algunas estrategias de optimización, en el
código intermedio que en el código fuente.
Sin embargo, el código
que puede generarse a partir del código intermedio por
lo general será meno eficiente que el código de
maquina generado directamente, debido al nivel de traducción
adicional.
Notación
postfija
La notación postfija
es una notación muy simple en la cual se colca un operador
en el extremo derecho de una expresión, es decir, después
de los operadores, en vez de estar entre ellos. Por ejemplo:
x + y – x* y
en notación postfija
es
x y + x y* -,
ya que x y + representa
la expresión infija x + y y xy* representa x * y, etc.
Por lo regular, la notación
postfija se emplea en maquinas de pilas, ya que puede manejarse
con gran facilidad usando una pula. Al analizar una notación
postfija de izq., a der., cada vez que se detecta un operador
se mete en la pila. La ocurrencia de un operador con m operadores
significa que el n – esimo operando estará en la cima
de la pila. Después se sacan los operandos de la pila
y se mete el resultado de la operación.
Código
de Tres Direcciones.
El código más
popular es el código de tres direcciones. La forma representativa
del código des direcciones es:
res := arg1 op arg2
donde res, arg1 y arg2 pueden
ser constantes (solo arg1 y arg2), o identificadores definidos
por el programador, o varias auxiliares definidas por el compilador,
mientras que op es un operador arbitrario. Las variables auxiliares
definidas por el compilador sirve para manejar expresiones mas
complejas que contiene mas de un operador; en otras palabras
las expresiones con operadores múltiples se dividen en
una secuencia de expresiones que contiene solo un operador y
que operan con variables auxiliares.
Si consideramos la forma representativa de del código
de tres direcciones antes presentada podemos distinguir cuatro
elementos básicos: op, arg1, arg2 y res, que suelen representarse
como sigue:
Donde por lo regular
ar1, arg2 y res son apuntadores a entradas de la tabla de símbolos.
En ese caso, esta forma se denomina cuádruplo.
El código de tres
direcciones, al igual que el de dos direcciones que veremos
mas adelante, permite que la traducción a código
para maquinas de registro sea muy simple ya que los operadores
muchas veces son el resultado de operaciones anteriores.
De esta manera, las
referencias a los resultados de las operaciones previas se dan
explícitamente mientras que en el código posfijo
las referencias las da la pila en forma implícita.
Código
de dos direcciones
Las variables auxiliares
en los códigos de tres direcciones se usan para almacenar
temporalmente resultados necesarias para proposiciones subsecuentes.
La idea es evitar el uso de estas variables auxiliares haciendo
referencia a la proposición cuyo resultado seria la variable
auxiliar como operando. Por lo tanto, en el campo de resultado
del código de direcciones ya no es necesario y los campos
arg1 y arg2 pueden contener apuntadores a la tabla de símbolos
y apuntadores a la secuencia de proposiciones de dos direcciones.
Entonces la forma general del código de dos direcciones
es la siguiente:
En forma también
se conoce como triple.
El ejemplo anterior, z
:= x ++ y – x* y, se transforma en el siguiente codigo de dos
direcciones:
-
ADD x y
-
MUL x y
-
SUB (1) (2)
-
STO (3) z
Donde los números
entre paréntesis representan apuntadores a la secuencia
de proposiciones de dos direcciones.
5.2 Traducción
diagrama por la sintaxis.
El análisis semántico
puede efectuarse en paralelo con el análisis sintáctico;
es decir, el análisis semántico cada vez que el
analizador sintáctico reconoce una estructura sintáctica,
o sea, una producción.
Esta acciones semánticas
generan código intermedio cada vez que se ejecutan. Así,
la estructura sintáctica del código fuente dirige
la traducción a código objeto o código
intermedio, por lo cual hablamos de traducción dirigida
por la sintaxis.
Acciones semánticas.
Las acciones semánticas
se asocian con las producciones de una gramática independiente
del contexto. Pueden considerarse como un fragmento de código
que se ejecutara cuando el analizador sintáctico reconozca
la producción apropiada.
Por ejemplo: consideremos
la producción G0.
TERMINO ® TERMINO
FACTO (*A*)
Que encontramos que
A es la acción semántica asociada. Entonces, si
trata de un:
Traducción
a cuádruplos.
La generación
del código de tres direcciones (cuádruplos) se
ilustra en el siguiente ejemplo, donde se considera la gramática
G0 y el análisis por desplazamiento y reducción
de la frase x + y –x * y. Los fragmentos de código que
representan acciones semánticas suponen una matriz "infinita"
de variables auxiliares (va[k]), para simplificar las cosas.
Por lo tanto, se incrementa una variable k cada vez que se usa
una nueva variable auxiliar. ApunT y ApunF son apuntadores al
lugar donde puede hallar el valor de una expresión, un
termino etc. Los subíndices sirven para distinguir varias
ocurrencias de símbolos no terminales. El procedimiento
GenC produce un cuádruplo de acuerdo con su parámetros.
Por lo tanto, la traducción de la
frase x + y – x y a notación postfija es
LOD x LOD
y ADD LOD x LOD y MUL SUB.
Lo cual corresponde al ejemplo
dado en la sección anterior.
Este esquema de traducción
se puede emplear no sólo para expresiones aritméticas,
sino para todas lasa estructuras de un lenguaje de programación.
Para ejemplificar esto, mostramos la traducción a notación
postfija de las proposiciones while e if de PL/O. Las proposiciones
while de PL/O se presenta el la siguiente forma:
WHILE CONDICION
DO PROPOSICIÓN.
La traducción de
las proposiciones condicionales y repetitivas genera instrucciones
de salto. Puesto que por lo regular no se conoce la dirección
destino cuando se general la instrucción de salto, es
necesario completar esta información más tarde.
Esto se puede hacer con un segundo paso, en el cual se fijan
todas la direcciones abiertas, o con una matriz que contiene
el código generado y al que se puede tener acceso directo
a través del índice de la instrucción de
salto previamente almacenado, para fijar la dirección
destino tan pronto como esta se conozca. ( Desde luego, el uso
de una matriz de código presenta la desventaja de que
el programador del compilador tiene que determinar por anticipado
el tamaño máximo del código. Otra alternativa
será le uso de etiquetas simbólicas. ) Entonces,
la estructura general del código para proporciones while
es:
L1
Instrucciones para
evaluar CONDICON
JPC L2
Instrucciones para
ejecutar PROPOSICIN
JMP L1
L2:
...
donde JPC y JMP son las
instrucciones de salto condicional e incondicional, respectivamente.
En la figura 5.2 se exhibe un fragmento de código rudimentario
para la generación del código postfijo de proposiciones
while de PL/O.
Una proposición
repetitiva requiere dos instrucciones de salto, pero la proposición
if, tal y como existe en PL/O, solo requiere una. Las proposiciones
if de PL/O se expresan de la sigu9ente forma:
IF CONDICION
THEN PROPOSICIÓN.
DE forma análoga
a la estructura general de código que acabamos de ver
para las proposiciones while, podemos presentar la estructura
general de las proposiciones if:
Código : ARRAY (
[ 0.. codigomax ] OF RECORD.
Co :
codigo_op;
Nivel :
CARDINAL;
Direct :
CARDINAL;
END;
(* código: contiene
el código intermedio generado *)
(* co: código de
operación; nivel: novel de declaración *)
(* direc: dirección
de desplazamiento*)
...
IF símbolo = símwhile
THEN
Fijar1 ; = índice;
( * índice: índice de código *)
Leer _ símbolo;
Condición ( ...
); (* analiza las expresiones condicionales *)
Fijar2 ; = índicec;
GenC ( JPC, 0, 0); (*
ge era el código para un salto condicional *)
(* donde
la dirección no está definida *)
IF símbolo = simdo
THEN
Leer_simbolo
ELSE
Error ( … )
END;
Proposición ( ..
]); 8* analiza proposiciones ejecutables *)
GenC ( JMP, 0, fijar1 )
; ( * genera código para un salto *)
( * incondicional, direc:
fijar1 *)
código [ fijar2
] direc := índicec;
(* fijar dirección
JPC *).
END;
Figura 5.2 Traducción
de proposiciones while.
Instrucciones para
evaluar CONDICION.
JPC L1
Instrucciones para
ejecutar PROPOSICON
L1:
...
Por ultimo, en la figura
5.3 se muestra un fragmento de código para la generación
de código postfijo para las proposiciones if de PL/O
( una vez más utilizamos una matriz de código
).
IF símbolo = simif
THEN
Leer_simbolo;
Condición;
If símbolo = simthen
Leer_símbolo
ELSE Error ( ... ) END;
Fijar1 := índice
(* almacenar la dirección fijada*)
Gen C ( JPC, 0,0 ); (*
genera código parea un salto condicional *)
(* donde la
dirección no está definida *)
Proposición;
Código [ fijar1
]. Direc := índicec;
(* ajustar
dirección de salto *)
END;
FIGURA 5.3 Traducción
de proposiciones if.
5.3 Comprobación
de tipos.
La comprobación de
tipos es una forma de asegurar que los identificadores relacionados
sean de tipos compatibles. Dos identificadores se relacionan:
-
Al formar el lado izquierdo
y derecho de un operador.
-
Al formar el lado izquierdo
y derecho de una proposición de asignación;
-
Al ser parámetros
reales y formales.
Las comprobaciones de
consistencia que se efectúan antes dela ejecución
del programa fuente ( es decir, que lleva a cabo el compilador
) se denominan comprobaciones estáticas, mientras que
aquellas realizadas ( o comprobaciones durante la ejecución
). La revisión de la sintaxis es un ejemplo de comprobación
estática, mientras que la comprobación de tipos
es un ejemplo de comprobación que con frecuencia puede
efectuarse en forma estática y que en ocasiones debe
realizarse dinámicamente:
Por ejemplo, consideremos
la siguiente declaración:
Str: ARRAY [ 0...80
] OF CHAR;
I : INTEGER;
En general, no puede garantizarse
estáticamente que se cumpla la condición 0 £
i £ 80 al usar str [ i ]; es decir, esta comprobación
debe efectuarse en forma dinámica. Sin embargo, es posible,
por ejemplo, comprobar estáticamente si la asignación
Str
[ i ] := ch ;
Está permitida, o
sea, si ambos lados de la proposición de asignación
son de tipos compatibles. Para ello es necesario consultar la
tabla de símbolos.
A continuación
se presenta un breve ejemplo de cómo introducir las reglas
que permiten la comprobación de tipos de expresiones
aritméticas. TipoE, TipoT y TipoF representan el tipo
de una expresión, términos, etx.; se emplean subíndices
para distinguir entre varias ocurrencias de un mismo símbolo
no terminal. Se usara el siguiente subconjunto de la gramática
G0 con las reglas correspondientes ( suponiendo la semántica
de PL/O ) :
E T (*TipoE:=
TipoT*)
E1 E2 + T (*TipoE1
:= if TipoE2 = integer and
TipoT = integer then integer
Else
error_tipo;*)
T F (*TipoT
:= TipoF*)
T1 T2*F (*TipoT1
:= if TipoT2 = integer and
TipoF = integer then integer
Else
error_tipo; *)
F x (*TipoF
:= buscar_Tipo(x); *)
F y (*TipoF
:= buscar_Tipo(y); *)
F ( E ) (*TipoF
:= TipoE; *)
El procedimiento buscar_Tipo(...)
se usa para determinar el tipo de un identificador por medio
de la revisión de la tabla de símbolos. Por ejemplo,
el tipo de una expresión formada por aplicar el operador
"+" a una sub expresión y un termino es entero
si el tipo de la sub expresión y el termino es entero;
en caso contrario será un error tipo.
Ahora bien, la formulación
d reglas para semánticas ( tipo PASCAL ) que establecen,
por ejemplo, que entero* real genera un resultado de tipo real,
es obvia y puede verse como se propagara un tipo. Así,
durante el proceso de análisis semántico, se puede
determinar donde se requieren cambios forzados de tipo ( coerción
) y que operadores deben seleccionarse ( por ejemplo, multiplicación
entera o de punto flotante ).
Debemos señalar
que n todos los lenguajes de programación permiten una
comprobación estática de tipos como la que acabamos
de exponer. En el lenguaje de programación APL, por ejemplo,
el valor actual de una variable determina el tipo de la variable.
Esto significa que el tipo de una variable puede cambiar durante
la ejecución del programa y, por lo tanto, debe comprobarse
durante la ejecución.
5.4 Generación
de código intermedio para PL/O.
Ahora presentaremos un rudimentario
segmento de código que es una expresión del analizador
sintáctico descendente recursivo del capitulo 4.3. Tiene
la misma estructura que el analizador sintáctico descendente
recursivo e indica cuando se ejecutan acciones semánticas
para generar el código intermedio. El código intermedio
está en notación postfija y usa el siguiente conjunto
de instrucciones:
LIT cargar un numero
( literal ) n en la pila;
LOD cargar la variable
en la pila;
STO almacenar variables
de acuerdo con proposiciones de asignación;
CAL llamada a procedimiento;
INT incrementar apuntador
de pila para asignación de memoria:
JMP salto incondicional;
JPC salto condicional;
ADD sumar dos operandos
de la pila;
SUB restar dos operandos
de la pila;
MUL multiplicar
dos operandos de la pila;
DIV dividir dos operandos
de la pila;
NEG negar la cima
de la pila;
OD ¿ es impar la
cima de la pila ?
EQ ¿ son iguales
los dos elementos superiores de la pila ?
NE ¿ son distintos
los dos elementos superiores de la pila ?
LE ¿ es menor o igual
la cima de la pila que ( cima de pila – 1) ?
GE ¿ es mayor o igual
la cima de la pila que ( cima de pila – 1) ?
LS ¿ es menor la
cima de la pila que ( cima de pila – 1 ) ?
GT ¿ es mayor la
cima de la pila que ( cima de pila – 1 ) ?
PROGRAM Compilador;
... ... ...
PROCEDURE Dispersión
( vn : alfa ): INTEGER.
BEGIN
...
END Dispersión;
PROCEDURE InsertarTS ( vn:
alfa; k: objeto );
BEGIN
…
END InsertarTS;
Procedure BuscarTS ( VAR
p: Tabsim_Disp; vn: alfa ): INTEGER
BEGIN.
…
END BuscarTS;
PROCEDURE GencC ( o: código_op;
n: INTEGER; d: INTEGER );
BEGIN
IF indice > codigomax
THEN Error(...); END;
WITH código [indice]
DO
Co := o;
Nivel := n;
Direc := d;
END;
INC ( indicec)
End genC;
PROCEDURE Bloque ( niv:
INTEGER);
PROCEDURE Declaración_const
;
BEGIN
...
END Declaración_const;
PROCEDURE Declaración_var;
BEGIN
...
END Declaración_var;
PROCEDURE expresión;
VAR ADDoSUB: símbolos;
PROCEDURE Término;
VAR MULoDIV: símbolos;
PROCEDURE Factor;
VAR i: INTEGER
;
BEGIN ( * Factor*
)
CASE símbolo
OF
Ident
: i := BuscarTS ( ElementoD, id);
IF
I = 0 THEN Error ( …)
ELSE
With ElementoD DO
CASE
tipo OF
Objconst: GenC(LIT, 0 val);
|
objvar : GenC(LOD, niv-nivel, dir)
|
objproc: Error (...);
END
END
END
Leer_Símbolo;
| número:
GenC(LIT, 0, núm); Leer_Símbolo;
| pareni: Leer_Símbolo;
Expresión;
IF símbolo
= parend THEN Leer_Símbolo
ELSE Error(…)
END
ELSE Error(…)
END;
END Factor;
BEGIN (*Término*)
Factor;
WHILE símbolo
IN [por, diagonal] DO
MULoDIV:= símbolo;
Leer_Símbolo; Factor;
IF MULoDIV= por
THEN
GenC(MUL, 0, 0)
ELSE
GenC(DIV, 0, 0)
END;
END
END Término;
BEGIN (*Expresión*)
IF símbolo IN
[más, menos] THEN
ADDoSUB := símbolo;
Leer_símbolo; Término;
IF.ADDoSUB = menos THEN
GenC(NEG, 0, 0) END;
ELSE Término
END;
WHILE símbolo
IN [más, menos] DO
ADDoSUB := símbolo;
Leer_símbolo; Término;
IF ADDoSUB = menos
THEN
GenC(SUB, 0, 0)
ELSE
GenC(ADD, 0, 0)
END
END
END Expresión;
PROCEDURE Condición;
VAR opcomp : símbolos;
BEGIN
IF símbolo =
símimpar THEN
Leer_Símbolo;
Expresión; GenC(OD, 0, 0);
ELSE
Expresión;
IF símbolo
IN [igual, noigual, menor, menorig, mayor, mayorig] THEN
opcomp := símbolo;
Leer_Símbolo; Expresión;
CASE opcomp OF
igual :
GenC (EQ, 0, 0);
| noigual : GenC
(NE, 0, 0);
| menor : GenC
(LS, 0, 0);
| mayorig : GenC
(GE,0, 0);
| mayor : GenC
(GT, 0, 0);
| menorig : GenC
(LE, 0, 0);
END
ELSE Error(...)
END;
END
END Condición;
PROCEDURE Proposición;
VAR i fijar1, fijar2 : INTEGER;
BEGIN
CASE símbolo
OF
ident : i := BuscarTS(ElementoD,
id) ;
IF i = 0 THEN Error(…)
ELSIF ElementoD.tipo
<> objvar THEN
Error(…) END;
Leer_Símbolo;
IF símbolo
= cambia THEN Leer_Símbolo
ELSE Error(...)
END;
Expresión;
WHIT ElementoD
DO
GenC(STO, niv-nivel,
dir)
END;
| símcall : Leer_Símbolo;
IF símbolo
= ident THEN
i := BuscarTS(ElementoD,
id);
IF i = 0 THEN
Error(…)
ELSE
WHIT ElementoD
DO
IF tipo
= objproc THEN
GenC(CAL,
niv-nivel, dir)
ELSE Error(...)
END;
END;
Leer_Símbolo
END
ELSE Error(…) END;
