%{
/*
*********************************************
*	
*	
*	Author: Donald Yessick
*	
*	C-- Recursive Descent Parser
*	
*	November 11, 2008
*	
*	Credit Keneth Louden For C-- Specification.
*	Credit Dragon Book (Aho, Sethi, Ullman, et al) On General Principle
*	
*	c++
*	flex
*	g++
*	
*	
*********************************************
*/


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

#define PRINTTOKEN  {if (token==T_WORD) cout<<"T_WORD" << flush; \
	else if (token==T_NUMBER) cout<<"T_NUMBER" << flush; \
	else cout<<(int)token<<(char)token; }
#define PRINTEXPECTED {if (expected==T_WORD) cout<<"T_WORD" << flush; \
	else if (expected==T_NUMBER) cout<<"T_NUMBER" << flush; \
	else cout<<(int)expected<<(char)expected; }
int bug(int token);
/*
*********************************************
*	T_WORD keywords and calls and other vars 
*	
*	T_NUMBER 9999999999 (TEN DIGITS) is max num
*		
*	although whitespace is stripped, most recent occurances		
*	can be found in global strings whitespace and newline 	
*		
*	all other characters use ascii values as tokens.	
*		
*********************************************
*/
#define T_NUMBER 999
#define T_WORD 1001

int pos			=0;
int token		=0;
int scanline		=0;
int linebreak		=0;
int lastpos		=0;
int prevpos		=0;
int lookaheadtoken	=0;

string newline		="";
string whitespace	="";

string *hash[255]={0};
%}

LETTER		[a-zA-Z]
DIGIT		[0-9]
D01		{DIGIT}?
D03		{D01}{D01}{D01}
D09		{D03}{D03}{D03}
IDCHAR		({LETTER}|{DIGIT}|[_])
WHITESPACE	[ \t\f\n\b\a]

ID		({LETTER}|[_]){IDCHAR}*
NUMBER		{DIGIT}{D09}

COMMENT		[/][*]([^*]*|[*]+[^/*])*[*]+[/]

%%

[\f]		;
{ID}		{return T_WORD;}
{NUMBER}	{cout << T_NUMBER << yytext << endl; return T_NUMBER;}

{COMMENT} 	{\
			for(char*cp=yytext;*cp;cp++) {\
				pos++;
				if (*cp=='\n') {\
					linebreak++;\
				}\
			}\
		}
[\n][ \t]*	{\
			pos+=yyleng;\
			whitespace+=yytext;\
			if (!linebreak) \
				newline = yytext; \
			else \
				newline += yytext; \
			cout << yytext;\
			linebreak++;\
		}
{WHITESPACE}	{pos+=yyleng;whitespace+=yytext; }

.		{\
			cout << "\'" << yytext << "\'" << ((int)(yytext[0])) ;\
			return yytext[0];\
		}


%%

//unusual stuff (allows next file via yyin and return 0};
int yywrap(){return 1;}

int bug(int token){
	cout << yytext << "\t";
	if (token == ';') cout << endl;
}
//prototypes;
int main(int argc, char * argv[]);

void nextToken();
void lookAhead();

bool accept(int expected);
bool acceptError(int expected);
bool acceptWarning(int expected);
bool acceptCritical(int expected);

bool in(char*expected);
bool match(char*expected);
bool accept(char*expected);
bool acceptError(char*expected);
bool acceptWarning(char*expected);
bool acceptCritical(char*expected);

bool acceptWarning(int expected){
	if (token != expected){ 
		cout << "\nline: " << scanline;
		cout << " WARNING found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected : " << flush;
		PRINTEXPECTED
		cout <<  "<" << expected << ">" << endl;
		return false;
	}
	nextToken();
	return true;
}
bool acceptWarning(char*expected){
	if (token != T_WORD) {
		cout << "\nline: " << scanline;
		cout << " WARNING found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		cout <<  "\"" << expected << "\"<T_WORD>" << endl;
		return false;
	}
	if (strcmp(yytext, expected)!=0){
		cout << "\nline: " << scanline;
		cout << " WARNING found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		cout <<  "\"" << expected << "\"<T_WORD>" << endl;
		return false;
	}

	nextToken();
	return true;
}
bool acceptError(int expected){
	if (token != expected){ 
		cout << "\nline: " << scanline;
		cout << " ERROR found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		PRINTEXPECTED 
		cout <<  "<" << expected << ">" << endl;
		return false;
	}
	nextToken();
	return true;
}
bool acceptError(char*expected){
	if (token != T_WORD) {
		cout << "\nline: " << scanline;
		cout << " ERROR found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		cout <<  "\"" << expected << "\"<T_WORD>" << endl;
		return false;
	}
	if (strcmp(yytext, expected)!=0){
		cout << "\nline: " << scanline;
		cout << " ERROR found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		cout <<  "\"" << expected << "\"<T_WORD>" << endl;
		return false;
	}

	nextToken();
	return true;
}
bool acceptCritical(int expected){
	if (token != expected){ 
		cout << "\nline: " << scanline;
		cout << " CRITCAL ERROR found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		PRINTEXPECTED 
		cout <<  "<" << expected << ">" << endl;
		exit(token);
		return false;
	}
	nextToken();
	return true;
}
bool acceptCritical(char*expected){
	if (token != T_WORD) {
		cout << "\nline: " << scanline;
		cout << " CRITCAL ERROR found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		cout <<  "\"" << expected << "\"<T_WORD>" << endl;
		exit(token);
		return false;
	}
	if (strcmp(yytext, expected)!=0){
		cout << "\nline: " << scanline;
		cout << " CRITCAL ERROR found: \"" << yytext << "\"<" << token << ">" << flush;
		cout << " expected: " << flush;
		cout <<  "\"" << expected << "\"<T_WORD>" << endl;
		exit(2);
		return false;
	}

	nextToken();
	return true;
}
bool accept(int expected){
	if (token != expected) 
		return false;
	nextToken();
	return true;
}
bool accept(char*expected){
	if (token != T_WORD) 
		return false;
	if (strcmp(yytext, expected)!=0)	
		return false;

	nextToken();
	return true;
}
void nextToken(){
	if (token < 256){//yytext is next token
		cout << "<'"<<((char) token)<<"'>" << flush;
		scanline+=linebreak;
		if (linebreak) {cout << newline;linebreak=0;}
		token = lookaheadtoken;
		lookaheadtoken = 0;
	}
	else {
		cout << "<"<<yytext<<">" << flush;
		token = yylex();
	}
	lookAhead();
}
void lookAhead(){
	if (token && token < 256)
		lookaheadtoken = yylex();
}

bool in(char *testset){
	while (*testset){
		if (token == *testset) 
			return true;
		testset++;
	}
	return false;
}
bool match(char * expected){
	if (token < 256) return false; //another hard bug
	return (strcmp(yytext, expected) == 0);
}







//main and cmm prototypes
//int main(char * argv[], int argc);
int parseCMM();


int  firstVarDeclaration();

bool firstProgram();
bool firstDeclarationList();
bool firstDeclaration();

bool firstVarFunDeclaration();
bool firstTypeSpecifier();
bool firstFunDeclaration();
bool firstParams();
bool firstParamList();
bool firstParam();
bool firstCompoundStmt();
bool firstLocalDeclarations();
bool firstStatementList();
bool firstStatement();
bool firstExpressionStmt();
bool firstSelectionStmt();
bool firstIterationStmt();
bool firstReturnStmt();
bool firstExpression();
bool firstVar();
bool firstSimpleExpression();
bool firstAdditiveExpression();
bool firstTerm();
bool firstFactor();
bool firstCall();
bool firstArgs();
bool firstArgList();
bool firstRelop();
bool firstAddop();
bool firstMulop();

int parseProgram();
int parseDeclarationList();
int parseDeclaration();
int parseVarFunDeclaration();
int parseVarDeclaration();
int parseFunDeclaration();
int parseParams();
int parseParamList();
int parseParam();
int parseCompoundStmt();
int parseLocalDeclarations();
int parseStatementList();
int parseStatement();
int parseExpressionStmt();
int parseSelectionStmt();
int parseIterationStmt();
int parseReturnStmt();
int parseExpression();
int parseVar();
//int parseCall();
int parseArgs();
int parseArgList();
int parseSimpleExpression(int&);
int parseAdditiveExpression(int&);
int parseTerm(int&);
int parseFactor(int&);
int parseVarCall(int&);

//see OPCODES and TYPES below
int parseRelop();
int parseAddop();
int parseMulop();
int parseTypeSpecifier();

#define OPCODE_PLUS 1
#define OPCODE_MINUS 2
#define OPCODE_MULT 3
#define OPCODE_DIV 4
#define OPCODE_EQ 5
#define OPCODE_NE 6
#define OPCODE_LT 7
#define OPCODE_LE 8
#define OPCODE_GT 9
#define OPCODE_GE 10
#define TYPEVOID 11
#define TYPEINT 12
#define TYPEARRAY 13
#define TYPEBOOL 14 
#define TYPEADDRESS 15


//code generation

ofstream gencode("out/gen.smc");

//functions 
int fid=0;
int fidcnt=0;
int paramcnt[100] = {0};
string *fidnames = new string[100];

//environment, runtime stack
string * names[1024]={0};
int * loc[1024]={0};
int * vtype[1024]={0};
int topenv = -1;
int envsize[1024]={0};
int cntnames[1024]={0};

//helpers
void pushEnv();
void pushEnv(int fid);
void popEnv();
void makeVar(string name, int size, int vartype);
bool getVar(string name, int &address,int &vartype, int &local);
void initfids();
int createfid(string funname);
int findFun(string name, int &numparams);
void emit(int n);
void emit(string s);
int makeLabel();
string funLabel(int labelnum);
string label(int labelnum);
void emitReturn();
void emitReturnValue(int);
void emitLabel(int labelnum);
void emitFunLabel(int labelnum);
void emitMakeVar(string name, int size);
void emitBranchZero(int branchlabel);
void emitJump(int branchlabel);

//cleanup
void emitPreamble();
void emitCallSwitch(int numfids);
void emitPrologue();

void  dumpVars();
/*
*********************************************
*	
*	
*	
*	
*********************************************


*/

#define TRACE if (trace)
int trace(0);
int main(int argc,  char * argv[]) {
	trace = (argc > 1);
	initfids();
	token = yylex();
	emitPreamble();
	cout << "CMM Parser" << endl;
	parseDeclarationList();
	if (token) {
		cout << endl << "CMM Syntax Error" << endl;
		cout << endl << "bailing out" << endl;

		cout << pos << linebreak << scanline ; 
		PRINTTOKEN;
		exit(token);
	}
	emitPrologue();
	cout << endl << "build successful" << endl;

	return 0;
}


/*
*********************************************
*	
*	RECURSIVE DESCENT PARSER FOR CMM
*	WITH CODE GENERATION
*	
*********************************************
*/

int parseDeclarationList(){
	//TRACE cout << "\tparseDeclarationList" << flush;
	TRACE emit("\n/*Declarations Section*/");
	TRACE emit("\n/*Function Declarations Section*/");
	if (!firstVarFunDeclaration()) 
	{
		//TRACE cout << "\tparseDeclarationList Error " << yytext << flush;
		exit(token);
	}
	while(firstVarFunDeclaration() ){
		parseVarFunDeclaration();
	}
	emitCallSwitch(fidcnt);
	TRACE emit("\n/*Var Declarations Section*/");
	emit("\nINIT:");
	for (int i = 0; i < envsize[0]; i++)
		emit("\n\tpush(0)");
	emit("\n\tstart");
	return 0;
}


/*
*********************************************
*	
*	
*	
*	
*********************************************
*/
int parseVarFunDeclaration() {
	//TRACE cout << "\tparseVarFunDeclaration" << flush;
	int typespecifier;
	if (!(typespecifier=parseTypeSpecifier()) )
		return 0;

	string name = yytext;		
	if ( !acceptError(T_WORD) ) {
		cout << "Fatal error: expected id, found: " << yytext << endl;
		exit(1);
	}

	//parseFunDeclaration
	if ( accept('(') )
	{
		fid = createfid(name);
		emitFunLabel(fid);
		pushEnv(fid);
		int pcnt = parseParams();
		accept(')');
		TRACE emit("\t/*function: "+name+ " label: "+ funLabel(fid) + " param cnt: ");
		TRACE emit(pcnt);
		TRACE emit(" */");
		parseCompoundStmt();
		TRACE emit("\n\t/* automatic return */");
		if (typespecifier == TYPEVOID) 
			emitReturn();//in case we fall through
		else 
			emitReturnValue(typespecifier);//in case we fall through
		popEnv();
		return 0;
	}

	//type checking
	if (typespecifier != TYPEINT){
		cout << "invalid type found" << endl;
		exit(1);
	}
	//parseVarDeclaraton
	if ( accept('[') ) {
		if ( token == T_NUMBER ) {
			int n = atoi(yytext);
			acceptError(T_NUMBER);
			makeVar(name,n,TYPEARRAY);
		}
		acceptError(']');
		TRACE emit("\n/*array "+name+" */");
	}
	else {
		makeVar(name,1, TYPEINT);
		TRACE emit("\n/*int "+name+" */");
	}
	accept(';');
	return 0;
}
int parseVarDeclaration() {
	//TRACE cout << "\tparseVarDeclaration" << flush; 
	if (parseTypeSpecifier() != TYPEINT )
		return 0;
	string name = yytext;		
	if ( !acceptError(T_WORD) ) {
		cout << "Fatal error: expected id, found: " << yytext << endl;
		exit(1);
	}
	if ( accept('[') )
	{
		if ( token == T_NUMBER ) {
			int n = atoi(yytext);
			acceptError(T_NUMBER);
			makeVar(name,n,TYPEARRAY);
		}
		acceptError(']');
	}
	else {
		makeVar(name,1,TYPEINT);
	}

	accept(';');
	return 1;
}

int parseParams() {
	//TRACE cout << "\tparseParams" << flush;
	if ( accept("void") ){
		paramcnt[fid] = 0;
		return 0;
	}
	//or
	return parseParamList();
}
int parseParamList()
{
	//TRACE cout << "\tparseParamList" << flush;
	parseParam();
	paramcnt[fid] = 1;
	while (accept(',')) {
		parseParam();
		paramcnt[fid]++;
	}
	return paramcnt[fid];
}
int parseParam()
{
	//TRACE cout << "\tparseParam" << flush;
	if ( parseTypeSpecifier() != TYPEINT) {
		cout << "invalid type found " << endl;
		exit(1);
	}

	string name = yytext;
	acceptError(T_WORD);
		
	if (accept('[')){
		acceptError(']');
		makeVar(name,1, TYPEARRAY);
		//TRACE cout << "ARRAY PARAM: ENV="<<topenv<<" name="<<name<<endl;
	}
	else {
		makeVar(name,1, TYPEINT);
		//TRACE cout << "INT PARAM: ENV="<<topenv<<" name="<<name<<endl;
	}
	return 0;
}
int parseCompoundStmt()
{
	//TRACE cout << "\tparseCompoundStmt" << flush;
	acceptError('{') ;
	pushEnv();
	TRACE emit("\n\t/* BEGIN LOCAL DECLARATIONS */");
	while ( parseVarDeclaration()) 
		;//emit("\n\tpush(0)");
	for (int i = envsize[topenv-1]; i < envsize[topenv]; i++)
		emit("\n\tpush(0)");
	TRACE("\n\t/* END LOCAL DECLARATIONS */");
	while ( parseStatement() ) ;
	acceptError('}');
	popEnv();
	return 0;
}
int parseStatement()
{
	//TRACE cout << "\tparseStatement" << flush;
	if (firstCompoundStmt() ) 
		parseCompoundStmt();
	else if ( firstSelectionStmt() )
		parseSelectionStmt();
	else if ( firstIterationStmt() )
		parseIterationStmt();
	else if ( firstReturnStmt() )
		parseReturnStmt();
	else if ( firstExpressionStmt() )
		parseExpressionStmt();
	else return 0;
	return 1;
}
int parseExpressionStmt()
{
	//TRACE cout << "\tparseExpressionStmt" << flush;
	parseExpression();
	accept(';');
	return 0;
}
int parseSelectionStmt()
{
	//TRACE cout << "\tparseSelectionStmt" << flush;
	int endlabel, elselabel;
	endlabel = makeLabel();
	elselabel = makeLabel();

	accept("if");
	acceptError('(');
	parseExpression();
	acceptError(')');
	emitBranchZero(elselabel);
	parseStatement();
	emitJump(endlabel);
	emitLabel(elselabel);
	if (accept("else") )
		parseStatement();
	emitLabel(endlabel);
	return 0;
}
int parseIterationStmt()
{
	//TRACE cout << "\tparseIterationStmt" << flush;
	int toplabel, endlabel;
	toplabel = makeLabel();
	endlabel = makeLabel();

	accept("while");
	acceptError('(');
	emitLabel(toplabel);
	parseExpression();
	emitBranchZero(endlabel);
	acceptError(')');
	parseStatement();
	emitJump(toplabel);
	emitLabel(endlabel);
	return 0;
}
int parseReturnStmt()
{
	//TRACE cout << "\tparseReturnStmt" << flush;
	accept("return");
	if (! firstSimpleExpression() ) 
		emitReturn();
	else
	{
		parseExpression();
		emitReturnValue(TYPEINT);//we only have one type
	}
	acceptError(';');
	return 0;
}

int dummy = 0;
int parseExpression()
{
	//TRACE cout << "\tparseExpression" << flush;
	int typevar = TYPEVOID;
	if (! firstSimpleExpression() ) return 0;
	TRACE emit("\n\t/* Begin Expression ");
	TRACE emit (yytext);
	TRACE emit(" */");
	parseSimpleExpression(typevar);
	TRACE emit("\n\t/* End Expression */");

	return 0;
}
int parseSimpleExpression(int &typevar)
{
	//TRACE cout << "\tparseSimpleExpression" << flush;
	parseAdditiveExpression(typevar);
	
	if (firstRelop()){
		int op = parseRelop();
		typevar = TYPEBOOL;
		parseAdditiveExpression(dummy);
		switch(op){
			case (OPCODE_EQ): emit("\n\teq");break;
			case (OPCODE_NE): emit("\n\tne");break;
			case (OPCODE_LT): emit("\n\tlt");break;
			case (OPCODE_GT): emit("\n\tgt");break;
			case (OPCODE_LE): emit("\n\tngt");break;
			case (OPCODE_GE): emit("\n\tnlt");break;
			default: cout << "invalid operator" << endl; exit(1);
		}
	}
	return 0;
}
int parseAdditiveExpression(int &typevar)
{
	//TRACE cout << "\tparseAdditiveExpression" << flush;
	parseTerm(typevar);
	while ( firstAddop() ) {	
		typevar = TYPEINT;
		int op = parseAddop();
		parseTerm(dummy);
		if (op == OPCODE_PLUS)
			emit("\n\tadd");
		else
			emit("\n\tsub");
	}
	return 0;
}
int parseAddop()
{
	//TRACE cout << "\tparseAddop" << flush;
	if ( accept('+')){
		return OPCODE_PLUS;
	}
	else {
		acceptError('-');
		return OPCODE_MINUS;
	}
	return 0;
}
int parseTerm(int &typevar)
{
	//TRACE cout << "\tparseTerm" << flush;
	parseFactor(typevar);
	while ( firstMulop() ) {
		typevar = TYPEINT;
		int op = parseMulop();
		parseFactor(dummy);
		if (op == OPCODE_MULT)
			emit("\n\tmult");
		else
			emit("\n\tdiv");
	}
	return 0;
}
int parseMulop()
{
	//TRACE cout << "\tparseMulop" << flush;
	if (accept('*')){
		return OPCODE_MULT;
	}
	else { 
		acceptError('/');
		return OPCODE_DIV;
	}
	return 0;
}

int parseFactor(int &typevar)
{
	//TRACE cout << "\tparseFactor" << flush;
	if ( accept('(') ) {
		typevar = TYPEINT;
		parseExpression();
		acceptError(')');
		return 0;
	}

	if ( token == T_NUMBER ){
		typevar = TYPEINT;
		emit(string("\n\tpush(")+yytext+")");
		accept(T_NUMBER);
		return 0;
	}

	parseVarCall(typevar);
	return 0;
}

int parseVarCall(int &typevar)
{
	//TRACE cout << "\tparseVarCall" << flush;
	string name = yytext;
	if (! acceptError(T_WORD) ) {
		typevar = TYPEVOID;
		return 0;
	}
	
	if ( accept('(') ) {//Call--input and output are handled here as well
		typevar = TYPEINT;
		parseArgs();
		acceptError(')');
		int numparams=0;
		int fid = findFun(name,numparams);
		emit("\n\tpush(");
		emit(fid);
		emit(" )");
		emit("\n\tcall");
		emit("( ");
		emit(numparams);
		emit(" )");
	
		return 0;
	}
	int address, type, local;
	if (!getVar(name,address, type, local)){
		cout << name << " not declared in this scope" << endl;
		TRACE dumpVars();
		exit(1);
	}
	TRACE 
	{
		emit("\n\t/* name:");  
		emit(name); 
		emit(" address:");  
		emit(address); 
		emit(" type:");  
		emit(type); 
		emit(" local:");  
		emit(local); 
		emit( " */");
	}
	if ( accept('[') ) {//Array
		parseExpression();
		acceptError(']');
		if (token == '=' && lookaheadtoken != '=') {//ASSIGNMENT
			typevar = TYPEARRAY;
			//assignment
			emit("\n\tpush(");
			emit(address);
			emit(")");
			if (local==1)//param -- contains indirect address
			{
				emit("\n\tload(SP)");
				TRACE emit("\t/* indirect address of array */");
			}
			emit("\n\tadd");
			accept ('=');
			parseExpression();
			if (local<=1)//param -- contains indirect address
				emit("\n\tstore(0)");
			else emit("\n\tstore(SP)");
		}
		else {//FETCH
			emit("\n\tpush(");
			emit(address);
			emit(")");
			if (local==1)//param -- contains indirect address
				emit("\n\tload(SP)");
			emit("\n\tadd");
			if (local > 1)
				emit("\n\tload(SP)");
			else
				emit("\n\tload(0)");
		}
		return 0;
	}
	else
	if (token == '=' && lookaheadtoken != '='){//ASSIGNMENT
		//assignment
		TRACE emit("\n\t/* LHS Assign (Address) */");
		emit("\n\tpush(");
		emit(address);
		emit(")");
		accept ('=');
		TRACE emit("\n\t/* RHS Assign (Value) */");
		parseExpression();
		typevar = TYPEADDRESS;
		emit("\n\tstore(SP)");
	}
	else {//FETCH
		emit("\n\tpush(");
		emit(address);
		emit(")");
		if (type == TYPEARRAY)//passing array parameter
		{
			if (local==1)//env holds indirect address
			{
				TRACE emit("\t/* indirect address of array */");
				emit("\n\tload(SP)");
			}
			TRACE emit("\t/* address address of array */");
		}
		else if (local){
			emit("\n\tload(SP)");
		}
		else {//global
			emit("\n\tload(0)");
		}
	}
	return 0;
}
int parseArgs()
{
	//TRACE cout << "\tparseArgs" << flush;
	if (token == ')') return 0;
	parseArgList();
	return 0;
}
int parseArgList()
{
	//TRACE cout << "\tparseArgList" << flush;
	parseExpression();
	while ( accept(',') )
	{
		parseExpression();
	}
	return 0;
}


//special care
//the return value of these methods is checked for success
int parseTypeSpecifier()
{
	//TRACE cout << "\tparseTypeSpecifier" << flush;
	if ( accept("void") )
		return TYPEVOID;
	if ( accept("int") )
		return TYPEINT;
	return 0;
}
int parseRelop()
{
	//TRACE cout << "\tparseRelop" << flush;
	//lookahead is required to distinguish '=' from "=="
	//as long as I have it I can recognize >= etc
	if ( !firstRelop() ) 
		return 0;
	if (lookaheadtoken == '=' ){
		if ( accept('=') ) {
			accept('=');
			return OPCODE_EQ;
		}
		if ( accept('!') ) {
			accept('=');
			return OPCODE_NE;
		}
		if ( accept('>') ) {
			accept('=');
			return OPCODE_GE;
		}
		if ( accept('<') ) {
			accept('=');
			return OPCODE_LE;
		}
	}
	else {
		if ( accept('>') )
			return OPCODE_GT;
		if ( accept('<') )	//hard to find bug was here!!!
			return OPCODE_LT;
	}
	return 0;
}

/*
	FIRST SETS 
*/

int  firstVarDeclaration()
{
	//TRACE cout << "\tfirstVarDeclaration" << flush;
	if (token != T_WORD)
		return false;
	return (match("int") || match("void"));
}
bool firstVarFunDeclaration()
{
	if (token != T_WORD)
		return false;
	return (match("int") || match("void"));
}


bool firstTypeSpecifier()
{
	if (token != T_WORD)
		return false;
	return (match("int") || match("void"));
}
bool firstParams()
{
	if (firstParamList()) 
		return true;
	if (token != T_WORD)
		return false;
	return match("void");
}
bool firstParamList()
{
	return firstParam();
}
bool firstParam()
{
	return firstTypeSpecifier();
}
bool firstCompoundStmt()
{
	return ( token == '{' );
}
bool firstLocalDeclarations()
{
	if (token != T_WORD)
		return false;
	return (match("int") || match("void"));
	return firstVarDeclaration();
}
bool firstStatementList()
{
	return firstStatement();
}
bool firstStatement()
{
	return ( 
		(token==';')
		|| (token == T_WORD) //implies || match("if") || match("while") || match("return")
		|| (token == T_NUMBER) 
		|| (token == '(')
	); 

}
bool firstExpression()
{
	return  (
		token == T_WORD
		|| (token == T_NUMBER) 
		|| (token == '(') 
		);
}
bool firstVar()
{
	return token == T_WORD;
}
bool firstSimpleExpression()
{
	if (token == T_NUMBER) return true;
	if (token == '(') return true;
	return  (token == T_WORD);
	return firstAdditiveExpression();
}
bool firstRelop()
{
	if (lookaheadtoken == '=')
		return in("<>=!");
	else return in("<>!");
}
bool firstAdditiveExpression()
{
	if (token == T_NUMBER) return true;
	if (token == '(') return true;
	return  (token == T_WORD);
	//return firstTerm();
}
bool firstAddop()
{
	return in("+-");
}
bool firstTerm()
{
	if (token == T_NUMBER) return true;
	if (token == '(') return true;
	return  (token == T_WORD);
	//return firstFactor();
}
bool firstMulop()
{
	return in("*/");
}
bool firstFactor()
{
	if (token == T_NUMBER) return true;
	if (token == '(') return true;
	return  (token == T_WORD);
}
bool firstCall()
{
	return (token == T_WORD);
}
bool firstArgs()
{
	return firstArgList();
}
bool firstArgList()
{
	return firstExpression();
}

bool firstIterationStmt()
{
	return match("while");
}
bool firstSelectionStmt()
{
	return match("if");
}
bool firstReturnStmt()
{
	return match("return");
}
bool firstExpressionStmt()
{
	return ( firstExpression() || (token==';'));
}


/*
	CODE GEN UTILITIES
*/


void pushEnv(){
	topenv++;
	envsize[topenv] = envsize[topenv-1]; //extends a function env
	cntnames[topenv] = 0;
	names[topenv] = new string[100];
	loc[topenv] = new int[100];
	vtype[topenv] = new int[100];
}
void pushEnv(int dummy){ // a new global env 
	topenv++;
	envsize[topenv] = 0;
	cntnames[topenv] = 0;
	names[topenv] = new string[100];
	loc[topenv] = new int[100];
	vtype[topenv] = new int[100];
}
void popEnv(){
	delete[] names[topenv];
	delete[] loc[topenv];
	topenv--;
}



void makeVar(string name, int size, int vartype){
	//TRACE cout << "\nname \t size \t vartype \t topenv \t cntnames[topenv] \t envsize[topenv];" << endl;
	//TRACE cout << name <<"\t"<< size <<"\t"<< vartype <<"\t\t"<< topenv <<"\t\t"<< cntnames[topenv] <<"\t\ti\t"<< envsize[topenv] << endl;
	//name occupies size cells on the stack
	//registerVar(fidname[fid], name, size, envsize[fid]);

	for (int i=0; i < cntnames[topenv];i++){
		if (name == names[topenv][i]){
			cout << name << " has already been declared " << endl;
			exit(1);
		}
	}


	loc[topenv][cntnames[topenv]]=envsize[topenv];
	vtype[topenv][cntnames[topenv]]=vartype;
	names[topenv][cntnames[topenv]]=name;
	cntnames[topenv]++;
	envsize[topenv] += size;
}


void  dumpVars(){
	for (int env = topenv; env >= 0; env--){
		for (int item = 0; item < cntnames[env]; item++){
			TRACE {
				cout << endl;
				cout << "env:"<<env << " item:"<<item;
				cout <<	" loc:"<<loc[env][item];	
				cout <<	" vtype:"<<vtype[env][item];	
			}
		}
	}
}
bool getVar(string name, int &address,int &vartype, int &local){
	for (int env = topenv; env >= 0; env--){
		for (int item = 0; item < cntnames[env]; item++){
			//TRACE cout << "*"<<names[env][item] << name << endl;
			if (names[env][item] == name)
			{
				address = loc[env][item];	
				vartype = vtype[env][item];	
				local = env; //will be zero for global
				//TRACE cout << endl << "&" << names[env][item] << " env: " << env << " offset: " << address << endl;
				return true;
			}
		}
	}
	return false;
}
void initfids(){
	fidcnt = 0;
	fidnames[fidcnt]=string("#globals");	
	pushEnv(0);
}
int createfid(string funname){
	fidcnt++;
	fid = fidcnt;
	fidnames[fidcnt]=funname;	
	return fidcnt;
}

void dumpFun(){
	for (int i = 0; i <= fidcnt; i++)
	{
		//TRACE cout << fidnames[i] << "(" << paramcnt[i] << ")" << endl;
	}
}
int findFun(string name, int &numparams){
	for (int i = 1; i <= fidcnt; i++)
	{
		if (fidnames[i]==name){ 	
			numparams = paramcnt[i];
			return i;
		}
	}
	
	if (name=="input"){
		numparams=0;
		return -2; 	
	}
	if (name=="output") {
		numparams=1;
		return -1; 	
	}
	cout << "unknown function " << name << endl;
	TRACE dumpFun();
	exit(1);
	return 0;
}



void emit(int n){
	gencode << n <<flush;
}
void emit(string s){
	gencode << s <<flush;
}
int makeLabel(){
	static int labelnum = 0;
	labelnum++;
	return labelnum;
}
string funLabel(int labelnum){
	char num[] = "0000";
	string label("F");
	int x = 3;
	while (labelnum) {
		num[x] += (labelnum%10);
		labelnum = labelnum/10;
		x--;
	}
	label = label + num;
	return label;
}
string label(int labelnum){
	char num[] = "0000";
	string label("L");
	int x = 3;
	while (labelnum) {
		num[x] += (labelnum%10);
		labelnum = labelnum/10;
		x--;
	}
	label = label + num;
	return label;
}
void emitReturn(){
	emit("\n\tend");
}
void emitReturnValue(int type){//we only have one type, int
	emit("\n\tret");
}
void emitLabel(int labelnum){
	gencode << endl << label(labelnum) << ":" << endl;
}
void emitFunLabel(int labelnum){
	gencode << endl << funLabel(labelnum) << ":" << endl;
}
void emitMakeVar(string name, int size){
	TRACE {emit ("\n/*"); 
	emit (name); 
	emit ("*/");}
	if (size<=0){
		cout << "invalid size specified" << endl;
		exit(1);
	}
	emit("\n\tpush(0)");
	size--;
	while (size){
		emit("\n\tpush(0)");
		size--;
	}
	emit("\n");
	TRACE {
		emit ("\n\t/*"); 
		emit (name); 
		emit ("*/");
	}
}
void emitBranchZero(int branchlabel){
	emit("\n\tbrz( ");
	emit(label(branchlabel)); 
	emit(" )");
}
void emitJump(int branchlabel){
	emit("\n\tjump( "); 
	emit(label(branchlabel)); 
	emit(" )");
}

void emitPreamble(){
	TRACE emit("\n/* BEGIN GENERATED CODE */");
	emit("#include \"cmm450.csci\"");
}
void emitPrologue(){
	TRACE emit("\n/* END OF GENERATED CODE */");
	emit("\n");
}
void emitCallSwitch(int numfids){
	emit("\nCALLSWITCH:");
	emit("\n\tjumptable");

	emit("\n\tentry( -2 , INPUT )");
	emit("\n\tentry ( -1 , OUTPUT )");
	emit("\n\tentry ( 0 , INIT )");

	for (int fid = 1; fid < numfids; fid++){
		emit("\n\tentry ( "); 
		emit(fid); 
		emit(" , ");
		emit(funLabel(fid));
		emit(" )");
		TRACE {
			emit(string("/* ") + fidnames[fid] +  " */");
		}
	}
	emit("\nMAIN:");
	emit("\n\tentry ( "); 
	emit(numfids); 
	emit(" , ");
	emit(funLabel(numfids));
	emit(" )");
	TRACE {
		emit(string("/* ") + fidnames[numfids] +  " */");
	}

	emit("\n\tendtable");
}