cursoprogsist

8/3/2019 CURSOProgSist

1/213

CURSO:

PROGRAMACION DESISTEMAS

Dr. Ramn Zatarain Cabada


2/213

ELEMENTOS DEL CURSO

Programa del Curso..... PDF

Datos del Profesor . RZC

Contenido del Curso. Diaps Proyectos . Archs

Software y Herramientas


3/213

Unidad I

Introduccin a la Programacinde Sistemas


4/213

1.1 Qu es y que estudia la P. de S. ?

Son los programas que residen en unsistema de computacin. Su funcin es

proporcionar al usuario o programador unainterfase mas eficiente y practica con relacinal hardware de la maquina.

La P. de S. estudia como estn

implementados cada uno de los programasde un Sistema (vernotas).


5/213

1.2 Herramientas desarrolladas

con la P de SEjemplos:

Compiladores (javac)

Ensambladores (Masm)

Interpretes (Visual Basic)

Ligadores (Link)

Cargadores

Sistema Operativo (Windows)

Utileras de Sistemas (Debugger)


6/213

1.3 Lenguajes

Naturales (Traductores de Ingles-Espaol,Ingles-Ruso, etc)

Artificiales (Compiladores de LP como Java,C++, Ada, etc.)


7/213

1.4 Traductor y su Estructura

Ensambladores . (notas)

Compiladores. (notas)

Intrpretes...... (notas)


8/213

1.5 Generador de Cdigo para Compiladores(Compilador de Compiladores)

Definicin: Un compilador de compiladores o generador deParsers es una utilera para generar el cdigo fuente de unparser, intrprete o compilador a partir de una descripcin delenguaje anotado en la forma de gramtica (usualmente BNF)

mas cdigo que es asociado con cada una de las reglas de lagramtica que debe ser ejecutada cundo esas reglas seanaplicadas por el parser. Esas piezas de cdigo son algunasveces llamadas rutinas de acciones semnticas ya que ellasdefinen la semntica de las estructura sintctica y que esanalizada por el parser. Dependiendo del tipo de parser que ser

generado, las rutinas pueden construir un rbol de parsing (oAST) o generar cdigo ejecutable directamente (notas).


9/213

Unidad II

Introduccin al Diseo deLenguajes de Programacin


10/213

Visin del Problema.

Consideraciones Preliminares.

Objetivos y filosofas del diseo de los

lenguajes de programacin.

Diseo detallado.

Caso de estudio.


11/213

Unidad IIIAnlisis de Lxico


12/213

3.1 Introduccin a los Autmatas Finitos

y Expresiones Regulares

(ver apuntes de Lenguajes y Autmatas).


13/213

3.2 Analizador de Lxico. Descompone la entrada en palabras individuales llamadas tokens. El

analizador de lxico (scanner) toma una cadena de caracteres queforman la entrada y produce una cadena de nombres o identificadores,palabras claves o reservadas (PC) signos o marcas de puntuacin,operadores aritmticos y lgicos, constantes (nmeros, cadenas, etc.)

y otros. Tambin el scanner tiene como funcin desechar espacios enblanco y comentarios entre los tokens, otra funcin podra ser crear latabla de smbolos.Ejemplo:TIPO EJEMPLOSID foo n14 lastNUM 73 0 00 515REAL 66.1 .5 10. 1e67

IF if COMMA ,NOTEQ!=LPAREN (


14/213

Analizador de Lxico (cont.)

Tokens de puntuacin como IF, VOID yRETURN son llamadas palabras reservadas

y en la mayora de los lenguajes no puedenusarse como identificadores.


15/213

3.3 Manejo de Buffers

El analizador de lxico (scanner) y el analizador desintxis (parser) forman un duo productor-consumidor. El scanner produce tokens y el parser

los consume.La implementacin de la lectura de los caracteresde la entrada (disco) es usualmente hecha por unbuffer (memoria) que contendr una buena parte de

la entrada, desde donde el scanner ir formando lostokens. Esto agiliza la entrada que de otra formaleera carcter por carcter desde el disco.


16/213

3.4 Creacin de la Tabla deSmbolos.

ChecarnotasLa tabla de smbolos es una estructura de datosmuy importante en casi todo el proceso decompilacin. En ella se guarda durante las primerasfases de compilacin los nombres de losidentificadores (smbolos) usados en el programafuente, adems de los atributos de cada uno deestos identificadores. Estos identificadores ysmbolosjunto con sus atributos sern usados

posteriormente para realizar funciones como elchequeo de tipos, la asignacin de memoria,generacin de cdigo objeto etc.


17/213

EjemploEjemplo.-Programa X1;

Var X, Y: Integer;Z: Real;

Arreglo: Array [1100] of int

Procedure compara (a, b: Integer)Var n, m: integer;Begin

--------

EndBegin

--------End


18/213

3.5 Manejo de Errores de Lxico

Errores posibles detectados en el anlisis delxico son:

Patrones de tokens que no coincidan con algnpatrn vlido. Por ejemplo el token #### serainvlido en algunos L.P.

Caracteres invlidos para el alfabeto del el

lenguaje. Longitud de ciertos tokens demasiado larga.


19/213

3.6 Generadores de CdigoLxico

La construccin de un scanner puedeautomatizarse por medio de un generador de

analizadores de lxico. El primer programa de este tipo que se hizo

popular fue Lex (Lesk, 1975) que generabaun scanner en lenguaje C.

Hoy en da existen muchos programas deeste tipo: Flex, Zlex, YooLex, JavaCC,SableCC, etc.


20/213

Ejemplo: Javacc

Javacc (Java Compiler Compiler) es un generadorde scanners y parsers (https://javacc.dev.java.net/).

Toma como entrada especificaciones de lxico

(expresiones regulares) y sintxis (gramtica decontexto libre) y produce como salida un analizadorde lxico y un parser recursivo decendente.

Se puede usar como pre-procesador de Javacc, ajjtree y a JTB para la construccin del rbolsintctico.


21/213

(cont.)

Miparser. jj javacc Miparser.jj Miparser.javaParseException.javaTokenMgrError.javaotros archivosjava

javac Miparser.java

Miparser.class java Miparser


22/213

(cont.)

PARSER_BEGIN(PS1)

class PS1 {}PARSER_END(PS1)

/* Para la expresin regular de la derecha lo de la izquierda ser retornado */

TOKEN: {||

||

}

SKIP: {|" "|"\t"

|"\n"|"\r"}

void Start():{}{ ( | | | )* }

EJEMPLO DE ESPECIFICACION PARA GENERAR UN SCANNER


23/213

Unidad IVAnlisis de Sintxis


24/213

4.1 Introduccin a las gramticasLibres de Contexto y rboles de

derivacin

El tipo de gramticas usadas en los LP son llamadas gramticas de contexto libre, las cules,junto con rboles de derivacin, fueron estudiadas en el curso de Lenguajes y Autmatas.

Un ejemplo de una gramtica para un LP simple es la siguiente:

1) SS;S 2) S id := E 3) S print (L)4) E id 5) E num 6) E E + E 7) E (S,E)

8) L E 9) L L , E

(ver ejemplo de derivaciones y rboles de parsing)

A continuacin veremos un ejemplo de una gramtica para Java en formato BNF (liga).


25/213

(cont.)

Gramtica Ambigua. Una gramtica es ambigua sipuede derivar una oracin (cadena) con dosdiferentes rboles de parsing. La sig. Gramtica esambiga:

Eid Enum E E*E E E/E

EE+E E E-E E (E)

ya que tiene dos rboles de parsing para la mismaoracin (rboles para id:=id+id+idcon primeragramtica y rboles para 1-2-3 con segunda en sigslice).


26/213

(cont.)S

Id := E

E + E

E + E id

Id id

S

Id := E

E + E

id E + E

id id


27/213

(cont.)

E

E - E

E - E 3

1 2

E

E - E

1 E - E

2 3


28/213

4.2 Diagramas de Sintaxis

Un mtodo alternativo al BNF para desplegarlas producciones de ciertas gramticas es eldiagrama de sintaxis. sta es una imagende la producciones que permite al usuario verlas sustituciones en forma dinmica, es decir,verlas como un movimiento a travs del

diagrama.Ejemplo en Java (liga)


29/213

4.3 Precedencia de Operadores

En los dos ejemplos vistos en seccin 4.1, los dosrboles de parsing para 1-2-3 significaba diferentescosas: (1-2)-3=-4 versus 1-(2-3)=2. Similarmente,(1+2)x3 no es lo mismo que 1+(2x3). Es por eso

que gramticas ambiguas son problemticas paraun compilador. Afortunadamente, una gramticaambigua puede convertirse en una no ambigua. Porejemplo, si queremos encontrar una gramtica noambigua para el lenguaje de la segunda gramtica

de seccin 4.1, lo podemos hacer por medio de dosoperaciones: primero, aplicar orden de precedenciaa los operadores y segundo aplicar asociatividadpor la izquierda. Con esto, tenemos la sig.gramtica:


30/213

(cont.)

SE$ nota: $es EOF- marker

EE+T EE-T ET

T-->T*F TT/F TF

Fid Fnum F(E)

Esta gramtica acepta el mismo lenguaje que la

de seccin 4.1 pero solo produce un rbol de

parsing por oracin. Esta gramtica no podra producir

rboles como los siguientes:

X

+ ?Y

+

?U

?V *

+


31/213

4.4 Analizador Sintctico En esta fase se analiza la estructura de la frase del programa. El parser es el programa que funciona como ncleo del compilador.

Alrededor del parser funcionan los dems programas como el scanner, elanalizador semntico y el generador de cdigo intermedio. De hecho sepodra decir que el parser comienza el proceso de compilacin y su primertarea es pedir al escner que enve los tokens necesarios para llevar acabo el anlisis sintctico, del estatuto, expresin o declaracin dentro de

un programa. Tambin el parser llama rutinas del anlisis semntico para revisar si el

significado del programa es el correcto. Por ultimo el parser genera cdigo intermedio para los estatutos y

expresiones si no se encontraron errores en ellos.


32/213

(cont.)

Existen diferentes tcnicas o mtodos para realizar un anlisissintctico Parsing. Estas tcnicas se dividen en dos tipos:

Descendentes Ascendentes

Las tcnicas descendentes realizan su anlisis partiendo desde elsmbolo inicial de la gramtica y realizando derivaciones hastallegar a producir las hojas o tokens.Por otra parte las tcnicas ascendentes realizan su anlisis

partiendo de las hojas o tokens y mediante una serie deoperaciones llamadas reducciones terminan en la raz o smboloinicial de la gramtica.Por lo general las tcnicas descendentes son mas sencillas deimplementar que las ascendentes, pero por otra parte son menoseficientes


33/213

4.4.1 Analizador descendente (LL).

Parsing Predictivo Algunas gramticas son sencillas de analizarse sintcticamente

usando un algoritmo o mtodo cuyo nombre es recursivodescendente. En esta tcnica cada produccin de la gramticase convierte en una clusula de una funcin recursiva.

Un parserPredictivo es aquel que predice que camino tomaral estar realizando el anlisis sintctico. Esto quiere decir que elparser nunca regresara a tomar otra decisin ( back tracking )para irse por otro camino, como sucede en las derivaciones.Para poder contar con un parser predictivo la gramtica debe detener ciertas caractersticas, entre ellas la mas importante es que

el primer smbolo de la parte derecha de cada produccin leproporcione suficiente informacin al parser para que esteescoja cual produccin usar. Normalmente el primer smbolomencionado es un Terminal o token.


34/213

(cont.)

Esta tcnica se utiliz o populariz en los aos 70 a partir delprimer compilador de pascal implementado con ella. Acontinuacin ilustraremos esto escribiendo un parser recursivodescendente para la siguiente gramtica:

S ifE then S else SS begin S LS print EL endL ; S L

Enum = num

Nuestro Parser tendra 3 mtodos (uno por cada produccin)


35/213

Programa del ParserFinal int if = 1, then = 2, else = 3, begin = 4, end = 5, print = 6, semi = 7,

num = 8, EQ = 9

int tok = get token ( );

void advance ( ) { tok = get token ( ); }void eat ( int t) { if ( tok == 1) advance ( ); else error ( ); }

void S ( ) { switch ( tok ) {case If: eat ( if ); E ( ); eat ( then ); S ( );

eat ( else ); S ( ); break;case begin: eat ( begin ); S ( ); L ( ); break;case print: eat ( print ); E ( ); break;default: error;}}

void L ( ) { switch ( tok ) {case end: eat ( end ); break;case semi: eat ( semi ); S ( ); L ( ); break;default: error ( );}}

void E ( ) { eat ( num ); eat ( EQ ); eat ( num ); }


36/213

(cont.)

Un parser predictivo que examina la entrada de izquierda aderecha (left-to-right) en un paso y realiza su derivacin por laizquierda es llamado Parser LL.

Cuando el parser solo necesita mirar el siguiente token para

hacer su funcin (llokahead(1)), recibe el nombre de ParserLL(1). Un parser podra necesitar mirar K tokens por adelantado para

tomar desiciones. En este caso recibe el nombre de parserLL(K).Ejemplo: (parte de una gramtica)

IF-STM ifEXPthen STM else STM| ifEXPthen STM


37/213

Eliminacin de Recursin por la izquierda

Suponer que queremos construr un Parserpredictivo para la gramtica de seccin 4.3.

S

E$ E

E+T E

E-T E

TT-->T*F TT/F TF

Fid Fnum F(E)

Producciones como E E + T contienen recursin por la izquierda.Parsers descendentes no pueden manejar recursin por la izquierdaen una gramtica. Para eliminar este tipo de recursin utilizamos lasiguiente transformacin:


38/213

(cont.)

En general, si tenemos producciones X X Ky X Edonde Eno comience con Xpodemos aplicar la siguiente transformacin:

X XK X EXX XK X EXX E X KX

XE X

KXX P


39/213

(cont.)

Aplicando la transformacin a la gramtica anterior,obtenemos la nueva equivalente gramtica (sinrecursin por la izquierda):

S E$E T E E + T E E - T E E P

T F T T * F T T / F T T P

F idF num F (E)


40/213

Factorizacin por la izquierda Otro problema en una gramtica ocurre cuando dos producciones

para el mismo no terminal comienza con el mismo smbolo. Porejemplo:

IF-STM if EXP then STM else STM

IF-STM if EXP then STM

En dicho caso podemos factorizar por la izquierda la gramtica. Elresultado sera el sig:

IF-STM if EXP then STM X

X P

X else IF-STM

las producciones anteriores facilitarn el trabajo del parserpredictivo.


41/213

4.4.2 Analizador ascendente(LR yLALR).

La debilidad de las tcnicas descendentes LL(k) es quedeben predecir que producciones usar, despus dehaber mirado los primeros ktokens de la cadena deentrada.

Una tcnica ascendente mas poderosa es la tcnicaLR(K), la cual pospone la decisin hasta que ha vistolos tokens de la entrada correspondientes a la partederecha de la produccin (adems de k mas tokenstambin).

LR(K) quiere decir parser de izquierda a derecha,derivacin por la derecha y lookahead(k). Estatcnica fue introducida por primera vez en 1965 porKnuth.


42/213

(cont.)

Un Parser LR(K) est compuesto de: La cadena de entrada

Una pila

Una tabla de Parsing LR

El parser obtiene los tokens de la entrada ydependiendo de el token actual y de lo que

est en el tope de la pila, ejecuta una de dosacciones (shift-reduce) con la ayuda de latabla de parsing


43/213

Algoritmo de Parsing LR (aho,Sethi y Ullman)

Tomar el primer token de w$ /* w es la cadena */Repeat forever begin

Sea s el estado en el tope de la pila y a el token actual;ifaccin[s,a] = shift s then begin

push a primero y sedpus s al tope de la pila;obten el siguiente token de la cadena de entrada

else ifaccin[s,a] = reduce A->B then beginpop 2*|B| smbolos fuera de la pila;Sea s ahora el estado en el tope de la pila;Push A y despus goto[s,A] al tope de la pila;Imprime la produccin A->B

end

else ifaccin[s,a] = accept thenreturnelse error()

end


44/213

Ejemplo: Parser LR(K)

S4 s7 g2s3 a

S4 s7 g5s6

r1 r1 r1S20 s10 s8 g11

s9S4 s7 g12

123

45

678910111213

1415161718192021

2223

id num print ; , + := ( ) $ S E L

S20 s10 g15 g14r5 r5 r5 r5 r5r2 r2 s16 r2s3 s18r3 r3 r3

s19 s13

r8 r8S20 s10 s8 g17

r6 r6 s16 r6 r6S20 s10 s8 g21S20 s10 s8 g23

r4 r4 r4 r4 r4s22

r7 r7 r7 r7 r7r9 s16 r9

TABLA DE PARSING


45/213

Ejemplo (cont.):PILA ENTRADA ACCION

1 a:=7;B:=c+(d:=5+6,d)$ shift1 id4 := 7;B:=c+(d:=5+6,d)$ shift1 id4 := 6 7;B:=c+(d:=5+6,d)$ shift

1 id4 := 6 num10 ;B:=c+(d:=5+6,d)$ reduceE->num

1 id4 := 6 E11 ;B:=c+(d:=5+6,d)$ reduceS->id:=E

.

.

.

.

.

.

.

$ accept1 S2

.

.

.

..

.

.

.

.

.

..

.

.


46/213

Parsing LALR

La tcnica de parsing LALR (LookAhead-LR) evita el usode tablas muy grandes, como las manejadas en latcnica de parsing LR.

Esta tcnica fue inventada por DeRemer en 1971. Casi cualquier construccin sinctica de un LP puede

ser expresado de manera conveniente por unagramtica LALR.

Generadores de Parsers famosos como YACC (YetAnother Compiler-Compiler-Johnson) producen unparser LALR.

Para una gramtica de un LP como Pascal una tabla deparsing LALR ocupara varios cientos de estados,mientras que una tabla LR seran miles de estados.


47/213

4.5 Administracin de tablas desmbolos.

Como se estudi en la unidad anterior,durante el anlisis de lxico se inicia laconstruccin de la tabla de smbolos.

Esto ocurre al detectarse las declaracionesen el programa fuente.

Sin embargo tambin el parser ayuda arealizar esta tarea pues el es quien llama alas respectivas rutinas semnticas para querealicen funciones relacionada con la tablade smbolos (ver figura).


48/213

4.6 Manejo de errores sintcticos y surecuperacin.

Dentro del cdigo del parser predictivo estudiado enclase se puede observar que el parser llama unmetodo error para el manejo de erroressintcticos, que es cuando el parser obtiene un

token no esperado. Cmo se maneja el error para esta clase de

parsers? Una forma simple es ejecutar unaexcepcin y parar la compilacin. Esto como que noes muy amigable par el usuario.

La mejor tcnica es desplegar un mensaje de errory recuperarse de este, para que otros posibleserrores sintcticos puedan ser encontrados en lamisma compilacin.


49/213

(cont.)

Un error sintctico ocurre cuando la cadena detokens de entrada no es una oracin en el lenguaje.La recuperacin del error es una forma de encontraralguna oracin correcta, similar a la cadena detokens.

Esto se puede realizar por medio de borrar,reemplazar o insertar tokens.

Por ejemplo la recuperacin de un error en S,

podra ser al insertar un token if,begin o print(opretender que existe en la cadena), desplegar elmensaje del error y continuar la compilacin.


50/213

Ejemplo:

void S ( ) { switch ( tok ) {case If: eat ( if ); E ( ); eat ( then ); S ( );

eat ( else ); S ( ); break;case begin: eat ( begin ); S ( ); L ( ); break;case print: eat ( print ); E ( ); break;default: print(se esperaba if, begin o print);

}}

Un problema que puede ocurrir al insertar un token faltante es que el programacaiga en un ciclo infinito, por eso a veces es preferible y mas seguro borrar eltoken, ya que el ciclo terminar cuando el EOF sea encontrado. Esta tcnica

trabaja muy cercanamente con la tabla de parsing (cuando el parser seimplementa con tablas).En un parser del tipo LR o LALR, la tabla de parsing tiene 4 acciones: shift,reduce, accept y error (entrada nula). Cuando el parser encuentra una accinerror, se para el proceso de anlisis y se reporta la falla.


51/213

4.7 Generadores de cdigo paraanalizadores sintcticos

Como se vio al final del captulo 3, Javacc es un generadorde scanners y de parsers (https://javacc.dev.java.net/).

Javacc produce un parser del tipo descendente (recursivo) oLL(k) donde k (lookahead) puede ser cualquier nmero entero

positivo. El parser producido puede correr en cualquier plataforma que

cuente con el compilador de Java. En el ejemplo siguiente del uso de Javacc, utilizamos de

nuevo la gramtica presentada anteriormente (seccin 4.4.1)

para un parser predictivo. Ejecutamos Javacccon la anteriorgramtica y obtendremos un parser recursivo descendentepara dicha gramtica.

Ejemplo: gramtica para estatutos


52/213

Ejemplo: gramtica para estatutosbegin, if y print

PARSER_BEGIN(MiniParser)public class MiniParser {

public static void main(String[] args) {MiniParser parser;try {// RGC: added line

if( args.length == 0 )parser= new MiniParser(System.in);

// RGC: added lineselse

parser= new MiniParser( new java.io.FileInputStream( args[0] ) ) ;

}// RGC: End

parser.Program();} catch (ParseException e) {

System.out.println(e.getMessage());}//RGC: added linescatch( Exception e ) {

System.out.println(e.getMessage());} //RGC :End

}}PARSER_END(MiniParser)

SKIP : {" "

| "\t"| "\n"| "\r"}


53/213


54/213

Unidad VAnlisis Semntico


55/213

5.1 Analizador semntico

Un compilador no solo tiene que revisar la sintaxis decdigo fuente, si no tambin la semntica de este.

Al igual que en los lenguajes naturales (espaol, ingles,etc.) en los lenguajes de programacin existen reglassemnticas para definir el significado de los programas,estatutos, expresiones, etc.

Por ejemplo un error semntico es usar (en pascal java) un identificador que no fue anteriormentedeclarado.

Otro ejemplo de error semntico en un programa escuando este es compilado y y no se detectan errorespero el momento de ser ejecutado este programa nofunciona correctamente.


56/213


57/213

5.3 Conversin de tipos.

Algunas veces los tipos de una expresin o estatuto sondiferente.

Por ejemplo en la asignacin,a = b * c;

el tipo del resultado de evaluarb*ces diferente al de elidentificadora. El compilador algunas veces con ciertos diferentes tipos puede

hacer una conversin interna en forma implcita para solucionarel problema. Otras veces el programador explcitamente es elque hace la conversin (casting).

Ejemplo:float dinero;int cambio;dinero = (float) cambio;


58/213

En un parser recursivo-descendente, el cdigo de las acciones semnticases mezclado dentro del flujo de control de las acciones del parser. En unparser especificado en javaCC, las acciones semnticas son fragmentos decdigo de programa en java unido a las producciones gramticales.

Cada smbolo terminal y noterminal puede asociarse con su propio tipo devalor semntico.Por ejemplo en la siguiente gramtica para YACC de una calculadorasimple, el tipo asociado con exp e INTpodra serint:

%token INT PLUS MINUS TIMES UMINUS%start exp%left PLUS MINUS

%left TIMES%left UMINISexp: INT | exp PLUS exp | exp MINUS exp | exp TIMES exp 1

MINUS exp %prec UMINUS

5.4 Acciones agregadas en un Analizadorsintctico descendente (top-down).


59/213

(cont.)

Los otros tokens no necesitaran tener unvalor.

Por otra parte el tipo asociado a un token

debe por supuesto coincidir con el tipo detoken que el scanner retorne.

Para una regla ABCD, la accin semnticadebe retornar un valor cuyo tipo es elasociado al noterminal A. Pero puedeconstrur este valor de los valores asociadosa los terminales y noterminales B, C, D.


60/213

Recursivo-descendente

En un parser recursivo-descendente, las accionessemnticas son los valores retornados por lasfunciones de parsing, o los efectos laterales deesas funciones o ambos.

Por cada smbolo terminal y noterminal, asociamosun tipo (desde el lenguaje de implementacin del LPdel compilador) de valor semntico representandofrases derivadas desde ese smbolo.

El siguiente programa es un intrprete recursivo

descendente para una parte de la gramtica en lacual eliminamos la recursin por la izquierda (porconveniencia la volvemos a mostrar):


61/213

(cont.)

S E$ E T E E + T E E - T E E P

T F T T * F T T / F T T P

F id F num F (E)

Los tokens ID y NUM deben ahora acarrear valores de tipo string e int,respectivamente. Asumiremos que existe una tabla lookup que mapeaidentificadores a enteros. El tipo asociado con E, T, F, etc., es int, y la accinsemntica es fcil de implementar.


62/213

Interprete

class Token2 {int kind; Object val;Token2(int k, Object v){kind=k;val=v;

}}final int EOF=0, ID=1, NUM=2, PLUS=3,

MINUS=4,LPAREN=5, RPAREN=6, TIMES=7;int lookup(String id) { . }int F_follow[] = {PLUS,TIMES,RPAREN,EOF};

int F() {switch(tok.kind) {case ID: int i=lookup((String)(tok.val));advance()return i;case NUM: int i=((integer)(tok.val)).intVal();

advance();return i;case LPAREN: eat(LPAREN);

int i=E();eatOrSkipTo(RPAREN,F_follow);return i;

case EOF:default: print("1 esperaba ID,NUM, o parent izq");//skipto(F_follow); return 0;

}}

int T_follow[]= {PLUS,RPAREN,EOF};

int T() {switch(tok.kind) {case ID:case NUM:case LPAREN: return Tprime(F());default: print("2 esperaba ID, NUM o parent izq");

//skipto(T_follow);

return 0;}}

int Tprime(int a) {switch (tok.kind) {case TIMES: eat(TIMES); return Tprime(a*F());case PLUS:case RPAREN:case EOF: return a;default: print("3 esperaba ID, NUM o parent izq");

//skipto(T_follow);return 0;

}}

void eatOrSkipTo(int expected, int[] stop) {if (tok.kind==expected)

eat(expected);else {print("4 esperaba ID, NUM o parent izq");

//skipto(stop);}}

Acciones semnticas


63/213


64/213


65/213

(cont.)

Otro ejemplo es en el rbol de parsing:

L

E + T

T * F F

F 4 8

2

Cuyo rbol sintctico abstracto sera:+

* 8

2 4


66/213

Ejemplo:

La gramtica siguiente nos muestra una sintaxisabstracta de un lenguaje para expresiones:

EE+E EE-E EE*E

EE/E Eid Enum Esta gramtica es imprctica para un parser ya que

es ambigua pues no tiene precedencia deoperadores.

Sin embargo, esta gramtica no es para el parser.El analizador semntico podra usarla el cual no semolesta por la ambiguedad puesto que ya tiene suarbol.


67/213

rboles de Sintaxis en Java

En Java las estructuras de datos para elrbol de sintaxis contienen una claseabstracta para cada noterminal y unasubclase para cada produccin. As, lasclases de el programa siguiente son lasclases de la sintaxis abstracta para la

gramtica de la diapositiva anterior.


68/213

public abstract class ExpCh4 {public abstract int eval();

}class PlusExp extends ExpCh4 {

private ExpCh4 e1,e2;public PlusExp(ExpCh4 a1, ExpCh4 a2)

{e1=a1; e2=a2;}public int eval() {

return e1.eval()+e2.eval();

}}class MinusExp extends ExpCh4 {

private ExpCh4 e1,e2;public MinusExp(ExpCh4 a1, ExpCh4 a2)


return e1.eval()-e2.eval();}

}class TimesExp extends ExpCh4 {private ExpCh4 e1,e2;public TimesExp(ExpCh4 a1, ExpCh4 a2)


return e1.eval()*e2.eval();}

}

class DivideExp extends ExpCh4 {private ExpCh4 e1,e2;public DivideExp(ExpCh4 a1, ExpCh4 a2)


return e1.eval()/e2.eval();}}class Identifier extends ExpCh4 {

private String f0;public Identifier(String n0) {f0=n0;}public int eval() {

return (7); //return lookup(f0);}

}class IntegerLiteral extends ExpCh4 {private String f0;public IntegerLiteral(String n0) {f0=n0;}public int eval() {

return (4);//return Integer.parseInt(f0);

}}

Programa de clases para Exp


69/213

Gramtica con acciones semnticas para


70/213

Gramtica con acciones semnticas pararboles sintcticos

PARSER_BEGIN(InterSinTree)class InterSinTree {}

PARSER_END(InterSinTree)

TOKEN: {

|

|

}

SKIP: {|" "|"\t"|"\n"|"\r"

}

ExpCh4 Start():{ ExpCh4 e; }{ e=Exp()

{System.out.println(e.eval()); return e; }}

ExpCh4 Exp():{ ExpCh4 e1,e2; }{ e1=Term()

("+" e2=Term() { e1=new PlusExp(e1,e2);}|"-" e2=Term() { e1=new MinusExp(e1,e2);})*{ return e1;}

}ExpCh4 Term():

{ ExpCh4 e1,e2; }{ e1=Factor()

("*" e2=Factor() { e1=new TimesExp(e1,e2);}|"/" e2=Factor() { e1=new DivideExp(e1,e2);})*{ return e1;}

}

ExpCh4 Factor() :{ Token t; ExpCh4 e; }{ (t=

{return new Identifier(t.image); } |t=

{return new IntegerLiteral(t.image); } |"(" e=Exp() ")" {return e; })

}


71/213

VISITADORES

Es una tcnica de patrones (opuesta a la orientadaa objetos) que se puede usar para implementar elrbol sintctico del compilador o intrprete. Unvisitador es un objeto que contiene un mtodo visitpor cada clase de rbol sintctico. Cada clase derbol sintctico debe contener un mtodo accept.Cada mtodo accept sirve como enganche paracada diferente tipo de operacin sobre el rbol y es

llamado por un visitador donde tiene una tarea:pasar el control de ida y venida (back and forth)entre el visitador y las clases del rbol sintctico.


72/213

(cont.)

A continuacin veremos un ejemplo delintrprete de expresiones anterior pero ahoraimplementado con visitadores. Cada visitador

implementa la interfase Visitor. Cadamtodo accept toma un visitador comoargumento y cada mtodo visit toma un

objeto de un nodo del rbol sintctico comoargumento.


73/213

Sintxis Abstracta para MiniJava

En la siguiente figura (siguiente diapositiva) mostramos las clasesde la sintaxis abstracta para minijava. Solo los constructores sonmostrados en la figura. Cada una de las clases de listas seimplementa en la misma forma. Por ejemplo:

public class ExpList {

private Vector list;public ExpList() {

list=new vector();

}

Public void addElement (Exp n) {

list.addElement(n);

}

public Exp elementAt(int i) {

return (exp)list.elementAt(i);

}

public int size() {

return list.size();

}

}


74/213

Package syntaxtree;

Program(MainClass m, ClassDeclList cl)MainClass(Identifier i1, Identifier i2, Statement s)

Abstract class ClassDecl

ClassDeclSimple(Identifier i, VarDeclList vl, MethodDeclList ml)ClassDeclExtends(Identifier i, identifierj, VarDeclList vl, MethodDeclList ml)

VarDecl(Type t, Identifier i)

MethodDecl(Type t, Identifier i, FormalList fl, VarDeclList vl, StatementList,Exp e)Formal(Type t, Identifier i)

Abstract class Type

IntArrayType() BooleanType() IntegerType() IdentifierType(String s)

Abstract class StatementBlock(StatementList sl)If(Exp e, Statement s1, Statement s2)While(Exp e, Statement s)Print(Exp e)Assign(Identifier i, Exp e)ArrayAssign(Identifier i, Exp e1, Exp e2)

(cont figura)


75/213

(cont. figura)

Abstract class Exp

And(Exp e1, Exp e2)LessThan(Exp e1, Exp e2)Plus(Exp e1, Exp e2) Minus(Exp e1, Exp e2) Times(Exp e1, Exp e2)ArrayLoockup(Exp e1, Exp e2)ArrayLength(Exp e)Call(Exp e, Identifier i, ExpList el)IntegerLiteral(int i)

True()False()IdentifierExp(String s)This()NewArray(Exp e)NewObject(Identifier i)Not(Exp e)

Identifier(String s)

List classes

ClassDeclList() ExpList() FormalList() MethodDeclList()StatementList() VarDeclList()


76/213

Arbol Sintctico

Cada una de las clases que no son listastiene un mtodo acceptpara usarse con elpatrn visitador. La interface Visitador se

muestra en la siguiente diapositiva.

public interface Visitor {


77/213

public interface Visitor {public voidvisit(Program n);publicvoid visit(MainClass n);publicvoid visit(ClassDeclSimplen);publicvoid visit(ClassDeclextends n);public voidvisit(VarDecl n);publicvoid visit(MethodDecl n);public voidvisit(Formaln);

publicvoid visit(IntArrayType n);publicvoid visit(BooleanType n);publicvoid visit(IntegerType n);publicvoid visit(IdentifierType n);public voidvisit(Block n);public voidvisit(If n);public voidvisit(While n);public voidvisit(Print n);public voidvisit(Assignn);publicvoid visit(ArrayAssign n);public voidvisit(And n);

publicvoid visit(LessThan n);public voidvisit(Pluss n);public voidvisit(Minus n);public voidvisit(Times n);publicvoid visit(ArrayLoockup n);publicvoid visit(ArrayLengthn);public voidvisit(Call n);publicvoid visit(IntegerLiteral n);public voidvisit(True n);public voidvisit(False n);publicvoid visit(IdentifierExpn);

public voidvisit(This n);public voidvisit(NewArray n);public voidvisit(NewObjectn);public voidvisit(Not n);publicvoid visit(Identifier n);

}

VisitadorMiniJava


78/213

(cont. Arbol Sintctico)

Podemos construir un rbol sintctico usando expresiones newanidadas. Por ejemplo el rbol sintctico para el estatuto MiniJava:

x = y.m(1,4+5);

usara el siguiente cdigo:

ExpList el= new ExpList();

el.addElement(newIntegerLiteral(1));

el.addelement(new Plus(newIntegerLiteral(4),

newIntegerLiteral(5)));

Statement s = newAssign(newIdentifierx ),

new Call(new identifierExp(y ),newIdentifier(m),

el));


79/213

5.6 Administracin de la tabla de


80/213

smbolos

El anlisis semntico conecta las definiciones de lasvariables con sus usos, checa que cada expresintenga un tipo correcto y traduce la sintaxis abstractaa una representacin mas simple para generar

cdigo mquina. Esta fase es caracterizada por el mantener la tabla

de smbolos (tambin llamada environment) la cualmapea identificadores con sus tipos y localidades.

Cada variable local en un programa tiene un mbito

(scope) dentro del cual es visible. Por ejemplo, enun mtodo MiniJava m, todos los parmetrosformales y variables locales declarados en m sonvisibles solo hasta que finalice m.


81/213


82/213

Ejemplo:1 Class C {2 int a, int b; int c;3 public void m() {4 System.out.println(a+c);5 int j=a+b;

6 String a=hello;7 System.out.println(a);8 System.out.println(j);9 System.out.println(b);10 }11 }

Suponer que compilamos esta clase en el ambiente z0. Las declaraciones decampo en lnea 2 nos da la tabla z1 igual a z0+ {aint,bint,cint}. Losidentificadores en lnea 4 pueden encontrarse (look up) en ambiente z1. Enlnea 5, la tabla o ambiente z2=z1+{jint} es creada; y en lnea 6,z3=z2+{astring} es creada.


83/213

Implementacin de la Tabla

Existen dos opciones: El estilo funcionaldonde cuando z1 existe y z2es creado, z1sigue existiendo. Y el imperativo en donde z1

es destruido al crearse z2. Mientras z2existeno podemos mirarz1. Pero al morirz2, z1 denuevo existe.

Mlti l T bl d S b l


84/213

Mltiple Tablas de Smbolos

En algunos LP pueden existir variosambientes a la vez: Cada mdulo, o clase oregistro en el programa tiene una tabla desmbolos zpropia. Ejemplos (ML y Java).

Structure M = structstructure E= struct

val a= 5;endstructure N= struct

val b=10val a=E.a+b

endstructure D = struct

val d=E.a+N.aend

end

Package M;class E {

static int a=5;}Class N {

static int b=10;

static int a=E.a+b;}Class D {

static int d=E.a+N.a;}


85/213

(cont.)

Al anlizar los 2 programas anteriores, sea z0 elambiente base conteniendo funciones predefinidas,y seaz1={aint}z2={Ez1}z3={bint,aint}z4={Nz3}

z5={d

int}z6={Dz5}z7=z2+z4+z6


86/213

(cont.)

En ML, N es compilado usando el ambientez0+z2 para buscar los identificadores en latabla;D es compilado usando z0+z2+z4 y el

resultado del anlisis es {Mz7}. En Java, referencias adelantads son

permitidas (dentro de N la expresin D.d

sera legal), asi E,N y D son compilados en elambiente z7.


87/213


88/213

(cont.)

Considere z+{at2} cuando zya contieneat1. La funcin insertdeja at1 en elbucket y pone at2 antes en la lista.Entonces, cuandopop se realiza despus delambito de a, zes restaurado.


89/213

SIMBOLOS

Para evitar comparaciones innecesarias decadenas podemos convertir cada cadena aun smbolo, y as todas las diferentes

ocurrencias de cualquier cadena seconviertan a un mismo objeto smbolo. El mdulo smbolo implementa los smbolos

y tiene estas propiedades: Comparar smbolos por igualdad o por mayor es

rpido (comparacin por apuntador o por entero). Extraer una llave hash de tipo entero es rpido


90/213

(cont.)

Los ambientes son implementados en la clase Symbol.Tablecomo Tables mapeando Symbols a ligados (bindings).

Para eso se manejan ligaduras para diferentes propsitos en elcompilador ligadura para tipos, para variables, para funciones,etc.

Entonces, una ligadura es un Objeto. Para implementar la clase Symbol, usaremos el mtodo intern()

(java.lang.String), para darnos un objeto nico a partir de unacadena de caracteres.

Para el uso de la tabla de smbolos usaremosjava.util.Hashtable. La funcin beginScope recuerda el estadoactual de la tabla y endScope restaura la tabla a donde estabaen el mas reciente beginScope que no ha terminado.


91/213

(cont.)

Cuando la atadura xb es metido a la tabla (table.put(x,b)),xesdispersado a un ndice i, y un objeto binderxb es puesto en lacabeza de la lista ligada para el bucket i.

Si la tabla ya tiene una ligaduraxb, esto permanecera en elbucket, pero escondido porxb. Esto es importante ya quesoportara la implementacin de undo (beginScope y endScope).

Tambin deber existir una pila auxiliar, que muestre en queorden los smbolos son metidos (pushed) a la tabla de smbolos.Cuando xb es encontrado, entoncesxes metido a la pila(beginScope). Entonces, para implementar endScope, los

smbolos deben sacarse de la pila.


92/213

Chequeo de Tipos en MiniJava

Con que se llena una tabla de smbolos? Esto es,Qu es la ligadura o binding?

Para realizar el chequeo de tipos de programasMiniJava, la tabla de smbolos debe contener todala informacin declarada: Cada nombre de variable y nombre de parmetro formal

debe ser ligado a su tipo. Cada nombre de mtodo debe ser ligado a sus

parmetros, tipo de resultado y variables locales. Cada nombre de clase debe ser ligado a su variable ydeclaraciones de mtodos.

Liga a pgina con mas informacin.


93/213


94/213

(cont.)

Los tipos primitivos en MiniJava son int y boolean;todos los otros tipos son arreglo de enteros onombres de clases.

Por simplicidad todos los tipos son string, en lugar

de smbolos; esto nos permite checar igualdad detipos por medio de comparacin de strings. El chequeo de tipos de un programa MiniJava

ocurre en dos fases. Primero, construimos la tablade smbolos y despus checamos los tipos de los

estatutos y las expresiones. Lo hacemos en dosfases porque en MiniJava (igual que en Java) lasclases son mutuamente recursivas.


95/213

(cont.)

La primera fase de el checador de tipos se puedeimplementarse por medio de un visitador que visitelos nodos del rbol sintctico de MiniJava yconstruya la tabla de smbolos.

Por ejemplo el mtodo visitador en el siguienteprograma maneja declaraciones de variables. Esteagrega el nombre de la variable y el tipo a laestructura de datos para la clase actual que mas

tarde ser agregada a la tabla de smbolos. El mtodo visitador checa si la variable ya fue

declarada anteriormente.


96/213

Mtodo Visitador

Class ErrorMsg {boolean anyErrors;void complain (String msg) {anyErrors = true;System.out.println(msg);

}

}// Type t;// Identifier i;Public void visit(VarDecl n) {Type t = n.t.accept(this);String id= n.i.toString();

if (currMethod ==null) {if (!currClass.addVar(id,t))

error.complain(id + is already defined in + currClass.getId());} else if (!currentMethod.addVar(id,t))

error.Complain(id + is already defined in + currClass.getId( ) + . + currMethod.getId( ));


97/213

(cont.)

La segunda fase del checador de tipos puede ser implementadapor un visitador que cheque tipos de todas los estatutos yexpresiones.

El tipo del resultado de cada mtodo visitador es String, querepresenta los tipos de MiniJava.

La idea es que cuando el visitador visita una expresin, entoncesretorna el tipo de esa expresin.

El siguiente mtodo (siguiente diapositiva) es el visitador queimplementa la adicin (plus) e1 + e2. En MiniJava ambosoperandos deben ser de tipo entero (el checador revisa esto) y el

resultado debe ser entero (el checador retorna este tipo).

Mtodo Visitador para


98/213

Mtodo Visitador paraexpresiones Plus

// Exp e1, e2;Public Type visit(Plus n) {

if (! (n.e1.accept(this) instanceOf IntegerType) )error.complain(Left side of LessThan must be of type integer);

if (! (n.e2.accept(this) instanceOf IntegerType) )error.complain(Right side of LessThan must be of type integer);

return new IntegerType( );}

5 7 Manejo de errores semnticos


99/213

5.7 Manejo de errores semnticos.

Cuando el checador de tipos detecta un error detipos o un identificador no declarado, debe imprimirel mensaje de error y continuar.

Esto debido a que normalmente el programador

prefiere que le describan todos los errores posiblesdel programa fuente. Esto quiere decir, que si un error de tipos es

encontrado, no debe producirse un programa objetopor parte del compilador.

As, las siguientes fases no deben ejecutarse. Hasta esta etapa (chequeo de tipos), la parte del

compilador se conoce con el nombre de front End.


100/213

REGISTROS DE ACTIVACION

En casi cualquier LP, una funcin (mtodo)puede tener variables locales que soncreadas cuando se llama la funcin (al entrar

a esta). Diferentes invocaciones a la funcin pueden

existir a la vez, y cada invocacin tiene su

propia instanciacin de variables.

(cont )


101/213

(cont.)

En el siguiente mtodo de JavaInt f(int x) {

int y=x+x;if (y


102/213


103/213

MARCOS DE PILA

Debido a que se trabaja con bloques de datos porfuncin un push y pop no funciona.

Entonces la pila es tratada como si fuera un granarreglo, con un registro especial- el stack pointer

que apunta a una localidad. Todas las localidades despus del apuntador son

basura y todas las que estn antes estnasignadas.

El rea en la pila dedicada a las variables locales,

parmetros, direccin de retorno y otras variablestemporales para una funcin es llamada el registrode activacin o marco de pila de la funcin.


104/213

(cont.)

El diseo de la estructura de los marcos esde acuerdo con la arquitectura y el LP que secompila.

Aunque normalmente el constructor de laarquitectura define un diseo de marcostandard para todos los compiladores para

esa arquitectura.

Ejemplo: Un marco de pila


105/213

Argumentosde entrada

ApuntadorDel marco

ArgumentosDe salida

ApuntadorDe pila

Argumento nArgumento 1Liga esttica

Argumento mArgumento 1Liga esttica

Variables

locales

Direccin retorno

Temporales

Registros salvados

Marcoactual

Marco anterior

Marco siguiente

Direcciones de Memoriamas altas

Marco de Pila


106/213

Marco de Pila

Los argumentos de entrada son los pasados por elllamador (tcnicamente son parte del marco anteriorpero pueden accesarse usando un desplazamientodel apuntador de marco).

Cuando la funcin actual llama otras funciones,puede usar el espacio de los argumentos de salidapara pasar parmetros.

La direccin de retorno es creada por la instruccinCALL.

Las variables locales tambin tienen su espacio. Las variables mantenidas en registros algunas

veces son salvadas a memoria.


107/213

El Apuntador de Marco (FP)

Suponer que una funcin g() llama la funcin f(a1,an).Diremos que ges el llamador (caller) y fel llamado (callee). Alentrar a f, el apuntador de la pila (SP) apunta al primerargumento que g pasa a f. Al entrar, fcoloca un marco solo conrestar el tamao del marco de el SP.

El viejo SP se convierte en el actual FP y el viejo FP es salvadoen el marco.

Cuando FP termina, solo copia FP de regreso a SP y regresa elvalor viejo salvado de FP.

Si los marcos son siempre del mismo tamao entonces no es

necesario contar con FP y todo se simplifica sumando orestando la constante framesize a SP.


108/213

Registros

Por eficiencia, es importante mantener las variableslocales, resultados intermedios y otros valores enregistros en lugar de la pila de marcos.

Si funcin fllama a gy ambas hacen uso de registror, entonces rdebe ser salvado (dentro de la pila demarcos) antes de que lo use gy restaurado (desdela pila) despus de que termine g.

de quien es responsabilidad de salvarr? de fog? si lo salva f se dice que r es un registro caller-save; si lo salva g se llama callee-save.


109/213

Pase de Parmetros

Estudios actuales han mostrado queraramente una funcin pasa mas de 4parmetros.

Debido a esto, la mayora de las mquinasdefinen que los primeros k argumentos (conk=4) se pasan en registros y el resto en

memoria.


110/213

Direcciones de Retorno

Si gllama a f, entonces si la instruccin calldentro de gest en direccin a, el lugar deretorno en ges a+1, la siguiente instruccin

del call. En mquinas modernas la direccin de

retorno es pasada a un registro en lugar de la

memoria. En funciones hoja la direccin no necesita

ponerse en la pila.


111/213

Registros vs. Memoria

Registros siempre deben usarse en asignacin amenos que: La variable sea pasada por referencia

La variable es accesada por una funcin anidada dentrode la funcin actual.

El valor es demasiado grande para un registro.

La variable es un arreglo, donde es necesario realizararitmtica de direcciones.

El registro que contiene la variable es necesitado paraotros propsitos.

Existen demasiadas variables locales y valores temporales


112/213

Ligas Estticas (Static Links)

En LP que admiten funciones anidadas (Pascal,MLy Java) las funciones de mas adentro pueden usarvariables declaradas en funciones de mas afuera

(Estructuras de Bloque). En el siguiente programa (sig. Diapositiva) la

funcin write hace referencia a la variable de afueraoutpute indenthace referencia a n y output. Para

cumplir con esto, indentdebe tener acceso no soloa su propio marco (para iy s) sino tambin a losmarcos de show(porn) yprettyprint(poroutput).

Programa de funciones Anidadas


113/213

og a a de u c o es dadas

Type tree= {key: string, left: tree, right: tree}

Function prettyprint(tree:tree): string=let

var output :=

function write(s:string) =output :=concat(output,s)

function show(n:int, t:tree) =let function indent(s:string)=

(for i:= 1 to ndo write( );output:=concat(output,s);write( );

in if t=nil then indent(.)else (indent(t.key);

show(n+1,t.left);show(n+1,t.right))end

in show(0,tree); outputend


114/213


115/213

(cont.) Lnea 21:prettyprintllama show, pasando el apuntador del marco del propio

prettyprintcomo una liga esttica de show. Lnea 10: showguarda su liga esttica (la direccin del marco deprettyprint)

dentro de su propio marco. Lnea 15: showllama indent, pasando su propio apuntador de marco como liga

esttica de indent.

Lnea 17: showllama a show,pasando su propia liga esttica (no su propioapuntador de marco) como la liga esttica. Lnea 12: indentusa el valorn del marco de show. Para hacer esto, trae un

desplazamiento apropiado de la liga esttica de indent(que apunta al marco deshow).

Lnea 13: indentllama a write. Debe pasar el apuntador de marco deprettyprintercomo la liga esttica. Para obtener esto, primero trae undesplazamiento de su propia liga esttica (desde el marco de show), la liga

esttica que haba sido pasada a show. Lea 14: indentusa la variable outputdel marco deprettyprint. Para hacer esto,

comienza con su propia liga esttica, entonces trae a show, y luego trae aoutput.


116/213

Unidad VI

Generacin de CdigoIntermedio

6 1 Lenguajes intermedios


117/213

6.1 Lenguajes intermedios.

El cdigo intermedio en una estructura de cdigocuya complejidad est entre un cdigo fuente en unlenguaje de alto nivel y el cdigo mquina.

Cdigo fuente Cdigo intermedio Cdigo Objeto

Un compilador produce primero un cdigointermedio, pues producir directamente el cdigo

objeto resulta sumamente complicado e ineficiente.


118/213

(cont.)

Ventajas de producir cdigo intermedio: Ms fcil de producir cdigo objeto despus,

si se parte de un cdigo intermedio. Facilita y hace eficiente la optimizacin de

cdigo (algunos tipos de optimizacin). El cdigo intermedio es transportable (puede

usarse en diferentes arquitecturas) ya que nohace referencia a componentes de lamquina.

6 2 Notaciones


119/213

6.2 Notaciones.

Infija. Es la notacin habitual. El orden es primeroperando, operador, segundo operando.

Ejemplo: a/b/c

La notacin infija tiene el problema de que enexpresiones con ms de un operador existeambiguedad sobre cual es el orden de evaluacin.Por ejemplo, la expresin 8/4/2 se puede interpretar

como (8/4)/2 o bien como 8/(4/2). Las otrasnotaciones (prefija y postfija) no sufren esteproblema.


120/213

(cont.) Postfija. El orden es primer operando, segundo operando, operador.

Ejemplo: La expresin X+Y-X*Yen notacin Postfija es XY+XY*-

Por lo general la notacin postfija se emplea en mquinas de pilas ya que la pila facilita laejecucin. Al analizar una notacin postfija de izquierda a derecha, cada vez que se detecta unoperando se mete a la pila. La ocurrencia de un operador con m' operandos significa que elensimo operando estar m-n posiciones por debajo del tope de la pila. Despus se sacan losoperandos de la pila y se mete el resultado de la operacin.

Por ejemplo, suponer que X=1 y Y=2.

Las operaciones seran:push 1 (meter 1)push 2' + ' requiere de 2 operandos, se sacan, se suman y se mete el resultado (3)push 1push 2

' * ' se mete el resultado(2)' - ' se mete el resultado (1)

Notacin prefija: El orden es operador, primer operando, segundo operando.

6.3 Representacin de cdigointermedio


121/213

intermedio.

Existen muchas clases de representaciones

intermedias. Algunas de las mas comunesson: Notacin polaca.

Cdigo P (Pascal).

Triples y Cuadruples.

Bytecodes (Java) MSIL (C#)


122/213

Notacin Polaca

Tambin conocida como notacin postfija. Seutiliza como se dijo anteriormente enmquinas de Pila.

Ejemplos:Pascal Notacin Polaca

a+b-c ab+c-

a+b*c abc*+a+b*c+d abc*+d+


123/213

Cdigo P

Se us como cdigo intermedio y objeto en lasprimeras implementaciones de Pascal.

El cdigo P era interpretado en una mquina

abstracta. Algunas implementaciones de Basic y Pascal usan

cdigo P el cual despus es traducido a cdigonativo por un compilador Just-in-Time.

La mquina P est orientada a usarse en una pila(stack-oriented).


124/213

Ejemplo:

Insn. Stack Stack Description

before after adi i1 i2 i1+i2 add two integers

Adr r1 r2 r1+r2 add two reals

dvi i1 i2 i1/i2 integer division

ldci i1 i1 load integer constant

mov a1 a2 movenot b1 ~b1 boolean negation

Triples y Cuadruplos


125/213

(Cdigo de 3 Direcciones)

Ha sido uno de los mas populares. Susinstrucciones constan de 3 direcciones o registrospara 2 argumentos u operandos y el resultado.

Su formato es:resultado:= argumento1 operador argumento2

Donde resultado, argumento1 y argumento2 puedenser constantes, identificadores y variables

temporales definidos por el compilador mientras queoperador representa una operacin arbitraria. Estaforma se denomina Cudruplo.

(cont.)


126/213

( )

EJEMPLO: Z:= X + Y X * Y

ADD X Y V AR1

MUL X Y V AR2

SUB V AR1 VAR2 VAR3

STORE VAR3 Z

(cont.)


127/213

(cont.)

EJEMPLO: (Estructure de Control):

If (a==b)

a=0;

else

a=1; En cuadruplos tendramos:

1 - A B t1

2 JnZ t1 5

3 = 0 A

4 JP 6

5 = 1 A

6

(cont.)


128/213

( )

En el cdigo de 2 direcciones se evita el uso sevariables temporales. El formato es:Operador argumento1 argumento2EJEMPLO: Z = X + Y - X * Y

1. ADD X Y

2. MUL X Y

3. SUB (1) (2)

4. STORE (3) ( Z)

Donde los nmeros entre parntesis representanapuntadores a la secuencia de operaciones de 2 direcciones.

Java Bytecodes


129/213

Java Bytecodes

El bytecode es un cdigo intermedio ms abstracto que el cdigomquina. Habitualmente viene a ser un archivo binario quecontiene un programa ejecutable similar a un mdulo objeto ocdigo mquina producido por el compilador.

El bytecode recibe su nombre porque generalmente cada cdigo

de operacin tiene una longitud de un byte, si bien la longitud delcdigo de las instrucciones vara.

Cada instruccin tiene un cdigo de operacin entre 0 y 255seguido de parmetros tales como los registros o las direccionesde memoria. Esta sera la descripcin de un caso tpico, si bien

la especificacin del bytecode depende ampliamente dellenguaje.

(cont.)


130/213

( )

Como cdigo intermedio, se trata de una forma de salidautilizada por los implementadores de lenguajes para reducir ladependencia respecto del hardware especfico y facilitar lainterpretacin.

Menos frecuentemente se utiliza el bytecode como cdigo

intermedio en un compilador. Algunos sistemas, llamadostraductores dinmicos o compiladores just-in-time (JIT) traducenel bytecode a cdigo mquina inmediatamente antes de suejecucin para mejorar la velocidad de ejecucin.

Los programas en bytecode suelen ser interpretados por un

intrprete de bytecode (en general llamado mquina virtual, dadoque es anlogo a un ordenador).

(cont.)


131/213

( )

Su ventaja es su portabilidad: el mismo cdigo binario puede serejecutado en diferentes plataformas y arquitecturas. Es la mismaventaja que presentan los lenguajes interpretados.

Sin embargo, como el bytecode es en general menos abstracto,ms compacto y ms orientado a la mquina que un programapensado para su modificacin por humanos, su rendimientosuele ser mejor que el de los lenguajes interpretados.

A causa de esa mejora en el rendimiento, muchos lenguajesinterpretados, de hecho, se compilan para convertirlos enbytecode y despus son ejecutados por un intrprete debytecode.

Entre esos lenguajes se encuentran Perl, PHP y Python. Elcdigo Java se suele trasmitir como bytecode a la mquinareceptora, que utiliza un compiladorjust-in-time para traducir elbytecode en cdigo mquina antes de su ejecucin.

La Mquina Virtual de Java(JVM)


132/213

(JVM)

La siguiente liga nos lleva a la informacin delo que es la JVM y mas sobre Javabytecodes.

b l d E bl d


133/213

rboles de Ensamblador

Un paso antes de generarEnsamblador Real

Permite mas fcil optimizacin de cdigo

Primero vamos a estudiar la implementacinde asignacin de memoria en el cdigogenerado (stack y heap).


134/213

Por ejemplo, la funcin:


135/213

Int foo() {

int a;

intb;

/* body of foo */

}

a

b

Registros

salvados

FP

SP

Tendra el registro de activacin

Existen dos apuntadores. FP queapunta al inicio del RA actual y SP queapunta a la primera localidad vaca. Elvalor retornado de una funcin espuesto en un registro especial en lugar

de la pila. Cuando una funcin esllamada los valores de los parmetrosde entrada son puestos en la pila, ycuando la funcin retorna un valor, elvalor es almacenado en el registro deresultado.

(cont.)


136/213

Como el FP siempre apunta al comienzo delRA actual, podemos acceder a las variableslocales usando un offsetdesde el FP.

Los parmetros de funciones son

almacenados en RA de la funcin que llama,no la que es llamada. Los parmetros deentrada a una funcin pueden ser accesadospor medio del FP, usando un offset en ladireccin opuesta a las variables locales. Elformato completo de un RA es mostrado enla siguiente diapositiva.

Formato completo de RA


137/213

Input Parameter n

Input Parameter 2

Input Parameter 1

Local Variables

Saved Registers

FP

SP

Previous Activation Record

Current Activation Record

Considere el siguiente programa:


138/213

g gvoid foo(int a, intb);

void foo(int c, int d);

void main() {

int u;

int v;

/* LabelA */

bar(1,2);

}

voidbar(int a, intb) {

int w;

int x;

foo(3,4);

}

void foo(int c, int d) {

int y;

int z;

/* Label B */

}

En label A de el programa, la pila de RA se mirara de laforma siguiente


139/213

g

u

v

Saved Registers

FP

SP

ActivationRecord formain

La variable local upuede accesarse examinando la localidad dememoria apuntada por FP. La variable vpuede accesarseexaminando (FP-wordsize). Algo para aclarar es que la pilacrece de direcciones altas a bajas.

En etiqueta B los RA semiraran as: u


140/213

v

Saved Registers

b

a

w

x

Saved Registers

d

c

y

z

Saved Registers

FP

SP

Activation Record

for main

Activation Recordfor bar

Activation Recordfor foo

(cont )


141/213

(cont.)

La variable yen funcin foo puede accesarse alexaminar la localidad de memoria apuntada porFP.La variable z en foo puede accesarse examinandola localidad (FP-wordsize). El parmetro de entradac en funcin foo puede accesarse examinando lalocalidad (FP+wordsize), mientras que el parmetrod puede accesarse con (FP+2*wordsize).

Algo importante es que la funcin llamadora esresponsable de poner los parmetros actuales y dequitarlos cuando acabe la funcin llamada.

Ensamblador Abstracto


142/213

El ensamblador abstracto es dividido en rboles deestatutos y rboles de expresiones. rboles deestatutos no tienen valores pero los de expresionessi lo tienen.

Existen cinco diferentes tipos de rboles deexpresiones: Constante. Consiste de un valor de la constante (solo

enteros). Registro. Una cadena que especifica el registro. Operador. Dos rboles de expresin para los operandos, y

el operador: +,-,*,/,,=,=,&&,||,!.

(cont.)


143/213

CallExpression. Contiene una etiqueta de lenguaje ensamblador y

un rbol de expresin por cada uno de los parmetros en la llamadade la funcin (function call). La etiqueta es la direccin del inicio dela funcin llamada. Por ejemplo la funcin foo(3,4,5) serepresentara por el rbol de expresin:

CallExpresion(foo)

Constant(4)Constant(3) Constant(5)

El ensamblador abstracto en este caso no contiene instruccionesexplcitas para asignar los parmetros actuales a la pila. Cuandose tradusca el ensamblador abstracto de una callExpression aensamblador real, se incluye el cdigo para hacer la copia de losparmetros actuales a la pila.

Memoria. Solo se denota la direccin de memoria.


144/213

Ejemplo:Memory

Constant(1006)

Casi nunca se manejan direcciones absolutas sino que estas sonrelativas al FP. Por ejemplo para referirse a la localidad de memoria deuna variable local con un desplazamiento (oofset) de 4 del FP esrepresentado con el rbol:

Memory

Operator(-)

Register(FP) Constant(4)

Existen 8 tipos de rboles de estatutos:


145/213

Move. Tienen dos subrboles elsubrbol izquierdo es el destino delmove, y el derecho es el valor a mover. El izquierdo necesita ser un rbol de

expresin de registro (mover un dato a un registro) o un rbol de expresinde memoria (mover un dato a memoria). La parte derecha puede ser unaexpresin arbitraria.

Label (Etiqueta). Se usan como destinos de jumps y calls. Jump. Saltos incondicionales contienen una etiqueta. Conditional Jump. Contienen un subrbol de expresin y una etiqueta de

lenguaje ensamblador. Si la expresin es verdadera se hace unatransferencia de control a una etiqueta. Si es falsa, entonces habr un no-

op. Sequential. Tiene dos subrboles. Representa la ejecucin del izquierdo

seguido del derecho. CallStatement. Contienen una rbol de etiqueta, y un rbol expresin de

cada uno de los parmetros actuales. Calls representan void functioncalls.

Empty. Son no-ops y son removidos cuando se traduce a ensamblador

real. Return. No retorna un valor (como Java). Solo cambia el flujo de control. Un

return de Java se implementa incluyendo cdigo que retorne el valor de lafuncin (en el registro resultado) adems del ensamblador abstracto delreturn.

Ejemplos: (asumiremos que wordsize=4 y que un entero seguarda en una palabra)


146/213

void foo(int a, int b) {

int x;

int y;

boolean z;

x= 1;

y = a * b;y++;

bar(y, x + 1, a);

x= function(y+1, 3);

if (x > 2)

z = true;else

z = false;

}

X=1;


147/213

Move

Memory Constant(1)

Register(FP)


148/213

Y++;


149/213

Move

Memory

Operator (-)

Constant(4)

Operator(+)

Memory Constant(1)

Operator (-)


Register(FP)

bar(y,x+1,a);


150/213

CallStatement(bar)

Memory

Operator (-)

Constant(4)Register(FP)

Operator (+)

Memory Constant(1)

Register(FP)

Memory

Operator (+)

Constant(4)Register(FP)

x=function(y+1,3);


151/213

Move

Memory

Register(FP)

Callexpression(function)

Constant(3)

Constant(1)

Operator(+)

Memory

Operator(-)


if (x > 2) z = true; else z = false;

S ti l


152/213

Sequential

ConditionalJump(iftrue)

Operator(>)

Memory Constant(2)

Sequential

Sequential

Sequential

Sequential

Label(ifend)

Jump(ifend)

Label(iftrue)

Move

Move

Constant(0)Memory

Operator(-)


Constant(1)Memory

Operator(-)


Register(FP)

Creacin de Ensamblador Abstracto


153/213

Variables Variables base

La variablexy yse representaran con losrboles:

void foo() {

int x;

int y;

/* Body of foo */

}

Memory

Register(FP)

Memory

Operator(-)


Variables Arreglo: Son almacenadas en el


154/213

heap, y usando un apuntador a la base del

arreglo el cual se almacena en la pila.La siguiente funcin o mtodo

void foo arrayallocation() {

int x;

int A[];

int B[];

A = new int [5];

B = new int [5];

/* Body of function */

}

La variable local x es almacenada en la pila,igual que la direccin base del arreglo A y delarreglo B


155/213

arreglo B.

Saved Registers

Stack Heapx

AB

FP

SP

A[0]

A[1]

A[2]

A[3]

A[4]

B[0]

B[1]

B[2]

B[3]B[4]

Cmo debemos representarel arreglo A[3]


156/213

el arreglo A[3]

Register(FP)

Memory

Operator(-)

Memory Operator(*)

Operator(-)

Constant(WORDSIZE)

Constant(WORDSIZE) Constant(3)

Y A[x] ?


157/213

Memory

Operator(-)

Memory Operator(*)

Operator(-)

Register(FP) Constant(WORDSIZE)

Constant(WORDSIZE) Memory

Register(FP)

Y para A[B[2]] ?

M


158/213

Memory

Operator(-)

Memory Operator(*)

Operator(-)


Constant(WORDSIZE) Memory

Operator(-)

Memory

Operator(-)

Register(FP) Constant(2*WORDSIZE)

Operator(*)

Constant(WORDSIZE)Constant(2)

Arreglos Multidimensionales se manejan demanera similar.Ejemplo:


159/213

Ejemplo:

void twoDarray {

int i;

int c [ ] [ ] ;

C = new int [3] [ ] ;

for (i=0; i


160/213

La variable C sera representada as:


161/213

Memory

Operator(-)


La variable C[2] as:


162/213

Memory

Operator(-)

Memory Operator(*)

Operator(-)



La variable c[2] [1]


163/213

Memory

Operator(-)

Memory Operator(*)

Operator(-)

Memory Operator(*)


Operator(-)


Constant(2)Constant(WORDSIZE)


164/213

Cul es el rbol de ensambladorpara s.y ?


165/213

Memory

Register(FP)

l rbol de s:

Para obteneryde s:

Memory

Memory

Operator(-)

Constant(WORDSIZE)

Register(FP)

El rbol de la variable s.x: Memory

Memory


166/213

Memory

Register(FP)

El rbol para .A[3]: Memory

Operator(-)

Memory Operator(*)

Operator(-)

Memory Constant(2*WORDSIZE)

Constant(WORDSIZE)

Constant(3)

Register(FP)

Estatutos

Estatutos de Asignacin


167/213

Estatutos de Asignacin

=

es representada por el rbol de ensamblador:

Move


168/213

Ejemplo:

Void main() {

int x;

int y;

y =x + 4;

}

Move

Memory Operator(+)

Operator(-)

Constant(4)

Memory

Register(FP)Register(FP)

Constant(4)

Estatuto If


169/213

if () else

se puede traducir en

If () goto IFTRUE

goto IFENDIFTRUE:

IFEND:


170/213

Estatutowhile:while ()


171/213

( )

se puede traducir en

WHILESTART:

if (not ) goto WHILEEND

gotoW

HILESTARTWHILEEND:

aunque es mas eficiente

goto WHILETEST

WHILESTART:

WHILETEST:

if () goto WHILESTART

WHILEEND:

Estatuto for:

for (;;)


172/213

for (;;)

es equivalent a:

while () {

}

Entonces queda como:

goto FORTESTFORSTART:

FORTEST:


173/213

Definiciones de Funcin o Mtodos:

El ensamblador abstracto debe:


174/213

El ensamblador abstracto debe: Guardar el viejo SP, FP y registros de direccin de retorno en la pila.

Apuntar el FP al inicio del RA actual.Apuntar el SP al final del RA actual. Incluir el ensamblador para el cuerpo de la funcin. Restaurar el viejo SP, FP y registros de direccin de retorno (el FP al ltimo si seusa para referenciar los datos en la pila). Retornar del mtodo, con una instruccin de ensamblador abstracto return. Incluir etiquetas despus del cuerpo para instrucciones return desde adentro delcuerpo

El cdigo ensamblador queda as:

Creacin de rboles de EnsambladorAbstracto (AAT) en Java


175/213

( )

Para construir AAT en Java, primerodefinimos una interfase para construir AATspara estatutos y para expresiones.

Entonces, se agregan en el anlisissemntico llamadas a las funciones definidasen la interfase.

De esta forma, el analizador semnticoconstruir los AATs al igual que checar porlos errores semnticos.


176/213


177/213


178/213

Igual, el ensamblador abstracto para el estatuto b = 2; y c= a + 1, puede crearse con:


179/213

AATEstatement s1, s2;

s1 = bt.assignmentStatemen(bt.baseVariable(0), bt.constantExpression(2));

s2 = bt.assignment(bt.BaseVariable(-4), bt.operatorExpression(bt.baseVariable(4), bt.constantExpression(1),

AATOperator.PLUS));

Finalmente, dadas las definiciones anteriores, el ensamblador abstracto para el estatutoif (a > 2) b = 2 else c= a + 1; puede crearse con:

AATstatement s3;

s3 = bt.ifStatement(e1,s1,s2);


180/213


181/213


182/213


183/213

VIII Generacin de Cdigo


184/213

La funcin de un generador de cdigo esbsicamente la traduccin de la salida del anlisissintctico y semantico (el cdigo intermedio) a unasecuencia equivalente de instrucciones que puedenejecutarse en la maquina destino.

El cdigo debe ser correcto y optimo. El generador de cdigo toma las desiciones

bsicas: Asignar Registros.- Registros generales, Prop. Especficos,

pares, impares, registros ndices, etc. Seleccin de Instrucciones.- La mejor secuencia de

instrucciones (la optima). Por ejemplo elegir INC en lugarde MOV ADD.

En el caso de nuestro compilador una vez que se ha creado un


185/213

En el caso de nuestro compilador, una vez que se ha creado un

rbol de ensamblador, el prximo paso es crear cdigoensamblador para una mquina especfica.

Generaremos cdigo ensamblador por medio de usar tiles pararellenar huecos, con el rbol de ensamblador abstracto.

Vamos a crear un conjunto de tiles o rellenos cada uno de loscuales pueden cubrir una porcin pequea de un rbol deensamblador abstracto.

Para generar el ensamblador real para un rbol de ensamblador

especfico, primero cubriremos el rbol con tiles, asegurndoseque todas las partes del rbol estn cubiertas y que no existantiles traslapados. Despus, se producir el ensambladorasociado con cada tile.

Cdigo Ensamblador ObjetoUsaremos un subconjunto del ensamblador para MIPS

Instruction Description


186/213

lw rt, (base) Add the constant value to the register base to get an address. Load the contents of this address into theregister rt. Rt = M[base + ]

sw rt, (base) Add the constant value to the register base to get an address. Store the contents of rt into this address.M[base + ] = rt

add rd, rs, rt Add contents of register rs and rt, put result in register rd.

sub rd, rs, rt Subtract contents of register rt from rs, put result in register rd.

addi rt, rs, Add the constant value to register rs, put result in register rt.

mult rs, rt Multiply contents of register rs by register rt, put the low order bits in register LO and the high bits in register HI

div rs, rt Dive contents of register rs by register rt, put the quotient in register LO and the remainder in register HI

mflo rd Move contents of the special register LOW into the register rd.

j Jump to the assembly label .

jal jump and link. Put the address of the next instruction in the return register, and then jump to the address .Used for function and procedure calls.

jr rs Jump to the address stored in register rs. Used in conjunction withjal to return from function and procedure calls

slt rd, rs, rt if rs < rt, rd = 1, else rd = 0

beq rs, rt, if rs == rt, jump to the label

bne rs, rt, if rs rt,jump to the label

bltz rs, if rs < 0,jump to the label

Bgez rs, if rs 0, jump to the label

Register that we will use for code generation


187/213

MnemonicName

SPIMName

Description

$FP $fp Frame pointer points to the top of the current activation record

$SP $sp Stack Pointer Used for the activation record stack

$ESP $esp Expression Stack Pointer The next expression stack holds temporary values forexpression avaluations

$result $v0 Result Register Holds the return value for functions

$return $ra Result Register Holds the return address for the current function

$zero $zero Zero register This register always has the value 0

$ACC $t0 Accumulator Register Used for expressioncalculation

$t1 $t1 General Purpose Register



TilingSimple


188/213

Usaremos una pila para guardar valores temporales enexpresiones. Esta pila estar adems de la pila normal de RA.

Primero describiremos una forma de producir cdigo ineficiente. Despus veremos como producir cdigo mas eficiente. Tilingsimple est basado en un recorridopost-orderdel rbol de

ensamblador abstracto. Esto es, despus de cubrir el rbol con tiles, emitiremos cdigo para

cada tile en una formapost-order. Primero emitiremos recursivamente tiles para cada uno de los sub-

rboles del rbol de ensamblador, de izquierda a derecha.

Despus, emitiremos el cdigo para el tile de la raz del rbol.

Ejemplos:


189/213

Tiling Simple para rboles de Expresiones.El cdigo asociado con el tile colocar el valor de la expresin en el tope de lapila de expresiones.

Expresiones de ConstantesConsidere el siguiente rbol:

Constant(5)El cdigo asociado con este tile necesita poner un 5 en el tope de la pila deexpresiones.

addi$t1, $zero, 5 % Load the constant value 5 into the register $t1

sw $t1, 0($ESP) % Store $t1 on the top of the expression stack

addi$

ESP,$

ESP, -4 % Update the expression stack pointer

En general, el tile para cualquier valor constante x es:

addi$t1, $zero, x % Load the constant value into x the register $t1

sw $t1, 0($ESP) % Store $t1 on the top of the expression stack

addi$ESP, $ESP, -4 % Update the expression stack pointer

Operaciones de Aritmtica Binaria


190/213

+

Constant(3) Constant(4)

En lugar de tratar de cubrir todo el rbol con un tile, usaremos tres. Laconstante 4 y 5 pueden cubrirse cada una con un tile de constante, yusaremos un tile + para cubrir la suma.

+


Cmo debe ser el cdigo para +?Recordemos que emitimos cdigo en post-order (subrbolizquierdo, subrbol derecho y luego raz). Podemos asumir


191/213

que los valores de los operandos de la izquierda y laderecha de el + ya estn en la pila cuando el cdigo de el tile+ es emitido. Ntonces, todo lo que necesitamos es hacer essacar (pop off) esos valores , hacer la suma y meter (push)el resultado de regreso a la pila. El cdigo para el tile + es:

lw $t1, 8(ESP) % Load the first operand into temporary $t1

lw $t2, 4(ESP) % Load the second operand into temporary $t2

add $t1, $t1, $t2 % Do the addition. Storing result in $t1

sw $t1, 8(ESP) % Store the result on the expression stackadd $ESP, $ESP, 4 % Update the expression stack pointer


192/213

RegistrosConsidere el rbol de expresin

Register(FP)


193/213

Esto ocupa un tile.

sw $FP, 0($ESP)addi $ESP, ESP, -4

Combinando otros tiles discutidos antes, el rbol

-


Puede ser los tiles:-


Produciendo el rbol

sw $FP 0($ESP) % Store frame pointer on the top of the expression stack


194/213

sw $FP, 0($ESP) % Store frame pointer on the top of the expression stack

addi $ESP, $ESP, -4 % Update the expression stack pointer

addi $t1, $zero, 8 % Load the constant value 8 into the register$t1

sw $t1, 0($esp) % Store $t1 on the top of the expression stack


lw $t1, 8($ESP) % Load the first operand into temporary $t1

lw $t2, 4($ESP) % Load the second operand into temporary $t2

sub $t1, $t1, $t2 % Do the subtraction, storing result in $t1

sw $t1, 8($ESP) % Store the result on the expression stack

add $ESP, $ESP, 4 % Update the expression stack pointer

Operaciones relacionalesARBOL ABSTRACTO:


195/213

>


>


TILES:

El cdigo para > es:

lw $t1, 8($ESP)lw $t2 4($ESP)


196/213

lw $t2, 4($ESP)

slt $t1, $t2, $t1sw $t1, 8($ESP)addi $ESP, $ESP, 4

Thus, one posibility for the code for the == tile is:

lw $t1, 8($ESP)lw $t2, 4($ESP)slt $t3, $t2, $t1 % $t3= (x < y)slt $t2, $t1, $t2 % $t2 = (y < x)add $t1, $t1, $t2 % $t1 = (x < y) I I (y


197/213

Lw $t1, 4 ($ESP) % Pop the address to dereference off the top of the

% expression stacklw $t1, 0($t1) % Dereference the pointer sw $t1, 4($ESP) % Push the result back on the expression stack

Memory

-


Los tiles son: Memory

-


Ejemplo: El rbol de expresinPara una variable simple es.

Que resulta en el siguiente ensamblador:

sw $FP, 0($ESP) % Store frame pointer on the top of the expression stack


addi $t1, $zero, 12 % Load the constant value 12 into the register $t1


198/213

sw $t1, 0($ESP) % Store $t1 on the top of the expression stackaddi $ESP, $ESP, -4 % Update the expression stack pointer

lw $t1, 4($ESP) % Load the first operand into temporary $t1

lw $t2, 8($ESP) % Load the second operand into temporary $t2

sub $t1, $t1, $t2 % Do the subtraction, storing result in $t1

sw $t1, 8($ESP) % Store the result on the expression stack

add $ESP, $ESP, 4 % Update the expression stack pointer

lw $t1, $4($ESP) % Pop the address to dereference off the top of

% the expression stack

lw $t1, $0($t1) % Dereference the pointer

sw $t1, 4($ESP) % Push the result back on the expression stack

El resultado de este cdigo es: El valor que estaba en memoria (FP 12) es empujado (pushed onto)

en el tope de la pila de expresiones.


199/213


200/213


201/213

Tiles de rboles de Estatutos

Mientras que el cdigo de ensamlador para rboles de expresionesmete (push) el valor de la expresin en el tope de la pila de


202/213

mete (push) el valor de la expresin en el tope de la pila de

expresiones, el cdigo ensamblador para rboles de estatutosimplementa el estatuto descrito por el rbol.

rboles de EtiquetasEl subrbol Label(label1) puede ser cubierto con solo un tile. Elcdigo para ese tile es:

Label1:

rboles para MoveEl lado izquierdo de un MOVE necesita que sea un registro o unalocalidad de memoria.Ejemplo:

Move

Register(r1) Constant(8)

Ser dividido en los tiles:

Move


203/213

Register(r1) Constant(8)

Considere el tile del MOVE registro:

Move

Register(r1)

Cuando el cdigo para este tile es ejecutado, el valor que es cargadoal registro est ya en el tope de la pila de expresiones. Entonces, todolo que necesitamos hacer es sacar el valor de la pila de expresiones ymeterlo al registro.

El tile del MOVE tiene el siguiente cdigo asociado:

lw $r1, 4($ESP) % load the rhs of the move into a register


204/213

addi $ESP, $ESP, 4 % update expression stack pointer

Todo el cdigo para el rbol es:

addi $t1, $zero, 8 % Store the constant 8 in a register sw $t1, 0($ESP) % Push the value on the expression stack

addi $ESP, $ESP, -4% Update the expression stack pointer

lw $r1, 4($ESP) % load the rhs of the move into a register

addi $ESP, $ESP, 4 % update expression stack pointer

Veamos ahora un MOVE a memoria. Consideremos el siguiente rbol:

Move

Constant(4)Memory


205/213

Register(FP)

El rbol puede tener los tiles:

Move

Constatnt(4)Mem

Register(FP)

El tile MOVE a memoria es:

Move

Necesita sacar dos valores del tope de la pila el destino del MOVE yel valor a almacenarse.

lw $t1, 8($ESP)

lw $t2 4($ESP)


206/213

lw $t2, 4($ESP)

sw $t2, 0($t1)

addi $ESP, $ESP, 8

Todo el rbol se puede implementar con el sig. Cdigo:

sw $FP 0($ESP)addi $ESP, $ESP, -4

addi $t1, $ZERO, 4

sw $t1, 0($ESP)

addi $ESP, $ESP, -4

lw $t1, 8($ESP)

lw $t2, 4($ESP)

sw $t2, 0($t1)

Addi $ESP, $ESP, 8


207/213

El cdigo que emitimos para el subrbol de la expresin jumpcondicional pone el valor de la expresin en el tope de la pila deexpresiones. Asi, necesitamos sacar la expresin del tope de la pila deexpresiones, y saltar a la etiqueta jumplab si la expresin es

8/3/2019 CURSOPro

cursoprogsist

Documents