Unidad Lenguajes Automas 2

Contenido

UNIDAD 2.GENERACIÓN DE CÓDIGO INTERMEDIO 3

2.1 Notaciones 3

2.1.1 Prefija 4

2.1.2 Notación de Infijo. 5

2.1.3. Notación Postfija 5

2.2. Representación de Código Intermedio. 6

2.2.1 Notación Polaca / Notación Polaca Inversa 8

2.2.2. Código P 10

2.2.3. Triplos 19

2.2.4. Cuádruplos 20

2.3. Esquema de Generación. 21

2.3.1 Variables y Constantes. 21

2.3.2. Expresiones 23

2.3.3. Instrucción de Asignación. 27

2.3.4 Instrucciones de Control. 28

2.3.5 Funciones. 34

2.3.6. Estructuras. 36

REFERENCIAS 37

UNIDAD 2.GENERACIÓN DE CÓDIGO INTERMEDIO

2.1 Notaciones

Notación es la acción y efecto de notar (señalar, advertir, apuntar). El término proviene del latín y hace referencia al sistema de signos convencionales que se adopta para expresar algún concepto.

Se conoce como notación científica al modo de representar un número utilizando potencias de base diez. En este sentido, los números se escriben como el producto de un número real denominado coeficiente (el cual puede ser igual o mayor a 1 y menor a 10) por 10 elevado a un número entero llamado orden de magnitud o exponente; esto se representa con la fórmula a x 10 elevado a n.

La notación matemática es el lenguaje simbólico formal que sigue convenciones propias. Los símbolos permiten representar conceptos, operaciones y todo tipo de entidades matemáticas.

En el ajedrez, la notación es un sistema de registro de las partidas que permite transmitir los movimientos que realizan los jugadores. Existen dos tipos de notación: la descriptiva (que actualmente se encuentra en desuso) y la algebraica.

La notación algebraica del ajedrez identifica cada una de las setenta y cuatro casillas del tablero con dos caracteres. El primero de ellos hace referencia a la columna y se representa con las letras desde la a a la h en minúscula, ordenadas desde la izquierda del jugador que mueve las piezas blancas hacia su derecha. El segundo carácter identifica la línea o fila de la casilla, con los números del 1 al 8 en orden ascendente, o sea, de menor a mayor.

El sistema de escritura que se usa para representar una obra musical de manera gráfica recibe el nombre de notación musical, y permite que cada intérprete ejecute una pieza determinada siguiendo las ideas e indicaciones del compositor y de los revisores.

2.1.1 Prefija

Es una forma de notación para la lógica, la aritmética, y el álgebra. 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. El lógico polaco JanŁukasiewicz inventó esta notación alrededor de 1920 para simplificar la lógica proposicional. Alonso Church menciona esta notación en su libro clásico sobre lógica matemática como digna de observación en los sistemas notacionales incluso contrastados con la Exposición notacional lógica y el trabajo Principia Mathematica de Whitehead y Russell.

Mientras que no se ha usado más en lógica, la notación polaca ha encontrado un espacio en las ciencias de la computación.

Sus características principales son:

 Los operandos 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 es una operación.

 Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos.

 Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite este hasta que nos quede un solo resultado.

2.1.2 Notación de Infijo.

La notación de infijo es la notación común de fórmulas aritméticas y lógicas, en la cual se escriben los operadores entre los operandos en que están actuando (ej. 2 + 2) usando un estilo de infijo. No es tan simple de analizar (parser) por las computadoras, como la notación de prefijo (ej. + 2 2) o la notación de postfijo (ej. 2 2 +), aunque muchos lenguajes de programación la utilizan debido a su familiaridad.

En la notación de infijo, a diferencia de las notaciones de prefijo o posfijo, es necesario rodear entre paréntesis a los grupos de operandos y operadores, para indicar el orden en el cual deben ser realizadas las operaciones. En la ausencia de paréntesis, ciertas reglas de prioridad determinan el orden de las operaciones.

2.1.3. Notación Postfija

El primer módulo del programa se encargará de traducir la expresión que digita el usuario (en notación infija) en una expresión más simple, esta segunda expresión se dice que está en notación postfija; esta forma de escribir una expresión matemática tiene la ventaja que se evalúa de forma lineal por lo que es más sencillo para una computadora "entenderlo''.

Al inicio tal vez se ve un poco complejo, pero no es así; lo que hace el lenguaje es colocar primero los números con los que va a operar y luego escribe la operación, por ejemplo se escribiría " +''; se escribiría "5 8 - 4 *'', otros ejemplos son:

Notación infija Notación postfija

1 3 4 * +

9 +

Notación infija Notación postfija

3 6 *

4 -

2 ^ 4 * +

Para evaluar una expresión en notación infija en un valor específico para se deben seguir las reglas matemáticas para la prioridad de las operaciones:

1. Las potencias tienen prioridad sobre cualquier operación

2. La multiplicación y la división tienen prioridad sobre la suma y la resta.

3. Si se presenta un paréntesis, se deben realizar primero las operaciones dentro de éste. Si hay un paréntesis dentro de otro tiene prioridad el paréntesis interno.

Por el contrario, en la notación postfija siempre se trabaja de izquierda a derecha; note además que la notación postfija no tiene paréntesis por la forma lineal en que se lee. Comparemos un ejemplo en donde se evalúa un valor en una expresión utilizando estas dos notaciones.

2.2. Representación de Código Intermedio.

INTRODUCCION.

En esta guía se abordarán los conceptos pertenecientes al componente de análisis de código intermedio, se analizaran los bloques de básicos de código a partir de un código en cualquier lenguaje previamente indicado. Además se analizara el uso de la notación polaca inversa y el uso de direcciones en ellas.

Generación de código intermedio

Representación de bloques básicos

Los bloques básicos son trozos de código intermedio en los que el flujo de control es lineal, es decir, trozos de código cuyas instrucciones se ejecutan una detrás de otra sin saltos intermedios. Los bloques básicos tienen por tanto una única instrucción de comienzo de bloque y una única instrucción de salida del bloque. Por ejemplo, la siguiente secuencia de instrucciones de tres direcciones forma un bloque básico.

Para identificar los bloques básicos que componen una secuencia de instrucciones en código máquina puede seguirse el siguiente algoritmo:

1. Buscar los puntos de entrada, que corresponden a:

a) La primera instrucción de código máquina.

b) Cualquier instrucción situada en la dirección a la que se refiere una instrucción de salto condicional o incondicional.

c) Cualquier instrucción consecutiva a una instrucción de salto condicional o incondicional.

2. Para cada punto de entrada construir un bloque básico que vaya desde el punto de entrada hasta el siguiente punto de entrada.

3. Los arcos del diagrama de flujo se obtienen mediante las reglas:

a) Si el bloque básico termina en un salto incondicional, entonces incluir un arco hasta la dirección señalada

b) Si el bloque básico termina en un salto condicional, entonces incluir un arco hasta la dirección señalada y otro al siguiente bloque básico.

Una instrucción de tres direcciones del tipo x:= y + z, se dice que define a x y que hace referencia a y (y también a z).

Una variable se dice que está activa en un determinado punto de la secuencia de instrucciones de tres direcciones si después de haber sido definida se hace referencia a ella en cualquier otro punto del programa que se ejecute posteriormente, (en el mismo bloque básico o en cualquier otro). Es decir, una variable está activa desde que nace con una definición, hasta que muere con el último uso que de ella hace cualquier instrucción del programa. Por el contrario, una variable esta inactiva, desde la última vez que se usa hasta que se define nuevamente.

El concepto de actividad e inactividad de las variables tiene importancia para la asignación de registros que se efectúa durante la generación de código máquina.

Ejemplo: Considere el siguiente fragmento de código en lenguaje C

Este ciclo se traduce en la representación en proposiciones de tres direcciones que se muestra a continuación:

En la figura 1, podremos observar el diagrama de bloques básicos correspondiente a este programa.

2.2.1 Notación Polaca / Notación Polaca Inversa

Notación prefija

...