• Author / Uploaded
• Oscar

• Categories
• Compilador
• Análisis
• Lenguaje de programación
• Herramientas de programación informática
• Gestión de tecnologías de la información

Citation preview

Procesadores de Lenguajes Ingeniería Técnica superior de Ingeniería Informática Departamento de Lenguajes y Sistemas informáticos

Generación de código intermedio I Sentencias y expresiones Javier Vélez Reyes [email protected] Departamento de Lenguajes Y Sistemas Informáticos UNED

Generación de código intermedio. Sentencias y expresiones Objetivos

Objetivos › Aprender en qué consiste la generación de código intermedio › Aprender qué es el código intermedio › Conocer los distintos tipos de lenguajes intermedios › Valorar la importaría de realizar una buena elección del lenguaje intermedio › Conocer cómo son los lenguajes intermedios lineales › Entender el significado de las variables temporales en el código intermedio lineal › Entender el significado de las etiquetas en el código intermedio lineal › Aprender a construir esquemas de traducción para generar código intermedio › Conocer los artefactos computacionales que son necesarios para darles soporte › Aprender a generar código intermedio para expresiones › Aprender a generar código intermedio para sentencias de control

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Índice

Índice › Introducción › Qué es el código intermedio › La fase de generación de código intermedio › El código intermedio como punto de desacoplamiento › Lenguajes intermedios › Representaciones jerárquicas de código intermedio › Representaciones lineales de código intermedio › Generación de código intermedio en la práctica › Artefactos para la generación de código intermedio › Generación de código intermedio para expresiones › Generación de código intermedio para sentencias › Desarrollo paso a paso › Bibliografía

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Introducción

¿Qué es el código intermedio? Una vez superadas todas las fases de análisis del código fuente, el compilador debe ser capaz de generar una representación simbólica del programa lo más aproximada a los potenciales lenguajes objetivos al que se va a traducir el mismo pero lo suficientemente distante de éstos como para garantizar su aplicabilidad en distintas arquitecturas físicas finales El código intermedio es una representación abstracta del programa cercana a los lenguajes objetivos potenciales pero independiente de cualquier consideración específica de una arquitectura física concreta

I. Independencia del entorno de ejecución La independencia del entorno de ejecución se refiere al hecho de que el código intermedio debe ser agnóstico del modelo de organización de memoria, el número, tipo y propósito de registros, etc. Esto implica que todas las referencias a datos en código intermedio siguen haciéndose a través de símbolos registrados o generados durante el proceso de compilación

II. Independencia del juego de instrucciones El código intermedio de un programa es una abstracción establecida a través de un compromiso de consenso entre los equipos dedicados al análisis de lenguajes y los dedicados a la síntesis. Esto significa que la colección de operadores disponibles en un código intermedio se debe mantener independiente y equidistante de cualquier lenguaje y juego de instrucciones propio de una arquitectura física real para garantizar la traducción a distintos códigos finales

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Introducción

La fase de generación de código intermedio La fase de generación de código intermedio se encarga de traducir el programa a una representación de código intermedio para que luego ésta pueda ser transformada en las fases subsiguientes a un código ejecutable en una determinada arquitectura física

S WHILE

E

DO

E > E

S

√

S

WHILE

E

DO

E > E

S

LD a t1 LD b t2 GRT t3 t1 t2 BRZ t3 L1 …

Código final

Código intermedio

e·l·i· h·w

Analizador léxico

While ( a > b ) do a := a + 1;

Analizador semántico

Etapa de síntesis

Analizador sintáctico

Etapa de análisis

0000 0011 0000 0011 0100 0001 0100 0000 0001 0010 …

› Expertos en lenguajes

› Expertos en arquitecturas

› Independencia de arquitectura

› Dependencia de arquitectura

› Dependencia de lenguaje

› Independencia de lenguaje

› Optimización de lenguajes

› Optimización de ejecución Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Introducción

El código intermedio como punto de desacoplamiento El código intermedio permite multiplexar los esfuerzos de desarrollo de los equipos de análisis de lenguajes y de síntesis de manera que se pueden crear M x N compiladores distintos a partir de M especificaciones y N traducciones a arquitecturas físicas reales While ( a > b ) do a := a + 1;

while ( a > b ) a++;

Equipo de Lenguaje

Pascal

M

C

Analizador léxico

Analizador léxico

Analizador sintáctico

Analizador sintáctico

Analizador semántico

…

Código intermedio

arquitectura

Equipo de

N

Código intermedio LD a t1 LD b t2 GRT t3 t1 t2 BRZ t3 L1 …

Código intermedio

Analizador semántico

Intel

Optimización Código intermedio Código final

…

Solaris

Optimización Código intermedio Código final

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Lenguajes intermedios El primer paro para la generación de código intermedio consiste en el diseño de un lenguaje intermedio que permita representar de forma fiel y suficientemente abstracta los programas de un compilador. Existen distintas alternativas que describiremos a continuación

Lenguajes intermedios

Las representaciones jerárquicas de código intermedio reflejan los programas de un lenguaje como una estructura relacional de nodos y arcos entre nodos. Estas representaciones son aconsejables para tareas de análisis y transformación pero no para sintetizar ejecutables en una arquitectura física real

II. Representaciones lineales Las representaciones lineales de código intermedio codifican un programa como una secuencia de instrucciones de bajo nivel abstractas próximas al lenguaje ensamblador. Este tipo de lenguajes resultan más apropiados para la etapa de síntesis puesto que se encuentran más cercanas a la estructura típica los lenguajes objetivos más comunes

I.I Arboles sintácticos abstractos Son una representación similar a los árboles de análisis sintácticos donde los artefactos semánticamente superfluos se omiten y los no terminales se sustituyen por operadores

I.I Grafos dirigidos acíclicos Cuando los nodos de un árbol sintáctico abstracto son referenciados por más de un padre surgen los grafos dirigidos acíclicos

II.I Lenguajes de tercetos o tripletas En los lenguajes de tercetos cada operación tiene hasta dos operandos de entrada y uno de salida que se sobrescribe sobre alguno de los de entrada



I. Representaciones jerárquicas

Foco de atención

II.II Lenguajes de cuartetos o cuádruplas En los lenguajes de cuartetos cada operación tiene hasta 2 operandos de entrada y uno independiente de salida para el resultado

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones jerárquicas Las representaciones jerárquicas describen el código fuente de un programa como una colección de nodos relacionados entre sí a través de arcos con el mismo nivel de abstracción que lo hacen los árboles de análisis sintáctico

Árboles sintácticos abstractos Los arboles sintácticos abstractos representan el código fuente de un programa de acuerdo a una estructura jerárquica de forma similar a como lo haces los árboles de análisis sintáctico. En estas representaciones no obstante se omiten todos tipo de símbolos semánticamente superfluos y se eliden los no terminales que dan información sobre el proceso de derivación gramatical Árbol de análisis sintáctico

(

E

)

E

>

E

while (a>b) do a++

› Apto para procesos de transformación › Inadecuado para la etapa de síntesis › Representación excesivamente abstracta

Código intermedio

SWhile WHILE

› Apto para análisis semántico

transformación

DO

WHILE

S

> ID

++ ID

ID

while (a>b) do a++

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones jerárquicas Las representaciones jerárquicas describen el código fuente de un programa como una colección de nodos relacionados entre sí a través de arcos con el mismo nivel de abstracción que lo hacen los árboles de análisis sintáctico

Grafos dirigidos acíclicos Los arboles dirigidos acíclicos realizan una representación del código fuente en forma de grafo. El método constructivo es similar al de los árboles sintácticos con la diferencia de que aquí se reutilizan los nodos que reflejen la misma estructura én aras a resultar más eficiente su representación en memoria Árbol de análisis sintáctico

› Apto para análisis semántico › Apto para procesos de transformación › Inadecuado para la etapa de síntesis › Representación excesivamente abstracta

Código intermedio

Asignación :=

ID

E

E E

:=

*

transformación

+ E

a := b * c + b * c

ID

+

E E

*

* E

ID

ID

a := b * c + b * c

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones lineales Las representaciones lineales suponen un secuenciamiento de la información codificada en los árboles de análisis sintácticos en forma de una colección de instrucciones abstractas de bajo nivel pero manteniendo las referencias simbólicas introducidas por el programador. Para articular el proceso de secuenciamiento se utilizan varios elementos como operandos de dichas instrucciones que serán utilizados en lo venidero a lo largo del tema

I. Valores literales

II. Variables

En numerosas ocasiones las operaciones de código intermedio utilizan operandos que representan valores literales enteros con o sin signo. La fase de traducción a código final se encarga posteriormente de traducir esos valores a la representación numérica correspondiente utilizada por la arquitectura

Muchos de los símbolos declarados por el programador, tales como constantes, variables globales o locales y parámetros, son referidos de forma general dentro del código intermedio como operandos de tipo ‘variable’

Los

valores

literales

utilizados

operandos en las operaciones

como de los

Las

variables

representan

las

de

código

constantes,

intermedio variables

lenguajes de código intermedio lineales

globales o locales y parámetros declarados

representan valores enteros con signo

por el programador a lo largo del código fuente

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones lineales Las representaciones lineales suponen un secuenciamiento de la información codificada en los árboles de análisis sintácticos en forma de una colección de instrucciones abstractas de bajo nivel pero manteniendo las referencias simbólicas introducidas por el programador. Para articular el proceso de secuenciamiento se utilizan varios elementos como operandos de dichas instrucciones que serán utilizados en lo venidero a lo largo del tema

III. Variables temporales

IV. Etiquetas de código

El secuenciamiento de expresiones complejas requiere del almacenamiento temporal de los resultados parciales de las subexpresiones en espacios de memoria específicamente reservados para ello. Los elementos de código intermedio que se utilizan para referencias esas direcciones se llaman variables temporales

Muchas de las sentencias de un lenguaje de alto nivel (control de flujo, invocación de subprogramas, etc.) requieren insertar etiquetas en el código final para luego realizar saltos a ellas. La forma de referirse a estas etiquetas en código intermedio es mediante las etiquetas de código

Una variable temporal es la representación

Una etiqueta de código es una referencia de

simbólica en código intermedio de un

código intermedio a una zona de memoria

espacio de memoria destinado a almacenar

donde comienza cierta porción de código

un resultado parcial de alguna expresión

final

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones lineales Las representaciones lineales suponen un secuenciamiento de la información codificada en los árboles de análisis sintácticos en forma de una colección de instrucciones abstractas de bajo nivel pero manteniendo las referencias simbólicas introducidas por el programador. A continuación describimos los 2 tipos de representaciones lineales

Lenguajes de tercetos Las representaciones de código intermedio basadas en tercetos están formados por una secuencia de instrucciones constituida por 3 elementos: un código de operación, un operando de entrada y otro de entrada y salida para almacenar el resultado

ADD Código de operación El código de operación es un acrónimo que representa el tipo de operación que se aplican entre los operandos del terceto

x

y

› Apto para la etapa de síntesis › Representación cercana al lenguaje objetivo › Complejidad en la traducción de construcciones Resultado En los lenguajes de tercetos uno de los operandos hace de almacén para el resultado de la operación lo que supone que el operando de entrada se pierde tras su ejecución Operandos Los operandos identifican los elementos sobre los que se efectúa la operación referida por el código de operación. Pueden ser valores literales, variables, variables temporales o etiquetas

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones lineales Las representaciones lineales suponen un secuenciamiento de la información codificada en los árboles de análisis sintácticos en forma de una colección de instrucciones abstractas de bajo nivel pero manteniendo las referencias simbólicas introducidas por el programador. A continuación describimos los 2 tipos de representaciones lineales

Lenguajes de tercetos Las representaciones de código intermedio basadas en tercetos están formados por una secuencia de instrucciones constituida por 3 elementos: un código de operación, un operando de entrada y otro de entrada y salida para almacenar el resultado

› Apto para la etapa de síntesis › Representación cercana al lenguaje objetivo › Complejidad en la traducción de construcciones

Árbol de análisis sintáctico Asignación :=

ID (a) E ID (b)

a := b * c

Código intermedio E *

transformación

E ID (c)

LOAD t0 b LOAD t1 c MUL t1 t0 STORE t1 a

t0 t1 t1 t1

   

b c t1 * t0 a

a := b * c

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones lineales Las representaciones lineales suponen un secuenciamiento de la información codificada en los árboles de análisis sintácticos en forma de una colección de instrucciones abstractas de bajo nivel pero manteniendo las referencias simbólicas introducidas por el programador. A continuación describimos los 2 tipos de representaciones lineales

Lenguajes de cuartetos Las representaciones de código intermedio basadas en cuartetos están formados por una secuencia de instrucciones constituida por 4 elementos: un código de operación, dos operando de entrada y otro de salida para almacenar el resultado

ADD Código de operación El código de operación es un acrónimo que representa el tipo de operación que se aplican entre los operandos del terceto

x

y

z

› Apto para la etapa de síntesis › Representación cercana al lenguaje objetivo › Mayor sencillez en la traducción de construcciones Resultado En los lenguajes de cuartetos el almacén para el resultado de la operación es un operando de salida independiente lo que supone que no hay perdida de información tras la ejecución de la operación Operandos Los operandos identifican los elementos sobre los que se efectúa la operación referida por el código de operación. Pueden ser valores literales, variables, variables temporales o etiquetas

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Lenguajes intermedios

Representaciones lineales Las representaciones lineales suponen un secuenciamiento de la información codificada en los árboles de análisis sintácticos en forma de una colección de instrucciones abstractas de bajo nivel pero manteniendo las referencias simbólicas introducidas por el programador. A continuación describimos los 2 tipos de representaciones lineales

Lenguajes de cuartetos Las representaciones de código intermedio basadas en cuartetos están formados por una secuencia de instrucciones constituida por 4 elementos: un código de operación, dos operando de entrada y otro de salida para almacenar el resultado

› Apto para la etapa de síntesis › Representación cercana al lenguaje objetivo › Mayor sencillez en la traducción de construcciones

Árbol de análisis sintáctico Asignación :=

ID (a) E ID (b)

a := b * c

Código intermedio E *

transformación

E ID (c)

LOAD t0 b LOAD t1 c MUL t2 t1 t0 STORE t2 a

t0 t1 t2 t2

   

b c t1 * t0 a

a := b * c

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Artefactos para la generación de código intermedio La generación de código intermedio se realiza a través de la definición de accesos semánticas en los esquemas de traducción gramaticales. Para llevar esto a cabo, el framework de desarrollo proporciona una colección de artefactos que conviene conocer ScopeManager TypeTable TemporalTable

< uses

IntermediateCodeBuilder

Scope

Create >

SymbolTable

TypeIF

SymbolIF

Quadruple

OperandIF

LabelFactory TemporalFactory

Create > Create >

Label

Variable

Temporal

Value

Reference to >

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Artefactos para la generación de código intermedio La generación de código intermedio se realiza a través de la definición de accesos semánticas en los esquemas de traducción gramaticales. Para llevar esto a cabo, el framework de desarrollo proporciona una colección de artefactos que conviene conocer

Cuádruplas Las cuádruplas son el elemento central de la arquitectura. Representan cada una de las operaciones atómicas que pueden ser referenciadas dentro del código intermedio para que surtan cierto efecto o realicen cierto cálculo a partir de los operandos

+ String getOperation () + void setOperation () + OperandIF getFirstOperand () + void setFirstOperand (OperandIF o) + OperandIF getSecondOperand () + void setSecondOperand (OperandIF o) + OperandIF getResult () + void setResult (OperandIF o)



Quadruple

Los objetos de tipo Quadruple se utilizan para representar operaciones atómicas del código intermedio. Una cuadrupla está formado por un código de operación, un operando opcional resultado y a lo sumo dos operandos de entrada también opcionales. En efecto, en función del tipo de operación el numero de operandos puede variar. Puede haber instrucciones con ningún operando ni resultado, como HALT. Puede haber otras con un sólo operando como los saltos del tipo BR L. O puede haber instrucciones con un resultado y dos operandos como en la suma ADD t3 t1 t2.

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Artefactos para la generación de código intermedio La generación de código intermedio se realiza a través de la definición de accesos semánticas en los esquemas de traducción gramaticales. Para llevar esto a cabo, el framework de desarrollo proporciona una colección de artefactos que conviene conocer

Variables, temporales, valores y etiquetas Los operandos sobre los que operan las cuádruplas son de uno de cuatro tipos: variables, variables temporales, valores literales enteros y etiquetas. Dentro de la arquitectura existe una clase abierta para representar cada uno de estos tipos que el alumno debe carácter con atributos Variable

Label

-String name

-String name

-ScopeIF scope

-ScopeIF scope

-Boolean isGlobal

Temporal -String name

Value -Integer value

-ScopeIF scope -Integer address

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Artefactos para la generación de código intermedio La generación de código intermedio se realiza a través de la definición de accesos semánticas en los esquemas de traducción gramaticales. Para llevar esto a cabo, el framework de desarrollo proporciona una colección de artefactos que conviene conocer

Tabla de temporales Los temporales que se van generando a medida que el compilador procesa las expresiones del lenguaje deben almacenarse en una tabla de temporales asociada a cada ámbito. Este es un aspecto importante para las fases posteriores. El artefacto TemporalTable gestiona los temporales de un ámbito

-ScopeIF scope -List temporals + ScopeIF getScope () + TemporalTable (ScopeIF scope) + List getTemporals () + void addTemporal (TemporalIF temporal) + boolean containsTemporal (TemporalIF temporal)



TemporalTable

Cada tabla de temporales se crea de forma automática asociada a un ámbito cuando este es abierto a través del gestor de ámbitos. Por tanto existe una tabla de temporales para cada ámbito. La responsabilidad de este artefacto es gestionar la colección de temporales generados durante el proceso de compilación del bloque sintáctico asociado al ámbito. Los métodos addTemporal y getTemporals sirven para registrar y tener acceso a los temporales respectivamente y son de utilidad en ésta y en las fases posteriores de generación de código final

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Artefactos para la generación de código intermedio La generación de código intermedio se realiza a través de la definición de accesos semánticas en los esquemas de traducción gramaticales. Para llevar esto a cabo, el framework de desarrollo proporciona una colección de artefactos que conviene conocer

Factorías de etiquetas y temporales Aunque la construcción de temporales y etiquetas puede realizarse haciendo uso directo de los constructores en sendas clases, el framework proporciona dos tipos de factorías cuyo uso para construir objetos de estas clases resulta recomendable por las ventajas que ello supone



La factoría de temporales es un artefacto asociado a un ámbito pasado como argumento en el constructor que se utiliza para crear temporales. El primer método create construye un temporal con nombre propio y lo registra automáticamente en la tabla de temporales. La diferencia del segundo create, es que éste método construye el temporal con un nombre autogenerado que garantiza la unicidad dentro del ámbito



TemporalFactory

La factoría de etiquetas es un que se utiliza para crear etiquetas. El primer método create construye una etiqueta con nombre propio. La diferencia del segundo create, es que éste método construye la etiqueta con un nombre autogenerado que garantiza la unicidad

+ TemporalFactory (ScopeIF scope) + TemporalIF create (String name) + TemporalIF create ()

LabelFactory + LabelFactory (ScopeIF scope) + LabelIF create (String name) + LabelIF create ()

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Artefactos para la generación de código intermedio La generación de código intermedio se realiza a través de la definición de accesos semánticas en los esquemas de traducción gramaticales. Para llevar esto a cabo, el framework de desarrollo proporciona una colección de artefactos que conviene conocer

IntermediateCodeBuilder La construcción de las cuádruplas que componen el código intermedio puede realizarse por invocación de sus constructores de clase. No obstante, resulta más sencillo y económico utilizar instancias de IntermediateCodeBuilder para realizar esta labor

+ void addQuadruple (String op, r) + void addQuadruple (String op, r, o1) + void addQuadruple (String op, r, o1, o2) + void addQuadruple (QuadrupleIF q) + void addQuadruples (List code) + List create ()



IntermediateCodeBuilder

Las operaciones addQuadruple se encargan de insertar un nuevo cuarteto dentro de la lista interna de código intermedio. Sin embargo su semántica depende del tipo y formato de los operandos › Si es de tipo OperandIF se inserta tal cual › Si es de tipo int se crea un Value y se inserta



› Si es de tipo String Primero se instancia el code builder pasándole como argumento de constructo el ámbito. Después se utilizan los métodos addQuadruple para ir acumulando cuartetos internamente. Al finalizar la acción semántica el código se obtiene invocando el método create ()

› Si comienza por “L_” se crea Label y se inserta › Si comienza por “T_” se crea Temporal y se inserta › Sino se busca en TS’s, se crea Variable y se inserta

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Diseño del lenguaje intermedio Antes de proceder con la generación de código intermedio es necesario determinar el juego de instrucciones (cuartetos) que será empleado. Estudie para ello el/los lenguajes objetivos finales Cuarteto

Descripción

NOP

Cuarteto

Nada

NOT

x

y

Descripción x := !y

ADD

x

y

z

x := y + z

BR

L

SUB

x

y

z

x := y – z

BRT

x

L

Si x, salto a L

MUL

x

y

z

x := y * z

BRF

x

L

Si !x, salto a L

DIV

x

y

z

x := y / z

INL

L

MOD

x

y

z

x := y % z

MV

x

y

x

:= y

INC

x

y

x := y + 1

MVP

x

y

x

:= *y

DEC

x

y

x := y – 1

MVA

x

y

x

:= &y

NEG

x

y

x := – y

STP

x

y

*x := y

GR

x

y

z

x := (y > z)

STA

x

y

&x := y

EQ

x

y

z

x := (y == z) ? 1 : 0

PUSH

x

*SP := x ; SP++

LS

x

y

z

x := (y < z)

POP

x

x := *SP ; SP --

AND

x

y

z

x := y && z

CALL f

Llamada a función f

OR

x

y

z

x := y || z

RET x

Retorno de f con valor x

XOR

x

y

z

x := y ^ z

HALT

Stop

? 1 : 0 ? 1 : 0

Salto a L

Insertar L:

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

Expresiones

exp ::= exp:e1 MENOS exp:e2

{: ... :}

Exp e = new Exp();

exp ::= exp:e1 POR exp:e2

{: ... :}

...

ScopeIF scope = scopeManager.getCurrentScope();

exp ::= exp:e1 AND exp:e2

{: ... :}

TemporalFactory tF = new TemporalFactory (scope);

exp ::= exp:e1 OR

{: ... :}

IntermediateCodeBuilder cb = new …Builder (scope)

exp ::= NOT exp:e1 {: ...

exp ::= exp:e1 MAS exp:e2 {:

:}

Expresiones

exp:e2

TemporalIF temp1 = e1.getTemporal ();

ScopeIF scope = scopeManager.getCurrentScope();

TemporalIF temp2 = e2.getTemporal ();

TemporalFactory tF = new TemporalFactory (scope);

TemporalIF temp = tF.create ();

IntermediateCodeBuilder cb = new …Builder (scope)

cb.addQuadruples (e1.getCode ());

TemporalIF temp1 = e1.getTemporal ();

cb.addQuadruples (e2.getCode ());

TemporalIF temp = tF.create ();

cb.addQuadruple (“ADD”, temp, temp1, temp2);

cb.addQuadruples (e1.getCode ());

e.setTemporal (temp);

cb.addQuadruple (“NOT”, temp, temp1);

e.setCode (cb.create());

e.setTemporal (temp);

RESULT = e

e.setCode (cb.create()); RESULT = e :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

Expresiones exp ::= MENOS exp:e1 {:

Expresiones exp ::= PI exp:e1 PD {: RESULT = e1;

Exp e = new Exp();

:}

ScopeIF scope = scopeManager.getCurrentScope();

exp ::= rNumero:rn {:

TemporalFactory tF = new TemporalFactory (scope);

Exp e = new Exp ();

IntermediateCodeBuilder cb = new …Builder (scope)

Integer value = rn.getValue ();

TemporalIF temp1 = e1.getTemporal ();

TemporalIF temp = tF.create ();

ScopeIF scope = scopeManager.getCurrentScope();

cb.addQuadruples (e1.getCode ());

TemporalFactory tF = new TemporalFactory (scope);

cb.addQuadruple (“NEG”, temp, temp1);

IntermediateCodeBuilder cb = new …Builder (scope);

e.setTemporal (temp);

TemporalIF temp = tF.create ();

e.setCode (cb.create());

cb.addQuadruple (“MV”, temp, value);

RESULT = e;

e.setTemp (temp); e.setCode (cb.create ()):

:}

RESULT = e; :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

Expresiones exp ::= referencia:r {:

Referencias referencia ::= ID:id {:

Exp e = new Exp ();

Referencia r = new Referencia ();

e.setType (r.getType ());

String name = id.getLexema ();

ScopeIF scope = scopeManager.getCurrentScope();

TemporalFactory tF = new TemporalFactory (scope);

ScopeIF scope = scopeManager.getCurrentScope();

IntermediateCodeBuilder cb = new …Builder (scope);

TemporalFactory tF = new TemporalFactory (scope);

TemporalIF rTemp = r.getTemporal ();

IntermediateCodeBuilder cb = new …Builder (scope);

TemporalIF temp = tF.create ();

TemporalIF temp = tF.create ();

cb.addQuadruples (r.getCode ());

SymbolVariable sV = scopeManager.searchSymbol (name);

cb.addQuadruple (“MVP”, temp, rTemp);

Variable var = new Variable (name, sV.getScope ());

e.setTemp (temp);

cb.addQuadruple (“MVA”, temp, var);

e.setCode (cb.create ()):

referencia.setTemporal (temp);

RESULT = e;

referencia.setCode (cb.create ()); RESULT = referencia;

:} :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

referencia ::= ID:id {: Referencia r = new Referencia (); String name = id.getLexema ();

D3

V

Referencias a elementos de Arrays i

j

D2

ScopeIF scope = scopeManager.getCurrentScope();

k

TemporalFactory tF = new TemporalFactory (scope); IntermediateCodeBuilder cb = new …Builder (scope); TemporalIF temp = tF.create ();

D1

TemporalIF tempI = tF.create (); cb.addQuadruple (“MVA”, temp, name); cb.addQuadruple (“MV”, tempI, 0); referencia.setTemporal (temp);

V [i][j][k] t1 := 0

&v + i x (D2 x D3 x size)

referencia.setTemporalIndex (tempI);

+ j x (D3 x size)

referencia.setCode (cb.create ());

+ k x size

RESULT = referencia; :}

size

=

t2 := t1 x D1 + i t3 := t2 x D2 + j t4 := t3 x D3 + k t5 := &v + t4 x size

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

referencia ::= referencia:r CI exp:e CD {:

i

Referencia rn = new Referencia ();

j

TypeIF

D3

V

Referencias a elementos de Arrays

D2

rType = r.getType();

int rDim = rType.getMax () – rType.getMin () + 1;

k

TemporalFactoryIF tF = new TemporalFactory (scope); TemporalIF rTemp = r.getTemporal (); TemporalIF rTempI = r.getTemporalIndex ();

D1

TemporalIF eTemp = e.getTemporal (); TemporalIF rnTempI = tF.create (); IntermadiateCodeBuilder cb = new …Builder (scope); cb.addQuadruples (e.getCode ());

size

V [i][j][k] t1 := 0

&v + i x (D2 x D3 x size)

cb.addQuadruples (r.getCode ());

+ j x (D3 x size)

cb.addQuadruple (“MUL”, rnTempI, rTempI, rDim);

+ k x size

cb.addQuadruple (“ADD”, rnTempI, rnTempI, eTemp); rn.setType (rType.getBaseType());

=

t2 := t1 x D1 + i t3 := t2 x D2 + j t4 := t3 x D3 + k t5 := &v + t4 x size

rn.setTemporal (rTemp); rn.setTemporalIndex (rnTempI); r.setCode (cb.create()); RESULT = rn; :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

exp ::= referencia:r {: Exp e = new Exp ();

D3

V

Referencias a elementos de Arrays i

j

D2

ScopeIF scope = scopeManager.getCurrentScope (); TemporalFactoryIF tF = new TemporalFactory (scope);

k

TemporalIF rTemp = r.getTemporal (); TemporalIF rTempI = r.getTemporalIndex (); TemporalIF eTemp = tF.create (); TypeIF

D1

rType = r.getType();

int rSize = rType.getSize (); IntermadiateCodeBuilder cb = new …Builder (scope); cb.addQuadruples (r.getCode ());

size

V [i][j][k]

cb.addQuadruple (“MUL”, eTemp, rTempI, rSize);

+ j x (D3 x size)

cb.addQuadruple (“ADD”, eTemp, eTemp, rTemp);

+ k x size

cb.addQuadruple (“MVP”, eTemp, eTemp); e.setTemporal (eTemp);

t1 := 0

&v + i x (D2 x D3 x size)

=

t2 := t1 x D1 + i t3 := t2 x D2 + j t4 := t3 x D3 + k t5 := &v + t4 x size

e.setCode (cb.create()); RESULT = e; :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

Referencia a campos de registro referencia ::= referencia:r PUNTO ID:id {:

Referencia a campos de registro expr ::= referencia:r {:

Referencia rn = new Referencia ();

Exp e = new Exp ();

String name = id.getLexema ();



ScopeIF scope = scopeManager.getCurrentScope ();

ScopeIF scope = scopeManager.getCurrentScope();

TemporalFactoryIF tF = new TemporalFactory (scope);

TemporalFactory tF = new TemporalFactory (scope);

TemporalIF rTemp = r.getTemporal ();

TemporalIF rTemp = r.getTemporal ();

TemporalIF rTempI = r.getTemporalIndex ();

TemporalIF rTempI = r.getTemporalIndex ();

TemporalIF rTempO = r.getTemporalOffset ();

TemporalIF rTempO = tF.create ();

TemporalIF eTemp = tF.create ();

IntermediateCodeBuilder cb = new …Builder (scope);

TypeIF

cb.addQuadruples (r.getCode ());

int rSize = rType.getSize ();

TypeRecord rType = r.getType ();

IntermadiateCodeBuilder cb = new …Builder (scope);

int idOffset = rType.getOffset

(name);

rType = r.getType();

cb.addQuadruples (r.getCode ());

cb.addQuadruple (“MV”, rTempO, idOffset);

cb.addQuadruple (“MUL”, eTemp, rTempI, rSize);

rn.setTemporal (rTemp);

cb.addQuadruple (“ADD”, eTemp, eTemp, rTemp);

rn.setTemporalIndex (rTempI);

cb.addQuadruple (“ADD”, eTemp, eTemp, rTempO);

rn.setTemporalOffset (rTempO) ;

cb.addQuadruple (“MVP”, eTemp, eTemp);

rn.serCode (cb.create()); RESULT = rn; :}

e.setTemporal (eTemp); e.setCode (cb.create());

RESULT = e; :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

Sentencia asignación sentenciaAsignacion ::= referencia:r IGUAL exp:e {:

Sentencia If sentenciaIF ::= IF PI exp:e PD s:s1 ELSE s:s2 {:

SentenciaAsignacion sa = new SAsignacion ();

SentenciaIf sIf = new SIf ();



ScopeIF scope = scopeManager.getCurrentScope();

ScopeIF scope = scopeManager.getCurrentScope ();

TemporalFactoryIF tF = new TemporalFactory (scope);

LabelFactoryIF lF = new LabelFactory (scope);

TemporalIF eTemp = e.getTemporal ();

LabelIF l1 = lF.create ();

TemporalIF rTemp = r.getTemporal ();

LabelIF l2 = lF.create ();

TemporalIF rTempI = r.getTemporalIndex ();

TemporalIF eTemp = e.getTemporal ();

TemporalIF rTempO = r.getTemporalOffset ();

IntermadiateCodeBuilder cb = new …Builder (scope);

TemporalIF temp = tF.create ();

cb.addQuadruples (e.getCode ());

IntermediateCodeBuilder cb = new …Builder (scope);

cb.addQuadruple (“BRF”, eTemp, l1);

cb.addQuadruples (e.getCode ());

cb.addQuadruples (s1.getCode ());

cb.addQuadruples (r.getCode ());

cb.addQuadruple (“BR”, l2);

cb.addQuadruple (“MUL”, temp, rTempI, rSize);

cb.addQuadruple (“INL”, l1);

cb.addQuadruple (“ADD”, temp, temp, rTemp);

cb.addQuadruples (s2.getCode ());

cb.addQuadruple (“ADD”, temp, temp, rTempO);

cb.addQuadruple (“INL”, l2);

cb.addQuadruple (“STP”, temp, eTemp);

sIF.setCode (cb.create ());

sa.setCode (cb.create()); RESULT = sa; :}

RESULT = sIF; :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Generación de código intermedio en Cup Una vez que conocemos los artefactos proporcionados por el framework para la fase de generación de código y diseñado un lenguaje de código intermedio apropiado, estamos en disposición de articular dicha generación dentro del esquema de traducción dirigida por la sintaxis de cup

Sentencia While sentenciaWhile ::= WHILE PI exp:e PD s:s1 {:

Sentencia For sentenciaFor ::= FOR sAsignacion:sa TO exp:e DO s:s1 {:

SentenciaWhile sWhile = new SWhile ();

SentenciaFor sFor = new SFor ();



ScopeIF scope = scopeManager.getCurrentScope ();

ScopeIF scope = scopeManager.getCurrentScope ();

LabelFactoryIF lF = new LabelFactory (scope);

LabelFactoryIF lF = new LabelFactory (scope);

LabelIF l1 = lF.create ();

LabelIF l1 = lF.create ();

LabelIF l2 = lF.create ();

LabelIF l2 = lF.create ();

TemporalIF eTemp = e.getTemporal ();

TemporalIF eTemp = e.getTemporal ();

IntermadiateCodeBuilder cb = new …Builder (scope);

IntermadiateCodeBuilder cb = new …Builder (scope);

cb.addQuadruple (“INL”, l1);

cb.addQuadruples (sa.getCode ());

cb.addQuadruples (e.getCode ());

cb.addQuadruple (“INL”, l1);

cb.addQuadruple (“BRF”, eTemp, l2);

cb.addQuadruples (e.getCode ());

cb.addQuadruples (s1.getCode ());

cb.addQuadruple (“BRF”, eTemp, l2);

cb.addQuadruple (“BR”, l1);

cb.addQuadruples (s1.getCode ());

cb.addQuadruple (“INL”, l2);

cb.addQuadruple (“BR”, l1);

sWhile.setCode (cb.create ());

cb.addQuadruple (“INL”, l2);

RESULT = sWhile; :}

sFor.setCode (cb.create ()); RESULT = sFor; :}

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Generación de código intermedio en la práctica

Desarrollo paso a paso La fase de generación de código intermedio requiere de la implementación de acciones semánticas en el esquema de traducción dirigidas a producir un código lineal cercano al código objeto pero independiente de una arquitectura física real. A continuación se resumen los pasos recomendados para esta fase 1. Diseñar un lenguaje intermedio -

Identificar todas las operaciones necesarias y asignarles un acrónimo y semántica

-

Tomar como referencia el lenguaje objeto de la arquitectura real

-

Comenzar por un juego sencillo e ir refinándolo bajo demanda

2. Implementar las clases necesarias del framework -

Caracterizar mediante atributos los operandos: Variable, Temporal, Label, Value

-

Incluir atributos necesarios a cada no terminal (Expresión, Sentencias, Referencias, …)

-

Considerar revisar la definición de otros artefactos: TypeIF, …

3. Implementar las acciones semánticas que generan código intermedio -

Código intermedio para expresiones, referencias, sentencias…

-

Incorporar este código al del comprobador de tipos implementado en la fase anterior

4. Probar el código intermedio -

Ejecutar el finalTestCase

-

semanticErrorManager.debug en reglas para que imprima el código intermedio generado Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Bibliografía

Material de estudio Bibliografía básica Construcción de compiladores: principios y práctica Kenneth C. Louden International Thomson Editores, 2004 ISBN 970-686-299-4

Javier Vélez Reyes [email protected]

Generación de código intermedio. Sentencias y expresiones Bibliografía

Material de estudio Bibliografía complementaria Compiladores: Principios, técnicas y herramientas. Segunda Edición Aho, Lam, Sethi, Ullman Addison – Wesley, Pearson Educación, México 2008

Diseño de compiladores. A. Garrido, J. Iñesta, F. Moreno y J. Pérez. 2002. Edita Universidad de Alicante

Javier Vélez Reyes [email protected]