Generación de
código
intermedio
15 JUNIO
Lenguajes y autómatas II
Creado por: Ing. Cesar Eduardo Mora
Hernandez
1
Unidad 2
Tema: Generacion de codigo intermedio
2.1 Notaciones.
2.1.1 Prefija.
2.1.2 Infija.
2.2.3 Postfija.
2.2 Representaciones de código Intermedio.
2.2.1 Notación Polaca.
2.2.2 Código P.
2.2.3 Triplos.
2.2.4 Cuádruplos.
2.3 Esquema de generación.
2.3.1 Variables y constantes.
2.3.2 Expresiones.
2.3.3 Instrucción de asignación.
2.3.4 Instrucciones de control.
2.3.5 Funciones.
2.3.6 Estructuras.
Objetivo: Diseña las reglas para traducir el código fuente a un código
intermedio.
2
Introducción
El código intermedio es un código que no concreta las características de la máquina final pero
que organiza el código objeto (el código del programa a compilar) para que sea el mismo o casi
el mismo, independientemente del lenguaje.
Es decir, se suele crear un código intermedio entre el código del lenguaje que queremos
compilar y el lenguaje máquina de la máquina de destino. Esto se hace así para que con un
pequeño esfuerzo adicional sea posible crear un compilador que pueda ser utilizado para
máquinas diferentes.
Dos características que hacen beneficioso crear un lenguaje intermedio entre el lenguaje fuente
y el ensamblador son:
Permite ahorrarse esfuerzo a la hora de crear varios compiladores para la misma
máquina, ya que cada lenguaje a compilar crearía el mismo código intermedio.
Se ahorra esfuerzo a la hora de crear un compilador para varias máquinas diferentes, ya
que el mismo código intermedio sirve para todas las máquinas.
Vistas las ventajas de la creación de un código intermedio, tendremos que definir cómo será
dicho lenguaje para que se adapte a lenguajes diferentes de alto nivel y lenguajes distintos de
bajo nivel.
En la realidad, es posible que haya que hacer pequeños cambios en el código intermedio para
diferentes máquinas, pero esos cambios suelen ser mínimos. La generación de código
intermedio, en adelante CI, es una tarea íntimamente ligada a la comprobación de tipos,
símbolos y al análisis semántico, por lo que se suele hacer paralelamente.
3
Por esto, todo el proceso de análisis semántico y la generación de CI están guiados por la
sintaxis. Si en vez de hacer un compilador lo que queremos es hacer un traductor, no suele ser
necesario generar código intermedio y luego código final, sino que directamente generamos
código final en el lenguaje de destino de la traducción.
2.1 Notaciones.
Cuando usted escribe una expresión aritmética como B * C, la forma de la expresión le
proporciona información para que pueda interpretarla correctamente. En este caso sabemos
que la variable B está siendo multiplicada por la variable C, ya que el operador de multiplicación
* aparece entre ellos en la expresión.
Este tipo de notación se conoce como infija ya que el operador está entre los dos operandos
sobre los que está actuando.
Considere otro ejemplo de notación infija, A + B * C. Los operadores + y * siguen apareciendo
entre los operandos, pero hay un problema. ¿Sobre qué operandos actúan? ¿Opera el + sobre
A y B o el * opera sobre B y C? La expresión parece ambigua.
De hecho, usted ha estado leyendo y escribiendo estos tipos de expresiones durante mucho
tiempo y no le causan ningún problema. La razón de esto es que usted sabe algo sobre los
operadores + y *. Cada operador tiene un nivel de precedencia. Los operadores de mayor
precedencia se utilizan antes que los operadores de menor precedencia. Lo único que puede
cambiar ese orden es la presencia de paréntesis. El orden de precedencia para los operadores
aritméticos ubica la multiplicación y la división por encima de la suma y la resta. Si aparecen
dos operadores de igual precedencia, se utiliza un ordenamiento o asociatividad de izquierda a
derecha.
Interpretemos la expresión problemática A + B * C usando la precedencia de los operadores. B
y C se multiplican primero y A se añade a ese resultado. (A + B) * C forzaría la suma de A y B
antes de la multiplicación. En la expresión A + B + C, por precedencia (vía asociatividad), el +
que está más a la izquierda operaría primero.
Aunque todo esto puede ser obvio para usted, recuerde que las computadoras necesitan saber
exactamente qué operadores deben ejecutarse y en qué orden. Una forma de escribir una
expresión que garantice que no habrá confusión con respecto al orden de las operaciones es
crear lo que se denomina expresión completamente agrupada. Este tipo de expresión utiliza
una pareja de paréntesis para cada operador. Los paréntesis dictan el orden de las operaciones;
no hay ambigüedad. Tampoco es necesario recordar las reglas de precedencia.
La expresión A + B * C + D se puede reescribir como ((A + (B * C)) + D) para mostrar que la
multiplicación ocurre primero, seguida por la adición que está más a la izquierda. A + B + C +
4
D se puede escribir como ((A + B) + C) + D) ya que las operaciones de adición se asocian de
izquierda a derecha.
Hay otros dos formatos de expresión muy importantes que, al principio, pueden no parecer
obvios. Considere la expresión infija A + B. ¿Qué pasaría si moviéramos el operador antes de
los dos operandos? La expresión resultante sería + A B. Del mismo modo, podríamos mover el
operador al final. Obtendríamos A B +. Estas expresiones se ven un poco extrañas.
Estos cambios en la posición del operador con respecto a los operandos crean dos nuevos
formatos de expresión, la notación prefija y la notación sufija (o postfija). La notación prefija
requiere que todos los operadores precedan a los dos operandos sobre los que actúan. La
notación sufija, por otro lado, requiere que sus operadores aparezcan después de los operandos
correspondientes. Algunos ejemplos más deberían ayudar a hacer esto un poco más claro. (ver
la Tabla 2).
A + B * C se escribiría como + A * B C en la notación prefija. El operador de multiplicación
aparece inmediatamente antes de los operandos B y C, denotando que el * tiene precedencia
sobre el +. El operador de adición aparece entonces antes de la A y del resultado de la
multiplicación.
En notación sufija, la expresión sería A B C * +. Una vez más, el orden de las operaciones se
conserva ya que el * aparece inmediatamente después de la B y la C, denotando que el * tiene
precedencia, con el + apareciendo después. Aunque los operadores se movieron y ahora
aparecen antes o después de sus respectivos operandos, el orden de cada operando se
mantuvo exactamente igual en relación con los demás.
EN RESUMEN
Notación Infija. Operador está entre los dos operandos sobre los que está actuando.
EJEMPLO: A+B
Notación Prefija. requiere que todos los operadores precedan a los dos operandos sobre
los que actúan.
EJEMPLO: + A B
Notación sufija (o postfija). Requiere que sus operadores aparezcan después de los
operandos correspondientes.
EJEMPLO: A B +
5
Tabla 2: Ejemplos en notación infija, prefija y sufija
Expresión infija Expresión prefija Expresión sufija
A+B +AB AB+
A+B*C +A*BC ABC *+
Ahora considere la expresión infija (A + B) * C. Recuerde que, en este caso, la notación infija
requiere los paréntesis para forzar que se lleve a cabo la adición antes de la multiplicación.
Sin embargo, cuando A + B fue escrito en notación prefija, el operador de adición fue movido
simplemente antes de los operandos, + A B.
El resultado de esta operación se convierte en el primer operando para la multiplicación. El
operador de multiplicación se mueve delante de toda la expresión, dándonos * + A B C.
Igualmente, en notación sufija A B + obliga a que la adición ocurra primero. La multiplicación se
puede hacer sobre ese resultado y el operando restante C. La expresión sufija correcta es
entonces A B + C *.
Considere nuevamente estas tres expresiones (ver la Tabla 3). Ha ocurrido algo muy
importante. ¿A dónde se fueron los paréntesis? ¿Por qué no los necesitamos en las notaciones
prefija y sufija? La respuesta es que los operadores ya no son ambiguos con respecto a los
operandos sobre los que actúan. Solamente la notación infija requiere los símbolos adicionales.
El orden de las operaciones dentro de las expresiones prefijas y sufijas está completamente
determinado por la posición del operador y nada más. De muchas maneras, esto hace que la
notación infija sea la notación menos deseable de usar.
Tabla 3: Una expresión con paréntesis
Expresión infija Expresión prefija Expresión sufija
(A + B) * C *+ABC AB+C*
6
PRACTICA 1
La Tabla 4 muestra algunos ejemplos adicionales de expresiones infijas de acuerdo a lo
analizado rellena los equivalente en notaciones prefija y sufija. Asegúrese de entender cómo
son equivalentes en términos del orden de las operaciones que se están realizando.
Tabla 4: Ejemplos adicionales en notaciones infija, prefija y sufija
Expresión infija Expresión prefija Expresión sufija
A+B*C+D
(A + B) * (C + D)
A*B+C*D
A+B+C+D
Conversión de expresiones infijas a notaciones prefija y sufija
Hasta el momento, hemos utilizado métodos ad hoc para convertir entre expresiones infijas y
las expresiones equivalentes en notaciones prefija y sufija. Como es de esperar, hay formas
algorítmicas para realizar la conversión que permiten transformar correctamente cualquier
expresión de cualquier complejidad.
La primera técnica que vamos a considerar utiliza la noción de una expresión completamente
agrupada que se discutió anteriormente. Recordemos que A+ B * C se puede escribir como (A
+ (B * C)) para mostrar explícitamente que la multiplicación tiene precedencia sobre la adición.
Sin embargo, al observar más de cerca, puede verse que cada pareja de paréntesis también
indica el comienzo y el final de un par de operandos con el operador correspondiente en la
mitad.
Observe el paréntesis derecho en la sub expresión (B * C) anterior. Si tuviéramos que mover el
símbolo de multiplicación a esa posición y quitar el paréntesis izquierdo correspondiente, nos
daría B C *, de hecho, habríamos convertido la sub expresión a notación sufija. Si el operador
de adición también es movido a la posición de su paréntesis derecho correspondiente y se
elimina el paréntesis izquierdo que le corresponde, se produciría la expresión sufija completa
(ver la Figura 6).
7
A B C*+
(((A + B) + C) + D)
Si hacemos lo mismo pero en lugar de mover el símbolo a la posición del paréntesis derecho,
lo movemos a la izquierda, obtenemos la notación prefija (ver la Figura 7). La posición de la
pareja de paréntesis es en realidad una pista sobre la posición final del operador encerrado
entre ellos.
+A*BC
Así que, para convertir una expresión, independientemente de su complejidad, ya sea a
notación prefija o a notación sufija, agrúpela completamente utilizando el orden de las
operaciones. A continuación, mueva cada operador a la posición correspondiente de los
paréntesis izquierdo o derecho dependiendo de si desea obtener la expresión en notación
prefija o en notación sufija.
PRACTICA 2
De acuerdo a lo analizado anteriormente realiza la conversión de la siguiente expresión infija a
sufija y prefija
(A + B) * C - (D - E) * (F + G).
8
Conversión General de notación infija a notación sufija
Necesitamos desarrollar un algoritmo para convertir cualquier expresión infija a una expresión
sufija. Para hacer esto vamos a examinar más de cerca el proceso de conversión.
Consideremos una vez más la expresión A + B * C. Como se muestra arriba, A B C * + es la
equivalencia en notación sufija. Ya hemos observado que los operandos A, B y C permanecen
en sus posiciones relativas. Sólo los operadores cambian de posición. Veamos de nuevo los
operadores en la expresión infija. El primer operador que aparece de izquierda a derecha es el
+. Sin embargo, en la expresión sufija, el + está al final dado que el siguiente operador, *, tiene
precedencia sobre la adición. El orden de los operadores en la expresión original se invierte en
la expresión sufija resultante.
A medida que procesamos la expresión, los operadores tienen que ser guardados en alguna
parte, ya que sus operandos derechos correspondientes no aparecen todavía. También, el
orden de estos operadores guardados puede necesitar ser invertido debido a su precedencia.
Ése es el caso con la adición y la multiplicación en este ejemplo. Dado que el operador de
adición aparece antes del operador de multiplicación y tiene menor precedencia, necesita
aparecer después de que se use el operador de multiplicación. Debido a esta inversión del
orden, tiene sentido considerar el uso de una pila para almacenar a los operadores hasta que
se necesiten.
Y ¿qué ocurrirá con (A + B) * C? Recuerde que A B + C * es la equivalencia en notación sufija.
De nuevo, procesando esta expresión infija de izquierda a derecha, vemos primero el +. En este
caso, cuando vemos el *, el + ya se ha transcrito en la expresión de resultado porque tiene
precedencia sobre el * en virtud de los paréntesis. Ahora podemos empezar a ver cómo
funcionará el algoritmo de conversión. Cuando veamos un paréntesis izquierdo, lo guardaremos
para indicar que habrá otro operador de alta precedencia. Ese operador tendrá que esperar
hasta que aparezca el paréntesis derecho correspondiente para indicar su posición (recuerde
la técnica de agrupar completamente). Cuando aparezca ese paréntesis derecho, el operador
puede ser extraído de la pila.
Al recorrer la expresión infija de izquierda a derecha, usaremos una pila para almacenar los
operadores. Esto proporcionará la inversión que hemos observado en el primer ejemplo. El tope
de la pila siempre será el operador guardado más recientemente. Siempre que leamos a un
operador nuevo, tendremos que comparar la precedencia de ese operador con la de los
operadores que ya estén en la pila, si los hay.
Suponga que la expresión infija es una cadena de símbolos delimitados por espacios. Los
símbolos de operaciones son *, /, + y -, junto con los paréntesis izquierdo y derecho, ( y ). Los
símbolos de operandos son los identificadores de un solo carácter A, B, C, y así sucesivamente.
Los siguientes pasos producirán una cadena de símbolos en el orden sufijo.
9
Reglas
1. Crear una pila vacía llamada pilaOperadores para almacenar los operadores. Crear una lista
vacía para almacenar la salida.
2. Convertir la cadena de entrada de notación infija a una lista, usando el método split.
3. Recorrer la lista de símbolos de izquierda a derecha:
o Si el símbolo es un operando, agregarlo al final de la lista de salida.
o Si el símbolo es un paréntesis izquierdo, enviarlo a pilaOperadores.
o Si el símbolo es un paréntesis derecho, extraer de pilaOperadores hasta que el
correspondiente paréntesis izquierdo se haya extraído. Agregar cada operador al final
de la lista de salida.
o Si el símbolo es un operador *, /, +, ó -, incluirlo en pilaOperadores.
o Si el operador es de menor precedencia sacar los operadores.
o Si el operando es mayor agregarlo a la pilaOperadores
o Si el operando es de igual precedencia se cambian y se agregar a la lista de salida.
4. Cuando la expresión de entrada ha sido procesada completamente, verificar pilaOperadores.
Todos los operadores que aún estén almacenados en ella se deben enviar a la lista de salida.
La Figura 9 muestra el algoritmo de conversión trabajando sobre la expresión A * B + C * D.
Observe que el primer operador * se elimina al verse el operador +. Además, el + permanece
en la pila cuando aparece el segundo *, ya que la multiplicación tiene precedencia sobre la
adición. Al final de la expresión infija, se extrae dos veces de la pila, eliminando ambos
operadores y colocando el + como el último operador en la expresión sufija.
10
EJEMPLO
(3 * 4) +6
A*B+C*D
34*6+
Lista: 3,4,*,6,+ Resultado = 18
Pila
11
PRACTICA 3
Convertir la siguiente expresión de infija a sufija.
(6+2)*3/2^2-4
Evaluación de expresiones en notación sufija
Como ejemplo final sobre las pilas, consideraremos la evaluación de una expresión que ya está
en notación sufija. En este caso, una pila será de nuevo la estructura de datos elegida. Sin
embargo, al recorrer la expresión sufija, son los operandos los que deben esperar, no los
operadores como en el algoritmo de conversión anterior. Otra forma de pensar en la solución
es que siempre que se vea un operador en la entrada, se usarán en la evaluación los dos
operandos más recientes.
Para ver esto con más detalle, considere la expresión sufija 4 5 6 * +. Al recorrer la expresión
de izquierda a derecha, usted encuentra primero los operandos 4 y 5. En este punto, usted
todavía no está seguro respecto a qué hacer con ellos hasta que vea el siguiente símbolo.
Ubicando cada uno en la pila asegura que estén disponibles si un operador viene a
continuación.
En este caso, el símbolo siguiente es otro operando. Así pues, como antes, inclúyalo en la pila
y examine el símbolo siguiente. Ahora vemos un operador, *. Esto significa que los dos
operandos más recientes necesitan ser utilizados en una operación de multiplicación. Al extraer
dos veces de la pila, podemos obtener los operandos adecuados y luego realizar la
multiplicación (en este caso obtenemos 30 como resultado).
Ahora podemos manejar este resultado colocándolo de nuevo en la pila para que pueda ser
utilizado como un operando para los operadores posteriores en la expresión. Cuando se
procesa el operador final, sólo quedará un valor en la pila. Se extrae y se devuelve como el
resultado de la expresión. La Figura 10 muestra el contenido de la pila a medida que se procesa
toda la expresión de ejemplo.
12
La Figura 11 muestra un ejemplo un poco más complejo, 7 8 + 3 2 + /. Hay dos cosas a tener
en cuenta en este ejemplo. En primer lugar, el tamaño de la pila crece, disminuye y, a
continuación, crece de nuevo a medida que las sub expresiones se evalúan. En segundo lugar,
la operación de división necesita ser manejada cuidadosamente. Recuerde que los operandos
en la expresión sufija están en su orden original ya que la notación sufija cambia sólo la
ubicación de los operadores. Cuando los operandos para la división se extraen de la pila, estos
se invierten. Dado que la división no es un operador conmutativo, en otras palabras 15/5 no es
lo mismo que 5/15, debemos estar seguros de que el orden de los operandos no esté
intercambiado.
13
Supongamos que la expresión sufija es una cadena de símbolos delimitados por espacios. Los
operadores son *, /, + y -; además, se supone que los operandos son valores enteros de un
solo dígito. La salida será un resultado entero.
1. Crear una pila vacía llamada pilaOperandos.
2. Convertir la cadena a una lista mediante la aplicación del método split.
3. Recorrer la lista de símbolos de izquierda a derecha.
o Si el símbolo es un operando, convertirlo de tipo cadena a tipo entero e incluir el valor
en pilaOperandos.
o Si el símbolo es un operador, *, /, +, ó -, éste necesitará dos operandos. Extraer dos
veces de pilaOperandos. La primera extracción corresponde al segundo operando y la
segunda al primer operando. Realizar la operación aritmética. Incluir el resultado
en pilaOperandos.
4. Cuando la expresión de entrada se ha procesado completamente, el resultado queda en la
pila. Extraerlo de pilaOperandos y devolver dicho valor.
La función completa para la evaluación de expresiones sufijas se muestra en el ActiveCode 2.
Para ayudar con la aritmética, se define una función auxiliar hacerAritmetica que tomará dos
operandos y un operador y luego realizará la operación aritmética apropiada.
14
