2.2 REPRESENTACIONES DE CÓDIGO INTERMEDIO
Una
representación intermedia (RI) es una estructura de datos creada a partir de
los datos de entrada de un programa informático y de la que parte o la
totalidad de los datos de salida son construidos por turno. El uso del término
suele implicar que la mayoría de la información presente en la entrada es
guardada por la representación intermedia junto con más anotaciones o
características de búsqueda rápida.
Un
ejemplo canónico se encuentra en la mayoría de compiladores modernos, donde el
texto linear entendible por los humanos es transformado en un grafo que permite
el análisis del flujo de datos y recolocaciones antes de empezar a crear la
lista de instrucciones del CPU que harán el trabajo. El uso de una
representación intermedia permite a sistemas de compiladores como GNU GCC y
LLVM poder tener como destino diferentes códigos fuente y admiten su generación
para diferentes tipos de arquitectura.
2.2.1 NOTACIÓN POLACA
Las notaciones de prefijo (o polaca, en homenaje a Jan Łukasiewicz), de infijo y de postfijo (o polaca inversa) son formas de escritura de expresiones algebraicas que se diferencian por la posición relativa que toman los operadores y los operandos. En la notación de prefijo, el operador se escribe delante de los operandos (+ 3 4), entre los operandos en la notación de infijo (3 + 4) y tras los operandos en la de posfijo (3 4 +).
La
notación de prefijo fue propuesta en 1924 por el matemático, lógico y filósofo
polaco Jan Łukasiewicz (1878-1956), de allí el nombre alternativo por la que se
conoce.
Al
igual que la de postfijo, la notación polaca permite prescindir de los
paréntesis en el caso de operadores de aridad fija conocida. Por ejemplo, la
operación 5 * (12 + 4). puede escribirse en prefijo como: * 5 (+ 12 4); o
sencillamente: * 5 + 12 4 (y como 5 12 4 + *en postfijo).
2.2.2 CÓDIGO P
La máquina de código-p, es una máquina virtual, la cual ejecuta códigos binarios de un procesador hipotético, es decir, el diseñador, en lugar de usar el conjunto de instrucciones de un procesador como podría ser el Pentium, el 68000, el 6502, etcétera, utiliza una serie de códigos de un procesador que no existe en el mundo real, pero que se simula a través de un programa de computadora, es decir, de un intérprete que ejecuta las instrucciones de un programa en código-p o pseudo-código.
Ejemplos
de máquinas virtuales son la de Java o el código pre-compilado de lenguajes
como MatLab. Otro famoso ejemplo es la implementación de Pascal por la
Universidad de California en San Diego, al cual denominaron UCSD Pascal y que
fue relevante en los años 80s con las Apple II.
Las
ventajas saltan a la vista: un intérprete puede escribirse fácilmente, porque
en general son pocas instrucciones que deben simularse. Es mucho más difícil
generar código para un procesador comercial porque, además, contiene muchas más
instrucciones o modos diferentes de las mismas. El código-p no es dependiente
del comportamiento de la computadora. Esto permite crear “compiladores” en
mucho menor tiempo. Una máquina virtual en general es una máquina ideal, por lo
que el código-p es con frecuencia mucho más pequeño que el mismo programa
traducido a código binario de un procesador real.
2.2.3
TRIPLOS
En la historia de los compiladores han sido utilizadas una amplia variedad de representaciones intermedias como lo es la siguiente clase de representación de código intermedio de un árbol de 3 direcciones,2 para los operandos y una para la ubicación del resultado. esta clase incluye un amplio número de representaciones diferentes entre las cuales encontramos cuádruplos y triples. la principal diferencia entre estas notaciones y la notación postfija es que ellos incluyen referencias explicitas para los resultados de los cálculos intermedios, mientras que la notación posfija los resultados son implícitos al representarlos en una pila.
Los
triples tienen una ventaja obvia de ser más consistente, pero ellos dependen de
su posición, y hacen que la optimización presente cambios de código mucho más
compleja.
Para
evitar tener que introducir nombres temporales en la tabla de símbolos, se hace
referencia a un valor temporal según la posición de la proposición que lo
calcula. Las propias instrucciones representan el valor del nombre temporal. La
implementación se hace mediante registros de solo tres campos (op, arg1, arg2).
En la
notación de tripletes se necesita menor espacio y el compilador no necesita
generar los nombres temporales. Sin embargo, en esta notación, trasladar una
proposición que defina un valor temporal exige que se modifiquen todas las
referencias a esa proposición. Lo cual supone un inconveniente a la hora de
optimizar el código, pues a menudo es necesario cambiar proposiciones de lugar.
2.2.4 CUÁDRUPLOS
Cuádrupla:
<operación>, <operando1>, <operando2>, <resultado>T1,
T2, T3, T4 son variables temporales.
Ejemplo:(A+B)*(C+D)-E+,
A, B, T1+, C, D, T2*, T1, T2, T3-, T3, E, T4
Las cuádruplas facilitan la aplicación de muchas optimizaciones, pero hay que tener un algoritmo para la reutilización de las variables temporales (reutilización de registros del procesador).