#writing | enscriptions | Explore Tumblr posts and blogs

davidhaltinner · 7 years ago

Text

Self compiling C compiler, written in C

// symboltable.h

#ifndef _SYMBOLTABLE_GUARD #define _SYMBOLTABLE_GUARD

using namespace std;

#include <string> #include "symbol.h" #include <list> #include <iostream>

// David Haltinner ******************************************************* // The SymbolTable class implements a symbol table, which is a set of // pointers to Symbols. // David Haltinner ******************************************************* // // public member functions // ======================= // // constructor/destructor // ====================== // not needed -- the defaults work fine // // mutators/modifiers // ================== // void Insert(SymbolPtr sym) -- add sym to the table (error if there is // -- already a symbol with the same name) // // other operations // ================ // SymbolPtr Lookup(string k) -- if there is a symbol with the given name, // -- return a pointer to it; // -- otherwise, return NULL // Print(ostream & out) // �� -- print the names of all the symbols, one // -- per line, to the given output stream

class SymbolTable { public: // mutator/modifier member functions

void Insert(SymbolPtr sym);

// other operations

SymbolPtr Lookup(string k); void Print(ostream &out);

private: static const int TABLESIZE = 17; list<SymbolPtr> bucket[TABLESIZE]; int Hash(string & S); };

#endif # Makefile for p4

CC = g++ CFLAGS = -Wall -g

LEX = flex LEXLIB = -lfl YACC = bison -yd

OBJ = main.o message.o symbol.o symboltable.o symlist.o ast.o \ y.tab.o lex.yy.o namecheck.o typecheck.o unparse.o int2str.o\ codegen.o emit.o

p5: $(OBJ) $(CC) $(OBJ) -o p5 $(LEXLIB) wosym: main.o message.o symbol.o symboltable.o symlist.obj ast.o y.tab.o lex.yy.o namecheck.o typecheck.o unparse.o int2str.o $(CC) main.o message.o symbol.o symboltable.o symlist.obj ast.o y.tab.o lex.yy.o namecheck.o typecheck.o unparse.o int2str.o -o p4 $(LEXLIB)

main.o: main.cc ast.h symbol.h scanner.h $(CC) -c $(CFLAGS) main.cc message.o: message.cc message.h $(CC) -c $(CFLAGS) message.cc symbol.o: symbol.cc symbol.h $(CC) -c $(CFLAGS) symbol.cc symboltable.o: symboltable.cc symbol.h symboltable.h $(CC) -c $(CFLAGS) symboltable.cc symlist.o: symlist.cc symlist.h $(CC) -c $(CFLAGS) symlist.cc ast.o: ast.cc ast.h symbol.h $(CC) -c $(CFLAGS) ast.cc unparse.o: unparse.cc ast.h symbol.h y.tab.h $(CC) -c $(CFLAGS) unparse.cc

int2str.o: int2str.cc int2str.h $(CC) -c $(CFLAGS) int2str.cc

namecheck.o: namecheck.cc ast.h symbol.h symboltable.h message.h \ symlist.h $(CC) -c $(CFLAGS) namecheck.cc typecheck.o: typecheck.cc ast.h symbol.h symboltable.h message.h \ symlist.h $(CC) -c $(CFLAGS) typecheck.cc

codegen.o: codegen.cc ast.h emit.h scanner.h y.tab.h message.h symlist.h\ symboltable.h int2str.h $(CC) -c $(CFLAGS) codegen.cc

emit.o: emit.cc emit.h ast.h message.h int2str.h $(CC) -c $(CFLAGS) emit.cc

y.tab.o: y.tab.c $(CC) -c $(CFLAGS) y.tab.c y.tab.h: y.tab.c touch y.tab.h y.tab.c: grammar.yacc ast.h symbol.h scanner.h $(YACC) grammar.yacc

lex.yy.o: lex.yy.c ast.h symbol.h scanner.h message.h int2str.h y.tab.h $(CC) -c $(CFLAGS) lex.yy.c -DYY_NO_UNPUT lex.yy.c: tokens.lex y.tab.h $(LEX) tokens.lex

listings: enscript -2r -P halseyLinux \ main.cc Makefile codegen.cc

test: Go clean: /bin/rm -f *.o lex.yy.c y.tab.* erase: /bin/rm -f *.o *.s lex.yy.c y.tab.* p5 preClean: /bin/rm -f *.s // symlist.h

#ifndef SYMLIST_H_ #define SYMLIST_H_

#include <list> #include <string>

#include "symboltable.h" using namespace std;

typedef SymbolTable *PSymbolTable;

class SymTableList {

public: SymTableList(); ~SymTableList();

void push( PSymbolTable v ); // AddToFront PSymbolTable pop(); // RemoveFromFront PSymbolTable top(); // current scope

SymbolPtr lookUp( string id ); // is id in any scope?

private: list<PSymbolTable> * symTableList; // STL list };

#endif // message.cc

#include <iostream> #include <iomanip> #include "message.h"

// GLOBAL VARIABLE bool errorFlag = false;

// David Haltinner ******************************************************* // Error // write the given error message, preceded by <line>:<col> to cerr // also set the global errorFlag to true // David Haltinner ******************************************************* void Error(int line, int col, string msg) { cerr << "ERROR line " << setw(2) << line << " column " << setw(2) << col << ": " << msg << endl; errorFlag = true; }

// David Haltinner ******************************************************* // Warn // write the given warning message, preceded by <line>:<col> to cerr // David Haltinner ******************************************************* void Warn(int line, int col, string msg) { cerr << "WARNING line " << setw(2) << line << " column " << setw(2) << col << ": " << msg << endl; }

// David Haltinner ******************************************************* // InternalError // write the given error message to cerr and quit // David Haltinner ******************************************************* void InternalError(string msg) { cerr << endl << "INTERNAL COMPILER ERROR: " << msg << endl<<endl; exit(1); } // this is just a test of string labels for print

int main(){ print("This is a test of the labeling"); print("\n"); print("This is a test of the labeling"); print("\n"); print("This is a test of the labeling"); print("\n"); print("This is a test of the labeling"); print("\n"); print("I hope this works"); print("\n"); print("This is a test of the labeling"); print("\n"); print("I hope this works"); print("\n"); print("This is a test of the labeling"); print("\n"); print("I hope this works"); print("\n"); print("This is a"); print("\n"); print("This is a test of the labeling"); print("\n"); } // test of various types of globals

int x; bool y; int w[2]; bool z[2];

int t(){ int x; bool z; z = true && y; // 1st true 2nd false x = 99; // 1st the then is executed // 2nd the else is executed if(z){ print("z is ", z, " x is ", x); print("\n"); x = 3; } else{ print("z failed", "\n"); x = 1; }

return x; }

int main(){ y = 3 == 3 && 4 < 5 && 7 != 9; // true x = 7; print("X before ", x, "\n"); w[0] = t(); print("X after ", x, "\n"); y = false; z[0] = false; z[1] = false; w[1] = t(); // this executes if(w[0] != w[1]){ print("Just as I thought", "\n"); print("W[0] is ", w[0], " and W[1] is ", w[1], "\n"); } return 1; } /* grammar.yacc */

%{ // stuff here is copied directly into y.tab.c above (outside of) yyparse()

#include "ast.h" #include "scanner.h"

// bison needs these two forward declarations (but yacc doesn't) extern int yylex(); int yyerror( char *msg);

// just need "one" null node // don't need to create a "new" null node every time we need one static NullNode * NULLnode = new NullNode();

/* define the data type of the value stack (YYSTYPE) the "value" associated with some tokens will be data type TokenType the "value" associated with nonterminals will be data type ...Node * */

%union{ TokenType t;

ProgramNode * Program ; GlobalListNode * GlobalList ; FunctionListNode * FunctionList ; FunctionDeclNode * FunctionDecl ; TypeNode * Type ; ParametersNode * Parameters ; ParamListNode * ParamList ; ParamNode * Param ; VarListNode * VarList ; DeclNode * Decl ; ArgListNode * ArgList ; StmtListNode * StmtList ; StmtNode * Stmt ; PrintListNode * PrintList ; PrintItemNode * PrintItem ; CoutListNode * CoutList ; CoutItemNode * CoutItem ; OrNode * Or ; AndNode * And ; RelOpNode * RelOp ; ArithOpNode * ArithOp ; ExpressionNode * Expression ; TargetNode * Target ; IdentifierNode * Identifier ; StringLiteralNode * StringLiteral ; }

/* since the value stack is a struct(union), it seems we need to use the notation $2.t or $$.a; the actual ugly notation is $<t>2 or $<a>$ the %type directive lets us use $2 or $$ because it tells yacc/bison which member of the struct(union) should be referenced */

/*** do not change these token and type specifications! ***/ /* David Haltinner ====================================================== */ %token SEMICOLON RPAREN RBRACE RBRACKET %token <t> ID INTLITERAL STRINGLITERAL ASSIGN PRINT INT VOID TRUE FALSE %token <t> LPAREN LBRACE LBRACKET PLUS MINUS TIMES SLASH BOOL AND OR %token <t> IF ELSE WHILE RETURN LT GT LEQ GEQ EQ NEQ COMMA %token <t> COUT AARROW

%type <Program> program %type <GlobalList> globalList %type <FunctionList> functionList %type <FunctionDecl> functionDecl %type <Type> type %type <Decl> variableDecl %type <Parameters> parameters %type <ParamList> paramList %type <Param> param %type <VarList> varList %type <StmtList> stmtList %type <ArgList> argList %type <Stmt> stmt %type <PrintList> printList %type <PrintItem> printItem %type <CoutList> coutList %type <PrintItem> coutItem

%type <Expression> expression %type <Expression> term %type <Expression> factor %type <Expression> primary %type <Expression> unit %type <Expression> nameVar %type <Expression> arrayVar %type <Expression> intLiteral

%type <Expression> ORexpression %type <Expression> ANDexpression %type <Expression> ORlist %type <Expression> ANDlist

%type <Target> target %type <Identifier> identifier %type <StringLiteral> stringLiteral /* David Haltinner ====================================================== */

%nonassoc THEN %nonassoc ELSE

%start program

program : globalList functionList { astRoot = new ProgramNode($1,$2, $1->line,$1->column); } ;

globalList : globalList variableDecl { $$ = new GlobalListNode($1, $2, $1->line,$1->column ); } | { $$ = (GlobalListNode *)NULLnode; } ;

functionList : functionList functionDecl { $$ = new FunctionListNode($1, $2, $2->line, $2->column); } | functionDecl {$$ = new FunctionListNode( (FunctionListNode *)NULLnode, $1,$1->line,$1->column);} ;

type : INT {$$ = new TypeIntNode ( $1.line,$1.column ); } | BOOL {$$ = new TypeBoolNode( $1.line, $1.column); } ;

variableDecl : type identifier SEMICOLON {$$ = new VariableDeclNode( $1,$2, $2->line,$2->column );} | type identifier LBRACKET intLiteral RBRACKET SEMICOLON {$$ = new ArrayDeclNode($1, $2, $4, $2->line, $2->column );} ;

functionDecl : VOID identifier parameters LBRACE varList stmtList RBRACE {$$ = new FunctionDeclNode( (TypeNode *)NULLnode, $2,$3,$5,$6,$2->line,$2->column);} | type identifier parameters LBRACE varList stmtList RBRACE {$$ = new FunctionDeclNode($1, $2, $3, $5, $6, $2->line, $2->column);} ;

parameters : LPAREN RPAREN { ParamListNode * n = (ParamListNode *)NULLnode; $$ = new ParametersNode( n, $1.line,$1.column ); } | LPAREN paramList RPAREN { $$ = new ParametersNode($2, $1.line, $1.column); } ;

paramList : paramList COMMA param { $$ = new ParamListNode($1, $3, $2.line, $2.column); } | param { $$ = new ParamListNode( (ParamListNode *)NULLnode, $1, $1->line, $1->column); } ;

param : type identifier { $$ = new ParamValNode($1, $2, $1->line, $1->column); } | type identifier LBRACKET RBRACKET { $$ = new ParamArrayNode($1, $2, $1->line, $1->column); } ;

varList : { $$ = (VarListNode *)NULLnode; } | varList variableDecl { $$ = new VarListNode($1, $2, $1->line, $1->column); } ;

stmtList : stmtList stmt { $$ = new StmtListNode( $1, $2, $1->line,$1->column ); } | { $$ = (StmtListNode *)NULLnode; } ;

stmt : target ASSIGN expression SEMICOLON { $$ = new AssignNode( $1, $3, $2.line,$2.column ); } | PRINT LPAREN printList RPAREN SEMICOLON { $$ = new PrintNode( $3, $1.line,$1.column ); } | COUT AARROW coutList SEMICOLON { $$ = new CoutNode( $3, $1.line, $1.column ); } | IF LPAREN expression RPAREN stmt %prec THEN { $$ = new IfNode($3, $5, (StmtNode *)NULLnode, $2.line, $2.column); } | IF LPAREN expression RPAREN stmt ELSE stmt { $$ = new IfNode($3, $5, $7, $2.line, $2.column); } | WHILE LPAREN expression RPAREN stmt { $$ = new WhileNode($3, $5, $1.line, $1.column); } | LBRACE varList stmtList RBRACE { $$ = new BlockNode($2, $3, $1.line, $1.column); } | RETURN SEMICOLON { $$ = new ReturnNode((ExpressionNode *)NULLnode, $1.line, $1.column); } | RETURN expression SEMICOLON { $$ = new ReturnNode($2, $1.line, $1.column); } | identifier LPAREN RPAREN SEMICOLON { ArgListNode * n = (ArgListNode *)NULLnode; $$ = new ProcCallNode($1, n, $2.line, $2.column); } | identifier LPAREN argList RPAREN SEMICOLON { $$ = new ProcCallNode($1, $3, $2.line, $2.column); } ;

argList : argList COMMA expression { $$ = new ArgListNode($1, $3, $1->line, $1->column); } | expression { $$ = new ArgListNode((ArgListNode *)NULLnode, $1, $1->line, $1->column); } ;

printList : printList COMMA printItem { $$ = new PrintListNode($1, $3, $1->line, $1->column); } | printItem { PrintListNode * n = (PrintListNode *)NULLnode; $$ = new PrintListNode( n, $1, $1->line,$1->column); } ;

printItem : stringLiteral { $$ = $1; } | expression { $$ = $1; } ;

coutList : coutList AARROW coutItem { $$ = new CoutListNode($1, $3, $1->line, $1->column); } | coutItem { CoutListNode *n = (CoutListNode *)NULLnode; $$ = new CoutListNode( n, $1, $1->line, $1->column); } ;

coutItem : stringLiteral {$$ = $1; } | expression {$$ = $1; };

expression : ORexpression { $$ = $1; };

ORexpression: ORlist { $$ = $1; };

ORlist: ORlist OR ANDexpression { $$ = new OrNode($1, $3, $2.line, $2.column); } | ANDexpression { $$ = $1; } ;

ANDexpression: ANDlist { $$ = $1; };

ANDlist: ANDlist AND term { $$ = new AndNode($1, $3, $2.line, $2.column); } | term { $$ = $1; };

term : factor LT factor { $$ = new RelOpNode( LT, $1, $3, $2.line, $2.column); } | factor GT factor { $$ = new RelOpNode( GT, $1, $3, $2.line, $2.column); } | factor LEQ factor { $$ = new RelOpNode( LEQ, $1, $3, $2.line, $2.column); } | factor GEQ factor { $$ = new RelOpNode( GEQ, $1, $3, $2.line, $2.column); } | factor EQ factor { $$ = new RelOpNode( EQ, $1, $3, $2.line, $2.column); } | factor NEQ factor { $$ = new RelOpNode( NEQ, $1, $3, $2.line, $2.column); } | factor { $$ = $1; } ;

factor : factor PLUS primary { $$ = new ArithOpNode( PLUS , $1, $3, $2.line,$2.column ); } | factor MINUS primary { $$ = new ArithOpNode( MINUS, $1, $3, $2.line,$2.column ); } | primary { $$ = $1; } ;

primary : primary TIMES unit { $$ = new ArithOpNode( TIMES, $1, $3, $2.line, $2.column); } | primary SLASH unit { $$ = new ArithOpNode( SLASH, $1, $3, $2.line, $2.column); } | unit { $$ = $1; } ;

unit : nameVar { $$ = $1; } | arrayVar { $$=$1;} | intLiteral { $$=$1;} | MINUS intLiteral { $$=$2; $$->myIntVal=-$2->myIntVal;} | identifier LPAREN RPAREN { $$= new FnCallNode($1, (ArgListNode *)NULLnode, $2.line, $2.column); } | identifier LPAREN argList RPAREN { $$= new FnCallNode($1, $3, $2.line, $2.column); } | TRUE { $$ = new TrueNode($1.line, $1.column);} | FALSE { $$ = new FalseNode($1.line, $1.column);} | LPAREN expression RPAREN { $$=$2; } ;

nameVar : identifier { $$ = new NameVarNode( $1, $1->line,$1->column ); };

arrayVar: identifier LBRACKET expression RBRACKET { $$ = new ArrayVarNode( $1, $3, $1->line, $1->column); };

intLiteral : INTLITERAL { $$ = new IntLiteralNode($1.intVal, $1.line,$1.column); };

stringLiteral : STRINGLITERAL { $$ = new StringLiteralNode($1.stringVal, $1.line, $1.column);};

target : identifier { ExpressionNode * n = (ExpressionNode *)NULLnode; $$ = new TargetNode( $1, n, $1->line,$1->column ); } | identifier LBRACKET expression RBRACKET { $$ = new TargetNode($1, $3, $1->line, $1->column ); } ;

identifier : ID { $$ = new IdentifierNode($1.stringVal, $1.line,$1.column); } ;

extern char *yytext; /* we must supply the yyerror function */ /* bison demands int; yacc accepts int or void */ int yyerror( char *msg ) { cerr << "\nbison: " << msg << " line " << yylval.t.line << " column " << yylval.t.column << " (yytext=\"" << yytext << "\")\n\n"; exit(1); } // symbol.h

#ifndef SYMBOL_GUARD #define SYMBOL_GUARD

#include <string> using namespace std;

// ********************************************* // The Symbol class defines a symbol-table entry // ********************************************* // // Member functions // ================ // // constructor // =========== // Symbol(string S) -- constructor: creates a Symbol with the given name //

enum SymbolType {VoidType, IntType, BoolType, StringType, ErrorType}; enum SymbolKind {VarKind,ArrayKind, FnKind, ValParamKind,ArrayParamKind, ErrorKind}; enum SymbolAdr {Global, Local};

class Symbol { public: Symbol(string S); // constructor

string symbolName; // symbol name

//set by the name checker

SymbolType symbolType; SymbolKind symbolKind;

int arraySize; int offset; int parameterCount; // only for functions int localVarCount; // only for functions int frameSize; // only for functions

//set by the code generator

SymbolAdr adr;

// class function (for debugging) static string printSymbolType( SymbolType t ); };

typedef Symbol * SymbolPtr;

#endif // t1.z // A demonstration of bools and if // it also prints intLits and global ints, and string lits

int x; int y; bool b; bool t; bool f;

int main() { x = 3; y = x; print( x, " ", y, " ", 5 ); print("\n");

if (true ) print("true"); else print("false"); print("\n"); if (false) print("true"); else print("false"); print("\n");

t = true; f = false; b = true ; if (b) print("true"); else print("false"); print("\n"); b = false; if (b) print("true"); else print("false"); print("\n"); b = t ; if (b) print("true"); print("\n"); t = f ; if (t) print("true"); else print("false"); print("\n");

return 0; } // ast.h

#ifndef AST_H_ #define AST_H_

#include <iostream> #include <iomanip> #include "symbol.h"

// forward class GlobalListNode ; class FunctionListNode ; class DeclNode ; class FunctionDeclNode ; class TypeNode ; class ParametersNode ; class ParamListNode ; class ParamNode ; class VarListNode ; class StmtListNode ; class StmtNode ; class ArgListNode ; class PrintListNode ; class PrintItemNode ; class ExpressionNode ; class TargetNode ; class IntLiteralNode ; class CoutListNode ; class CoutItemNode ;

class ASTnode // ABSTRACT BASE CLASS { public:

// every node will have a line number and a column number // so unparsing can produce a kind of pretty-printing const int line ; const int column; void doLineNum() { cout << setw(6) << line << ": "; } int Reg; int lbl;

SymbolType nodeType;

ASTnode(int l, int c) : line(l), column(c) {};

virtual bool isNull () { return false; } virtual bool isBlock() { return false; } virtual bool isName() { return false; } virtual bool isOr() { return false; } virtual bool isAnd() { return false; } virtual bool isRel() { return false; } virtual bool isTrue() { return false; } virtual bool isFalse() { return false; } virtual void unparse(int indent=0) =0; virtual void checkNames() =0; virtual void checkTypes() =0; virtual void emitCode() =0; private:

// disable copy constructor and copy assignment operator ASTnode(const ASTnode & n); ASTnode & operator= (const ASTnode & n); };

class IdentifierNode : public ASTnode { private: string * myStringVal; Symbol * mySymbolTableEntry; public: IdentifierNode(string *, int, int); string getMyStringVal() { return * myStringVal; } void setMySymbolTableEntry(Symbol * s) { mySymbolTableEntry = s; } Symbol * getSymbol() { return mySymbolTableEntry; } virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode() {return;} };

class ProgramNode : public ASTnode { private: GlobalListNode * myGlobalList; FunctionListNode * myFunctionList; public: ProgramNode(GlobalListNode*, FunctionListNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class GlobalListNode : public ASTnode { private: GlobalListNode * myGlobalList; DeclNode * myDecl; public: GlobalListNode(GlobalListNode*, DeclNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class FunctionListNode : public ASTnode { private: FunctionListNode * myFunctionList; FunctionDeclNode * myFunctionDecl; public: FunctionListNode(FunctionListNode*, FunctionDeclNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class FunctionDeclNode : public ASTnode { private: TypeNode * myType; IdentifierNode * myIdentifier; ParametersNode * myParameters; VarListNode * myVarList; StmtListNode * myStmtList; Symbol * mySymbolTableEntry; public: FunctionDeclNode( TypeNode*, IdentifierNode*, ParametersNode*, VarListNode*, StmtListNode*, int, int); void setMySymbolTableEntry(Symbol * s) { mySymbolTableEntry = s; } virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class TypeNode : public ASTnode // ABSTRACT BASE CLASS { public: TypeNode(int, int); virtual void unparse(int indent=0) =0; virtual void checkNames() = 0; virtual void checkTypes() = 0; }; // --------------- SUBCLASSES OF TypeNode --------------- class TypeIntNode : public TypeNode { public: TypeIntNode(int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class TypeBoolNode : public TypeNode { public: TypeBoolNode(int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); }; // --------------- SUBCLASSES OF TypeNode ---------------

class DeclNode : public ASTnode // ABSTRACT BASE CLASS { public: DeclNode(int, int); virtual void unparse(int indent=0) =0; virtual void checkNames() = 0; virtual void checkTypes() = 0; virtual void emitCode() = 0; }; // --------------- SUBCLASSES OF DeclNode ---------------

class VariableDeclNode : public DeclNode { private: TypeNode * myType; IdentifierNode * myIdentifier; public: VariableDeclNode(TypeNode*, IdentifierNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class ArrayDeclNode : public DeclNode { private: TypeNode * myType; IdentifierNode * myIdentifier; ExpressionNode * myIntLit; public: ArrayDeclNode(TypeNode*, IdentifierNode*, ExpressionNode*, int,int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); }; // --------------- SUBCLASSES OF DeclNode ---------------

class ParametersNode : public ASTnode { private: ParamListNode * myParamList; public: ParametersNode :: ParametersNode(ParamListNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class ParamListNode : public ASTnode { private: ParamListNode * myParamList; ParamNode * myParam ; public: ParamListNode :: ParamListNode(ParamListNode*, ParamNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class ParamNode : public ASTnode // ABSTRACT BASE CLASS { public: ParamNode :: ParamNode(int, int); virtual void unparse(int indent=0) =0; virtual void checkNames() =0; virtual void checkTypes() =0; virtual void emitCode() =0; }; // --------------- SUBCLASSES OF ParamNode --------------- class ParamValNode : public ParamNode { private: TypeNode * myType ; IdentifierNode * myIdentifier; public: ParamValNode :: ParamValNode(TypeNode*, IdentifierNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class ParamArrayNode : public ParamNode { private: TypeNode * myType ; IdentifierNode * myIdentifier; public: ParamArrayNode::ParamArrayNode(TypeNode*, IdentifierNode*, int,int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); }; // --------------- SUBCLASSES OF ParamNode ---------------

class VarListNode : public ASTnode { private: VarListNode * myVarList; DeclNode * myDecl; public: VarListNode(VarListNode *, DeclNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class StmtListNode : public ASTnode { private: StmtListNode * myStmtList; StmtNode * myStmt; public: StmtListNode(StmtListNode *, StmtNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class StmtNode : public ASTnode // ABSTRACT BASE CLASS { public: StmtNode(int, int); virtual void unparse(int indent=0) =0; virtual void checkNames() =0; virtual void checkTypes() =0; virtual void emitCode() =0; }; // --------------- SUBCLASSES OF StmtNode --------------- class AssignNode : public StmtNode { private: TargetNode * myTarget; ExpressionNode * myExpression; public: AssignNode(TargetNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class IfNode : public StmtNode { private: ExpressionNode * myExpression; StmtNode * myThenStmt; StmtNode * myElseStmt; public: IfNode(ExpressionNode *, StmtNode *, StmtNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class WhileNode : public StmtNode { private: ExpressionNode * myExpression; StmtNode * myStmt; public: WhileNode(ExpressionNode *, StmtNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class BlockNode : public StmtNode { private: VarListNode * myVarList; StmtListNode * myStmtList; public: BlockNode( VarListNode*, StmtListNode*, int, int); virtual bool isBlock() { return true; } virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class ReturnNode : public StmtNode { private: ExpressionNode * myReturnVal; public: ReturnNode(ExpressionNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class ProcCallNode : public StmtNode { private: IdentifierNode * myIdentifier; ArgListNode * myArgList ; public: ProcCallNode(IdentifierNode*, ArgListNode*, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class PrintNode : public StmtNode { private: PrintListNode * myPrintList; public: PrintNode(PrintListNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class CoutNode : public StmtNode { private: CoutListNode * myCoutList; public: CoutNode(CoutListNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames() {return;} virtual void checkTypes() {return;} virtual void emitCode() {return;} }; // --------------- SUBCLASSES OF StmtNode ---------------

class ArgListNode : public ASTnode { private: ArgListNode * myArgList ; ExpressionNode * myExpression;

public: ArgListNode(ArgListNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class PrintListNode : public ASTnode { private: PrintListNode * myPrintList; PrintItemNode * myPrintItem; public: PrintListNode(PrintListNode *, PrintItemNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class CoutListNode : public ASTnode { private: CoutListNode * myCoutList; PrintItemNode * myCoutItem; public: CoutListNode(CoutListNode *, PrintItemNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames() {return;} virtual void checkTypes() {return;} virtual void emitCode() {return;} };

class PrintItemNode : public ASTnode // ABSTRACT BASE CLASS { public: SymbolType myType; Symbol * mySymbolTableEntry; void setMySymbolTableEntry(Symbol * s) { mySymbolTableEntry = s; } PrintItemNode(int,int); virtual void unparse(int indent=0) =0; virtual void checkNames() =0; virtual void checkTypes() =0; virtual void emitCode() =0; };

class ExpressionNode : public PrintItemNode // ABSTRACT BASE CLASS { public: int myIntVal;

ExpressionNode(int,int); virtual void unparse(int indent=0) =0; virtual void checkNames() =0; virtual void checkTypes() =0; virtual void emitCode() =0; int emitRight() { return -1;} int emitLeft() { return -1;} ExpressionNode * getL() {return NULL;} ExpressionNode * getR() {return NULL;} virtual IdentifierNode * getID() {return NULL;} virtual void doSethiUllmanLabeling() =0; virtual void doSethiUllmanCodeGen() =0; int getOp() {return -1;} }; // --------------- SUBCLASSES OF ExpressionNode --------------- class OrNode : public ExpressionNode { private: ExpressionNode * myLeft ; ExpressionNode * myRight ; public: OrNode(ExpressionNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling() { return; } virtual void doSethiUllmanCodeGen() { return; } virtual bool isOr() { return true; } ExpressionNode * getL() {return myLeft;} ExpressionNode * getR() {return myRight;} };

class AndNode : public ExpressionNode { private: ExpressionNode * myLeft ; ExpressionNode * myRight ; public: AndNode(ExpressionNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling() { return; } virtual void doSethiUllmanCodeGen() { return; } virtual bool isAnd() { return true; } ExpressionNode * getL() {return myLeft;} ExpressionNode * getR() {return myRight;} };

class RelOpNode : public ExpressionNode { private: int myRelOp; ExpressionNode * myLeft ; ExpressionNode * myRight; public: RelOpNode(int, ExpressionNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling() { return; } virtual void doSethiUllmanCodeGen() { return; } int emitRight() { myRight->emitCode(); return myRight->Reg;} int emitLeft() { myLeft->emitCode(); return myLeft->Reg;} int getOp() { return myRelOp;} virtual bool isRel() { return true; } };

class ArithOpNode : public ExpressionNode { private: int myArithOp; ExpressionNode * myLeft ; ExpressionNode * myRight; public: ArithOpNode(int, ExpressionNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling(); virtual void doSethiUllmanCodeGen(); };

class FnCallNode : public ExpressionNode { private: IdentifierNode * myIdentifier; ArgListNode * myArgList ; public: FnCallNode(IdentifierNode *, ArgListNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling(); virtual void doSethiUllmanCodeGen(); IdentifierNode * getID() { return myIdentifier; } };

class TrueNode : public ExpressionNode { public: TrueNode(int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling() { return; } virtual void doSethiUllmanCodeGen() { return; } virtual bool isTrue() { return true; } };

class FalseNode : public ExpressionNode { public: FalseNode(int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling() { return; } virtual void doSethiUllmanCodeGen() { return; } virtual bool isFalse() { return true; } };

class NameVarNode : public ExpressionNode { private: IdentifierNode * myIdentifier; public: NameVarNode( IdentifierNode *, int, int); virtual bool isName() { return true;} virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling(); virtual void doSethiUllmanCodeGen(); virtual IdentifierNode * getID() {return myIdentifier;} };

class ArrayVarNode : public ExpressionNode { private: IdentifierNode * myIdentifier; ExpressionNode * myExpression; public: ArrayVarNode( IdentifierNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling(); virtual void doSethiUllmanCodeGen(); };

class IntLiteralNode : public ExpressionNode { public: IntLiteralNode(int, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); virtual void doSethiUllmanLabeling(); virtual void doSethiUllmanCodeGen(); }; // --------------- SUBCLASSES OF ExpressionNode ---------------

class TargetNode : public ASTnode { private: IdentifierNode * myIdentifier; ExpressionNode * myExpression; public: TargetNode(IdentifierNode *, ExpressionNode *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); IdentifierNode * getID() { return myIdentifier; } ExpressionNode * getExp() {return myExpression; } };

class StringLiteralNode : public PrintItemNode { private: string * myStringVal; public: StringLiteralNode(string *, int, int); virtual void unparse(int indent=0); virtual void checkNames(); virtual void checkTypes(); virtual void emitCode(); };

class NullNode : public ASTnode { public: NullNode() : ASTnode(0,0) {} virtual bool isNull() { return true; } virtual void unparse(int indentVal=0) { return; } virtual void checkNames() { return; }; virtual void checkTypes() { return; }; virtual void emitCode() {return;} };

extern ASTnode * astRoot;

#endif /* scanner.h */

#ifndef SCANNER_H_ #define SCANNER_H_

#include <stdio.h> #include <iostream> #include <string> using namespace std;

//input file pointer used by yylex(); defined in lex.yy.c extern FILE *yyin;

struct TokenType { int line; int column; int intVal; // used by integer token string *stringVal; // used by identifier and string tokens };

#endif // namecheck.cc

/* * build symbol table and check for declaration/use errors: * a) multiply declared identifiers * b) undeclared identifiers * find errors with the "main" function * compute offsets and other information */ using namespace std; #include <string> #include "symbol.h" #include "symboltable.h" #include "symlist.h" #include "ast.h" #include "message.h"

#define DEBUG 0 #define BUG(d) if(d)cerr<<whoami()<<endl;cerr.flush();

static SymTableList symList; static SymbolTable * ptrCurrentSymTab;

int declErrors = 0; int currentOffset = 0; int numParameters = 0; int localVarCount = 0; bool isGlobal = true;

void ProgramNode :: checkNames() { // Global Symbol Table symList.push( new SymbolTable ); ptrCurrentSymTab = symList.top(); // ... your code goes here myGlobalList->checkNames(); isGlobal = false; myFunctionList->checkNames(); string str = "main"; if( symList.lookUp(str) == NULL || symList.lookUp(str)->symbolKind != FnKind){ string msg = "function main is missing"; Error(0,0,msg); declErrors++; } symList.pop(); }

void GlobalListNode :: checkNames() { myGlobalList -> checkNames(); myDecl -> checkNames(); }

void FunctionListNode :: checkNames() { myFunctionList -> checkNames(); myFunctionDecl -> checkNames(); } // in file namecheck.cc, these are the only two nodes that // will record a data type in the member nodeType // this is done so that symbols entered in the symbol table // will have complete information // the next pass, implemented in file typecheck.cc, will // give other nodeType members data type information

void TypeIntNode :: checkNames() { nodeType = IntType; } void TypeBoolNode :: checkNames() { nodeType = BoolType; }

void VariableDeclNode :: checkNames() // int x; { myType -> checkNames(); // data type localVarCount++;

// name is being DECLARED // check for multiply-declared variable name

// strategy // we cannot recurse to the identifier node because // identifier node assumes the USAGE of a name // so, we must access identifier node information indirectly // by following the pointer to the identifier node

string varName = myIdentifier -> getMyStringVal(); // variable name Symbol * symbol = ptrCurrentSymTab -> Lookup(varName); // look it up

currentOffset += 4; s->arraySize = 0; ptrCurrentSymTab->Insert(s); myIdentifier->setMySymbolTableEntry(s); } }

void ArrayDeclNode :: checkNames() { myType -> checkNames();

string varName = myIdentifier -> getMyStringVal(); Symbol * symbol = ptrCurrentSymTab -> Lookup(varName);

if (symbol != NULL) { // name is already in the symbol table // ERROR : variable is MULTIPLY_DECLARED string msg = varName + " is already declared"; Error(line,column,msg); declErrors++; } else{ // create symbol Symbol * s = new Symbol(varName); s->symbolType = myType-> nodeType; s->symbolKind = ArrayKind; s->arraySize = myIntLit->myIntVal; if(isGlobal){ s->adr = Global; } else{ s->adr = Local; } localVarCount += s->arraySize; currentOffset += s->arraySize * 4; s->offset = currentOffset - 4; ptrCurrentSymTab->Insert(s); myIdentifier->setMySymbolTableEntry(s); } }

void FunctionDeclNode :: checkNames() { bool multipleDecl = false; currentOffset = 0; numParameters = 0; localVarCount = 0;

myType -> checkNames();

// your code goes here string varName = myIdentifier -> getMyStringVal(); // variable name Symbol * symbol = ptrCurrentSymTab -> Lookup(varName); // look it up

if (varName == "main") { if(myType->isNull() || myType->nodeType == BoolType){ string msg = varName + " does not return int"; Error(line,column,msg); declErrors++; } }

if (symbol != NULL) { // name is already in the symbol table // ERROR : function is MULTIPLY_DECLARED multipleDecl = true; string msg = varName + " is already declared"; Error(line,column,msg); declErrors++; } // create symbol mySymbolTableEntry = new Symbol(varName);

if(!multipleDecl) ptrCurrentSymTab->Insert(mySymbolTableEntry); // make new Symbol table and set it as the current one symList.push(new SymbolTable); ptrCurrentSymTab = symList.top();

myParameters -> checkNames(); currentOffset += 8;

if(numParameters != 0 && varName == "main"){ string msg = varName + " has a parameter"; Error(line, column, msg); declErrors++; } // in either case, keep going; name check body of function myVarList -> checkNames(); myStmtList -> checkNames();

symList.pop(); ptrCurrentSymTab = symList.top();

// if not multiply declared // insert values into Symbol then put it into the symbolTable if(! multipleDecl ){ if(!myType->isNull()){ mySymbolTableEntry->symbolType = myType->nodeType; } else{ mySymbolTableEntry->symbolType = VoidType; } mySymbolTableEntry->symbolKind = FnKind; mySymbolTableEntry->parameterCount = numParameters; mySymbolTableEntry->frameSize = (numParameters + localVarCount + 2) * 4; mySymbolTableEntry->localVarCount = localVarCount; //ptrCurrentSymTab->Insert(mySymbolTableEntry); } }

void ParametersNode :: checkNames() { myParamList->checkNames(); }

void ParamListNode :: checkNames() { myParamList->checkNames(); myParam ->checkNames(); }

void ArgListNode :: checkNames() { myArgList ->checkNames(); myExpression->checkNames(); }

void ParamValNode :: checkNames() { myType -> checkNames(); numParameters++;

string varName = myIdentifier -> getMyStringVal(); // variable name Symbol * symbol = ptrCurrentSymTab -> Lookup(varName); // look it up

if (symbol != NULL) { // name is already in the symbol table // ERROR : variable is MULTIPLY_DECLARED string msg = varName + " is already declared"; Error(line,column,msg); declErrors++; } else{ // create symbol Symbol * s = new Symbol(varName); s->symbolType = myType -> nodeType; s->symbolKind = ValParamKind; s->offset = currentOffset; currentOffset += 4; s->arraySize = 0; s->adr = Local; ptrCurrentSymTab->Insert(s); myIdentifier->setMySymbolTableEntry(s); } }

void ParamArrayNode :: checkNames() { myType -> checkNames(); numParameters++;

string varName = myIdentifier -> getMyStringVal(); // variable name Symbol * symbol = ptrCurrentSymTab -> Lookup(varName); // look it up

if (symbol != NULL) { // name is already in the symbol table // ERROR : variable is MULTIPLY_DECLARED string msg = varName + " is already declared"; Error(line,column,msg); declErrors++; } else{ // create symbol Symbol * s = new Symbol(varName); s->symbolType = myType -> nodeType; s->symbolKind = ArrayParamKind; s->offset = currentOffset; s->adr = Local; currentOffset += 4; ptrCurrentSymTab->Insert(s); myIdentifier->setMySymbolTableEntry(s); } }

void VarListNode :: checkNames() { myVarList->checkNames(); myDecl ->checkNames(); }

void StmtListNode :: checkNames() { myStmtList -> checkNames(); myStmt -> checkNames(); }

void AssignNode :: checkNames() { myTarget -> checkNames(); myExpression -> checkNames(); }

void IfNode :: checkNames() { myExpression-> checkNames(); myThenStmt -> checkNames(); myElseStmt -> checkNames(); }

void WhileNode :: checkNames() { myExpression -> checkNames(); myStmt -> checkNames(); }

void BlockNode :: checkNames() { // make new Symbol table and set it as the current one symList.push(new SymbolTable); ptrCurrentSymTab = symList.top();

// check the children's names myVarList -> checkNames(); myStmtList -> checkNames();

// now that you're leaving take the symboltable off the stack symList.pop(); ptrCurrentSymTab = symList.top(); }

void ReturnNode :: checkNames() { myReturnVal->checkNames(); }

void ProcCallNode :: checkNames() { myIdentifier -> checkNames(); myArgList -> checkNames(); }

void PrintNode :: checkNames() { myPrintList -> checkNames(); }

void PrintListNode :: checkNames() { myPrintList-> checkNames(); myPrintItem-> checkNames(); }

void OrNode :: checkNames() { myLeft -> checkNames(); myRight -> checkNames(); }

void AndNode :: checkNames() { myLeft -> checkNames(); myRight -> checkNames(); }

void RelOpNode :: checkNames() { myLeft -> checkNames(); myRight -> checkNames(); }

void ArithOpNode :: checkNames() { myLeft -> checkNames(); myRight -> checkNames(); }

void TrueNode :: checkNames() { return; }

void FalseNode :: checkNames() { return; }

void NameVarNode :: checkNames() { myIdentifier-> checkNames(); }

void ArrayVarNode :: checkNames() { myIdentifier->checkNames(); myExpression->checkNames(); }

void FnCallNode :: checkNames() { myIdentifier->checkNames(); myArgList ->checkNames(); }

void IntLiteralNode :: checkNames() { return; }

void TargetNode :: checkNames() { myIdentifier->checkNames(); myExpression->checkNames(); }

void StringLiteralNode :: checkNames() { return; }

void IdentifierNode :: checkNames() // name USAGE { // getting here recursively means that a // name is being USED; check for undefined name string varName = getMyStringVal(); Symbol * symbol = symList.lookUp(varName);

if (symbol == NULL){ string msg = varName + " is undeclared"; Error(this->line, this->column, msg); declErrors ++; symbol = new Symbol(varName); symbol->symbolType = ErrorType; ptrCurrentSymTab -> Insert(symbol); } setMySymbolTableEntry(symbol); } // codegen.cc OO

using namespace std; #include "ast.h" #include "scanner.h" #include "y.tab.h" #include "message.h" #include "symlist.h" #include "symboltable.h" #include "int2str.h" #include "emit.h" #include <list> #include <map>

#define BUG(m) // cerr<<m<<endl #define EMIT(m) // emitComment(m)

#define NUMERIC false // Turn on numeric style coding / turn off control flow

void emitPrintString(); void emitPrintInt ( int reg ); void emitPrintBool( int reg );

void emitL ( string label, string opcode="", string arg1="", string arg2="", string arg3="" ); void emitProgramHeader(); void emitProgramFooter(); void emitFunctionPrologue( string fn, int frameSize, int localVarCount ); void emitFunctionEpilogue( string fn, int parameterCount, int frameSize ); void declareGlobalVar ( string name ); void declareGlobalArray( string name, int size ); void emitStringDefinition( string label, string String );

extern ofstream asmFile; extern bool SethiUllmanFlag; static string currentFunctionName(""); static SymbolPtr currentFunctionSym = NULL; map<string, string> l; //// static list<ExpressionNode *> * argumentList = NULL; // David Haltinner ===========================================================

string setRelOp( int kind ) { string s;

switch (kind) { case LT : s = "slt"; break; case LEQ: s = "sle"; break; case GT : s = "sgt"; break; case GEQ: s = "sge"; break; case EQ : s = "seq"; break; case NEQ: s = "sne"; break; default : assert(0); break; } return s; }

string binaryOp( int kind ) { string s;

switch (kind) { case PLUS : s = "add" ; break; case MINUS: s = "sub" ; break; case TIMES: s = "mulo"; break; case SLASH: s = "div" ; break; default : assert(0) ; break; } return s; }

//*************storeIntoTarget is complete**************** void storeIntoTarget( ExpressionNode *astR, TargetNode *astL ) { int reg = astR->Reg; Symbol *ptrL = astL->getID()->getSymbol();

if(ptrL->adr == Global && ptrL->symbolKind == VarKind){ emit( "sw", "$t"+IntToStr(reg), ptrL->symbolName+".v" ); } else if( ptrL->adr == Global && ptrL->symbolKind == ArrayKind){ int regEx = astL->Reg; string regStr = "0($t"+IntToStr(regEx)+")"; emit("sw", "$t"+IntToStr(reg), regStr); freeReg(regEx); } else if( ptrL->adr == Local && ( ptrL->symbolKind == VarKind || ptrL->symbolKind == ValParamKind )){ int o = ptrL->offset; string off = IntToStr(o); if(o > 0) off= "-"+off; emit("sw", "$t"+IntToStr(reg), off+"($fp)"); } else if( ptrL->adr == Local && ptrL->symbolKind == ArrayKind){ int regEx = astL->Reg; int o = ptrL->offset; string off = IntToStr(o); if(o > 0) off= "-"+off; string regStr = off+"($t"+IntToStr(regEx)+")"; emit("sw", "$t"+IntToStr(reg), regStr); freeReg(regEx); } else if( ptrL->adr == Local && ptrL->symbolKind == ArrayParamKind){ int regEx = astL->Reg; string regStr = "0($t"+IntToStr(regEx)+")"; emit("sw", "$t"+IntToStr(reg), regStr); freeReg(regEx); } }

void evaluateCondition( ExpressionNode *ast, string t, string f ) { if(ast->isAnd()) { string right(NextLabel()); evaluateCondition(((AndNode *)ast)->getL(), right, f); emitLabel(right); evaluateCondition(((AndNode *)ast)->getR(), t, f); } else if(ast->isOr()) { string next(NextLabel()); evaluateCondition(((OrNode *)ast)->getL(), t, next); emitLabel(next); evaluateCondition(((OrNode *)ast)->getR(), t, f); } else if(ast->isRel()){ string op; int kind = ((RelOpNode *)ast)->getOp(); int leftReg = ((RelOpNode *)ast)->emitLeft(); int rightReg = ((RelOpNode *)ast)->emitRight(); string left = "$t" + IntToStr(leftReg); string right = "$t" + IntToStr(rightReg); switch (kind) { case LT : op = "blt"; break; case LEQ: op = "ble"; break; case GT : op = "bgt"; break; case GEQ: op = "bge"; break; case EQ : op = "beq"; break; case NEQ: op = "bne"; break; default : assert(0); break; } emit(op, left, right, t); emit("j", f);

freeReg(leftReg); freeReg(rightReg); } else if(ast -> isTrue()){ emit("j", t); } else if(ast -> isFalse()){ emit("j", f); } else{ ast->emitCode(); emit( "beqz", ast->Reg, f ); emit( "j", t ); freeReg(ast->Reg); } } // David Haltinner ===========================================================

void ProgramNode :: emitCode() { emitProgramHeader(); myGlobalList -> emitCode(); myFunctionList -> emitCode(); emitProgramFooter(); }

void GlobalListNode :: emitCode() { myGlobalList -> emitCode(); myDecl -> emitCode(); }

void FunctionListNode :: emitCode() { myFunctionList -> emitCode(); myFunctionDecl -> emitCode(); }

void ParametersNode :: emitCode() { myParamList -> emitCode(); }

void ParamListNode :: emitCode() { myParamList -> emitCode(); myParam -> emitCode(); }

void VarListNode:: emitCode() { myVarList -> emitCode(); myDecl -> emitCode(); }

void StmtListNode :: emitCode() { myStmtList -> emitCode(); myStmt -> emitCode(); }

void PrintNode :: emitCode() { myPrintList -> emitCode(); }

void TypeIntNode :: emitCode() {return;} void TypeBoolNode :: emitCode() {return;}

void BlockNode :: emitCode() { myVarList->emitCode(); myStmtList->emitCode(); }

void ParamValNode :: emitCode() { return; }

void ParamArrayNode :: emitCode() { return; }

void ArgListNode :: emitCode() { myArgList->emitCode(); myExpression->emitCode(); int reg = myExpression->Reg; emit("subu", "$sp", "$sp", IntToStr(4), "# argument"); emit("sw", "$t"+IntToStr(reg), "($sp)"); freeReg(reg); }

// David Haltinner ===========================================================

void VariableDeclNode :: emitCode() // int x; { //zinc always allocates 4 bytes for int and bool //so, do not need to visit myType

if(myIdentifier->getSymbol()->adr == Global){ declareGlobalVar( myIdentifier->getMyStringVal()+".v" ); } }

void ArrayDeclNode :: emitCode() { Symbol * s = myIdentifier->getSymbol();

if(s->adr == Global){ declareGlobalArray( s->symbolName+".v" , s->arraySize * 4 ); } }

void FunctionDeclNode :: emitCode() { currentFunctionName = myIdentifier -> getMyStringVal(); currentFunctionSym = mySymbolTableEntry; emitFunctionPrologue( currentFunctionName, currentFunctionSym->frameSize, currentFunctionSym->localVarCount);

myParameters -> emitCode(); myVarList -> emitCode(); myStmtList -> emitCode();

emitFunctionEpilogue ( currentFunctionName, currentFunctionSym->frameSize, currentFunctionSym->parameterCount );

if (currentFunctionName!="main") emit( "jr", "$ra" ); // return else{ emitEmptyLine(); emit( "li", "$v0", 10 ); // halt emit( "syscall", "\t\t# program exit" ); } }

// David Haltinner ===========================================================

void PrintListNode :: emitCode() { myPrintList -> emitCode(); //emitComment( "print" );

myPrintItem -> emitCode(); // string literal or expression

switch( myPrintItem->nodeType ) {

case StringType: emitPrintString(); break; case IntType: emitPrintInt( myPrintItem->Reg ); freeReg(myPrintItem->Reg); break; case BoolType: if(NUMERIC){ emitPrintBool( myPrintItem->Reg ); freeReg(myPrintItem->Reg); } else{ string endLabel = NextLabel(); emit( "la", "$a0", ".false" ); emit( "beqz", myPrintItem->Reg, endLabel); emit( "la", "$a0", ".true" ); emitLabel(endLabel); emitPrintString(); freeReg(myPrintItem->Reg); } break; default: assert(0); break; } }

void AssignNode :: emitCode() { emitComment( "assignment" );

myExpression -> emitCode(); // translate RHS (expression) myTarget -> emitCode(); // translate LHS (targetNode)

storeIntoTarget( myExpression, myTarget );

freeReg( myExpression->Reg ); freeReg( myTarget ->Reg ); }

void IfNode :: emitCode() { emitComment("if"); string trueLabel ( NextLabel() ); string falseLabel( NextLabel() ); string endifLabel( NextLabel() );

if(NUMERIC){ myExpression -> emitCode(); emit( "beqz", myExpression->Reg, falseLabel ); freeReg(myExpression->Reg); } else{ evaluateCondition(myExpression, trueLabel, falseLabel); }

emitLabel(trueLabel); emitComment("then"); myThenStmt -> emitCode(); // then clause emit( "j", endifLabel );

emitLabel(falseLabel); emitComment("else"); myElseStmt -> emitCode(); // else clause

emitLabel(endifLabel); }

void WhileNode :: emitCode() { if(NUMERIC){ string compareLabel( NextLabel()); string trueLabel( NextLabel());

emitComment("while"); emit("j", compareLabel); emitLabel(trueLabel); myStmt -> emitCode(); emitLabel(compareLabel); myExpression->emitCode(); emit("bnez", myExpression->Reg, trueLabel); freeReg(myExpression->Reg); } else{ string compareLabel( NextLabel()); string trueLabel( NextLabel()); string falseLabel( NextLabel() );

emitComment("while"); emit("j", compareLabel); emitLabel(trueLabel); myStmt -> emitCode(); emitLabel(compareLabel); evaluateCondition(myExpression, trueLabel, falseLabel); emitLabel(falseLabel); } }

void ProcCallNode :: emitCode() { Symbol * s = myIdentifier->getSymbol(); emitComment("call"); saveRegs(); //throw args on stack myArgList->emitCode(); emit("jal", s->symbolName+".f"); restoreRegs(); }

void ReturnNode :: emitCode() { emitEmptyLine(); emitComment("return");

if( !myReturnVal->isNull()) { myReturnVal -> emitCode(); emit( "move", "$v0", "$t"+IntToStr(myReturnVal->Reg) ); freeReg( myReturnVal->Reg ); }

if(currentFunctionName=="main") emit( "j", currentFunctionName+".." ); else emit( "j", currentFunctionName+".f.." ); }

// David Haltinner ===========================================================

void OrNode :: emitCode() { if(NUMERIC){ string falseLabel( NextLabel() ); string endLabel( NextLabel() );

myLeft->emitCode(); string regL = "$t"+IntToStr(myLeft->Reg); emit("beqz", regL, falseLabel ); emit("j", endLabel); emitLabel(falseLabel);

freeReg(myLeft->Reg); myRight->emitCode(); string regR = "$t"+IntToStr(myRight->Reg); emitLabel(endLabel); Reg = myRight->Reg; } else{ // THIS IS CONTROL FLOW CODE --------------------- string falseLabel = NextLabel(); string trueLabel = NextLabel(); string endLabel = NextLabel(); evaluateCondition(this, trueLabel, falseLabel); emitLabel(trueLabel); Reg = getReg(); emit( "li", Reg, 1 ); emit( "j", endLabel); emitLabel(falseLabel); emit( "li", Reg, 0 ); emitLabel(endLabel); } }

void AndNode :: emitCode() { if(NUMERIC){ string endLabel( NextLabel() ); myLeft->emitCode(); string regL = "$t"+IntToStr(myLeft->Reg); emit("beqz", regL, endLabel); freeReg(myLeft->Reg); myRight->emitCode(); Reg = myRight->Reg; emitLabel(endLabel); } else{ // THIS IS CONTROL FLOW CODE --------------------- string falseLabel = NextLabel(); string trueLabel = NextLabel(); string endLabel = NextLabel(); evaluateCondition(this, trueLabel, falseLabel); emitLabel(trueLabel); Reg = getReg(); emit( "li", Reg, 1 ); emit( "j", endLabel); emitLabel(falseLabel); emit( "li", Reg, 0 ); emitLabel(endLabel); } }

void RelOpNode :: emitCode() { if(NUMERIC){ // THIS IS NUMERIC CODE ----------- string op = setRelOp(myRelOp); int regL, regR; myLeft->emitCode(); myRight->emitCode(); regL = myLeft-> Reg; regR = myRight-> Reg; emit(op, "$t"+IntToStr(regL), "$t"+IntToStr(regL), "$t"+IntToStr(regR)); Reg = regL; freeReg(regR); // ------------------------------- } else{ // THIS IS CONTROL FLOW CODE--------------------- string trueLabel = NextLabel(); string falseLabel = NextLabel(); string endLabel = NextLabel(); evaluateCondition(this, trueLabel, falseLabel); // Might need to load a 1 or a 0 into Reg for this to work emitLabel(trueLabel); Reg = getReg(); emit( "li", Reg, 1 ); emit( "j", endLabel); emitLabel(falseLabel); emit( "li", Reg, 0 ); emitLabel(endLabel); } }

void ArithOpNode :: emitCode() { // ***************** ArithOpNode is finished ****************** if(SethiUllmanFlag){ doSethiUllmanLabeling(); doSethiUllmanCodeGen(); } else{ string op = binaryOp(myArithOp); int regL, regR; myLeft->emitCode(); myRight->emitCode(); regL = myLeft->Reg; regR = myRight->Reg; emit(op, "$t"+IntToStr(regL), "$t"+IntToStr(regL), "$t"+IntToStr(regR)); Reg = regL; freeReg(regR); } }

// David Haltinner ===========================================================

void FnCallNode :: emitCode() { emitComment("call"); saveRegs(); //save args if any myArgList->emitCode(); emit("jal", myIdentifier->getMyStringVal()+".f"); Reg=getReg(); emitComment("function value"); emit("move", Reg, "$v0"); }

void NameVarNode :: emitCode() { Reg = getReg(); if(myIdentifier->getSymbol()->adr == Global && myIdentifier->getSymbol()->symbolKind == VarKind){ string name = myIdentifier->getMyStringVal(); emit( "lw", Reg, name+".v" ); // SUFFIX(variable) } else if(myIdentifier->getSymbol()->symbolKind == ArrayKind && myIdentifier->getSymbol()->adr == Global){ string name = myIdentifier->getMyStringVal(); emit("la", Reg, name+".v" ); } else if(myIdentifier->getSymbol()->symbolKind == ArrayKind || myIdentifier->getSymbol()->symbolKind == ArrayParamKind ){ Symbol * s = myIdentifier->getSymbol(); int o = s->offset; string off = IntToStr(o); if(o > 0) off= "-"+off; emit( "addi", "$t"+IntToStr(Reg), "$fp", off); } else if(myIdentifier->getSymbol()->symbolKind == VarKind || myIdentifier->getSymbol()->symbolKind == ValParamKind){ Symbol * s = myIdentifier->getSymbol(); int o = s->offset; string off = IntToStr(o); if(o > 0) off= "-"+off; string regStr = off+ "($fp)"; emit( "lw", "$t"+IntToStr(Reg), regStr ); } else{ assert(0); } }

void ArrayVarNode :: emitCode() { //need for all 3 myExpression->emitCode(); int RegFromExp=myExpression->Reg; emit("sll", "$t"+IntToStr(RegFromExp), "$t"+IntToStr(RegFromExp), "2");

//global only if(myIdentifier->getSymbol()->adr == Global){ Reg=getReg(); string str(myIdentifier->getMyStringVal()); emit("la","$t"+IntToStr(Reg), str+".v"); emit("add","$t"+IntToStr(RegFromExp), "$t"+IntToStr(RegFromExp) , "$t"+IntToStr(Reg)); emit("lw", "$t"+IntToStr(RegFromExp), "($t"+IntToStr(RegFromExp)+")"); freeReg(Reg); //am i really done with it? Reg = RegFromExp; } else if(myIdentifier->getSymbol()->adr == Local && myIdentifier->getSymbol()->symbolKind == ArrayKind){ //local Symbol * s = myIdentifier->getSymbol(); emit("add", "$t"+IntToStr(RegFromExp), "$fp", "$t"+IntToStr(RegFromExp)); int o = s->offset; string off = IntToStr(o); if(o > 0) off= "-"+off; emit("lw", "$t"+IntToStr(RegFromExp), off+"($t"+IntToStr(RegFromExp)+")"); //freeReg(Reg); Reg = RegFromExp; } else{ //Param Reg=getReg(); Symbol * s = myIdentifier->getSymbol(); int o = s->offset; string off = IntToStr(o); if(o > 0) off= "-"+off; string regStr = off+ "($fp)"; emit("lw", "$t"+IntToStr(Reg), regStr); emit("add", "$t"+IntToStr(RegFromExp), "$t"+IntToStr(Reg), "$t"+IntToStr(RegFromExp)); emit("lw", "$t"+IntToStr(RegFromExp), "0($t"+IntToStr(RegFromExp)+")"); freeReg(Reg); //ami really done with it though? Reg = RegFromExp; } }

void IntLiteralNode :: emitCode() { Reg = getReg(); emit( "li", Reg, myIntVal ); }

void TrueNode :: emitCode() { Reg = getReg(); emit( "li", Reg, 1 ); }

void FalseNode :: emitCode() { Reg = getReg(); emit( "li", Reg, 0 ); }

// David Haltinner ===========================================================

void TargetNode :: emitCode() { // Explicitly tell the target it is the fp // since all local vars are offset from fp // and globals don't use registers Reg = 30; Symbol *ptrL = getID()->getSymbol();

if(ptrL->adr == Global && ptrL->symbolKind == VarKind){ return; } else if( ptrL->adr == Global && ptrL->symbolKind == ArrayKind){ getExp()->emitCode(); int regEx = getExp()->Reg; int global = getReg(); string regStr = "$t"+IntToStr(regEx); emit("sll", regStr, regStr, IntToStr(2)); emit("la", "$t"+IntToStr(global), ptrL->symbolName+".v"); emit("add", regStr, regStr, "$t"+IntToStr(global)); freeReg(global); Reg = regEx; } else if( ptrL->adr == Local && ( ptrL->symbolKind == VarKind || ptrL->symbolKind == ValParamKind )){ return; } else if( ptrL->adr == Local && ptrL->symbolKind == ArrayKind){ getExp()->emitCode(); int regEx = getExp()->Reg; string regStr = "$t"+IntToStr(regEx); emit("sll", regStr, regStr, IntToStr(2)); emit("add", regStr, "$fp", regStr); Reg = regEx; } else if( ptrL->adr == Local && ptrL->symbolKind == ArrayParamKind){ getExp()->emitCode(); int reg = getReg(); int regEx = getExp()->Reg; int o = ptrL->offset; string regS = "$t"+IntToStr(reg); string regStr = "$t"+IntToStr(regEx); string off = IntToStr(o)+"($fp)"; if(o != 0) off = "-" + off; emit("sll", regStr, regStr, IntToStr(2)); emit("lw", regS, off); emit("add", regStr, regS, regStr); Reg = regEx; freeReg(reg); } }

void StringLiteralNode :: emitCode() { string label;

if ( *myStringVal == "\"\\n\"" ) label = ".nl"; else{ if(l.find((*myStringVal)) == l.end()){ label = NextLabel(); emitStringDefinition( label, *myStringVal ); l[(*myStringVal)] = label; } else{ label = l[*myStringVal]; } }

// load into $a0 so it can be printed; can do it here // because a string literal is only used in print statements emit( "la", "$a0", label ); }

// David Haltinner =========================================================== // // H I G H E R - L E V E L E M I T R O U T I N E S // // David Haltinner ===========================================================

void emitPrintString() { emit( "li", "$v0", 4 ); emit( "syscall", "\t\t# print_string" ); }

void emitPrintInt( int reg ) { emit( "move", "$a0", "$t"+IntToStr(reg) ); emit( "li" , "$v0", 1 ); emit( "syscall", "\t\t# print_int" ); }

void emitPrintBool( int reg ) { string falseLabel = NextLabel(); string endLabel = NextLabel(); emit( "beqz", "$t"+IntToStr(reg), falseLabel); emit( "la", "$a0", ".true" ); emit( "j", endLabel); emitLabel(falseLabel); emit( "la", "$a0", ".false" ); emitLabel(endLabel); emit( "li", "$v0", 4); emit( "syscall", "\t\t# print_bool" ); }

// David Haltinner ===========================================================

void emitL (string label, string opcode,string arg1,string arg2,string arg3) { asmFile << label << ":\t" ; if ( opcode=="" ) {asmFile<<endl; return;} else asmFile << opcode; if ( arg1 =="" ) {asmFile<<endl; return;} else asmFile << arg1; if ( arg2 =="" ) {asmFile<<endl; return;} else asmFile << arg2; if ( arg3 =="" ) {asmFile<<endl; return;} else asmFile << arg3; asmFile<<endl; asmFile.flush(); }

// David Haltinner ===========================================================

void emitProgramHeader() { emit ( ".data" ); emitL( ".true" , ".asciiz\t", "\"true\"" ); emitL( ".false", ".asciiz\t", "\"false\"" ); emitL( ".nl" , ".asciiz\t", "\"\\n\"" ); emit ( ".text" ); emit ( ".globl main" ); emitEmptyLine(); }

void emitProgramFooter() { asmFile.close(); }

// David Haltinner ===========================================================

void emitFunctionPrologue( string fn, int frameSize, int localVarCount ) { emitEmptyLine(); if(fn!="main") emitLabel( fn+".f" ); else emitLabel( fn ); emitBlockComment( "PROLOGUE" );

string space( IntToStr(localVarCount*4+8) ); if (localVarCount == 0) emit( "subu", "$sp", "$sp", "8" , "# registers ra & fp" ); else emit( "subu", "$sp", "$sp", space, "# ra, fp & locals" ); emit( "sw" , "$ra", IntToStr(localVarCount*4+4)+"($sp)" ); emit( "sw" , "$fp", IntToStr(localVarCount*4 )+"($sp)" );

emit( "addu", "$fp", "$sp", IntToStr(frameSize-4), "# set new fp" ); }

void emitFunctionEpilogue( string fn, int frameSize, int parameterCount ) { emitEmptyLine(); if(fn!="main") emitLabel( fn+".f.." ); else emitLabel( fn+".." ); emitBlockComment( "EPILOGUE" );

emitOffset( "lw" , "$ra", parameterCount*4, "$fp", "# restore ra" ); emitOffset( "lw" , "$fp", parameterCount*4+4, "$fp", "# restore fp" );

emit( "addu", "$sp", "$sp", IntToStr(frameSize), "# Pop" ); }

// David Haltinner ===========================================================

void declareGlobalVar( string name ) { emit ( ".data" ); emit ( ".align 2" ); emitL( name, ".space 4" ); //always 4 for simplicity emit ( ".text" ); emitEmptyLine(); }

void declareGlobalArray( string name, int size ) { emit ( ".data" ); emit ( ".align 2" ); emitL( name, ".space "+IntToStr(size) ); emit ( ".text" ); emitEmptyLine(); }

void emitStringDefinition( string label, string String ) { emitEmptyLine(); emit ( ".data" ); emitL( label, ".asciiz\t ", String ); emit ( ".text" ); emitEmptyLine(); }

// David Haltinner =========================================================== // // S E T H I - U L L M A N // // David Haltinner ===========================================================

void ArithOpNode :: doSethiUllmanLabeling() { myLeft->doSethiUllmanLabeling(); myRight->doSethiUllmanLabeling(); if(myLeft->lbl == myRight->lbl){ lbl = myLeft->lbl+1; } else if(myLeft->lbl > myRight->lbl){ lbl = myLeft->lbl; } else{ lbl = myRight->lbl; } }

void IntLiteralNode :: doSethiUllmanLabeling() { lbl = 1; } void NameVarNode :: doSethiUllmanLabeling() { lbl = 1; } void ArrayVarNode :: doSethiUllmanLabeling() { lbl = 1; } void FnCallNode :: doSethiUllmanLabeling() { lbl = 1; }

void ArithOpNode :: doSethiUllmanCodeGen() { string op = binaryOp(myArithOp); int regL, regR;

if(myLeft->lbl > myRight->lbl){ myLeft->doSethiUllmanCodeGen(); myRight->doSethiUllmanCodeGen(); } if(myRight->lbl >= myLeft->lbl){ myRight->doSethiUllmanCodeGen(); myLeft->doSethiUllmanCodeGen(); }

regL = myLeft->Reg; regR = myRight->Reg; emit(op, "$t"+IntToStr(regL), "$t"+IntToStr(regL), "$t"+IntToStr(regR)); Reg = regL; freeReg(regR); }

void IntLiteralNode :: doSethiUllmanCodeGen() { emitCode(); } void NameVarNode :: doSethiUllmanCodeGen() { emitCode(); } void ArrayVarNode :: doSethiUllmanCodeGen() { emitCode(); } void FnCallNode :: doSethiUllmanCodeGen() { emitCode(); } int j(int x, int y){ //tests function call, arithmatic operations, as well as print statements it should return 7 as the answer int z; z = 3; z = x + y + z; print(z);print("\n"); return z; } int main(){ //tests the main function, calls a function, and prints. Should print 7. int y; int x; x = 2; y = j(2, x); print(y);print("\n"); return 1; } int main(){ //tests printing and arithmatic operations plus, multiply, and divide. Should print "x is 28" followed by a new line int x; x = 2 + 3 * 5 / 4 * 8 + 2; print("x is ", x, "\n"); return x; } /* tokens.lex */

/* * char *yytext contains the lexeme of each token * int yyleng is the length of the lexeme */

/* * section 1: names for regular expressions */

delimiter [ \t] newline [\n] whitespace {delimiter}+ digit [0-9] letter [a-zA-Z] integer {digit}+ other . identifier ({letter}|_)({letter}|{digit}|_)* comment1 "//"[^\n]*[\n] comment2 "//"[^\n]* mgcStrLt \"([^\"\n]|\\[^\n])*\" strLt \"([^\"\000-\037\177\n\\]|\\[^\000-\037\177\n])*\" rnAwyStrLt \"([^\"\000-\037\177\n]|\\[^\000-\037\177\n])*

%{ /* * stuff here is copied directly into lex.yy.c * as info outside of (above) yylex() */ using namespace std; #include "ast.h" #include "message.h" #include "scanner.h" #include "y.tab.h" // token definitions created by bison #include "int2str.h"

#define MAXINT 2147483647

static int line = 1; /* current line number */ static int column = 1; /* current column number */

/* forward */ void setPosition(); void doIntConvert(); int idScreener(string *lexeme);

%{ /* * section 2: rules for regular expressions */ %}

{whitespace} { column += yyleng; } {newline} { line++; column=1; }

"=" { setPosition(); return ASSIGN; } "," { setPosition(); return COMMA; } ";" { setPosition(); return SEMICOLON; } "(" { setPosition(); return LPAREN; } ")" { setPosition(); return RPAREN; } "{" { setPosition(); return LBRACE; } "}" { setPosition(); return RBRACE; } "[" { setPosition(); return LBRACKET; } "]" { setPosition(); return RBRACKET; } "+" { setPosition(); return PLUS; } "-" { setPosition(); return MINUS; } "*" { setPosition(); return TIMES; } "/" { setPosition(); return SLASH; } ">" { setPosition(); return GT; } "<" { setPosition(); return LT; } "==" { setPosition(); return EQ; } "!=" { setPosition(); return NEQ; } ">=" { setPosition(); return GEQ; } "<=" { setPosition(); return LEQ; } "&&" { setPosition(); return AND; } "||" { setPosition(); return OR; } "<<" { setPosition(); return AARROW; }

{integer} { doIntConvert(); setPosition(); return INTLITERAL; }

{identifier} { setPosition(); string *lexeme = new string(yytext); yylval.t.stringVal = lexeme; return idScreener(lexeme); }

{strLt} { setPosition(); yylval.t.stringVal = new string(yytext); return STRINGLITERAL; }

{rnAwyStrLt} { string c(yytext); string msg = "unterminated string "; msg = msg + c; Warn(line,column, msg); column += yyleng; }

{mgcStrLt} { string c(yytext); string msg = "magic string "; msg = msg + c; Warn(line,column, msg); column += yyleng; }

{comment1} { line++; column = 1; } {comment2} { line++; column = 1; }

{other} { int bad = yytext[0]; string c(IntToStr(bad)); string msg = "yylex(): ignoring illegal character "; msg = msg + " (ascii code " + c + ")"; Warn(line,column, msg); column += yyleng; }

/* * section 3: functions used in section 2 */

void setPosition() { yylval.t.line = line ; yylval.t.column = column; column += yyleng; }

int idScreener(string *lexeme) { if ( *lexeme == "print" ) return PRINT; if ( *lexeme == "cout" ) return COUT; else if ( *lexeme == "int" ) return INT; else if ( *lexeme == "void" ) return VOID; else if ( *lexeme == "if" ) return IF; else if ( *lexeme == "else" ) return ELSE; else if ( *lexeme == "while" ) return WHILE; else if ( *lexeme == "bool" ) return BOOL; else if ( *lexeme == "true" ) return TRUE; else if ( *lexeme == "false" ) return FALSE; else if ( *lexeme == "return" ) return RETURN; else return ID; }

void doIntConvert() { if(atof(yytext) > MAXINT){ yylval.t.intVal = MAXINT; string msg = "int literal exceeds MAXINT;\n\tsubstituting MAXINT"; Warn(line, column, msg); } else{ yylval.t.intVal = atoi(yytext); } } // unparse.cc

#include <assert.h> #include <iomanip> #include <typeinfo> #include "ast.h" #include "scanner.h" #include "y.tab.h"

void indent(int indentVal=0) { for (int i=1; i<=indentVal; i++) cout << " "; // 3 spaces }

//============================================================

void ProgramNode :: unparse( int indentVal ) { indent(indentVal+1); cout<<"functionName<parameters:locals:frameSize>;"<<endl; indent(indentVal+1); cout<<"variableName<offset>\n"; myGlobalList -> unparse(); myFunctionList -> unparse(); }

void GlobalListNode :: unparse( int indentVal ) { myGlobalList -> unparse(); myDecl -> unparse(); }

void TypeIntNode :: unparse( int indentVal ) { cout << "int "; }

void TypeBoolNode :: unparse( int indentVal ) { cout << "bool "; }

void VariableDeclNode :: unparse( int indentVal ) { doLineNum(); indent(indentVal); myType -> unparse(indentVal); myIdentifier -> unparse(indentVal); if(myIdentifier->getSymbol()->adr == Local){ cout<<" <" << myIdentifier->getSymbol()->offset << "> "; } cout << ";" << endl; }

void FunctionDeclNode :: unparse( int indentVal ) { doLineNum(); myType -> unparse(indentVal); if(myType->isNull()) { indent(indentVal); cout<<"void "; } myIdentifier -> unparse(indentVal); cout<<" <"<<mySymbolTableEntry->parameterCount<<":" <<mySymbolTableEntry->localVarCount<<":"<<mySymbolTableEntry->frameSize <<"> ("; myParameters -> unparse(indentVal); cout << ")" << endl;

doLineNum(); cout << "{" << endl; myVarList->unparse(indentVal+1); myStmtList -> unparse(indentVal+1); doLineNum(); cout << "}" << endl; }

void ParametersNode:: unparse(int indentVal){ myParamList -> unparse(indentVal); }

void ParamListNode:: unparse(int indentVal){ if(!myParamList->isNull()){ myParamList->unparse(indentVal); cout<< ", "; } cout<<endl; doLineNum(); indent(indentVal+2); myParam->unparse(indentVal); }

void ParamValNode::unparse(int indentVal){ myType->unparse(indentVal); myIdentifier->unparse(indentVal); cout << " <" << myIdentifier->getSymbol()->offset << "> "; }

void ParamArrayNode::unparse(int indentVal){ myType->unparse(indentVal); myIdentifier->unparse(indentVal); cout<< " <" << myIdentifier->getSymbol()->offset << "> " << "[]"; }

void ArgListNode :: unparse(int indentVal){ if (!myArgList->isNull()) { myArgList->unparse(indentVal); cout<<", "; } myExpression->unparse(indentVal); }

void OrNode :: unparse(int indentVal){ if(!myLeft->isNull()){ cout << "("; myLeft->unparse(indentVal); cout <<" || "; myRight->unparse(indentVal); cout << ")"; return; } myRight->unparse(indentVal); }

void StringLiteralNode::unparse(int indentVal){ cout<< *myStringVal; }

void FnCallNode::unparse(int indentVal){ myIdentifier->unparse(indentVal); cout<<"("; myArgList->unparse(indentVal); cout<<")"; }

void TrueNode::unparse(int indentVal){ cout<<"true"; }

void FalseNode::unparse(int indentVal){ cout<<"false"; }

void ArrayVarNode::unparse(int indentVal){ myIdentifier->unparse(indentVal); cout<<"["; myExpression->unparse(indentVal); cout<<"]"; }

void AndNode::unparse(int indentVal){ if(!myLeft->isNull()){ cout << "("; myLeft->unparse(indentVal); cout << " && "; myRight->unparse(indentVal); cout << ")"; return; } myRight->unparse(indentVal); }

void ReturnNode::unparse(int indentVal){ doLineNum(); indent(indentVal); cout<<"return"; if(!myReturnVal->isNull()){ cout << " "; myReturnVal -> unparse(indentVal); } cout << ";" << endl; }

void IfNode::unparse(int indentVal){ doLineNum(); indent(indentVal); cout<<"if ("; myExpression->unparse(indentVal); cout<<")"<<endl; if(!myThenStmt->isBlock()){ indentVal++; } myThenStmt->unparse(indentVal); if(!myElseStmt->isNull()){ doLineNum(); if(!myThenStmt->isBlock()){ indentVal = indentVal - 1; } indent(indentVal); cout<<"else"<<endl; if(!myElseStmt->isBlock()){ indentVal = indentVal + 1; } myElseStmt->unparse(indentVal); } }

void BlockNode::unparse(int indentVal){ doLineNum(); indent(indentVal); cout<<"{"<<endl; if(!myVarList->isNull()){ myVarList->unparse(indentVal+1); } myStmtList->unparse(indentVal+1); doLineNum(); indent(indentVal); cout<<"}"<<endl; }

void WhileNode::unparse(int indentVal){ doLineNum(); indent(indentVal); cout<<"while ("; myExpression->unparse(indentVal); cout<<")"<<endl; if(!myStmt->isBlock()){ indentVal = indentVal + 1; } myStmt->unparse(indentVal); }

void VarListNode::unparse(int indentVal){ if(!myVarList->isNull()){ myVarList->unparse(indentVal); } myDecl->unparse(indentVal); }

void ProcCallNode::unparse(int indentVal){ doLineNum(); indent(indentVal); myIdentifier->unparse(indentVal); cout<<"("; myArgList->unparse(indentVal); cout<<");"<<endl; }

void ArrayDeclNode :: unparse( int indentVal ) { doLineNum(); indent(indentVal); myType -> unparse(indentVal); myIdentifier -> unparse(indentVal); cout << " <" <<myIdentifier->getSymbol()->offset<< "> "; cout << "["; myIntLit -> unparse(indentVal); cout << "];"<< endl; }

void FunctionListNode :: unparse( int indentVal ){ myFunctionList -> unparse(indentVal); myFunctionDecl -> unparse(indentVal); }

void StmtListNode :: unparse( int indentVal ){ myStmtList -> unparse(indentVal); myStmt -> unparse(indentVal); }

void AssignNode :: unparse( int indentVal ){ doLineNum(); indent(indentVal); myTarget -> unparse( indentVal ); cout << " = "; myExpression -> unparse( indentVal ); cout << ";" << endl; }

void PrintNode :: unparse( int indentVal ){ doLineNum(); indent(indentVal); cout<<"print("; myPrintList->unparse( indentVal ); cout<<");"<<endl; }

void PrintListNode :: unparse( int indentVal ){ if(!myPrintList->isNull()){ myPrintList->unparse( indentVal ); cout << ","; } myPrintItem->unparse( indentVal ); if (myPrintItem->nodeType==IntType) cout<<" <IntType>"; else if (myPrintItem->nodeType==BoolType) cout<<" <BoolType>"; else if (myPrintItem->nodeType==StringType) cout<<" <StringType>"; }

void CoutNode :: unparse( int indentVal ){ doLineNum(); indent(indentVal); cout<<"cout"; myCoutList->unparse( indentVal ); cout<<";"<<endl; }

void CoutListNode :: unparse( int indentVal ){ myCoutList->unparse( indentVal ); cout << "<<"; myCoutItem->unparse( indentVal ); }

void ArithOpNode :: unparse( int indentVal ) { cout << "("; myLeft -> unparse(indentVal); switch (myArithOp) { case PLUS : cout << " + "; break; case MINUS : cout << " - "; break; case TIMES : cout << " * "; break; case SLASH : cout << " / "; break; default : assert(0); } myRight -> unparse(indentVal); cout << ")"; }

void RelOpNode :: unparse(int indentVal ){ cout << "("; myLeft -> unparse(indentVal); switch (myRelOp) { case LT : cout << " < "; break; case GT : cout << " > "; break; case EQ : cout << " == "; break; case NEQ : cout << " != "; break; case LEQ : cout << " <= "; break; case GEQ : cout << " >= "; break; default : assert(0); } myRight -> unparse(indentVal); cout << ")"; }

void NameVarNode :: unparse( int indentVal ){ myIdentifier -> unparse(indentVal); }

void IdentifierNode :: unparse( int indentVal ){ cout << myStringVal->c_str(); }

void TargetNode :: unparse(int indentVal ){ myIdentifier -> unparse(indentVal); if(!myExpression->isNull()){ cout <<"["; myExpression -> unparse(indentVal); cout <<"]"; } }

void IntLiteralNode :: unparse( int indentVal ){ cout << myIntVal; }

// symbol.cc

#include "symbol.h" #include <string>

// implementation of Symbol class

// David Haltinner ******************************************************* // Symbol constructor: initialize Symbol to have given name // David Haltinner ******************************************************* Symbol::Symbol(string S) : symbolName(S), symbolType(ErrorType), symbolKind(ErrorKind) {} // main.cc

/* * Description: * This is a compiler for the language zinc * * Usage: * $ p5 <source_file> * $ p5 -u <source_file> * $ p5 -R <source_file> * S p5 -u -R <source_file> * $ p5 -R -u <source_file> * * Input: * p5 takes between 1 and 3 arguments the last argument * must always be the source file to be compiled, which must end * in .z. the flags -u and -R are optional. -u == unparse (or pretty * print info about the source file) and -R == Sethi Ullman Register * Allocation is to be used in code generation. * * Written by: * Shawn Gens and David Haltinner */

using namespace std; #include <iostream> #include <fstream>

#include "ast.h" #include "scanner.h" // yyin is here

ASTnode * astRoot; // root of AST

extern int declErrors; extern int typeErrors; bool SethiUllmanFlag; extern ofstream asmFile;

int main( int argc, char **argv ) { // Check for correct usage (arguments) if ( argc==1 || argc==3 && (strcmp(argv[1],"-u")!=0&&strcmp(argv[1],"-R")!=0) || argc==4 && ((strcmp(argv[1], "-u")!=0&&strcmp(argv[2], "-R")!=0)&& (strcmp(argv[1], "-R")!=0&&strcmp(argv[2], "-u")!=0))|| argc>4 ) { cerr << "\nusage: " << argv[0] << " <source_file>" <<endl; cerr << " " << argv[0] << " -u <source_file>" <<endl; cerr << " " << argv[0] << " -R <source_file>" <<endl; cerr << " " << argv[0] << " -u -R <source_file>" <<endl; cerr << " " << argv[0] << " -R -u <source_file>" <<endl; cerr << " options: -u==unparse, -R==SethiAllman register allocation" <<endl<<endl; return 1; }

bool unparse = false; SethiUllmanFlag = false; int fileName = 1;

// Which flags (if any) are set? if ( (argc==3||argc==4) && strcmp(argv[1],"-u")==0 ) { unparse = true; fileName = 2; } if( (argc==3||argc==4) && strcmp(argv[1], "-R")==0 ) { SethiUllmanFlag = true; fileName = 2; } if( argc==4 && strcmp(argv[2], "-R")==0 ) { SethiUllmanFlag = true; fileName = 3; } if( argc==4 && strcmp(argv[2], "-u")==0 ) { unparse = true; fileName = 3; }

// Now look at the source file string file_name = argv[fileName]; string asmfile = file_name; string ex = "s"; if (file_name.size() <= 2) { cerr << endl << argv[0] << ": " << argv[1] << " does not have a \".z\" extension" << endl << endl; return 1; } if (file_name.substr(file_name.size()-2, 2) != ".z") { cerr << endl << argv[0] << ": " << argv[1] << " does not have a \".z\" extension" << endl << endl; return 1; }

if ( (yyin = fopen(argv[fileName],"r")) == NULL ) { cerr<<endl<<argv[0] << ": could not open " << argv[fileName] <<endl<<endl; return 1; }

asmfile[asmfile.length()-1] = ex[0]; char afile[asmfile.length()]; for(unsigned int i=0; i<=asmfile.length(); i++){ afile[i] = asmfile[i]; }

asmFile.open(afile); if(asmFile.fail()){ cerr << endl << argv[0] << ": could not open " << asmfile <<endl<<endl; return 1; }

// Start compilation extern int yyparse(); cout << "source file: " << argv[fileName] << endl; cout << "...parse" << endl;

if ( yyparse() == 0 ) {

cout << "...name check" << endl; astRoot->checkNames(); if (declErrors>0) { string msg = "error"; if (declErrors>1) msg = msg + "s"; cerr << declErrors << " declaration/use " << msg << " found" << endl; cerr << "Compilation aborted." << endl; return 1; }

cout << "...type check" << endl; astRoot->checkTypes(); if (typeErrors>0) { string msg = "error"; if (typeErrors>1) msg = msg + "s"; cerr << typeErrors << " type " << msg << " found" << endl; cerr << "Compilation aborted." << endl; return 1; }

// The file made it to code generation cout << "...emit code"; if( SethiUllmanFlag ) { // Sethi Ullman Flag has been set...tell the user cout << " using Sethi Ullman register allocation"; } cout << endl; astRoot->emitCode();

if ( unparse ) { // The unparse flag is set...tell the user cout << "...unparse" << endl; astRoot->unparse(); } }

fclose(yyin); return 0; } // test of some complex expressions using &&

int x(bool q, int z[], bool y[], int w){ y[w] = q; //y[1] = true z[2] = 2; // this is true if(q && 3 > 2 && true && true && (q || true) && (true && true)){ print("HERE", "\n"); // prints z[2] = z[2] + 4 - 1 - 3 + w / w; // z[2] = 3 print("z[2] is: ", z[2], "\n"); } return (3 + 8 + z[2]); }

int main(){ bool y[6]; int v[2]; bool q; int hi; v[2] = 0; q = 4 < 1; y[1] = true && true || false || true && q; //y[1] = true v[1] = x(true, v, y, 1); // v[1] = 14 print("v[1] ", v[1], " v[2] ", v[2], " y[1] ", y[1], "\n"); return 0; } .data .true: .asciiz "true" .false: .asciiz "false" .nl: .asciiz "\n" .text .globl main

j.f: ##### ####### PROLOGUE ####### ##### subu $sp, $sp, 12 # ra, fp & locals sw $ra, 8($sp) sw $fp, 4($sp) addu $fp, $sp, 16 # set new fp #assignment li $t0, 3 sw $t0, -16($fp) #assignment lw $t0, 0($fp) lw $t1, -4($fp) add $t0, $t0, $t1 lw $t1, -16($fp) add $t0, $t0, $t1 sw $t0, -16($fp)

#return lw $t0, -16($fp) move $v0, $t0 j j.f..

j.f..: ##### ####### EPILOGUE ####### ##### lw $ra, -8($fp) # restore ra lw $fp, -12($fp) # restore fp addu $sp, $sp, 20 # Pop jr $ra

t.f: ##### ####### PROLOGUE ####### ##### subu $sp, $sp, 8 # registers ra & fp sw $ra, 4($sp) sw $fp, 0($sp) addu $fp, $sp, 16 # set new fp

t.f..: ##### ####### EPILOGUE ####### ##### lw $ra, -12($fp) # restore ra lw $fp, -16($fp) # restore fp addu $sp, $sp, 20 # Pop jr $ra

main: ##### ####### PROLOGUE ####### ##### subu $sp, $sp, 28 # ra, fp & locals sw $ra, 24($sp) sw $fp, 20($sp) addu $fp, $sp, 24 # set new fp #assignment lw $t0, -24($fp) li $t1, 3 li $t2, 3 mulo $t1, $t1, $t2 add $t0, $t0, $t1 sw $t0, -24($fp)

#return li $t0, 1 move $v0, $t0 j main..

main..: ##### ####### EPILOGUE ####### ##### lw $ra, 0($fp) # restore ra lw $fp, -4($fp) # restore fp addu $sp, $sp, 28 # Pop

li $v0, 10 syscall # program exit source file: OO/test.z ...parse ...name check ...type check ...code generation ...unparse functionName<parameters:locals:frameSize>; variableName<offset> 1: int j <2:1:20> ( 1: int x <0> , 1: int y <4> ) 1: { 2: int z <16> ; 3: z = 3; 4: z = ((x + y) + z); 5: return z; 1: } 8: void t <3:0:20> ( 8: int z <0> , 8: int q <4> [], 8: bool e <8> ) 8: { 8: } 10: int main <0:5:28> () 10: { 11: int y <20> [4]; 12: int x <24> ; 14: y[1] = (((x + 3) + x) - (y[3] * 2)); 17: return 1; 10: }

******** p5/OO/typecheck.obj: Not a text file ********

source file: test.z ...parse ...name check ...type check ...unparse functionName<parameters:locals:frameSize>; variableName<offset> 1: int j <2:1:20> ( 1: int x <0> , 1: int y <4> ) 1: { 2: int z <16> ; 3: z = 3; 4: z = ((x + y) + z); 5: return z; 1: } 8: void t <3:0:20> ( 8: int z <0> , 8: int q <4> [], 8: bool e <8> ) 8: { 8: } 10: int main <0:5:28> () 10: { 11: int y <20> [4]; 12: int x <24> ; 14: y[1] = (((x + 3) + x) - (y[3] * 2)); 17: return 1; 10: } ...emit code int j(int x, int y){ int z; z = 3; z = x + y + z; return z; }

void t(int z, int q[], bool e){}

int main(){ int y[4]; int x; //x = 2; x = x + 3 * 3; //y[3] = j(2, x); //t(x, y, true); return 1; }

******** p5/OO/namecheck.obj: Not a text file ********

.data .true: .asciiz "true" .false: .asciiz "false" .nl: .asciiz "\n" .text .globl main

j.f: ##### ####### PROLOGUE ####### ##### subu $sp, $sp, 12 # ra, fp & locals sw $ra, 8($sp) sw $fp, 4($sp) addu $fp, $sp, 16 # set new fp #assignment li $t0, 3 sw $t0, -16($fp) #assignment lw $t0, -4($fp) lw $t1, 0($fp) add $t1, $t1, $t0 lw $t0, -16($fp) add $t1, $t1, $t0 sw $t1, -16($fp)

#return lw $t0, -16($fp) move $v0, $t0 j j.f..

j.f..: ##### ####### EPILOGUE ####### ##### lw $ra, -8($fp) # restore ra lw $fp, -12($fp) # restore fp addu $sp, $sp, 20 # Pop jr $ra

t.f: ##### ####### PROLOGUE ####### ##### subu $sp, $sp, 8 # registers ra & fp sw $ra, 4($sp) sw $fp, 0($sp) addu $fp, $sp, 16 # set new fp

t.f..: ##### ####### EPILOGUE ####### ##### lw $ra, -12($fp) # restore ra lw $fp, -16($fp) # restore fp addu $sp, $sp, 20 # Pop jr $ra

main: ##### ####### PROLOGUE ####### ##### subu $sp, $sp, 28 # ra, fp & locals sw $ra, 24($sp) sw $fp, 20($sp) addu $fp, $sp, 24 # set new fp #assignment li $t0, 3 li $t1, 3 mulo $t1, $t1, $t0 lw $t0, -24($fp) add $t0, $t0, $t1 sw $t0, -24($fp)

#return li $t0, 1 move $v0, $t0 j main..

main..: ##### ####### EPILOGUE ####### ##### lw $ra, 0($fp) # restore ra lw $fp, -4($fp) # restore fp addu $sp, $sp, 28 # Pop

li $v0, 10 syscall # program exit

******** p5/OO/z5: Not a text file ********

// message.h

#ifndef MESSAGE_GUARD #define MESSAGE_GUARD

#include <string> using namespace std;

void Error(int line, int col, string msg); void Warn (int line, int col, string msg); void InternalError(string msg);

// GLOBAL VARIABLE extern bool errorFlag;

#endif #! /bin/csh

# usage # zoc test

echo "p5" $1.z

./p5 $1.z if ( $status != 0 ) exit -1

echo "...peephole optimization" /home/perrie/spim/bin/copt peephole.rules <$1.s >$1.S

echo "...assemble and execute" echo "/home/perrie/spim/bin/spim -file " $1".S"

/home/perrie/spim/bin/spim -file $1.S

echo "" echo "" echo "differences between" $1".s and" $1".S:" diff $1.s $1.S echo "" int x; //test global variables bool y; int w[2]; bool q[2];

int z(int i, bool b, int v[], bool n[]){ //tests functin calls int t; int h[2]; bool p[2]; bool m; h[1] = i; //local arrays h[0] = h[1] + 3 + v[0] / x; //mathematic operations with local arrays t = 1 + (x - i) / v[0] * v[1] - w[0] + w[1]; m = b && i != 6 || b && t <= 4; //boolean math with local variables p[1] = true; p[0] = p[1] && b && y && q[0] && q[1]; print(1,2,3, true, false, "\n"); //a bunch of prints print("t is local and it is...", t, "\n"); print("m is local and it is ...", m, "\n"); print("p[1] is local and it is ...", p[1], "\n"); print("h[0] is local and it is ...", h[0], "\n"); print("i is a param and it is ...", i, "\n"); print("v[1] is a param and it is ...", v[1], "\n"); print("n[0] is a param and it is ...", n[0], "\n"); print("b is a param and it is ...", b, "\n"); print("x is global and it is ...", x, "\n"); print("y is global and it is ...", y, "\n"); print("w[0] is global and it is ...", w[0], "\n"); print("q[1] is global and it is ...", q[1], "\n"); return h[1]; }

int main(){ //math with global and local arrays and variabales, as well as a funtion call int try; int tArray[2]; tArray[0] = 1; tArray[1] = 9; x = 1 + 3 + 2; y = false; w[0] = x * x; w[1] = x / 5; q[0] = true; q[1] = false; try = z(w[1], y, w, q); try = z(tArray[1], y, tArray, q); return w[1]; } // int2str.cc

#include "int2str.h" #include <assert.h>

//David Haltinner ******************************************************* // IntToStr // convert the given (non-negative) int to a String // David Haltinner ******************************************************* string IntToStr(int k) { int digit; string tmp = "";

assert(k >= 0); if (k == 0) return("0"); while (k>0) { digit = k % 10; k = k / 10; switch (digit) { case 0: tmp = "0" + tmp; break; case 1: tmp = "1" + tmp; break; case 2: tmp = "2" + tmp; break; case 3: tmp = "3" + tmp; break; case 4: tmp = "4" + tmp; break; case 5: tmp = "5" + tmp; break; case 6: tmp = "6" + tmp; break; case 7: tmp = "7" + tmp; break; case 8: tmp = "8" + tmp; break; case 9: tmp = "9" + tmp; break; } } return(tmp); }

// symboltable.cc

#include <cassert> #include <list> #include <string> #include <iostream> #include <iomanip> #include "symbol.h" #include "symboltable.h"

// implementation of the SymbolTable class using a hash table

/* Assignment #1: * a) Do not modify functions Hash or Print * b) Implement functions Insert and Lookup */

// David Haltinner ====================================================== // Insert // David Haltinner ====================================================== // add the given symbol to the table // error if there is already a symbol with the same name

void SymbolTable::Insert(SymbolPtr sym) { //error if Lookup(sym->symbolName)!=NULL assert(Lookup(sym->symbolName) == NULL);

// at this point, Lookup(sym->symbolName) == NULL // i.e. we have a guarantee that sym is not already in the symbol table // software needs to call Lookup before calling Insert // i.e. duplicate names will never be in the symbol table

// now, add sym to the symbol table // Hash the item int hashVal = Hash((sym->symbolName));

// Put it in the back of the bucket bucket[hashVal].push_back(sym); }

// David Haltinner ====================================================== // Lookup // David Haltinner ====================================================== // if there is a symbol with the given name in the table, return a // pointer to that symbol; // otherwise, return NULL

SymbolPtr SymbolTable::Lookup(string name) { int hashVal = Hash(name); // Which list to look in list<SymbolPtr> L; // Pointer to the list list<SymbolPtr>::iterator i; // Iterator for the list SymbolPtr sym; // Pointer for examining items in list bool found = false; // Tells if item is found or not L = bucket[hashVal]; i = L.begin();

while( i != L.end()){ sym = *i; if(sym->symbolName == name){ found = true; // The item is found return sym; // Now stop looking } i++; }

return NULL; }

// David Haltinner ====================================================== // Hash // David Haltinner ====================================================== // hash function

int SymbolTable::Hash(string & S) { int val = 0; for (int j=0; j<int(S.length()); j++) val = (val << 3) + S[j]; if (val < 0) val = -val; return(val % TABLESIZE); }

// David Haltinner ====================================================== // Print // David Haltinner ====================================================== // print the names of all the symbols, one per line

void SymbolTable::Print(ostream & out) { SymbolPtr sym; list<SymbolPtr> L; list<SymbolPtr>::iterator i;

for (int k=0; k<TABLESIZE; k++) { L = bucket[k]; i = L.begin(); while ( i != L.end() ) { sym = *i; out << sym->symbolName.c_str() << endl; i++; } } } // int2str.h

#ifndef _INT2STR_H #define _INT2STR_H

using namespace std; #include <string>

string IntToStr( int k );

#endif #! /bin/csh

# usage # zcc test

echo "" echo "p5" $1.z

./p5 $1.z if ( $status != 0 ) exit -1

echo "...assemble and execute" echo "spim -file " $1".s"

/home/perrie/spim/bin/spim -file $1.s echo "" // emit.cc

using namespace std; #include "ast.h" #include "emit.h" #include "int2str.h" #include "message.h"

#include <iostream> #include <iomanip> #include <fstream> #include <string> #include <assert.h>

ofstream asmFile;

//David Haltinner ============================================================ // // Reg Routines // //David Haltinner ============================================================

// oops. should have 10 $t registers static int regInUse[8] = { 0,0,0,0,0,0,0,0 }; // 0 == free; 1 == in use static int nRegInUse = 0;

static int argRegInUse[4] = { 0,0,0,0 }; // 0 == free; 1 == in use static int nArgRegInUse = 0;

int getReg() { int i;

for (i=0; i<8 && regInUse[i]==1; i++) {}; if ( i==8 ) InternalError("emit: out of registers in getReg");

regInUse[i] = 1; nRegInUse++; return i; }

void freeReg( int r ) { if (r==30) { return; } assert( r>=0 && r<=7 ); regInUse[r] = 0; nRegInUse--; }

static void emitOffsetSP ( string opcode, int rD, int offset ) { asmFile << "\t" << opcode << "\t" ; asmFile << "$t"+IntToStr(rD) << ", " << IntToStr(offset) << "($sp)" <<endl; asmFile.flush(); }

void saveRegs() { if(nRegInUse>0) emit( "subu", "$sp, $sp", IntToStr(nRegInUse*4) ); for (int i=0; i<8; i++) if(regInUse[i]==1) emitOffsetSP("sw", i, i*4 ); }

void restoreRegs() { for (int i=0; i<8; i++) if(regInUse[i]==1) emitOffsetSP("lw", i, i*4 ); if(nRegInUse>0) emit( "addu", "$sp, $sp", IntToStr(nRegInUse*4) ); }

int getArgReg() { int i;

for (i=0; i<4 && argRegInUse[i]==1; i++) {}; if ( i==4 ) InternalError("emit: out of registers in getArgReg");

argRegInUse[i] = 1; nArgRegInUse++; return i; }

void freeArgReg( int r ) { assert( r>=0 && r<=3 ); argRegInUse[r] = 0; nArgRegInUse--; }

// David Haltinner =========================================================== // // Emit Routines // // David Haltinner ===========================================================

void emit( string opcode, string arg1, string arg2, string arg3, string comment ) { asmFile << "\t" << opcode;

if ( arg1 != "" ) { asmFile << "\t" << arg1; if ( arg2 != "" ) { asmFile << ", " << arg2; if ( arg3 != "" ) { asmFile << ", " << arg3; if ( comment != "" ) asmFile << "\t" << comment; } } }

asmFile<<endl; asmFile.flush(); }

// David Haltinner ===========================================================

void emit( string opcode, int rD, string arg ) { asmFile << "\t" << opcode << "\t";

asmFile << "$t" << IntToStr(rD) << ", " << arg << endl; asmFile.flush(); }

void emit( string opcode, string rD, int arg ) { asmFile << "\t" << opcode << "\t";

asmFile << rD << ", " << arg << endl; asmFile.flush(); }

void emit( string opcode, int rD, int arg ) { asmFile << "\t" << opcode << "\t";

asmFile << "$t" << IntToStr(rD) << ", " << arg << endl; asmFile.flush(); }

// David Haltinner ===========================================================

void emitOffset ( string opcode, string arg1, int offset, string arg2, string comment ) { asmFile << "\t" << opcode << "\t" ;

string stringOffset = (offset==0) ? IntToStr(offset) : "-"+IntToStr(offset); asmFile << arg1 << ", " << stringOffset << "(" << arg2 << ")";

if (comment!="") asmFile << "\t" << comment;

asmFile<<endl; asmFile.flush(); }

void emitOffset ( string opcode, int rD, int offset, string arg2, string comment ) { asmFile << "\t" << opcode << "\t" ;

string stringOffset = (offset==0) ? IntToStr(offset) : "-"+IntToStr(offset); asmFile << "$t"+IntToStr(rD) << ", " << stringOffset << "(" << arg2 << ")";

if (comment!="") asmFile << "\t" << comment;

asmFile<<endl; asmFile.flush(); }

// David Haltinner ===========================================================

void emitComment( string comment ) { asmFile << "#" << comment << endl; asmFile.flush(); }

void emitBlockComment( string comment ) { asmFile << "\t#####" << endl; asmFile << "\t####### " << comment << " #######" << endl; asmFile << "\t#####" << endl; asmFile.flush(); }

void emitEmptyLine() { asmFile << endl; asmFile.flush(); }

// David Haltinner ===========================================================

void emitLabel( string label ) { asmFile << label << ":" << endl; }

// =================================== // Return a different label each time: // .L0, .L1, .L2, etc. // =================================== string NextLabel() { static int currLabel = 0;

string tmp = ".L" + IntToStr(currLabel++); return(tmp); } // typecheck.cc #include "ast.h" #include "message.h" #include "symbol.h" #include "symboltable.h" #include "symlist.h" #include "scanner.h" #include "y.tab.h"

/* * do type checking, i.e. find type errors * */

int typeErrors = 0;

void ProgramNode :: checkTypes() { myFunctionList -> checkTypes(); }

void GlobalListNode :: checkTypes() { return; }

void FunctionListNode :: checkTypes() { myFunctionList -> checkTypes(); myFunctionDecl -> checkTypes(); }

void FunctionDeclNode :: checkTypes() { myStmtList -> checkTypes(); }

void VariableDeclNode :: checkTypes() { return; }

void ArrayDeclNode :: checkTypes() { return; }

void TypeIntNode :: checkTypes() { return; }

void TypeBoolNode :: checkTypes() { return; }

void ParametersNode :: checkTypes() { return; }

void ParamListNode :: checkTypes() { return; }

void ArgListNode :: checkTypes() { myArgList -> checkTypes(); myExpression -> checkTypes(); }

void ParamValNode :: checkTypes() { return; }

void ParamArrayNode :: checkTypes() { return; }

void VarListNode :: checkTypes() { myVarList -> checkTypes(); myDecl -> checkTypes(); }

void StmtListNode :: checkTypes() { myStmtList -> checkTypes(); myStmt -> checkTypes(); }

void AssignNode :: checkTypes() { bool errors = false; myTarget -> checkTypes(); myExpression -> checkTypes(); Symbol * s = myTarget->getID()->getSymbol(); if((s->symbolKind == ArrayKind || s->symbolKind == ArrayParamKind) && myTarget->getExp()->isNull()){ typeErrors++; string msg = "assignment: LHS name is an array name"; Error(line, column, msg); errors = true; } if(s->symbolKind == FnKind){ typeErrors++; string msg = "assignment: LHS name is a function name"; Error(line, column, msg); errors = true; } if(myExpression->isName()){ s = myExpression->getID()->getSymbol(); if(s->symbolKind == FnKind){ typeErrors++; string msg = "assignment: RHS name is a function name"; Error(line, column, msg); errors = true; } else if(s->symbolKind == ArrayKind || s->symbolKind == ArrayParamKind){ typeErrors++; string msg = "assignment: RHS name is an array name"; Error(line, column, msg); errors = true; } } if(myExpression-> nodeType != myTarget->nodeType && !errors){ typeErrors++; string msg = "assignment: LHS type != RHS type"; Error(line, column, msg); } }

void IfNode :: checkTypes() { myExpression -> checkTypes(); myThenStmt -> checkTypes(); myElseStmt -> checkTypes(); }

void WhileNode :: checkTypes() { myExpression -> checkTypes(); myStmt -> checkTypes(); }

void BlockNode :: checkTypes() { myStmtList -> checkTypes(); return; }

void ReturnNode :: checkTypes() { myReturnVal -> checkTypes(); nodeType = myReturnVal -> nodeType; }

void ProcCallNode :: checkTypes() { myArgList->checkTypes(); }

void PrintNode :: checkTypes() { myPrintList -> checkTypes(); }

void PrintListNode :: checkTypes() { myPrintList -> checkTypes(); myPrintItem -> checkTypes(); if(myPrintItem->nodeType == VoidType){ typeErrors++; myPrintItem->nodeType = ErrorType; string msg = "print expression is void type"; Error(line, column, msg); } }

void OrNode :: checkTypes() { myLeft->checkTypes(); myRight->checkTypes(); nodeType = myRight -> nodeType; if(!myLeft->isNull() && !myRight->isNull()){ if(myLeft->nodeType != BoolType){ typeErrors++; string msg = "left operand of || is not bool"; Error(line, column, msg); } if(myRight->nodeType != BoolType){ typeErrors++; string msg = "right operand of || is not bool"; Error(line, column, msg); } nodeType = BoolType; } }

void AndNode :: checkTypes() { myLeft->checkTypes(); myRight->checkTypes(); nodeType = myRight->nodeType; if(!myLeft->isNull()&&!myRight->isNull()){ if(myLeft->nodeType != BoolType){ typeErrors++; string msg = "left operand of && is not bool"; Error(line, column, msg); }

if(myRight->nodeType != BoolType){ typeErrors++; string msg = "right operand of && is not bool"; Error(line, column, msg); } nodeType = BoolType; } }

void RelOpNode :: checkTypes() { myLeft->checkTypes(); myRight->checkTypes(); nodeType = myRight->nodeType; if(!myLeft->isNull()&&!myRight->isNull()){ if(myLeft->nodeType != IntType){ typeErrors++; string msg = "left operand of"; switch(myRelOp){ case LT: msg = msg + " < "; break; case GT: msg = msg + " > "; break; case LEQ: msg = msg + " <= "; break; case GEQ: msg = msg + " >= "; break; case EQ: msg = msg + " == "; break; case NEQ: msg = msg + " != "; break; } msg = msg + "is not int"; Error(line, column, msg); } if(myRight->nodeType != IntType){ typeErrors++; string msg = "right operand of"; switch(myRelOp){ case LT: msg = msg + " < "; break; case GT: msg = msg + " > "; break; case LEQ: msg = msg + " <= "; break; case GEQ: msg = msg + " >= "; break; case EQ: msg = msg + " == "; break; case NEQ: msg = msg + " != "; break; } msg = msg + "is not int"; Error(line, column, msg); } nodeType = BoolType; } }

void ArithOpNode :: checkTypes() { myLeft->checkTypes(); myRight->checkTypes(); nodeType = myRight->nodeType; if(!myLeft->isNull()&&!myRight->isNull()){ if(myLeft->nodeType != IntType){ typeErrors++; string msg = "left operand of "; switch(myArithOp){ case PLUS: msg = msg + " + "; break; case MINUS: msg = msg + " - "; break; case TIMES: msg = msg + " * "; break; case SLASH: msg = msg + " / "; break; } msg = msg + "is not int"; Error(line, column, msg); } if(myRight->nodeType != IntType){ typeErrors++; string msg = "right operand of "; switch(myArithOp){ case PLUS: msg = msg + " + "; break; case MINUS: msg = msg + " - "; break; case TIMES: msg = msg + " * "; break; case SLASH: msg = msg + " / "; break; } msg = msg + "is not int"; Error(line, column, msg); } nodeType = IntType; } }

void NameVarNode :: checkTypes() { myIdentifier -> checkTypes(); nodeType = myIdentifier->nodeType; }

void ArrayVarNode :: checkTypes() { myIdentifier -> checkTypes(); nodeType = myIdentifier->nodeType;

myExpression -> checkTypes(); }

void FnCallNode :: checkTypes() { myIdentifier->checkTypes(); nodeType = (myIdentifier->getSymbol())->symbolType; myArgList->checkTypes(); }

void TrueNode :: checkTypes() { nodeType = BoolType; } void FalseNode :: checkTypes() { nodeType = BoolType; } void IntLiteralNode :: checkTypes() { nodeType = IntType; } void TargetNode :: checkTypes() { Symbol * s = myIdentifier->getSymbol(); nodeType = s->symbolType; } void IdentifierNode :: checkTypes() { nodeType = mySymbolTableEntry->symbolType; } void StringLiteralNode :: checkTypes() { nodeType = StringType; } // more tests of booleans

bool y;

int main(){ bool x; x = false; //x = true; y = (x && true) || (false && x); // y = false print("X is ", x, "\n"); // false print("Y is ", y, "\n"); // false

// fails if(false || y && true || x){ print("Its true", "\n"); } else{ int i; i = 0; while(i < 3 || x){ print("Its false", "\n"); i = i + 1; } } } // emit.h

#ifndef EMIT_H_ #define EMIT_H_

#include <iostream> #include <iomanip> #include <fstream> #include <string> using namespace std;

int getReg(); void freeReg( int r ); int getArgReg(); void freeArgReg( int r );

void saveRegs(); void restoreRegs();

// David Haltinner ============================================================

void emit( string opcode, string arg1="", string arg2="", string arg3="", string comment="" );

void emit( string opcode, int rD, string arg ); void emit( string opcode, string rD, int arg ); void emit( string opcode, int rD, int arg );

// David Haltinner ============================================================

void emitOffset ( string opcode, string arg1, int offset, string arg2, string comment="" ); void emitOffset ( string opcode, int rD, int offset, string arg2, string comment="" );

// David Haltinner ============================================================

void emitLabel( string label ); void emitComment ( string comment ); void emitBlockComment( string comment ); void emitEmptyLine ();

// David Haltinner ============================================================

string NextLabel();

#endif // test of assignment of functions and while

bool t(bool y){ bool z; // z is true // y is true z = y || y && false; print(z, "\n", y, "\n"); return true; }

int main(){ int x; x = 3; while(x > 0){ bool z; print("Test: ", x, "\n"); z = t(true); // z is true print("t returns: ", z, "\n"); x = x - 1; } return 1; } // ast.cc

#include "symbol.h" #include "ast.h"

ProgramNode :: ProgramNode(GlobalListNode*g, FunctionListNode*f, int l, int c) : ASTnode(l,c), myGlobalList(g), myFunctionList(f) {}

GlobalListNode :: GlobalListNode(GlobalListNode*g, DeclNode*v, int l, int c) : ASTnode(l,c), myGlobalList(g), myDecl(v) {}

FunctionListNode :: FunctionListNode(FunctionListNode*f, FunctionDeclNode*d, int l, int c) : ASTnode(l,c), myFunctionList(f), myFunctionDecl(d) {}

FunctionDeclNode :: FunctionDeclNode(TypeNode*t, IdentifierNode*i, ParametersNode*p, VarListNode*v, StmtListNode*s, int l, int c) : ASTnode(l,c), myType(t), myIdentifier(i), myParameters(p), myVarList(v), myStmtList(s) {}

TypeNode :: TypeNode(int l, int c) : ASTnode(l,c) {}

TypeIntNode :: TypeIntNode (int l, int c) : TypeNode(l,c) {} TypeBoolNode :: TypeBoolNode(int l, int c) : TypeNode(l,c) {}

DeclNode :: DeclNode(int l, int c) : ASTnode(l,c) {}

VariableDeclNode :: VariableDeclNode(TypeNode *t, IdentifierNode *i, int l, int c) : DeclNode(l,c), myType(t), myIdentifier(i) {}

ArrayDeclNode :: ArrayDeclNode(TypeNode*t, IdentifierNode*i, ExpressionNode*n, int l,int c) : DeclNode(l,c), myType(t), myIdentifier(i), myIntLit(n) {}

ParametersNode :: ParametersNode(ParamListNode* p, int l, int c) : ASTnode(l,c), myParamList(p) {}

ParamListNode :: ParamListNode(ParamListNode* p, ParamNode* n, int l, int c) : ASTnode(l,c), myParamList(p), myParam(n) {}

ArgListNode :: ArgListNode(ArgListNode *a, ExpressionNode *e, int l, int c) : ASTnode(l,c), myArgList(a), myExpression(e) {}

ParamNode :: ParamNode(int l, int c) : ASTnode(l,c) {}

ParamValNode :: ParamValNode(TypeNode* t, IdentifierNode* i, int l, int c) : ParamNode(l,c), myType(t), myIdentifier(i) {}

ParamArrayNode :: ParamArrayNode(TypeNode* t, IdentifierNode* i, int l,int c) : ParamNode(l,c), myType(t), myIdentifier(i) {}

VarListNode :: VarListNode(VarListNode *v, DeclNode *d, int l, int c) : ASTnode(l,c), myVarList(v), myDecl(d) {}

StmtListNode :: StmtListNode(StmtListNode *s, StmtNode *n, int l, int c) : ASTnode(l,c), myStmtList(s), myStmt(n) {}

StmtNode :: StmtNode(int l, int c) : ASTnode(l,c) {}

AssignNode :: AssignNode(TargetNode *t, ExpressionNode *e, int l, int c) : StmtNode(l,c), myTarget(t), myExpression(e) {}

IfNode :: IfNode(ExpressionNode *ex, StmtNode *t, StmtNode *e, int l, int c) : StmtNode(l,c), myExpression(ex), myThenStmt(t), myElseStmt(e) {}

WhileNode :: WhileNode(ExpressionNode *e, StmtNode *s, int l, int c) : StmtNode(l,c), myExpression(e), myStmt(s) {}

BlockNode :: BlockNode( VarListNode *v, StmtListNode *s, int l, int c) : StmtNode(l,c), myVarList(v), myStmtList(s) {}

ReturnNode :: ReturnNode(ExpressionNode *e, int l,int c) : StmtNode(l,c), myReturnVal(e) {}

ProcCallNode :: ProcCallNode(IdentifierNode*i, ArgListNode*a, int l, int c) : StmtNode(l,c), myIdentifier(i), myArgList(a) {}

PrintNode :: PrintNode(PrintListNode *p, int l, int c) : StmtNode(l,c), myPrintList(p) {}

CoutNode :: CoutNode(CoutListNode *p, int l, int c) : StmtNode(l,c), myCoutList(p) {}

PrintListNode :: PrintListNode(PrintListNode *p, PrintItemNode *i, int l, int c) : ASTnode(l,c), myPrintList(p), myPrintItem(i) {}

CoutListNode :: CoutListNode(CoutListNode *p, PrintItemNode *i, int l, int c) : ASTnode(l,c), myCoutList(p), myCoutItem(i) {}

PrintItemNode :: PrintItemNode(int l, int c) : ASTnode(l,c) {}

ExpressionNode :: ExpressionNode(int l, int c) : PrintItemNode(l,c) {}

OrNode :: OrNode(ExpressionNode *e1, ExpressionNode *e2, int l,int c) : ExpressionNode(l,c), myLeft(e1), myRight(e2) {}

AndNode :: AndNode(ExpressionNode *e1, ExpressionNode *e2, int l,int c) : ExpressionNode(l,c), myLeft(e1), myRight(e2) {}

RelOpNode :: RelOpNode(int o, ExpressionNode *e1, ExpressionNode *e2, int l,int c) : ExpressionNode(l,c), myRelOp(o), myLeft(e1), myRight(e2) {}

ArithOpNode :: ArithOpNode (int o,ExpressionNode *e1,ExpressionNode *e2, int l,int c) : ExpressionNode(l,c), myArithOp(o), myLeft(e1), myRight(e2) {}

TrueNode :: TrueNode (int l, int c) : ExpressionNode(l,c) {} FalseNode :: FalseNode(int l, int c) : ExpressionNode(l,c) {}

NameVarNode :: NameVarNode( IdentifierNode *n, int l, int c) : ExpressionNode(l,c), myIdentifier(n) {}

ArrayVarNode :: ArrayVarNode( IdentifierNode *n, ExpressionNode *e, int l, int c) : ExpressionNode(l,c), myIdentifier(n), myExpression(e) {}

FnCallNode :: FnCallNode(IdentifierNode *i, ArgListNode *a, int l, int c) : ExpressionNode(l,c), myIdentifier(i), myArgList(a) {}

IntLiteralNode :: IntLiteralNode(int n, int l, int c) : ExpressionNode(l,c) { myIntVal=n; }

TargetNode :: TargetNode(IdentifierNode *i, ExpressionNode *e, int l, int c) : ASTnode(l,c), myIdentifier(i), myExpression(e) {}

IdentifierNode :: IdentifierNode(string *s, int l, int c) : ASTnode(l,c), myStringVal(s) {}

StringLiteralNode :: StringLiteralNode(string *s, int l, int c) : PrintItemNode(l,c), myStringVal(s) {} // test of global arrays and while loops

int x[3]; bool y[3];

void fill(){ int j[3]; bool k[3]; int i; i = 0; while(i < 3){ j[i] = i; x[i] = j[i]; // 0, 1 y[i] = true; k[i] = y[i]; // true print("k[", i, "] is ", k[i], "\n"); print("j[", i, "] is ", j[i], "\n"); i = i + 1; } }

void printItems(){ int i; i = 0; while(i < 3){ print("y[", i, "] is ", y[i], "\n"); print("x[", i, "] is ", x[i], "\n"); i = i + 1; } }

int main(){ fill(); printItems(); return 1; } #!/bin/sh

for i in 1 2 3 4 5 6 7 do echo "****************" zcc "t$i" echo "****************" done for i in 1 2 3 do echo "****************" zcc "test$i" echo "****************" done echo "Printing Big and Bad" echo "" echo "*************" echo "Big" zcc eBig echo "*************" echo "Bad" zcc eBad echo "*************"

******** p5/z5: Not a text file ********

// This is a test to use all 8 registers

int main(){ int x; int y; int z; x = 1; y = 2; z = 3;

// Lets use all of the registers x = x + x * (3 + 4 * (z + 3 * (4 * 1))); // Print the value 64 print("X is ", x, " and it uses a lot of registers"); print("\n"); } // This is a test to run out of registers

int main(){ int x; int y; int z; x = 1; z = 3; // Now lets break the compiler x = x - x / (3 - 4 / (z - 3 / (4 - 4 / 1))); } // symlist.cc

#include "message.h" #include "symlist.h"

SymTableList::SymTableList() { symTableList = new list<PSymbolTable>(); }

SymTableList::~SymTableList() { delete symTableList; }

void SymTableList::push(PSymbolTable v) { symTableList->push_front(v); } PSymbolTable SymTableList::pop() { PSymbolTable p=symTableList->front(); symTableList->pop_front(); return p; } PSymbolTable SymTableList::top() { return symTableList->front(); } SymbolPtr SymTableList::lookUp(string id) { list<PSymbolTable>::iterator i; for (i=symTableList->begin(); i != symTableList->end(); i++) { SymbolPtr p=(*i)->Lookup(id); if (p!=NULL) return p; } return NULL; }

1 note · View note