Don't wanna be here? Send us removal request.
Statistics
We looked inside some of the posts by davidhaltinner and here's what we found interesting.
Average Info
Notes Per Post
1
Likes Per Post
1
Reblog Per Post
0
Reply Per Post
0
Number of Posts By Type
Text
1
Last Seen Tumblr Blogs
Fun Fact
Tumblr has 16.74 million mobile monthly users in the US.
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
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 = VarKind; s->offset = currentOffset; if(isGlobal){ s->adr = Global; } else{ s->adr = Local; }
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