2.3.2 Expresiones

2.3.1 Variables y constantes

Variables y constantes

• Una constante es un dato numérico o alfanumérico que no cambia durante la ejecución del programa.

Ejemplo: pi = 3.1416

• Una variable es un espacio en la memoria de la computadora que permite almacenar temporalmente un dato durante la ejecución de un proceso, su contenido puede cambiar durante la ejecución del programa.

Ejemplo: area=pi*radio^2

Las variables son: el radio, el area y la constate es pi

• Las declaraciones de variables y constantes deben

separarse de tal manera que queden las expresiones

una por una de manera simple.

2.3 Esquema de generación

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.

2.2.4 Cuádruplos

Cuádruplos

Es una estructura tipo registro con cuatros campos que se llaman:

Operador

Operando1

Operando2

Resultado

Donde operando1, operando2 y resultado pueden ser constantes, identificadores y variables temporales definidos por el compilador mientras que operador representa una operación arbitraria.

Operador	Operando1	Operando2	Resultado
*	C	D	T1
+	B	T1	T2
=	T2		A

EJEMPLO:

A := B + C * D

2.2.3 Triplos

Triplos. 

En la historia de los compiladores han sido utilizadas una amplia variedad de representaciones intermedias como lo es la siguiente clase de representación de código intermedio de un árbol de 3 direcciones,2 para los operandos y una para la ubicación del resultado. esta clase incluye un amplio número de representaciones diferentes entre las cuales encontramos cuadruplos y triples. la principal diferencia entre estas notaciones y la notación postfija es que ellos incluyen referencias explicitas para los resultados de los cálculos intermedios, mientras que la notación posfija los resultados son implícitos al representarlos en una pila.

§     La diferencia entre triples y cuadruplos es que con los triples es referenciado el valor intermedio hacia el número del triple que lo creo, pero en los cuádruplos requiere que ellos tengan nombres implícitos.

§     Los triples tienen una ventaja obvia de ser más consistente, pero ellos dependen de su posición, y hacen que la optimización presente cambios de código mucho más compleja.

Para evitar tener que introducir nombres temporales en la tabla de símbolos, se hace referencia a un valor temporal según la posición de la proposición que lo calcula. Las propias instrucciones representan el valor del nombre temporal. La implementación se hace mediante registros de solo tres campos (op, arg1, arg2).

§     En la notación de tripletes se necesita menor espacio y el compilador no necesita generar los nombres temporales. Sin embargo, en esta notación, trasladar una proposición que defina un valor temporal exige que se modifiquen todas las referencias a esa proposición. Lo cual supone un inconveniente a la hora de optimizar el código, pues a menudo es necesario cambiar proposiciones de lugar.

§     Una forma de solucionar esto consiste en listar las posiciones a las tripletas en lugar de listar las tripletas mismas. De esta manera, un optimizador podría mover una instrucción reordenando la lista, sin tener que mover las tripletas en si.

2.2.2 Código P.

Generación de Código Intermedió

*Después de los análisis sintácticos y semánticos, algunos compiladores generan una representación intermedia explicita del programa fuente. Se puede considerar esta representación intermedia como un programa para una maquina abstracta. Esta representación intermedia debe tener dos propiedades importantes, debe ser fácil de producir y fácil de traducir al programa objeto.

*El código intermedió es particularmente utilizado cuando el objetivo de compilador es producir código muy eficiente, ya que para hacerlo así se requiere una cantidad importante del análisis de las propiedades del código objetivo, y esto se facilita mediante el uso del código intermedio.

*El código intermedio también puede ser útil al hacer que un compilador sea mas fácilmente re dirigible: si el código intermedio es hasta cierto punto independiente de la maquina objetivo, entonces genera código para una maquina objetivo diferente solo requiere volver a escribir el traductor de código intermedio a código objetivo, y por lo regular esto es mas fácil que volver a escribir todo un generador de código.

*La representación intermedia puede tener diversas formas, se trata una forma intermedia llamada "CÓDIGO DE TRES DIRRECCIONES" y el "CÓDIGO P"

*El código de tres direcciones consiste en una secuencia de instrucciones, cada una de las cuales tiene como máximo tres operadores.

            temp1 := entareal(60)

            temp2 := id3 * temp1

            temp3 := id2 + temp2

            id1 := temp3

Esta representación intermedia tiene varias propiedades.

- primera, cada instrucción de tres direcciones tiene a lo sumo un operador, además de la asignación. Por tanto, cuando genera esas instrucciones, el  compilador tienes de decidir el orden en que deben efectuarse las operaciones; la multiplicación precede a la adicción en el programa fuente.

- segunda, el compilador debe generar un nombre temporal para guardar los valores calculados por cada instrucción.

- tercera, algunas instrucciones de "tres direcciones" tiene menos de tres operadores, por ejemplo, la primera y la ultima instrucción.

                     EL 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 maquina 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 interprete 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 especifica para la maquina P, que debe conocer si se desea que un programa de código P se comprensible. La maquina P esta 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.

        COMPARACIÓN

*El código P en muchos aspectos está más código de maquina real que al código de tres direcciones. Las instrucciones en código P también requiere menos de tres direcciones: tosas las instrucciones que hemos visto son instrucciones de "una dirección" o "cero direcciones". Por otra parte, el código P es menos compacto que el código de tres direcciones en términos de números de instrucciones, y el código P no esta "auto contenido" en el sentido que las instrucciones funciones implícitas en una pila (y las localidades de pila implícitas son de hecho las direcciones "perdidas"). La ventaja respecto a la pila es que contiene los valores temporales necesarios en cada punto del código, y el compilador no necesita asignar nombre a ninguno de ellos, como el código de tres direcciones.

            Ejemplo

·         — Se puede considerar esta una representación intermedia como un programa para una maquina abstracta.

·         — Traducción de una proposición  

            CÓDIGO DE TRES DIRECCIONES

Las reglas semánticas para generar código de tres direcciones  a partir de construcciones de lenguaje de programación comunes son similares a las reglas para construir arboles sintácticos o para notación posfija.

El código de tres direcciones es una secuencia de preposiciones  de la forma general

x := y op z

Donde 'x', 'y' y 'z' son nombres, constates o variables temporales generadas por el compilador, op representa cualquier valor, como un operador aritmético de punto fijo o flotante, o un operador lógico sobre datos con valores booleanos. Obsérvese que no se permite ninguna expresión aritmética compuesta, pues solo hay un operador en el lado derecho de una proposición. Por tanto, una expresión del lenguaje fuente como x+y*z  se puede traducir en una secuencia

t1  :=  y * z

t2 :=  x + t1

Donde t1 y t2 son nombres temporales generados por el compilador.

El código de tres direcciones  es una reprehensión linealizada de un árbol sintáctico o un GDA en la que lo nombres explícitos corresponde a los nodos interiores del grafo.

            t1 := -c                                                                       t1 := -c

            t2 := b * t1                                                                 t2 := b*t1

            t3 := -c                                                                       t5 := t2 + t2

            t4 := b * t3                                                                 a := t5

            t5 := t2 +t4

            a := t5

(a) Código para el árbol sintáctico                      (b) Código para el GDA

Las proposiciones de tres direcciones son análogas al código ensamblador. Las proposiciones pueden tener etiquetas simbólicas y existen proposiciones para el flujo del control. Una etiqueta simbólica representa el índice de una proposición  de tres direcciones en la matriz que contiene código intermedio. Los índices reales se pueden sustituir por las etiquetas ya sea realizado una pasada independiente o mediante "relleno en retroceso".

La notación gen(x ':='  y '+' z) en la figura (1) para representar la proposición de tres direcciones x := y + z

Se puede añadir proposiciones de flujo del control al lenguaje de asignaciones de la figura (1) mediante producciones y reglas semánticas como las de las proposiciones while de la figura (2).

1.) Definición dirigida por la sintaxis para producir código de tres direcciones para las asignaciones.

Producción	Reglas semántica
S à id := E	S. Código := E. código || gen (id. lugar ':=' E. lugar)
E à E1 +E2	E. lugar := tempnuevo; E. código := E1. código || E2. código || gen(E. lugar ':=' E1. lugar '+' E2.lugar)
E à E1 * E2	E. lugar := tempnuevo; E. código := E1. código || E2. código || gen(E. lugar ':=' E1. lugar '*' E2.lugar)
E à -E1	E. lugar := tempnuevo; E. código := E1. código || gen('E. lugar ':='  'menosu' E1. lugar)
E à (E1)	E. lugar  := E1. lugar; E. código := E1. código
E à id	E. lugar := id. lugar; E. código  := ' '

2.) Reglas semánticas que genera código para una proposición while:

IMPLEMENTACIÓN DE CÓDIGO DE TRES DIRECCIONES 

·         — Cuádruplas.

·         — Estructura con 4 campos: operador, operando1, operando2, resultado.

·         — Triplas.

·         — Estructura con 3 campos: operador, operando1, operando2. Los resultados temporales se referecian por la posición en que fueron calculados.

EL 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. la descripción de diversas versiones de código P.

La máquina P está compuesta por una memoria de código, una memoria de datos no especificada  para variables nombradas y una pila para datos temporales, junto cualquier registro que sea necesario para mantener la pila y apoyar la ejecución.

Como primer ejemplo se considera la expresión:

·         — La versión de código P para esta expresión es la que se muestra en seguida:

ldc 2   ; carga la constante 2

lod a   ; carga el valor de la variable a

mpi     ; multiplicación entera

lod b  ; carga el valor de la variable b

ldc 3   ; carga la constante 3

sbi      ; sustracción o resta entera

adi      ; adiciona de enteros

            Esta instrucción se ven  como si representaran las siguientes operaciones en una maquina P.

En primer lugar, ldc 2 inserta el valor 2 en la pila temporal. Luego, lod a inserta el valor de la variable a  en la pila. Las instrucción mpi extrae estos dos valores de la pila, los multiplica (en orden inverso) e inserta el resultado en la pial. Las siguientes dos instrucciones (lod b y ldc 3) inserta valor de b y la constante 3 en la pila (ahora tenemos tres valores en la pila). Posteriormente, la instrucción sbi extrae los dos valores superiores de la pila, resta el primero del segundo, e inserta el resultado. Finalmente, la instrucción adi extrae los dos valores restantes de la pila, los suma e inserta el resultado. El código final con un solo valor en la pila, que representa el resultado del cálculo.

IMPLEMENTACIÓN DEL CÓDIGO P

Históricamente, el código P ha sido en su mayor  parte generado como un archivo de texto, pero las  descripciones anteriores de las implementaciones de estructura de datos internas para el código de tres direcciones (cuádruples  y triples) también funcionara como una modificación propia para el código P.

GENERACION DEL CODIGO PARTIENDO DE LI. ALGORITMOS:

Se sabe que entre el parse y el lenguaje objeto resultado de la compilación, habrá una de estas dos cosas o ambas.

Un lenguaje intermedio LI.

Una generación de código.

Se supone la existencia de ambos componentes, nos hace falta ahora el regresar el código objeto para la maquina objeto deseada, que en el caso normal de no tratarse de un compilador cruzado, es el mismo código con el que está escrito el compilador.

Como ejemplo de las posibilidades existentes se mencionan las de la figura 5 para el lenguaje pascal.

Se emplea in código P para un maquina hipotética que opera con una pila. Este compilador es muy portable de una maquina a otra. Es el método usado en el USCD PASCAL que al estar todo escrito en el código de la maquina ficticia P, sólo se precisa tener un pequeño interprete distinto para cada maquina objeto dada.

Pero la hipotética maquina a pila, ya nos es tan hipotética puesto que ahora existe ya como microprocesador, con lo que el código P se ejecuta directamente.

También es como el primer caso, pero en vez de emplear un interprete, se traduce con un ensamblador para la maquina objeto dada.

El compilador puede dar directamente un módulo cargable para la maquina objeto en cuestión.

El compilador suministra un objeto responsable que se puede montar con otros objetos.

Para dar concreción vamos a definir el conjunto de instrucciones de un ordenador sencillo que tenga sólo un acumulador A y un registro índice X. Una instrucción simbólica con un ensamblador para esta maquina tendría hasta 4 partes separadas entre si por blancos:

-Una parte opcional, la etiqueta.

-El código de operación.

-El operando.

-Comentario opcional.

La forma de direccionar la memoria son las siguientes:

DIRECTA: Se toma como operando el contenido en memoria del campo de dirección.

INDIRECTA: Como antes pero, el contenido de memoria se considera a su vez como dirección del dato.

INMEDIATA: El valor de la dirección lo tomo inmediatamente como operando.

Y salvo en el caso del direccionamiento inmediato, las direcciones pueden ser: Absolutas o reales, Relativas a la instrucción actual, Indexadas con un registro.

TÉCNICAS BÁSICAS DE GENERACIÓN DE CÓDIGO

La generación de código intermedio(o generación de código objetivo directa sin código intermedio), en realidad, si el código generado se ve como un atributo de cadena, entonces este código se convierte en un atributo sintetizado.

Para ver como el código de tres direcciones, o bien, el código P se puede definir como un atributo sintetizado, considere la siguiente gramática que representa un pequeño subconjunto de expresiones en C:

exp à id = exp | aexp

aexp à aexp + factor | factor

factorà (exp)| num | id

El código P considerando el caso de la generación de código P en primer lugar, ya que la gramática con atributos es más simple debido a que no es necesario generar nombres para elementos temporales.

Por ejemplo, la expresión (x=x+3)+4 tiene ese atributo

lda      x

lod      x

ldc      3

adi

stn

ldc      4

adi

  

Gramática con atributos para código de tres direcciones de cadena sintetizada

Regla Gramatical	Reglas Semánticas
exp à id = exp2	exp1.pcode ="lda" ||id.strval++ exp2.pcode++"stn"
exp à aexp	exp. pcode =aexp.pcode
aexp1à aexp2 + factor	aexp1. pcode = aexp2.pcode ++ factor. pcode ++ "adi"
aexp à factor	aexp. pcode =factor. pcode
factor à (exp)	factor. pcode =exp. pcode
factor à num	factor. pcode = "idc"||num.stval
factor à id	factor. pcode = "lod"||id.strval

Un parse es un procesador de cualquier lenguaje, por ejemplo, los navegadores llevan internamente procesadores de varios lenguajes, html, xhtml, xml, css, javascript, etc.
Los compiladores tienen un procesador de comandos que revisan la sintaxis antes de realizar la compilación.
Así que en general, los parsers o procesadores, son los motores de procesamiento del lenguaje (el que aplique en cada momento).

2.2.1 Notación Polaca

 Notación Polaca

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:

Estándar

      Ejemplo 1: 2 * ( 3 + 5 )

      Ejemplo 2: 2 * 3 + 5

Polaca

      Ejemplo 1: * 2 + 3 5

      Ejemplo 2: + * 2 3 5

2.2 Representaciones de código Intermedio

Representaciones de 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 consiste en la secuencia de código de tres direcciones.

t1 = 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. 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 anterior, tienen menos de tres operandos.

Unidad II. Notaciones Prefija,Infija y Posfija

Notaciones Prefija,Infija y Posfija.

Prefija:

Nos indica que el operador va antes de los operandos 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 el 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.

Notación prefija: El orden es operador, primer operando, segundo.
Infija:

Es la forma más común que utilizamos para escribir expresiones
matemáticas, estas notaciones se refiere a que el operador esta entre
los operandos. 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+2=14
3*(4+2)=18
[size=12]

Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando.
Posfija

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:
(A+B)*C AB+C*

Notación postfija: El orden es primer operando, segundo operando, operador.

EJEMPLO:

Si deseamos representar las expresiones (2+(3*4)) = x y ((2+3)*4)= x en las tres 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 =