GENERACIÓN DE CÓDIGO OBJETO

4 Generación de código objeto

 El generador de código objeto como lo menciona (Urbina, 2011) transforma el código Intermedio optimizado en código objeto de bajo nivel. Toma código intermedio y genera Código objeto para la máquina considerada Es la parte más próxima a la arquitectura de la Máquina. Habitualmente, se escriben ``a mano´´ desarrollo a medida´ para cada máquina Específica.

4.1 REGISTROS

¿Qué son?

Los registros son la memoria principal de la computadora. Existen diversos registros de propósito general y otros de uso exclusivo. Algunos registros de propósito general son utilizados para cierto tipo de funciones. Existen registros acumuladores, puntero de instrucción, de pila, etc.

Los registros son espacios físicos dentro del microprocesador con capacidad de 4 bits hasta 64 bits dependiendo del microprocesador que se emplee.

¿Quiénes lo utilizan?

Antes de nada, para el desarrollo de esta parte hablaremos indistintamente de registros de activación o de marcos de pila. Esto se debe a que en la documentación encontrada sobre el manejo de los registros ebp y esp se hace mención a dicho concepto de marco de   pila.   Puesto   que   el   lenguaje   permite   recursividad,   los   registros   de   activación   se asignan dinámica mente. 

                                                                                          

                                                                         

Distribución

La UCP o CPU tiene 14 registros internos, cada uno de ellos de 16 bits (una palabra). Los bits están enumerados de derecha a izquierda, de tal modo que el bit menos significativo es el bit 0.

Los registros se pueden clasificar de la siguiente forma: 

Registros de datos:

AX: Registro acumulador. Es el principal empleado en las operaciones aritméticas.

BX: Registro base. Se usa para indicar un desplazamiento.

CX: Registro contador. Se usa como contador en los bucles.

DX: Registro de datos.

Estos registros son de uso general y también pueden ser utilizados como registros de 8 bits, para utilizarlos como tales es necesario referirse a ellos como por ejemplo: AH y AL, que son los bytes alto (high) y bajo (low) del registro AX. Esta nomenclatura es aplicable también a los registros BX, CX y DX. 

Registros de segmentos: 

CS: Registro de segmento de código. Contiene la dirección de las instrucciones del programa. 

DS: Registro segmento de datos. Contiene la dirección del área de memoria donde se encuentran los datos del programa.

SS: Registro segmento de pila. Contiene la dirección del segmento de pila. La pila es un espacio de memoria temporal que se usa para almacenar valores de 16 bits (palabras).

ES: Registro segmento extra. Contiene la dirección del segmento extra. Se trata de un segmento de datos adicional que se utiliza para superar la limitación de los 64Kb del segmento de datos y para hacer transferencias de datos entre segmentos.

Registros punteros de pila:

SP: Puntero de la pila. Contiene la dirección relativa al segmento de la pila.

BP: Puntero base. Se utiliza para fijar el puntero de pila y así poder acceder a los elementos de la pila.

Registros índices:

 SI: Índice fuente.

 DI: Índice destino.

¿Cuales su aplicación en la generación de códigos?

1. usar el registro de y si está en un registro que no tiene otra variable, y además y no

está viva ni tiene uso posterior. Si no:

2. usar un registro vacío si hay. Si no:

3. usar un registro ocupado si op requiere que x esté en un registro o si x tiene uso

Posterior. Actualizar el descriptor de registro. Si no:

4. usar la posición de memoria de x

4.2 Lenguaje ensamblador

¿Qué es?

El   lenguaje   Assembly  (Urbina,   2011)  (a   veces   mal   llamado   "Ensamblador"   por  su traducción literal al español) es un tipo de lenguaje de bajo nivel utilizado para escribir programas informáticos, y constituye la representación más directa del código máquina específico para cada arquitectura de computadora

 Segunda generación de lenguajes

Versión simbólica de los lenguajes máquina (Urbina, 2011) (MOV, ADD).La comunicación en lenguaje de máquina es particular de cada procesador que se usa, y programar en este lenguaje es muy difícil y tedioso, por lo que se empezó a buscar mejores medios de comunicación con ésta. Los lenguajes ensambladores tienen ventajas sobre los lenguajes de máquina.

Este lenguaje  fue  usado  ampliamente  en el  pasado para  el  desarrollo de software, pero actualmente sólo se utiliza encontradas   ocasiones,   especialmente   cuando   se requiere   la manipulación directa del hardware o se pretenden rendimientos inusuales de los equipos

Características:

El programa lee un archivo escrito en lenguaje ensamblador y sustituye cada uno de los códigos mnemotécnicos por su equivalente código máquina. Los programas se hacen fácilmente portables de máquina a máquina y el cálculo de bifurcaciones se hace de manera fácil.

Clasificación:

• Ensambladores básicos: Son de muy bajo nivel, y su tarea consiste básicamente, en ofrecer nombres simbólicos a las distintas instrucciones, parámetros y cosas tales como los modos de direccionamiento
• Ensambladores modulares, o macro ensambladores: Descendientes de los ensambladores básicos, fueron muy populares en las décadas de los 50 y los 60, fueron antes de la generalización de los lenguajes de alto nivel. Un macroinstrucción es el equivalente a una función en un lenguaje de alto nivel.

Operaciones básicas

(Urbina, 2011) Las operaciones básicas en un lenguaje ensamblador son la suma la resta la multiplicación y la división y Necesitara un poco más de información sobre la  arquitectura y SO para el cual programas.

Pero la idea básica es:

--definir que parámetros tendrá la función.

--hacer el programa, propiamente dicho, en assembler.

Siguiendo la convención de pasaje de parámetros, manejará registros y posiciones de  memoria, devolviendo los resultados en donde deba (una posición de memoria, el registro eax, etc.).

4.3 Lenguaje Máquina

 Es el que proporciona poca o ninguna abstracción del microprocesador de un ordenador. El lenguaje máquina solo es entendible por las computadoras. Se basa en una lógica binaria de 0 y 1, generalmente implementada por mecanismos eléctricos. En general el lenguaje maquina es difícil de entender para los humanos por este motivo hacemos uso de lenguajes más parecidos a los lenguajes naturales.

Se denomina lenguaje máquina a la serie de datos que la parte física de la computadora o hardware, es capaz de interpretar. El lenguaje máquina fue el primero que empleo el hombre para la programación de las primeras computadoras. Una instrucción en lenguaje máquina puede representarse   de   la   siguiente   forma:  011011001010010011110110.   Esta   secuencia   es fácilmente ejecutada por la computadora, pero es de difícil interpretación, siendo aún más difícil la interpretación de un programa (conjunto de instrucciones) escrito de esta forma.

Esta   dificultad   hace   que   los   errores   sean   frecuentes   y   la   corrección   de   los   mismos costosa, cuando no imposible, al igual que la verificación y modificación de los programas.

Características:

El lenguaje máquina realiza un conjunto de operaciones predeterminadas llamadas micro operaciones. Las micro operaciones sólo realizan operaciones del tipo aritmética (+,- ,*,/), lógicas (AND, OR, NOT) y de control (secuencial, de control y repetitiva). El lenguaje maquina es dependiente del tipo de arquitectura. Así un programa máquina para una arquitectura Intel x86 no sé ejecutara en una arquitectura Power PC de IBM (al menos de manera nativa).

Algunos microprocesadores implementan mas funcionalidades llamado CISC, pero son más lentos que los RISC ya que estos tienen registros más grandes.

Ventajas

• Mayor adaptación al equipo.
• Máxima velocidad con mínimo uso de memoria.

Desventajas

• Imposibilidad de escribir código independiente de la máquina.
• Mayor dificultad en la programación y en la comprensión de los programas.
• El programador debe conocer más de un centenar de instrucciones.
• Es necesario conocer en detalle la arquitectura de la máquina.

4.4 Administrador de memoria

La administración de la memoria es un proceso hoy en día muy importante, de tal modo que su mal o buen uso tiene una acción directa sobre el desempeño de memoria. En general un ensamblador tiene un administrador de memoria más limitado que un compilador; en la mayoría de los lenguajes de programación el uso de punteros no estaba vigilado por lo que se tienen muchos problemas con el uso de memoria. Los lenguajes más recientes controlan el uso de punteros y tienen un programa denominado recolector de basura que se encarga de limpiar la memoria no utilizada mejorando el desempeño.

La   memoria   principal   puede   ser   considerada   como   un arreglo lineal de localidades de almacenamiento de un byte de tamaño. Cada localidad de almacenamiento tiene asignada una dirección que la identifica

 Se distinguen los siguientes propósitos del sistema de administración de memoria:

Protección.

Si   varios   programas   comparten   la   memoria   principal,   se   debería   asegurar   que   el programa no sea capaz de cambiar las ubicaciones no pertenecientica él. Aunque una acción  de  escritura  puede  tener efectos  más graves que una  de  lectura,  esta última tampoco debería estar permitida, para proporcionar algo de privacidad al programa.

Compartimiento.

Este objetivo parece contradecir al anterior, sin embargo a veces es necesario para los usuarios poder compartir y actualizar información (por ejemplo, en una base de datos) y, si se organiza la tarea de entrada a la misma, se puede evitar el tener varias copias de la rutina.

Reubicación.

La técnica de multiprogramación requiere que varios programas ocupen la memoria al mismo  tiempo.   Sin   embargo   no   se   sabe   con   anticipación   donde   será   cargado   cada programa por lo que no es práctico usar direccionamiento absoluto de memoria.

Organización física.

Debido al  costo  de una  memoria  principal  rápida, éste se   usa   en   conjunto  con una memoria secundaria mucho más lenta (y por consiguiente, barata) a fines de extender su capacidad.

Organización lógica.

 Aunque   la   mayor   parte   de   las   memorias   son   organizadas   linealmente   con   un direccionamiento secuencial, esto difícilmente concuerde con el camino seguido por el programa, debido al uso de procedimientos, funciones, subrutinas, arreglos, etc

LENGUAJE ENSAMBLADOR

OPTIMIZACION

TIPOS DE OPTIMIZACION

TAREA_8_FERNANDEZ

OPTMIZACION

La optimización busca mejorar la forma en que un programa utiliza los recursos. Las optimizaciones se realizan en base al alcance ofrecido por el compilador. La optimización va a depender del lenguaje de programación y es directamente proporcional al tiempo de compilación; es decir, entre más optimización mayor tiempo de compilación.

Existen diversas técnicas de optimización se pueden clasificar o dividir de diversas formas:

1)      Dependientes de la maquina: técnicas que solo se pueden aplicar a una determinada maquina objeto.

2)     Independientes de la maquina: técnicas que son aplicables a cualquier maquina objeto.

3)      Locales: analizaran solo pequeñas porciones de código y en ellas realizaran mejoras.

4)     Globales: será necesario el análisis de todo el código.

TIPOS DE OPTIMIZACION

Técnicas de optimización que se aplican al código generado para un programa sencillo (aquel que se reduce a un solo procedimiento o subrutina).

1-  LOCALES

La optimización local se realiza sobre módulos del programa. En la mayoría de las ocasiones a través de funciones, métodos, procedimientos, clases, etc.

Las características de las optimizaciones locales es que solo se ven reflejados en dichas secciones. La optimización local sirve cuando un bloque de programa o sección es crítico por ejemplo: la E/S, la concurrencia, la rapidez y confiabilidad de un conjunto de instrucciones.

EJEMPLOS:

1-      Ejecución en tiempo de compilación

Precalcular  expresiones constantes (con constantes o variables cuyo valor no cambia).

3 ! i = 5

j = 4

f = j + 2.5

!

j = 4

f = 6.5

2-     Reutilización de expresiones comunes

a = b + c

d = a - d

e = b + c

f = a - d

!

a = b + c

d = a - d

e = a

f = a – d

3-     Propagación de copias

Ante instrucciones f=a, sustituir todos los usos de f por a.

a = 3 + i

f = a

b = f + c

d = a + m

m = f + d

!

a = 3 + i

b = a + c

d = a + m

m = a + d

4-     Eliminación redundancias en acceso matrices

Localizar expresiones comunes en cálculo direcciones de matrices.

5-     Transformaciones algebraicas:

Aplicar propiedades matemáticas para simplificar expresiones

o   Eliminación secuencias nulas

o   Reducción de potencia

o   Reacondicionamiento de operandos

2- CICLOS

Los ciclos son una de las partes más esenciales en el rendimiento de un programa dado que realizan acciones repetitivas, y si dichas acciones están mal realizadas, el problema se hace N veces más grandes. La mayoría de las optimizaciones sobre ciclos tratan de encontrar elementos que no deben repetirse en un ciclo.

El problema de la optimización en ciclos y en general radica en que es muy difícil saber el uso exacto de algunas instrucciones. Así que no todo código de proceso puede ser optimizado. Otro uso de la optimización puede ser el mejoramiento de consultas en SQL o en aplicaciones remotas (sockets, E/S, etc.).

Optimización global

1. 1. Optimización Global • Grafo del flujo de ejecución – Antes de realizar una optimización global es necesario crear el grafo de flujo de ejecución. – El grafo de flujo de ejecución representa todos los caminos posibles de ejecución del programa. – La información contenida en el grafo es útil para • • • el programador y el optimizador La optimización global a partir del análisis del grafo del flujo de ejecución permite – – Eliminación del código no utilizado – • Una propagación de constantes fuera del bloque básico. Una mejor asignación de los registros. Problema: la optimización global es muy costosa en tiempo de compilación Construcción del Grafo del Flujo de Ejecución • Tipos de grafo – – • Orientado a procedimiento/función Grafo de llamadas Ejemplo int fact(int n) { int r; r=1; i=1; while (i<=n) { r=r*i;

MIRILLA

La optimización de mirilla trata de estructurar de manera eficiente el flujo del programa, sobre todo en instrucciones de bifurcación como son las decisiones, ciclos y saltos de rutinas. La idea es tener los saltos lo más cerca de las llamadas, siendo el salto lo más pequeño posible.

Ideas básicas:

• Se recorre el código buscando combinaciones de instrucciones que pueden ser reemplazadas por otras equivalentes más eficientes.
• Se utiliza una ventana de n instrucciones y un conjunto de patrones de transformación (patrón, secuencias, remplazan).
• Las nuevas instrucciones son reconsideradas para las futuras optimizaciones.

Ejemplos:

• Eliminación de cargas innecesarias
• Reducción de potencia
• Eliminación de cadenas de saltos

OPTIMIZACIÓN : COSTOS

Los costos son el factor más importante a tomar en cuenta a la hora de optimizar ya que en ocasiones la mejora obtenida puede verse no reflejada en el programa final pero si ser perjudicial para el equipo de desarrollo.

NOTACIÓN POLACA

Algoritmo de notación prefija

NOTACIÓN POLACA

La notación polaca, también conocida como notación prefija, es un tipo de notación que se aplica en lógica, aritmética y álgebra. Fue creada por Jan Łukasiewicz allá por los años 20 del siglo XX. Su principal característica, y por lo que se la conoce como notación prefija, es que los operadores preceden a los operandos, lo que significa, traducido al ámbito de la lógica, que las conectivas preceden a las variables.

El alcance de un operador queda perfectamente determinado por su posición en la fórmula, cuanto más a la izquierda se haye un operador mayor alcance tiene. Del mismo modo, la conectiva principal de una fórmula en notación polaca es la situada más a la izquierda.

Este tipo de notación evita por tanto el uso de símbolos auxiliares (paréntesis, corchetes…) para establecer el alcance de las conectivas, a diferencia de la notación estándar. Esta notación puede leerse sin ambigüedad sin recurrir a estos símbolos. Esta característica hace su escritura más compacta.

Por ejemplo, el axioma de no contradicción, que en notación estándar escribimos ¬(p ∧ ¬ p), en notación polaca lo expresaríamos así: NKpNp.

Conectivas en notación polaca

Tradicionalmente, la notación polaca usa letras mayúsculas para expresar conectivas, tomando normalmente la primera letra del nombre de la conectiva en polaco. Aquí tenemos una lista con los símbolos más comunes:

Definición de fórmula bien formada en notación polaca

Tomando la lista anterior de conectivas en notación polaca más un conjunto de variables proposicionales como alfabeto de un lenguaje, tenemos la siguiente definición recursiva de fórmula bien formada en dicho lenguaje:

• Sea α una variable proposicional. α es una fórmula bien formada.
• Sean α, β fórmulas bien formadas. Nα, Cαβ, Kαβ, Aαβ, Eαβ, Mα, Lα, Πα, Σα son fórmulas bien formadas.

Método para traducir una fórmula en notación estándar a notación polaca

(1) Buscamos la conectiva principal y escribimos la equivalente en notación polaca.

(2) Si la conectiva es unaria, tomamos su argumento como una subfórmula y aplicamos (1).

(3) Si la conectiva es binaria, (3a) tomamos el primer argumento y aplicamos (1), a continuación tomamos el segundo argumento y aplicamos (1).

(4) Si el símbolo es una variable proposicional, la escribimos a continuación.

El procedimiento acaba en un número finito de pasos dado que en sucesivas aplicaciones de (1) la complejidad de la fórmula disminuye. Si se trata de una fórmula bien formada, el procedimiento acabará por darnos otra fórmula bien formada en notación polaca. Baste esta descripción para mostrar el carácter formal del procedimiento.

En la práctica, resultaría tedioso aplicar este procedimiento paso por paso. Resulta más adecuado entender la mecánica por medio de ejemplos y aplicarla directamente; con cierto entrenamiento la traducción se hace de manera casi automática.

Como ejemplo de este procedimiento vamos a utilizar una instancia de la ley de De Morgan, que en notación estándar escribiríamos así: ¬(p ∧ q) → (¬p ∨ ¬q). En este ejemplo la conectiva principal es la implicación, una conectiva binaria, cuyos argumentos tienen como conectiva principal la negación y la disyunción respectivamente. Tendremos que traducir las sucesivas subfórmulas hasta las variables variables proposicionales.

2.2.2 Código P 

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 diverso 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. 

2.2.3 Triplos

• 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. 2.2.4 Cuádruplos 

• , , , Ejemplo: (A+B)*(C+D)-E +, A, B, T1 +, C, D, T2 *, T1, T2, T3 -, T3, E, T4 Las cuádruplas facilitan la aplicación de muchas optimizaciones, pero hay que tener un algoritmo para la reutilización de las variables temporales (reutilización de registros del procesador). 

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. 

2.3.1 Variables y constantes

 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; intc; respectivamente. 

2.3.2 Expresiones 

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. 

2.3.3 Instrucciones 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 area! = 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.

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 éste 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 éstos casos utilizaremos instrucciones de control iterativas o repetitivas (ciclos). Sentencias WHILE, DO-WHILE y FOR. 

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.

Expresiones en notaciones infija, prefija y sufija.

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.

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.

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.

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 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ú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.

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.

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:
   • Si el símbolo es un operando, agregarlo al final de la lista de salida.
   • Si el símbolo es un paréntesis izquierdo, enviarlo a pilaOperadores.
   • 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.
   • 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 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.

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. 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/