TEMA-2-REPORTE DE PRACTICAS Y ACTIVIDADES LENG Y AUTOMATAS 2 - Mauricio axel 20

Vista previa del material en texto

REPORTE DE PRACTICA/ACTIVIDADES DEL APRENDIZAJE 
DEL TEMA 2 GENERACIÓN DE CODIGO INTERMEDIO 
FECHA DE ENTREGA: 26 DE ABRIL DE 2021 
PERIODO ESCOLAR: FEBRERO – JUNIO 2021 
 
 
 
INDICE 
INTRODUCCIÓN ..................................................................................................................................... 4 
TEMA 2 GENERACIÓN DE CÓDIGO INTERMEDIO ........................................................................ 7 
SUBTEMAS .............................................................................................................................................. 7 
2.1 NOTACIONES ................................................................................................................................... 7 
2.1.1 PREFIJA ...................................................................................................................................... 7 
2.1.2 INFIJA .......................................................................................................................................... 8 
2.1.3 POSTFIJA ................................................................................................................................... 9 
2.2 REPRESENTACIONES DEL CÓDIGO INTERMEDIO ............................................................. 10 
2.2.1 NOTACIÓN POLACA .............................................................................................................. 11 
2.2.2 CÓDIGO P ................................................................................................................................ 12 
2.2.3 TRIPLOS ................................................................................................................................... 13 
2.2.4 CUÁDRUPLOS ......................................................................................................................... 14 
2.3 ESQUEMA DE GENERACIÓN ..................................................................................................... 15 
2.3.1 VARIABLES Y CONSTATES ................................................................................................. 16 
2.3.2 EXPRESIONES ........................................................................................................................ 17 
2.3.3 INSTRUCCIÓN DE ASIGNACIÓN ........................................................................................ 18 
2.3.4 INSTRUCCIONES DE CONTROL ........................................................................................ 19 
2.3.5 FUNCIONES ............................................................................................................................. 20 
2.3.6 ESTRUCTURAS....................................................................................................................... 21 
ACTIVIDAD 1. APLICAR LOS TIPOS DE NOTACIÓN PARA LA CONVERSIÓN DE 
EXPRESIONES: INFIJA, PREFIJA Y POSTFIJA ............................................................................. 26 
ACTIVIDAD 2. REPRESENTAR EXPRESIONES MEDIANTE EL CÓDIGO INTERMEDIO ..... 37 
ACTIVIDAD 3. RECONOCER EL MANEJO DE TIPOS EN LAS EXPRESIONES Y EL USO DE 
OPERADORES ...................................................................................................................................... 41 
ACTIVIDAD 4. DESARROLLAR LAS ACCIONES QUE REPRESENTEN LA ESTRUCTURA 
DE UN LENGUAJE DE PROGRAMACIÓN DE ALTO NIVEL DE UN CÓDIGO INTERMEDIO 49 
 
 
 
ACTIVIDAD 5. APLICAR LAS ACCIONES CONSTRUIDAS A LA GRAMÁTICA DEL 
LENGUAJE PROTOTIPO ..................................................................................................................... 53 
ACTIVIDAD 6. INTEGRAR EQUIPOS DE TRABAJO PARA LA GENERACIÓN DE UN 
CÓDIGO INTERMEDIO ........................................................................................................................ 62 
CONCLUSIÓN ........................................................................................................................................ 66 
BIBLIOGRAFIA ....................................................................................................................................... 70 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
INTRODUCCIÓN 
La generación de código es la fase más compleja de un compilador, puesto que no 
sólo depende de las características del lenguaje fuente sino también de contar con 
información detallada acerca de la arquitectura objetivo, la estructura del ambiente 
de ejecución y el sistema operativo que esté corriendo en la máquina objetivo. La 
generación de código por lo regular implica también algún intento por optimizar, o 
mejorar, la velocidad y/o el tamaño del código objetivo recolectando más 
información acerca del programa fuente y adecuando el código generado para sacar 
ventaja de las características especiales de la máquina objetivo, tales como 
registros, modos de direccionamiento, distribución y memoria caché. En el modelo 
de análisis y síntesis de un compilador, la etapa inicial traduce un programa fuente 
a una representación intermedia a partir de la cual la etapa final genera el código 
objeto. Los detalles del lenguaje objeto se confinan en la etapa final, si esto es 
posible. Aunque un programa fuente se puede traducir directamente al lenguaje 
objeto, algunas ventajas de utilizar una forma intermedia independiente de la 
máquina son: 
1. Se facilita la redestinación; se puede crear un compilador para una máquina 
distinta uniendo una etapa final para la nueva máquina a una etapa inicial ya 
existente. 
2. Se puede aplicar a la representación intermedia un optimizador de código 
independiente de la máquina. 
Hay lenguajes que son pseudo 
interpretados que utilizan un código 
intermedio llamado código-P que 
utiliza lo que se denomina byte Codés 
(sentencias de un μP hipotético). Por 
ejemplo, Java utiliza los ficheros.class, 
éstos tienen unos bytes Codés que se 
someten a una Java Virtual Machine, 
para que interprete esas sentencias. 
 
 
 
Una vez ha terminado el análisis y se ha obtenido un AST decorado, comienza la 
generación de código. Esta fase suele dividirse en dos partes: 
• Generación de código intermedio. 
• Generación de código de máquina. 
El primero es código para una máquina virtual. Estas máquinas se definen con dos 
objetivos: 
• Ser lo suficientemente simples como para poder generar código para ellas 
de manera sencilla, pero con la suficiente riqueza para poder expresar las 
construcciones del lenguaje fuente. 
• Estar lo suficientemente próximas a los procesadores reales para que el paso 
del código intermedio al código de máquina sea prácticamente directo. 
Para conseguirlo, las máquinas virtuales tienen una serie de características 
simplificadoras. Por ejemplo: 
• Tienen pocos modos de direccionamiento. 
• Pueden tener un número ilimitado de registros (que pueden estar 
organizados en forma de pila). 
• Tienen un juego de instrucciones relativamente simple. 
En principio, el código intermedio es independiente del lenguaje de programación 
fuente. En la práctica, es habitual que se definan códigos intermedios que faciliten 
la representación de determinadas características del lenguaje fuente. Así, el P-
code está pensado para traducir Pascal y el Java-bytecode es muy bueno para el 
Java. Otra de las ventajas del código intermedio es que facilita la escritura de 
compiladores para distintas máquinas. 
La traducción del lenguaje a código intermedio sería idéntica en todas y lo único que 
cambiaría sería el traductor de código intermedio a código de máquina. Esta idea 
de independencia del código intermedio de la máquina puede llevarse un paso más 
allá, como se hace en diversos lenguajes, de los cuales Java es quizá el más 
 
 
 
representativo. La idea es compilar el lenguaje a un código intermedio que después 
es interpretado. De esta manera, un mismo“binario” puede ejecutarse en máquinas 
con arquitecturas y sistemas operativos totalmente distintos. Una vez generado el 
código intermedio, se traduce ´este a código de máquina. La traducción tiene que 
hacerse de manera que se aprovechen adecuadamente los recursos de la máquina 
real. 
Aunque en principio estas dos fases bastan para la generación del código final, en 
la práctica están mezcladas con fases de optimización. Es habitual tener entonces 
un esquema similar al que vimos en el primer tema: 
Podríamos entonces decir que la generación de código tiene como objetivo generar 
el ejecutable que después empleara el usuario. Sin embargo, es habitual que el 
producto del compilador no sea directamente un fichero ejecutable. Es bastante más 
común que sea un fichero en lenguaje ensamblador. 
De esta manera, se evitan problemas como tener que medir el tamaño exacto de 
las instrucciones o llevar la cuenta de sus direcciones. Además, es muy probable 
que el código generado tenga referencias a objetos externos como funciones de 
biblioteca. Estas referencias externas serán resueltas por el enlazador o el cargador. 
 
 
 
 
 
TEMA 2 GENERACIÓN DE CÓDIGO INTERMEDIO 
SUBTEMAS 
2.1 NOTACIONES 
Las notaciones son una forma especial en la que se pueden expresar una expresión 
matemática y puedan ser de 3 formas: infija, prefija y posfija. Los prefijos, Pre - Pos 
- In se refieren a la posición relativa del operador con respecto a los dos operandos. 
• Las notaciones sirven de base para expresar sentencias bien definidas. 
• El uso más extendido de las notaciones sirve para expresar operaciones 
aritméticas. 
• Las expresiones aritméticas se pueden expresar de tres formas distintas: 
infija, prefija y postfija. 
• La diversidad de notaciones corresponde en que para algunos casos es más 
sencillo un tipo de notación. 
• Las notaciones también dependen de cómo se recorrerá el árbol sintáctico, 
el cual puede ser en inorden, preorden o postorden; teniendo una relación de 
uno a uno con la notación de los operadores. 
2.1.1 PREFIJA 
La expresión o notación prefija nos indica que el operador va antes de los 
Operandos sus características principales son: 
• Los operadores conservan el mismo orden que la notación infija equivalente. 
• No requiere de paréntesis para indicar el orden de precedencia de 
operadores ya que él es una operación. 
• Se evalúa de izquierda a derecha hasta que encuentra el primer operador 
seguido inmediatamente de un par de operando. 
• Se evalúa la expresión binaria y el resultado se cambia como un nuevo 
operando. Se repite hasta que nos quede un solo resultado. 
 
 
 
• El orden es operador, primer operando, segundo operando. 
 
 
La notación prefija pone el operador primero que los dos operandos, por lo que la 
expresión anterior queda: +ab-5. Esto se representa con una estructura del tipo 
FIFO (First In First Out) o cola. • Las estructuras FIFO son ampliamente utilizadas, 
pero tienen problemas con el anidamiento aritmético. 
2.1.2 INFIJA 
La expresión o notación infija es la forma más común que utilizamos para escribir 
expresiones matemáticas, estas notaciones se refieren a que el operador esta entre 
los operadores. La notación infija puede estar completamente parentizada o puede 
basarse en un esquema de precedencia de operadores, así como el uso de 
paréntesis para invalidar los arreglos al expresar el orden de evaluación de una 
expresión: 
• 3 * 4 = 12 
• 3 * 4 + = 14 
• 3 * (4 + 2) = 18 
La notación infija tiene el problema de que en expresiones con más de un operador 
existe ambigüedad sobre cuál es el orden de evaluación. Por ejemplo, la expresión 
8/4/2 se puede interpretar como (8 / 4) / 2 o bien 8 / (4 / 2). Las otras notaciones no 
sufren este problema. La notación habitual. El orden es primer operando, operador, 
segundo operando. 
• La notación infija es la más utilizada por los humanos porque es la más 
comprensible ya que ponen el operador entre los dos operandos. 
• Por ejemplo, a+b-5. 
• No existe una estructura simple para representar este tipo de notación en la 
computadora por esta razón se utilizan otras notaciones. 
 
 
 
2.1.3 POSTFIJA 
Como su nombre lo indica se refiere a que el operador ocupa la posición después 
de los operandos sus características principales son: 
• El orden de los operandos se conserva igual que la expresión infija 
equivalente no utiliza paréntesis ya que no es una operación ambigua. 
• La operación posfija no es exactamente lo inverso a la operación prefija 
equivalente. 
• El orden es primer operando, segundo operando, operando. 
(A + B) * C A B + C * 
Ejemplo: Si deseamos representar las expresiones (2 + (3 * 4)) = xy ((2 + 3) * 4) = x 
en las tres notaciones mencionadas, el resultado sería: (2 + (3 * 4)) = x ((2 + 3) * 4) 
= x 
Notación postfija 
2 3 4 * + x = 
2 3 + 4 * x = 
• La notación postfija pone el operador al final de los dos operandos, por lo que 
la expresión queda: ab+5- 
• La notación postfija utiliza una estructura del tipo LIFO (Last In First Out) pila, 
la cual es la más utilizada para la implementación. 
 
 
 
 
 
 
2.2 REPRESENTACIONES DEL CÓDIGO INTERMEDIO 
En el proceso de traducir un programa fuente a código destino, un compilador puede 
construir una o más representaciones intermedias, las cuales pueden tener una 
variedad de formas. Los árboles sintácticos son una forma de representación 
intermedia; por lo general, se utilizan durante el análisis sintáctico y semántico. 
Después del análisis sintáctico y semántico del programa fuente, muchos 
compiladores generan un nivel bajo explícito, o una representación intermedia 
similar al código máquina, que podemos considerar como un programa para una 
máquina abstracta. Esta representación intermedia debe tener dos propiedades 
importantes: debe ser fácil de producir y fácil de traducir en la máquina destino. 
Existe una forma intermedia llamada código de tres direcciones, que consiste en 
una secuencia de instrucciones similares a ensamblador, con tres operandos por 
instrucción. Cada operando puede actuar como un registro. La salida del generador 
de código intermedio en la figura 2.7 consiste en la secuencia de código de tres 
direcciones. 
• 1 = inttofloat(60) 
• t2 = id3 * t1 
• t3 = id2 + t2 
• id1 = t3 
Hay varios puntos que vale la pena mencionar sobre las instrucciones de tres 
direcciones. En primer lugar, cada instrucción de asignación de tres direcciones 
tiene, por lo menos, un operador del lado derecho. Por ende, estas instrucciones 
corrigen el orden en el que se van a realizar las operaciones; la multiplicación va 
antes que la suma en el programa fuente (2.1). En segundo lugar, el compilador 
debe generar un nombre temporal para guardar el valor calculado por una 
instrucción de tres direcciones. En tercer lugar, algunas "instrucciones de tres 
direcciones" como la primera y la última en la secuencia (2.3) anterior, tienen menos 
de tres operandos. 
 
 
 
• Existen maneras formales para representar código intermedio. 
• Estas notaciones simplifican la traducción de nuestro código fuente a nuestro 
código objeto ya que ahorran y acotan símbolos de la tabla de símbolos. 
2.2.1 NOTACIÓN POLACA 
La notación polaca es la originada por un Autómata con pila, en la que los 
operadores siempre preceden a los operandos sobre los que actúan, y que tiene la 
ventaja de no necesitar paréntesis: 
• Se utiliza principalmente para la 
representación de expresiones 
aritméticas. 
• Expresión a notación polaca inversa. 
• Algoritmo 
✓ Representa la expresión en forma 
de árbol sintáctico. 
✓ Recorrer el árbol en postorden 
VENTAJAS Y DESVENTAJAS DE LA NOTACIÓN POLACA 
➢ Generación de código: simple, no utiliza registros. 
➢ Optimización: es difícil de reordenar ya que hay que considerar el contenido de la pila. 
➢ Interpretación rápida: es muy fácil de interpretar ya que solo necesita unapila. 
➢ Transportable: si, ya que todos los procesadores implementan una pila. 
La notación polaca, también conocida como notación de prefijo o notación prefija, 
es una forma de notación para la lógica, la aritmética, el álgebra y la computación. 
Su característica distintiva es que coloca los operadores a la izquierda de 
sus operandos. Si la aridad de los operadores es fija, el resultado es una sintaxis 
que carece de paréntesis u otros signos de agrupación, y todavía puede ser 
analizada sin ambigüedad. La notación polaca es la originada por un Autómata con 
pila, en la que los operadores siempre preceden a los operandos sobre los que 
actúan, y que tiene la ventaja de no necesitar paréntesis: 
 
 
 
 
 
 
 
 
2.2.2 CÓDIGO P 
• El código P hace referencia a máquinas que utilizan o se auxilian de pilas 
para generar código objeto. 
• En muchos casos la P se asociado a código portable el cual garantiza que el 
código compilado en una máquina se pueda ejecutar en otras. 
El código P comenzó como un código ensamblador objetivo estándar producido por 
varios compiladores Pascal en la década de 1970 y principios de la de 1980. Fue 
diseñado para código real para una máquina de pila hipotética la idea era hacer que 
los compiladores de Pascal se transportaran fácilmente requiriendo solo que se 
volviera a escribir el intérprete de la maquina P para una plataforma, el código P 
también a probado ser útil como código intermedio y sean utilizado varias 
extensiones y modificaciones del mismo en diversos compiladores de código nativo, 
la mayor parte para lenguaje tipo Pascal. Como el código P fue diseñado para ser 
directamente ejecutable, contiene una descripción implícita de un ambiente de 
ejecución particular que incluye tamaños de datos, además de mucha información 
específica para la maquina P, que debe conocer si se desea que un programa de 
código P se comprensible. La máquina P está compuesta por una memoria de 
código, una memoria de datos no específica para variables nombre das y una pila 
para datos temporales, junto como cualquiera registro que sea necesario para 
mantener la pila y apoyar la ejecución. Para garantizar la portabilidad del código se 
necesita que el lenguaje este estandarizado por algún instituto y que dicho código 
no tenga extensiones particulares. También se recomienda la no utilización de 
 
 
 
características especiales exclusivas de alguna arquitectura de computadoras en 
particular. 
2.2.3 TRIPLOS 
Las proposiciones de tres direcciones se parecen mucho al ensamblador, el cual es 
un lenguaje intermedio más entendible para la máquina. Las estructuras de control 
(if, switch, while, do-while, for) son realmente etiquetas goto disfrazadas. El 
problema de utilizar cuádruplos radica en que se tienen que colocar los valores 
temporales en la tabla de símbolo. Con una estructura de tres campos se pueden 
omitir los valores temporales, dicha estructura recibe el nombre de triples y tiene los 
siguientes campos: op, arg1 y arg2. Generalmente el código que generan los triples 
recibe el nombre de código de dos direcciones, aunque en ocasiones puede variar. 
Cuando se utilizan triples se ocupan punteros a la misma estructura de los triples. 
• b t1 t2 //cuádruplos. 
• * b (0) //triple. 
Se debe tener en cuenta el proceso de asignación, de declaración, expresiones 
booleanas. Las expresiones lógicas también pueden pasarse a código de tres 
direcciones, utilizando para ello expresiones en corto circuito. La evaluación de 
expresiones en corto circuito implica que se evalúan condiciones revisando valores 
anteriores; por ejemplo, para el operador AND con una condición que se detecte 
como falsa toda la expresión es falsa, en el caso del operador OR si se encuentra 
una condición verdadera todo será verdadero. La notación de tres direcciones es 
una forma abstracta de código intermedio. Esta notación se puede implementar 
como registros con campos para el operador y operadores. 
➢ <Operador>, <Operando 1>, <Operando 2> 
➢ El resultado se asocia al número de tripleta. 
➢ Ejemplo: W * X + (Y + Z) 
1. *, W, X 
2. +, Y, Z 
 
 
 
3. +, (1), (2) 
➢ Control de flujo: IF X>Y THEN Z=X ELSE Z=Y+1 
1. >, X, Y 
2. Saltar si falso, (1), 5 
3. =, Z, X 
4. Saltar,, 7 
5. +, Y, 1 
6. =, Z, (5) 
➢ Problema: La optimización supone mover tripletas y hay que recalcular las 
referencias. 
INTÉRPRETES: Los intérpretes generalmente utilizan este triplos para generar el 
código intermedio para ejecutarse una vez considerado la instrucción como válido. 
En este sentido, un compilador es más difícil de implementar ya que tendrá que 
mantener todas las estructuras generadas que en muchas ocasiones serán 
cuádruplos. 
2.2.4 CUÁDRUPLOS 
Es una estructura tipo registro con cuatros campos que se llaman: op, arg1, arg2 y 
resultado. OP tiene un código intermedio. Los operadores unarios como x: = -y no 
utilizan arg2. Generalmente arg1, arg2 y resultado son valores de tipo puntero y 
apuntan a una entrada en la tabla de símbolos. 
• <operador>, <operando1>, <operando2>, <resultado> 
• Ejemplo: (A+B) * (C+D)-E 
1. +, A, B, T1 
2. +, C, D, T2 
3. *, T1, T2, T3 
4. -, 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) 
 
 
 
2.3 ESQUEMA DE GENERACIÓN 
Los esquemas de generación son las estrategias o acciones que se deberán 
realizarse y tomarse en cuenta en el momento de generar código intermedio. Los 
esquemas de generación dependen de cada lenguaje. Tomaremos algunos 
esquemas de generación del lenguaje C. 
EXPRESIONES 
INSTRUCCIONES DE CONTROL: Para generar expresiones estas deben 
representarse de manera más simple y más literal para que su conversión sea más 
rápida. Por ejemplo, la traducción de operaciones aritméticas debe especificarse 
una por una, de tal forma que una expresión sea lo más mínimo posible. Son 
aquellas que asignan un valor a una variable o una expresión ejemplo: X = 23 ó Y = 
expresión 
INSTRUCCION DE ASIGNACION: Las funciones son un grupo de instrucciones con 
un propósito en general las cuales pueden recibir parámetros, mientras que la 
estructura es un conjunto de datos elementales interrelacionados que realizan 
ciertas operaciones entre ellos 
VARIABLES Y CONSTANTES: Las declaraciones de variables y constantes deben 
separarse de tal manera que queden las expresiones una por una de manera simple. 
Los esquemas de generación son las estrategias o acciones que se deberán 
realizarse y tomarse en cuenta en el momento de generar código intermedio. Son 
aquellas que permiten modificar o variar el flujo de ejecución de un programa, 
existen 3 tipos los cuales son: 
• Instrucciones condicionales o alternativas 
• Instrucciones de salto 
• Instrucciones repetitivas 
 
 
 
2.3.1 VARIABLES Y CONSTATES 
Las variables y constantes deben separarse de tal manera que queden las 
expresiones una por una de manera simple. 
• Por ejemplo, int a, b, c; se descompone a int a; int b; int c; respectivamente. 
Las declaraciones de variables y constantes deben separarse de tal manera que 
queden las expresiones una por una de manera simple. 
• Por ejemplo, int a, b, c; se descompone a int a; int b; int c; respectivamente. 
Las variables utilizadas en los programas se clasifican en dos tipos: 
• VARIABLES LOCALES: Aquella que está declarada para el programa o 
algoritmo completo. Para definir variables locales, la definición debe hacerse 
inmediatamente después de una llave de inicio ({), y la variable deja de existir 
fuera de la llave de fin (}) que corresponde a la llave de inicio después del 
cuál fue definida la variable. 
Ejemplo: 
{ 
int a,b; 
a=5; 
b=a + 100; 
} 
• VARIABLES GLOBALES: Aquella que está declarada y definida dentro de 
una función y sólo es válida dentro de la misma función yno podrá utilizarse 
en otra parte del programa. Una variable global se declara fuera de cualquier 
función y primero que cualquier función que requiera de ella. Una variable se 
declara de la siguiente forma: tipo identificador1, identificador2..ident n; 
Ejemplos: Algunos ejemplos de cómo definir variables son los siguientes: 
• int alumnos, contador; 
• float A,B,C; 
 
 
 
• char Letra; 
DECLARACION DE CONSTANTES: Para declarar constantes en el lenguaje C, 
sólo basta anteponer el calificador const seguido del tipo de dato que manejará esa 
constante (int, char, etc.), y por último el valor que tomará esa variable. 
Ejemplo: const int k = 12 
2.3.2 EXPRESIONES 
Para generar expresiones estas deben representarse de manera más simple y más 
literal para que su conversión sea más rápida. Por ejemplo, la traducción de 
operaciones aritméticas debe especificarse una por una, de tal forma que una 
expresión sea lo más mínimo posible. 
En esta función recibe una cadena que representa una línea de código intermedio 
y toma las medidas oportunas para que ese código se utilice. Estas medidas pueden 
ser escribir la línea en un fichero adecuado, almacenar la instrucción en una lista 
que después se pasará a otros módulos, o cualquier otra que necesitemos en 
nuestro compilador. 
En esta función recibe una cadena que representa una línea de código intermedio 
y toma las medidas oportunas para que ese código se utilice. Estas medidas pueden 
ser escribir la línea en un fichero adecuado, almacenar la instrucción en una lista 
que después se pasará a otros módulos, o cualquier otra que necesitemos en 
nuestro compilador. 
EXPRESIONES ARITMÉTICAS: Son aquella donde los operadores que intervienen 
en ella son numéricos, el resultado es un número y los operadores son aritméticos. 
Los operadores aritméticos más comúnmente utilizados son: +, -, *, / y %. 
Comenzamos el estudio por las expresiones aritméticas. Lo que tendremos que 
hacer es crear por cada tipo de nodo un método que genere el código para calcular 
la expresión y lo emita. Ese código dejará el resultado en un registro, cuyo nombre 
 
 
 
devolverá el método como resultado. Para reservar estos registros temporales, 
utilizaremos una función, reserva. En principio bastar ‘a con que esta función 
devuelva un registro distinto cada vez que se la llame. 
Cada nodo generará el código de la siguiente manera: 
• Por cada uno de sus operandos, llamara al método correspondiente para que 
se evalúe la sub expresión. Si es necesario, reservara un registro para 
guardar su resultado.} 
• Emitirá las instrucciones necesarias para realizar el cálculo a partir de los 
operandos. 
• Para generar expresiones estas deben representarse de manera más simple 
y más literal para que su conversión sea más rápida. 
• Por ejemplo, la traducción de operaciones aritméticas debe especificarse una 
por una, de tal forma que una expresión sea lo más mínimo posible. 
2.3.3 INSTRUCCIÓN DE ASIGNACIÓN 
La sintaxis general de la instrucción de asignación es: nombre_de_la_variable = 
valor 
El valor a la derecha del signo igual puede ser una constante, otra variable o una 
expresión que combine constantes y variables, pero siempre la variable y su valor 
deben ser del mismo tipo de dato. 
Ejemplos: 
edad% = 5 
área! = 12.3 
nombre$ = “Pedro” 
INSTRUCCIONES DE ASIGNACIÓN COMPUESTA: Las instrucciones de 
asignación compuesta realizan primero una operación en una expresión antes de 
 
 
 
asignarla a un elemento de programación. En el siguiente ejemplo se muestra uno 
de estos operadores, +=, que incrementa el valor de la variable del lado izquierdo 
del operador con el valor de la expresión de la derecha. Una instrucción de 
asignación asigna el valor de una expresión a una variable. En general, si la variable 
que se va a asignar es una propiedad, la propiedad debe ser de lectura y escritura 
o de sólo escritura; en caso contrario, se produce un error de compilación. Si la 
variable es una variable de sólo lectura, la asignación debe producirse en un 
constructor Shared o un constructor de instancia apropiado para el tipo de la variable; 
en caso contrario, se producirá un error de compilación. 
Las operaciones de asignación deben quedar expresadas por una expresión 
sencilla, si está es compleja se debe reducir hasta quedar un operador sencillo. Por 
ejemplo: x = a + b / 5; debe quedar de la forma y = b / 5; z = a + y; x = z. 
2.3.4 INSTRUCCIONES DE CONTROL 
Esta forma de programación sólo permite resolver problemas sencillos. Para 
resolver problemas más complejos, nos puede interesar que, dependiendo de los 
valores de los datos, se ejecuten unas instrucciones u otras. 
Las instrucciones condicionales nos van a permitir representar este tipo de 
comportamiento. Sentencias IF y SWITCH. En otros casos, nos encontraremos con 
la necesidad de repetir una instrucción o instrucciones un número determinado de 
veces. En estos casos utilizaremos instrucciones de control iterativas o repetitivas 
(ciclos). Sentencias WHILE, DO-WHILE y FOR. En los lenguajes de programación 
hay estructuras y operadores que permiten controlar el flujo de la ejecución, estos 
pueden ser ciclos, saltos, condiciones entre otros. 
EXPRESIONES BOOLEANAS: En los lenguajes de programación, las expresiones 
booleanas tienen dos propósitos principales. Se utilizan para calcular valores 
lógicos y como expresiones condicionales en proposiciones que alteran el flujo del 
control, como las proposiciones if-else o do-while. Las expresiones booleanas se 
componen de los operadores boleanos (and, or y not) aplicados a los elementos 
 
 
 
que son variables booleanas o expresiones relacionales. Algunos lenguajes 
permiten expresiones más generales donde se pueden aplicar operadores 
booleanos, aritméticos y relacionales a expresiones de cualquier tipo, sin diferenciar 
valores booleanos de aritméticos; si es necesario se realiza una coerción. Saltos En 
el código de los saltos los operadores lógicos &&, y! son traducidos a saltos, aunque 
estos no aparecen realmente en el código. Por ejemplo, la expresión: if (x < 00 x > 
200 && x! = y ) x=0; se puede traducir como las siguientes instrucciones: If x < 00 
goto L2 If False x > 200 goto L If False x!= y goto L L2: x =0 L: Si la expresión es 
verdadera se alcanza la etiqueta L2 y se realiza la asignación. 
• Las condiciones deben expresarse de manera lo más sencilla posible de tal 
forma que puedan evaluarse en cortocircuito. Por ejemplo, una instrucción 
como: if (a == b && f! =5 && f%3 == 0) se evalúa primero x = (a==b && f! = 5) 
y = x && f%3 == 0; if (y). Las instrucciones de decisión compleja como switch 
se reducen a una versión complejas de if’s 
• Los ciclos se descomponen en un ciclo genérico, por lo que ciclos while, for 
y do-while tienen la misma representación interna. En el caso de C, todo 
queda en forma de while. Las condiciones lógicas también pueden ser 
evaluadas en cortocircuito y reducidas. 
2.3.5 FUNCIONES 
Las funciones pueden reducir a en línea, lo que se hace que expandir el código 
original de la función. Las funciones se descomponen simplificando los parámetros 
de manera individual al igual que el valor de retorno. Las funciones se descomponen 
simplificando los parámetros de manera individual al igual que el valor de retorno. 
Entendemos que es el uso de la lengua que hace un hablante. En simples palabras, 
las funciones del lenguaje son los diferentes objetivos, propósitos y servicio que se 
le da al lenguaje al comunicarse, dándose una función del lenguaje por cada factor 
que tiene éste, en donde la función que prevalece es el factor en donde más se 
pone énfasis al comunicarse. Diversos lingüistas (Karl Bühler, Roman Jakobson, 
 
 
 
Michael Halliday) han propuesto distintas clasificaciones de las funciones del 
lenguaje: Bühler propuso que existían únicamente tres funciones: 
• LA REPRESENTATIVA: (por la cualse trasmiten informaciones 
objetivamente). 
• LA EXPRESIVA O EMOTIVA: (que expresa sentimientos del emisor). 
• LA CONATIVA: mediante la que se influye en el receptor del mensaje a través 
de órdenes, mandatos o sugerencias 
• ESTRUCTURAS: El código intermedio no es el lenguaje de programación de 
ninguna máquina real, sino que corresponde a una máquina abstracta, que 
se debe de definir lo más general posible, de forma que sea posible traducir 
este código intermedio a cualquier máquina real. El objetivo del código 
intermedio es reducir el número de programas necesarios para construir 
traductores, y permitir más fácilmente la transportabilidad de unas máquinas 
a otras. Supóngase que se tienen n lenguajes, y se desea construir 
traductores entre ellos. Sería necesario construir n*(n-) traductores. Sin 
embargo, si se construye un lenguaje intermedio, tan sólo son necesarios 2*n 
traductores. Así por ejemplo un fabricante de compiladores puede construir 
un compilador para diferentes máquinas objeto con tan sólo cambiar las dos 
últimas fases de la tarea de síntesis. 
2.3.6 ESTRUCTURAS 
ESTRUCTURA Y FASES DE UN COMPILADOR 
1. ANÁLISIS LINEAL: También conocido como: análisis léxico o exploración. 
Ejemplo, en la proposición de asignación: posición = inicial + velocidad * 60 
Se identifican los siguientes componentes léxicos: 
• Identificador (posición) 
• Símbolo de asignación (=) 
• Identificador (inicial) 
• Signo de suma (+) 
 
 
 
• Identificador (velocidad) 
• Signo de multiplicación (*) 
• Número (60). 
2. ANÁLISIS JERÁRQUICO: También llamado análisis sintáctico. Implica 
agrupar los componentes léxicos en frases gramaticales que el compilador 
utiliza para sintetizar la salida. Por lo general, las frases gramaticales se 
representan mediante un árbol de análisis sintáctico. Ejemplo: 
• Proposición de asignación 
• Identificador posición = expresión 
• expresión identificadora + expresión inicial 
• expresión identificadora * expresión velocidad Número 60 
3. LA ESTRUCTURA JERÁRQUICA: La estructura jerárquica de un programa 
normalmente se expresa utilizando reglas recursivas. Para el ejemplo 
anterior de la proposición de asignación se tiene: Cualquier identificador es 
una expresión Cualquier número es una expresión Si expresión1 y 
expresión2 son expresiones, entonces también lo son: 
• expresión1 + expresión2 
• expresión1 * expresión2 
• (expresión1) Proposición de asignación 
• Identificador posición = expresión 
• expresión identificadora + expresión inicial 
• expresión identificadora * expresión velocidad Número 60 
4. LENGUAJES: Muchos lenguajes definen recursivamente las proposiciones 
mediante reglas como: Si identificador1 es un identificador y expresión2 es 
un identificador, entonces: 
• Identificador1 = expresión2 Si expresión1 es una expresión y 
proposición2 es una proposición 
• Entonces: while (expresión1) do proposición2 if (expresión1) then 
proposición2 
 
 
 
• El análisis lineal (léxico) no es suficientemente poderoso para analizar 
proposiciones o expresiones recursivas. Cuando una construcción del 
lenguaje fuente es recursiva, entonces es factible emplear una 
gramática libre de contexto para formalizar la recursión. 
5. ANÁLISIS SEMÁNTICO: Revisa el programa e intenta encontrar errores 
semánticos. Reúne la información sobre los tipos para la fase posterior de 
generación de código. Un componente importante es la verificación de tipos. 
Se verifica si cada operador tiene los operandos permitidos. Un real no debe 
utilizarse como índice de un arreglo. Convertir un número entero a real para 
algunos operadores. = posición + inicial * velocidad 60 = posición + inicial * 
velocidad int a real 60 El análisis semántico inserta una conversión de entero 
a real en el árbol de análisis sintáctico 
6. COMPILADOR: Conceptualmente un compilador opera en fases, cada una 
de las cuales transforma al programa fuente de una representación a otra. 
Analizador léxico Programa fuente Analizador sintáctico Analizador 
semántico Generador de código intermedio Optimizador de código 
Generador de código Programa objeto Manejador de errores Administrador 
de la Tabla de símbolos. 
7. ADMINISTRACIÓN DE LA TABLA DE SÍMBOLOS: Registra los 
identificadores e información referente a ellos. Se tiene un registro por cada 
identificador. Todas las fases hacen uso de esta tabla. Detección e 
información de errores En cada fase se pueden encontrar errores. Se debe 
definir como se deben tratar los errores en cada una de las fases. Las fases 
de análisis Cambian la representación interna del programa fuente conforme 
avanza cada una de ellas. Generación de código intermedio Se puede 
considerar como código para una máquina abstracta. Dicha representación 
debe ser fácil de producir y fácil de traducir al código objeto. Optimización de 
código Trata de mejorar el código intermedio de modo que resulte un código 
máquina más rápido de ejecutar. Generación de código Por lo general se 
trata de código máquina relocalizable o código ensamblador. Se deben 
seleccionar posiciones de memoria para cada una de las variables: 
 
 
 
• posición = inicial + velocidad * 60 
• Analizador léxico id1 = id2 + id3 * 60 
• Analizador sintáctico = id1 + id2 * id3 60 
• Analizador semántico = id1 + id2 * id3 ent a real 60 
• Generador de código intermedio temp1 = entre al (60) temp2 = id3 * 
temp1 temp3 = id2 +temp2 Id1 = temp3 
• Optimizador de código temp1 = id3 * 60.0 temp2 = id2 +temp1 Id1 = 
temp2 
• Generador de código: 
➢ MOVF id3 
➢ R2 MULF #60.0 
➢ R2 MOVF id2 
➢ R1 ADDF R2 
➢ R1 MOV R1 
➢ id1 
• TABLA DE SIMBOLOS posición … inicial … velocidad … 1 2 3 4 
8. Con frecuencia las fases de un compilador se agrupan en una etapa inicial y 
una etapa final: 
• ETAPA INICIAL: 
➢ Comprende aquellas fases que dependen principalmente del 
código fuente. 
➢ Normalmente incluye el análisis léxico, sintáctico y semántico, 
la creación de la tabla de símbolos, la generación de código 
intermedio y cierta optimización de éste. 
➢ También incluye el manejo de errores correspondientes a cada 
etapa. 
• ETAPA FINAL: 
➢ Comprende aquellas partes del compilador que dependen de la 
máquina objeto. 
➢ En general estas partes dependen del lenguaje intermedio, más 
que del lenguaje fuente. 
 
 
 
➢ Comprende aspectos de optimización y generación de código, 
junto con el manejo de errores necesario y las operaciones con 
la tabla de símbolos. 
➢ CLR Architecture. 
➢ PNG. 
9. Pasadas Consiste en leer un archivo de entrada y escribir uno de salida: 
• Es común que se apliquen varias fases de la compilación en una sola 
pasada Reducción de pasadas. 
• Es deseable tener pocas pasadas dado que la lectura y la escritura de 
archivos intermedios lleva tiempo. 
• Sin embargo, en ocasiones resulta muy difícil generar código si no se 
tiene una representación intermedia completa. 
• Por ejemplo: Las instrucciones de tipo goto que saltan hacia delante. 
En este caso es posible dejar un espacio en blanco y rellenar cuando 
la información esté disponible 
 
 
 
 
 
 
 
 
 
 
 
ACTIVIDAD 1. APLICAR LOS TIPOS DE NOTACIÓN PARA LA 
CONVERSIÓN DE EXPRESIONES: INFIJA, PREFIJA Y POSTFIJA 
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 + 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. 
Tabla 2: Ejemplos en notación infija, prefija y sufija 
Expresión infija Expresión prefija Expresión sufija 
A + B + A B A B + 
A + B * C + A * B C A B C * + 
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 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#tbl-example1
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#tbl-parexample
 
 
 
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 * + A B C A B + C * 
La Tabla 4 muestra algunos ejemplos adicionales de expresiones infijas y las 
expresiones equivalentes 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) * + A B + C D A B + C D + * 
A * B + C * D + * A B * C D A B * C D * + 
A + B + C + D + + + A B C D A B + C + D + 
3.9.1. 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 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#tbl-example3
 
 
 
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 subexpresió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 
subexpresió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). 
 
Figura 6: Traslado de operadores a la derecha para producir la notación sufija 
Figura 6: Traslado de operadores a la derecha para producir la notación sufija 
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. 
 
Figura 7: Traslado de operadores a la izquierda para producir la notación prefija 
Figura 7: Traslado de operadores a la izquierda para producir la notación prefija 
Así que, para convertir una expresión, independientemente de su complejidad, ya 
sea a notación prefija o a notación sufija, agrúpelacompletamente 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. 
La siguiente es una expresión más compleja: (A + B) * C - (D - E) * (F + G). La Figura 
8 muestra la conversión a las notaciones sufija y prefija. 
 
Figura 8: Conversión de una expresión compleja a notaciones prefija y sufija 
Figura 8: Conversión de una expresión compleja a notaciones prefija y sufija 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-moveright
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-moveleft
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-complexmove
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-complexmove
 
 
 
3.9.2. 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. 
 
 
 
1. Crear una pila vacía llamada pilaOperadores para almacenar los operadores. 
Crear una lista vacía para almacenar la salida. 
2. Corvertir 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. 
No obstante, extraer previamente de la pila los operadores que tengan 
mayor o igual precedencia y agregarlos 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. 
 
Figura 9: Conversión de A * B + C * D a notación sufija 
Figura 9: Conversión de A * B + C * D a notación sufija 
Para codificar el algoritmo en Python, usaremos un diccionario 
llamado precedencia para almacenar los valores de precedencia para los 
operadores. Este diccionario mapeará cada operador a un entero que se pueda 
comparar con los niveles de precedencia de otros operadores (hemos utilizado 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-intopost
 
 
 
arbitrariamente los números enteros 3, 2 y 1). El paréntesis izquierdo recibirá el valor 
más bajo posible. De esta manera cualquier operador que se compara con él tendrá 
mayor precedencia y se colocará encima de él. La línea 15 define los operandos 
como cualquier carácter en mayúsculas o dígito. La función de conversión completa 
se muestra en el ActiveCode 1. 
1 
from pythoned.basicas.pila import Pila 
2 
 
3 
def infija_a_sufija(expresionInfija): 
4 
 precedencia = {} 
5 
 precedencia["*"] = 3 
6 
 precedencia["/"] = 3 
7 
 precedencia["+"] = 2 
8 
 precedencia["-"] = 2 
9 
 precedencia["("] = 1 
10 
 pilaOperadores = Pila() 
11 
 listaSufija = [] 
12 
 listaSimbolos = expresionInfija.split() 
13 
 
14 
 for simbolo in listaSimbolos: 
15 
 if simbolo in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or simbolo in "0123456
789": 
16 
 listaSufija.append(simbolo) 
17 
 elif simbolo == '(': 
18 
 pilaOperadores.incluir(simbolo) 
19 
 elif simbolo == ')': 
20 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#lst-intopost
 
 
 
 simboloTope = pilaOperadores.extraer() 
21 
 while simboloTope != '(': 
22 
 listaSufija.append(simboloTope) 
23 
 simboloTope = pilaOperadores.extraer() 
24 
 else: 
25 
 while (not pilaOperadores.estaVacia()) and \ 
26 
 (precedencia[pilaOperadores.inspeccionar()] >= \ 
27 
 precedencia[simbolo]): 
28 
 listaSufija.append(pilaOperadores.extraer()) 
29 
 pilaOperadores.incluir(simbolo) 
30 
 
31 
 while not pilaOperadores.estaVacia(): 
32 
 listaSufija.append(pilaOperadores.extraer()) 
33 
 return " ".join(listaSufija) 
34 
 
 
A continuación se muestran algunos ejemplos de ejecución en la consola de Python. 
>>> infija_a_sufija("( A + B ) * ( C+ D )") 
'A B + C D + *' 
>>> infija_a_sufija("( A + B ) * C") 
'A B + C *' 
>>> infija_a_sufija("A + B * C") 
'A B C * +' 
>>> 
 
 
 
3.9.3. 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. 
 
Figura 10: Contenido de la pila durante la evaluación 
Figura 10: Contenido de la pila durante la evaluación 
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 subexpresiones 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. 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-evalpost1
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#fig-evalpost2
 
 
 
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/515/5 no es lo 
mismo que 5/155/15, debemos estar seguros de que el orden de los operandos no 
esté intercambiado. 
 
Figura 11: Un ejemplo más complejo de evaluación 
Figura 11: Un ejemplo más complejo de evaluación 
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. 
1 
from pythoned.basicas.pila import Pila 
2 
 
3 
def evaluacionNotacionSufija(expresionSufija): 
4 
 pilaOperandos = Pila() 
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#id1
https://runestone.academy/runestone/static/pythoned/BasicDS/ExpresionesInfijasPrefijasYSufijas.html#lst-postfixeval
 
 
 
5 
 listaSimbolos = expresionSufija.split() 
6 
 
7 
 for simbolo in listaSimbolos: 
8 
 if simbolo in "0123456789": 
9 
 pilaOperandos.incluir(int(simbolo)) 
10 
 else: 
11 
 operando2 = pilaOperandos.extraer() 
12 
 operando1 = pilaOperandos.extraer() 
13 
 resultado = hacerAritmetica(simbolo,operando1,operando2) 
14 
 pilaOperandos.incluir(resultado) 
15 
 return pilaOperandos.extraer() 
16 
 
17 
def hacerAritmetica(operador, operandoIzquierda, operandoDerecha): 
18 
 if operador == "*": 
19 
 return operandoIzquierda * operandoDerecha 
20 
 elif operador == "/": 
21 
 return operandoIzquierda / operandoDerecha 
22 
 elif operador == "+": 
23 
 return operandoIzquierda + operandoDerecha 
24 
 else: 
25 
 return operandoIzquierda - operandoDerecha 
26 
 
27 
print(evaluacionNotacionSufija('7 8 + 3 2 + /')) 
 
 
 
28 
 
Es importante tener en cuenta que tanto en el programa de conversión de 
expresiones sufijas como en el programa de evaluación de expresiones sufijas 
asumimos que no había errores en la expresión de entrada. Utilizando estos 
programas como punto de partida, usted puede fácilmente pensar cómo podría 
incluirse una detección de errores y la generación de informes. Dejamos esto como 
un ejercicio para el final del capítulo. 
 
 
ACTIVIDAD 2. REPRESENTAR EXPRESIONES MEDIANTE EL 
CÓDIGO INTERMEDIO 
EL código fuente puede ser traducido en su código de la máquina destino, entonces, 
¿por qué hemos de traducir el código fuente en un código intermedio que luego se 
traduce en su código de destino? Vamos a ver las razones por las que necesitamos 
un código intermedio. 
 
• Si un compilador traduce el idioma de origen a su ordenador de destino sin 
tener la opción de generar código intermedio, a continuación, en cada nueva 
máquina, una nativa del compilador completo es necesario. 
• Código Intermedio elimina la necesidad de un nuevo compilador completo 
para cada máquina de la sección de análisis mismo de todos los 
compiladores. 
• La segunda parte del compilador, síntesis, se modifica de acuerdo a la 
máquina de destino. 
• Es más fácil de aplicar las modificaciones del código fuente para mejorar 
rendimiento del código mediante la aplicación de técnicas de optimización 
código el código intermedio. 
 
 
 
Representación intermedia 
Códigos intermedios puede ser representado en una variedad de formas y tienen 
sus propios beneficios. 
• Alto nivel IR - Alto nivel de representación de código intermedio está muy 
cerca de la lengua de origen. Pueden ser fácilmente generados desde el 
código fuente y podemos aplicar fácilmente modificaciones de código para 
mejorar el rendimiento. Pero para optimización de la máquina destino, es 
menos preferido. 
• Bajo Nivel IR - Este es cerca de la máquina de destino, lo que lo hace 
adecuado para registro y asignación de memoria, un conjunto de 
instrucciones selección, etc. es bueno para optimizaciones dependientes de 
la máquina. 
Código intermedio puede ser específica para cada idioma (p. ej., código de bytes 
de Java) o independiente de la lengua (tres-código de dirección). 
Código Three-Address 
Generador de código intermedio recibe la entrada de su predecesor, analizador 
semántico, en la formade un árbol de sintaxis anotado. Árbol de sintaxis que luego 
se puede convertir en una representación lineal, por ejemplo, postfix notación. 
Código intermedio tiende a ser código independiente de la máquina. Por lo tanto, 
generador de código supone que tiene número ilimitado de almacenamiento en 
memoria (registro) para generar el código. 
Por ejemplo: 
a = b + c * d; 
El generador de código intermedio, tratar de dividir esta expresión en sub-
expresiones y, a continuación, generar el código correspondiente. 
r1 = c * d; 
r2 = b + r1; 
r3 = r2 + r1; 
a = r3 
R que se utilizan como registros en el programa de destino. 
Un código de dirección tiene un máximo de tres direcciones para calcular la 
expresión. Un código de dirección puede estar representado en dos formas : 
cuádruples y triples. 
Cuadruplica 
Cada instrucción cuadruplica exposición se divide en cuatro campos: operador, 
arg1, arg2, y resultado. El ejemplo anterior se representa a continuación 
cuadruplica en formato: 
 
 
 
Op. Arg1 Arg2 Resultado 
* c d r1 
+ b r1 r2 
+ r2 r1 r3 
= r3 
 
a 
Triples 
Cada instrucción en triples presentación tiene tres campos : op, arg1, arg2.Los 
resultados de las respectivas sub-expresiones son indicados por la posición de 
expresión. Similitud con Triples representan DAG y árbol de sintaxis. Son 
equivalentes a DAG al tiempo que representan las expresiones. 
Op Arg1 Arg2 
* c d 
+ b (0) 
+ (1) (0) 
= (2) 
 
Triples ante el problema de optimización código un inmovilismo mientras que, en 
la medida en que los resultados son posicionales y cambiar el orden o la posición 
de una expresión puede causar problemas. 
 
 
 
Indirectos Triples 
Esta representación es una mejora sobre representación triples. Se usa punteros 
en lugar de su posición para almacenar los resultados. Esto permite a los 
optimizadores libremente volver a colocar la sub-expresión para producir un código 
optimizado. 
Declaraciones 
Una variable o procedimiento tiene que ser declarado antes de que se pueda 
utilizar. Declaración implica asignación de espacio en la memoria y la entrada de 
tipo y nombre de la tabla de símbolos. Un programa puede ser codificada y 
diseñado siguiendo la estructura de la máquina destino en mente, pero es posible 
que no siempre se pueda convertir con precisión un código fuente para su idioma 
de destino. 
Tomando el conjunto del programa, como una colección de procedimientos y sub-
procedimientos, es posible declarar que todos los nombres locales en el 
procedimiento. Asignación de memoria se realiza de manera consecutiva y 
nombres son asignados a la memoria en la secuencia en la que se declara en el 
programa. Podemos utilizar el desplazamiento variable y ponerlo a cero {offset = 0} 
que denotan la dirección base. 
La fuente lenguaje de programación y la arquitectura del equipo de destino puede 
variar en la forma los nombres se almacenan, por lo tanto se utiliza 
direccionamiento relativo. Mientras que el primer nombre se asigna memoria a 
partir de la posición de memoria 0 {offset= 0}, el siguiente nombre declaró después, 
debe ser asignada la memoria junto a la primera. 
Ejemplo: 
Tomamos el ejemplo de lenguaje de programación C en una variable de tipo entero 
se le asigna 2 bytes de memoria y una variable de tipo float se asigna 4 bytes de 
memoria. 
int a; 
float b; 
Allocation process: 
{offset = 0} 
 int a; 
 id.type = int 
 id.width = 2 
offset = offset + id.width 
{offset = 2} 
 float b; 
 id.type = float 
 id.width = 4 
offset = offset + id.width 
{offset = 6} 
 
 
 
Para entrar en este detalle en una tabla de símbolos, un procedimientoentrar puede 
ser utilizado. Este método puede tener la siguiente estructura: 
enter(name, type, offset) 
Este procedimiento debe crear una entrada en la tabla de símbolos, de nombre de 
la variable, en su tipo y el tipo de desplazamiento de dirección relativa en su área 
de datos. 
 
 
 
ACTIVIDAD 3. RECONOCER EL MANEJO DE TIPOS EN LAS 
EXPRESIONES Y EL USO DE OPERADORES 
Traducción de una expresión en un arbol binario 
Para nuestro problema una expresión matemática será un medio que permite indicar el 
orden en que se deben realizar una serie de operaciones para obtener un resultado. Las 
operaciones se indican mediante operadores, que en nuestro caso representan las 
operaciones suma, resta, producto, división e igualdad, todas ellas operaciones binarias 
(necesitan exactamente dos argumentos para poderse evaluar). 
Existen varias notaciones para representar expresiones matemáticas, que se diferencian en 
el orden en que se escriben los argumentos (operandos) de los operadores. Las más 
relevantes son: 
• Notación infija: La notación habitual. El orden es primer operando, operador, segundo 
operando. 
• Notación prefija: El orden es operador, primer operando, segundo operando. 
• Notación postfija: El orden es primer operando, segundo operando, operador. 
• Notación funcional: Se escribe el operador/función y despues, entre paréntesis, los 
operadores separados por comas. 
La notación infija tiene el problema de que en expresiones con más de un operador existe 
ambiguedad sobre cual es el orden de evaluación. Por ejemplo, la expresión 8/4/2 se puede 
interpretar como (8/4)/2 o bien como 8/(4/2). Las otras notaciones no sufren este problema. 
Para resolver estas ambiguedades, se añaden unas reglas denominadas orden de 
precedencia de operadores. Cuando dos operadores compiten por el mismo operando (en el 
ejemplo anterior, el primer y el segundo operador de división se disputan el operando 4) 
gana el el operador (se evalúa primero) con mayor precedencia, o a igualdad de 
precedencia, el operador situado más a la izquierda. 
 
 
 
Las reglas de precedencia habituales son que los operadores división y producto tienen 
igual precedencia y ganan al resto de operadores, y que los operadores suma y resta tienen 
igual precedencia y ganan al operador igualdad. 
Así, la expresión 8/4/2 se evalúa como (8/4)/2, y 2+3*4 se evalúa como 2+(3*4). Si 
deseamos cambiar el orden de evaluación, se pueden agrupar partes de una expresión 
utilizando paréntesis. En el resto de las notaciones no es necesario utilizar paréntesis ya que 
siempre podemos indicar el orden exacto de evaluación sin que exista ambiguedad. 
Por ejemplo, si deseamos representar las expresiones (2+(3*4)) = x y ((2+3)*4)= x en las 
cuatro notaciones mencionadas, el resultado sería: 
 (2+(3*4)) = x ((2+3)*4) = x 
Notación prefija = + 2 * 3 4 x = * + 2 3 4 x 
Notación infija 2+3*4 = x (2+3)*4 = x 
Notación postfija 2 3 4 * + x = 2 3 + 4 * x = 
Notación funcional igual(suma(2,producto(3,4)),x) igual(producto(suma(2,3),4),x) 
Generalmente a la hora de traducir una expresión en notación infija a su representación 
como arbol binario se suele efectuar un primer paso de traducción a una notación más 
adecuada (generalmente a notación prefija o postfija), y luego se traduce la expresión en 
esa notación a arbol binario. 
Las dos etapas anteriores se pueden realizar directamente mediante un algoritmo recursivo, 
o en dos pasos utilizando estructuras adicionales (generalmente pilas). 
2. Algoritmo recursivo 
Es posible traducir directamente una expresión en notación infija a un arbol binario 
mediante uno o varios subprogramas recursivos, aunque el algoritmo no es trivial. En lugar 
de intentar desarrollar un único subprograma que analize completamente una expresión, 
suele ser más sencillo utilizar un enfoque ligeramente distinto, utilizando dos 
subprogramas: 
• El primero de ellos se encargaría de asignar el operando derecho a un operador, el cual se 
proporciona como un arbol binario al que le falta el hijo derecho, utilizando para ello la lista de 
términos correspondiente a la parte de la expresión que falta por traducir. El resultado del 
subprograma será el arbol binario completado y la lista de términos que faltan por analizar. 
• El segundo subprograma traduce parte o toda una expresiónen un arbol binario, que pasa a 
considerarse como operando. Una expresión en notación infija responde al esquema N1 O1 N2 
O2 N3..., donde los términos Ni son operandos y los t&eacuterminos Oi operadores. Este 
 
 
 
subprograma construiríia el arbol binario asignando N1 como operando izquierdo de O1, y 
llamaría al subprograma anterior para encontrar el operando derecho de O1. Por ejemplo, en 
la expresión 2*3+4, el operando derecho del producto es 3, pero en la expresión 2+3*4 el 
operando derecho de la suma es el arbol binario (3*4). 
• Si en algun momento aparece un paréntesis izquierdo en lugar de un operando, se llamaría al 
segundo subprograma para que traduzca esa subexpresión al arbol binario correspondiente, 
que pasa a considerarse como el operando que faltaba. 
3. Conversion de notacion infija a postfija 
El siguiente algoritmo en pseudocódigo traduce una expresión en notación infija a notación 
postfija, como paso previo a la obtención del arbol binario correspondiente a la expresión: 
• Entrada: Una lista que contiene los terminos de la ecuacion en notación infija (la notación 
habitual). 
• Salida: Una lista que contiene los terminos de la ecuacion en notacion postfija. 
• Datos locales: Una pila, que va a contener operadores y parentesis izquierdos. 
 INICIO 
 Crear pila y la lista de salida, inicialmente vacias. 
 MIENTRAS lista de entrada no este vacia y 
 no se ha encontrado ningun error HACER 
 Extraer el primer termino de la lista (lo llamaremos E) 
 SEGUN-SEA E 
 CASO E es número : 
 Insertar E al final de la lista de salida 
 CASO E es la variable x : 
 Insertar E al final de la lista de salida 
 CASO E es un paréntesis izquierdo : 
 Insertar E en la pila 
 CASO E es un paréntesis derecho : 
 MIENTRAS La pila no este vacía y 
 su cima no sea un paréntesis izquierdo HACER 
 Extraer elemento de la pila 
 Insertarlo al final de la lista de salida 
 FIN-MIENTRAS 
 SI Encontramos el parentesis izquierdo ENTONCES 
 Extraerlo de la pila y destruirlo 
 SINO 
 Se ha detectado un ERROR 2 
 FIN-SI 
 Destruir E 
 CASO E es un operador : 
 MIENTRAS La pila no este vacía y 
 su cima sea un operador 
 de precedencia mayor o igual que la de E HACER 
 Extraer elemento de la pila 
 Insertarlo al final de la lista de salida 
 FIN-MIENTRAS 
 Insertar E en la pila 
 FIN-SEGUN-SEA 
 FIN-MIENTRAS 
 MIENTRAS Pila no esté vacía HACER 
 
 
 
 Extraer elemento de la pila 
 Insertarlo al final de la lista de salida 
 FIN-MIENTRAS 
 Destruir pila 
 FIN 
A continuación se muestra el estado de la lista de entrada, la lista de salida y la pila en cada 
iteración del bucle principal del algoritmo al dar como entrada la lista de términos 
correspondiente al ejemplo del enunciado de la práctica. En color rojo se muestra el 
término que se procesa en cada iteración, y en color verde los términos que se han añadido 
a la lista de salida o a la pila como consecuencia de las acciones realizadas en la iteración 
anterior: 
-4 * ( -5 - 2 ) / ( -1 * x - -3 ) = -1 / -2 
 
* ( -5 - 2 ) / ( -1 * x - -3 ) = -1 / -2 
 
 -4 
 
 
( -5 - 2 ) / ( -1 * x - -3 ) = -1 / -2 
 
 -4 
 
 * 
 
-5 - 2 ) / ( -1 * x - -3 ) = -1 / -2 
 
 -4 
 
 ( * 
 
- 2 ) / ( -1 * x - -3 ) = -1 / -2 
 
 -4 -5 
 
 ( * 
 
2 ) / ( -1 * x - -3 ) = -1 / -2 
 
 -4 -5 
 
 - ( * 
 
) / ( -1 * x - -3 ) = -1 / -2 
 
 -4 -5 2 
 
 - ( * 
 
/ ( -1 * x - -3 ) = -1 / -2 
 
 -4 -5 2 - 
 
 * 
 
( -1 * x - -3 ) = -1 / -2 
 
 -4 -5 2 - * 
 
 / 
 
-1 * x - -3 ) = -1 / -2 
 
 -4 -5 2 - * 
 
 ( / 
 
* x - -3 ) = -1 / -2 
 
 -4 -5 2 - * -1 
 
 ( / 
 
x - -3 ) = -1 / -2 
 
 -4 -5 2 - * -1 
 
 * ( / 
 
- -3 ) = -1 / -2 
 
 -4 -5 2 - * -1 x 
 
 * ( / 
 
 
 
 
-3 ) = -1 / -2 
 
 -4 -5 2 - * -1 x * 
 
 - ( / 
 
) = -1 / -2 
 
 -4 -5 2 - * -1 x * -3 
 
 - ( / 
 
= -1 / -2 
 
 -4 -5 2 - * -1 x * -3 - 
 
 / 
 
-1 / -2 
 
 -4 -5 2 - * -1 x * -3 - / 
 
 = 
 
/ -2 
 
 -4 -5 2 - * -1 x * -3 - / -1 
 
 = 
 
-2 
 
 -4 -5 2 - * -1 x * -3 - / -1 
 
 / = 
 
 -4 -5 2 - * -1 x * -3 - / -1 -2 
 
 / = 
 
 
-4 -5 2 - * -1 x * -3 - / -1 -2 / = 
Nota: El algoritmo anterior no puede detectar errores relacionados con la ausencia de 
paréntesis de cierre. Aunque con una pequeña modificación es posible detectarlos, se ha 
preferido hacerlo en la siguiente etapa: 
4. Traducción de notación postfija a arbol binario 
• Entrada: La lista obtenida en el algoritmo anterior, que contiene los terminos de la ecuacion en 
notación postfija. 
• Salida: Un arbol binario que representa la ecuación. 
• Datos locales: Una pila, que va a contener operandos (numeros, la variable x y expresiones 
(subarboles). 
 INICIO 
 Crear pila y arbol, inicialmente vacios. 
 MIENTRAS lista de entrada no este vacia y 
 no se ha encontrado ningun error HACER 
 Extraer el primer termino de la lista (lo llamaremos E) 
 SEGUN-SEA E 
 CASO E es número : 
 Insertar E en la pila 
 CASO E es la variable x : 
 Insertar E en la pila 
 CASO E es una expresión (un arbol) : 
 Insertar E en la pila 
 CASO E es un paréntesis izquierdo : 
 Se ha detectado un ERROR 2 
 CASO E es un operador : 
 SI La pila tiene menos de dos elementos ENTONCES 
 
 
 
 Se ha detectado un ERROR 3 
 SINO 
 Extraer elemento de la pila (lo llamaremos A2) 
 Extraer elemento de la pila (lo llamaremos A1) 
 Crear un arbol donde la raiz contenga al operador E, 
 el hijo izquierdo sea A1 y el hijo derecho sea A2 
 Insertar el arbol en la pila 
 FIN-SI 
 FIN-SEGUN-SEA 
 FIN-MIENTRAS 
 SI pila vacía o con más de un elemento ENTONCES 
 Se ha detectado un ERROR 3 
 SINO 
 Extraer elemento de la pila (lo llamaremos E) 
 SI Elemento no es una expresión (un arbol) ENTONCES 
 Convertir E en un arbol con hijo izquierdo y derecho vacíos 
 FIN-SI 
 El resultado del algoritmo (el arbol de salida) es E 
 FIN-SI 
 { Borrado de la pila, si se ha producido error } 
 MIENTRAS pila no esté vacía HACER 
 Extraer elemento de la pila 
 Destruir elemento 
 FIN-MIENTRAS 
 Destruir pila 
 FIN 
A continuación se muestra el estado de la lista de entrada y la pila al ejecutar el algoritmo 
anterior sobre la lista de terminos en notación postfija obtenidos anteriormente. Para 
abreviar el listado, cuando varios términos consecutivos de la lista son operandos se han 
agrupado las iteraciones correspondientes en una única linea: 
-4 -5 2 - * -1 x * -3 - / -1 -2 / = 
 
- * -1 x * -3 - / -1 -2 / = 
 
 2 -5 -4 
 
* -1 x * -3 - / -1 -2 / = 
 
 
 
-4 
 
-1 x * -3 - / -1 -2 / = 
 
 
 
 
 
 
 
* -3 - / -1 -2 / = 
 
 x -1 
 
 
-3 - / -1 -2 / = 
 
 
 
 
 
- / -1 -2 / = 
 
 -3 
 
 
 
/ -1 -2 / = 
 
 
 
 
-1 -2 / = 
 
 
 
 
/ = 
 
 -2 -1 
 
 
= 
 
 
 
 
 
 
 
 
 
 
 
El resultado es el arbol binario resultante de extraer el único termino existente en la pila. 
5. Traducción de expresiones más complejas 
Aunque no es necesario para la realización de la práctica, se ha incluido este apartado para 
aquellos que deseen saber cómo ampliar los algoritmos