#include #include #include #include #include #include #include "hash.h" #ifdef DMALLOC #include "dmallocFor241.h" #endif #define ERROR_NONE 0 // Program state is OK #define ERROR_LITERAL 1 // Error while parsing a literal /* Some helper functions */ void reportLexerError( char* input, int fail_at ) { fprintf( stderr, "ERROR in lexing after reading \"" ); fwrite( input, 1, fail_at, stderr ); fprintf( stderr, "\"\n" ); } void reportLiteralError(char* input, char* literal) { fprintf( stderr, "ERROR in scanning line: %sNumeric literal invalid or out of range: %s\n", input, literal ); } /* The various kinds of tokens. */ typedef enum { ID, // Opcode or identifier (use of a label) INT, // Decimal integer HEXINT, // Hexadecimal integer REGISTER, // Register number COMMA, // Comma LPAREN, // ( RPAREN, // ) LABEL, // Declaration of a label (with a colon) DOTWORD, // .word directive WHITESPACE, // Whitespace NUL // Bad/invalid token } Kind; /* Representation of a token. */ typedef struct { Kind kind; // The kind of token. char * lexeme; // String representation of the actual token in the source code. int value; // Numerical value of this token, if representable as a number (e.g. INT, HEXINT, REGISTER) } Token; typedef struct TokenNode_ { Token * token; struct TokenNode_ * next; } TokenNode; typedef struct { TokenNode * first, * last; } TokenList; void freeFirstToken( TokenList * tokenlist ) { TokenNode *temp = tokenlist->first; free( temp->token->lexeme ); free( temp->token ); tokenlist->first = temp->next; free( temp ); } void append( TokenList ** list, Token * token ) { if( *list == NULL ) { *list = (TokenList*) malloc( sizeof(TokenList) ); (*list)->first = (*list)->last = (TokenNode*)malloc( sizeof(TokenNode) ); } else { (*list)->last = (*list)->last->next = (TokenNode*) malloc( sizeof(TokenNode) ); } (*list)->last->token = token; (*list)->last->next = NULL; } char* tokenToString( Token * token ) { char * kstring, * result; char * kinds[11] = { "ID", "INT", "HEXINT", "REGISTER", "COMMA", "LPAREN", "RPAREN", "LABEL", "DOTWORD", "WHITESPACE", "NUL" }; kstring = kinds[token->kind]; result = (char*) malloc( 4 + strlen(token->lexeme) + strlen(kstring) ); sprintf( result, "%s {%s}", kstring, token->lexeme ); return result; } int parseLiteral( char * s, int base, int * retVal ) { // strtol(...) and strtoul(...) set errno (defined in errno.h) to flag errors. *retVal = ( s[0] == '-' ? strtol(s,NULL,base) : strtoul(s,NULL,base) ); return (errno == ERANGE ? (errno=0, ERROR_LITERAL) : ERROR_NONE ); } /* For tokens denoting integer literals (i.e., INT and HEXINT), returns * the integer constant as an int. For tokens of kind REGISTER, returns the * register number. For all other token types, the function does nothing. */ int tokenToInt( Token * token, int * retVal ) { if( token->kind == INT ) return parseLiteral( token->lexeme, 10, retVal ); if( token->kind == HEXINT ) return parseLiteral( token->lexeme + 2, 16, retVal ); if( token->kind == REGISTER ) { int result = parseLiteral( token->lexeme + 1, 10, retVal ); return ( (*retVal & 0x1f) != *retVal ? ERROR_LITERAL : result ); } return ERROR_NONE; } /* Lexer -- partitions an input line into a list of tokens. */ // See the definition of the macro "all" further on - the set of // all characters is represented by NULL. unsigned char charSetContains( char* chars, char newC ) { return !chars || strchr(chars,newC); } typedef enum { ST_START = 1, ST_DOLLAR, ST_MINUS, ST_REGISTER, ST_INT, ST_ID, ST_LABEL, ST_COMMA, ST_LPAREN, ST_RPAREN, ST_ZERO, ST_ZEROX, ST_HEXINT, ST_COMMENT, ST_DOT, ST_DOTW, ST_DOTWO, ST_DOTWOR, ST_DOTWORD, ST_WHITESPACE } State; Kind stateKinds[ST_WHITESPACE+1] = { NUL, NUL, NUL, NUL, REGISTER, INT, ID, LABEL, COMMA, LPAREN, RPAREN, INT, NUL, HEXINT, WHITESPACE, NUL, NUL, NUL, NUL, DOTWORD, WHITESPACE }; unsigned char stateIsFinal( State state ) { return stateKinds[state] != NUL; } typedef struct { State fromState; char* chars; State toState; } Transition; #define whitespace "\t\n\r " #define letters "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" #define digits "0123456789" #define hexDigits "0123456789ABCDEFabcdef" #define oneToNine "123456789" #define all NULL Transition delta[] = { { ST_START, whitespace, ST_WHITESPACE }, { ST_START, letters, ST_ID }, { ST_ID, letters digits, ST_ID }, { ST_START, oneToNine, ST_INT }, { ST_INT, digits, ST_INT }, { ST_START, "-", ST_MINUS }, { ST_MINUS, digits, ST_INT }, { ST_START, ",", ST_COMMA }, { ST_START, "(", ST_LPAREN }, { ST_START, ")", ST_RPAREN }, { ST_START, "$", ST_DOLLAR }, { ST_DOLLAR, digits, ST_REGISTER }, { ST_REGISTER, digits, ST_REGISTER }, { ST_START, "0", ST_ZERO }, { ST_ZERO, "x", ST_ZEROX }, { ST_ZERO, digits, ST_INT }, { ST_ZEROX, hexDigits, ST_HEXINT }, { ST_HEXINT, hexDigits, ST_HEXINT }, { ST_ID, ":", ST_LABEL }, { ST_START, ";", ST_COMMENT }, { ST_START, ".", ST_DOT }, { ST_DOT, "w", ST_DOTW }, { ST_DOTW, "o", ST_DOTWO }, { ST_DOTWO, "r", ST_DOTWOR }, { ST_DOTWOR, "d", ST_DOTWORD }, { ST_COMMENT, all, ST_COMMENT } }; State findTransition( State state, char c ) { Transition *t; for(t = delta; t < delta + sizeof(delta)/sizeof(Transition); t++) if(t->fromState == state && charSetContains(t->chars, c)) return t->toState; return (State) 0; } /* Partitions the line passed in as input into a linked list of tokens. * The linked list of tokens is returned. */ TokenList * scan( char * input ) { int i = 0; int startIndex = 0; State state = ST_START; TokenList * ret = NULL; int len = strlen(input); while( i < len ) { State t = findTransition( state, input[i] ); if( ! t ) { /* no more transitions possible */ if( ! stateIsFinal(state) ) { reportLexerError( input, i ); return NULL; } else if( stateKinds[state] != WHITESPACE ) { // Whitespace separates tokens, & is otherwise ignored. // Create and add the new token to the list Token *token = (Token*) malloc( sizeof(Token) ); token->kind = stateKinds[state]; token->lexeme = (char*) malloc( 1 + i - startIndex ); strncpy( token->lexeme, (input+startIndex), (i-startIndex) ); token->lexeme[i-startIndex] = '\0'; // Was NULL. // Fill in the numerical representation of the token, if applicable if( tokenToInt(token,&token->value) == ERROR_LITERAL ) { reportLiteralError( input, token->lexeme ); return NULL; } append( &ret, token ); } startIndex = i; state = ST_START; } else { state = t; i++; } } return ret; } /* //Consumes an array containing a binary num, prints it in binary void printbin(int a[]) { int current = 0; while(current != 32) { putchar(a[current]<<7 | a[current+1]<<6 | a[current+2]<<5 | a[current+3]<<4 | a[current+4]<<3 | a[current+5]<<2 | a[current+6]<<1 | a[current+7]); current = current +8; } } //Consumes an integer, converts to 2's complement void dtob(int dec) { int negtag = 0; int arrbin[32] = {0}; int curr = 31; int rem; int quo; if(dec<0) { quo = -1 - dec; negtag = 1; } else { quo = dec; } while (quo != 0) { rem = quo % 2; quo = quo / 2; arrbin[curr] = rem; curr--; } curr = 0; if (negtag == 1) { while(curr != 32) { if(arrbin[curr] == 0) { arrbin[curr] = 1; curr++; } else if(arrbin[curr] == 1) { arrbin[curr] = 0; curr++; } } } printbin(arrbin); } */ //Credit Mike D'Anna (same function as huge one above) void dtob(int num) { for(int i = 24; i >= 0; i -= 8) { putchar(num>>i); } } //Prints codes for jr and jalr void print_j(int value, int a) { if (a == 0) { //jr dtob(value << 21 | 8); } else { //jalr dtob(value << 21 | 9); } } //Prints codes for add sub slt sltu beq bne void print_asssb(int value1, int value2, int value3, int a) { if (a == 0) { //add dtob(value2 << 21 | value3 << 16 | value1 << 11 | 32); } else if (a == 1) { //sub dtob(value2 << 21 | value3 << 16 | value1 << 11 | 34); } else if (a == 2) { //slt dtob(value2 << 21 | value3 << 16 | value1 << 11 | 42); } else if (a == 3) { //sltu dtob(value2 << 21 | value3 << 16 | value1 << 11 | 43); } else if (a == -1) { //beq dtob(4 << 26 | value1 << 21 | value2 << 16 | (value3 & 65535)); } else { //bne dtob(5 << 26 | value1 << 21 | value2 << 16 | (value3 & 65535)); } } //Prints codes for lis mflo mfhi void print_lmm(int value, int a) { if (a == 0) { //lis dtob(value << 11 | 20); } if (a == 1) { //mflo dtob(value << 11 | 18); } else { //mfhi dtob(value << 11 | 16); } } //Check if string is valid, i.e. alphanumeric, first char not number, ':' at end. Returns 1 if valid, 0 otherwise. int validl(char* label) { if (isalpha(label[0])) { int i = 1; while (isalnum(label[i])) { i++; } if ((label[i] != ':') || (label[i+1] != NULL)) return 0; //If first two not alnum chars aren't :, EOF else return 1; } else return 0; //first character not letter } //Same as validl but does not require the colon before EOF int validlnoc(char* label) { if (isalpha(label[0])) { int i = 1; while (isalnum(label[i])) { i++; } if (label[i] != NULL) return 0; //If first not alnum char isnt EOF else return 1; } else return 0; //first character not letter } //Removes the end colon from the end string char* removecolon(char* label) { char* new = label; int i = 0; while (new[i] != ':') { i++; } new[i] = new[i+1]; return new; } //Same as lookup, implemented with getAll int mylookup(hashtbl tbl, char *key) { Node *ls = getAll(tbl); //stores the symbol table while(ls != NULL) { if(strcmp(ls->key, key) == 0) { return ls->value; } else ls = ls->next; } return -1; } //Triple storage concept credit to Alex Forbes int main() { char line[256]; TokenList * tlist = NULL; //setup storage int size = 50; Kind *kindstore = malloc(size * sizeof(Kind)); int *valstore = malloc(size * sizeof(int)); // check char **lexemestore = malloc(size * sizeof(char*)); char *new; int nextindex = 0; int wordflag = 0; //0 when prev token not .word, 1 if it is .word int next_reg_flag = 0; //1 if next token should be register, 0 otherwise int next_comma_flag = 0; //1 if next token should be comma, 0 otherwise int id_length_asss = 0; //Number of arguments (registers and commas) left to store, used for error checking int id_length_br = 0; hashtbl symtbl = newHashTable(911); //new hash table int adrcount = 0; //address of next instruction #ifdef DMALLOC dmalloc_setup( DMALLOC_high, "print-messages" ); #endif while( fgets( line, 256, stdin ) ) { for( tlist=scan(line); tlist && tlist->first; freeFirstToken(tlist) ) { if (nextindex >= size) { //reallocate if out of memory size *= 2; kindstore = realloc(kindstore, size * sizeof(Kind)); valstore = realloc(valstore, size * sizeof(int)); lexemestore = realloc(lexemestore, size * sizeof(char*)); } if (tlist->first->token->kind == COMMA) { if (next_comma_flag == 1) { next_comma_flag = 0; if ((id_length_asss > 0) || (id_length_br > 0)) { next_reg_flag = 1; if (id_length_asss > 0) id_length_asss--; else if (id_length_br > 0) { id_length_br--; if (id_length_br == 1) next_reg_flag = 0; } } } else { //Invalid position for comma fprintf(stderr, "ERROR: Invalid comma position"); exit(0); } } else if ((tlist->first->token->kind == DOTWORD)) { if ((wordflag == 1) || (next_reg_flag == 1) || (next_comma_flag == 1) || (id_length_asss > 0) || (id_length_br > 0)) { //Invalid position for .word fprintf(stderr, "ERROR: Invalid .word position"); exit(0); } else { wordflag = 1; adrcount +=4; } } else if ((tlist->first->token->kind == INT) || (tlist->first->token->kind == HEXINT)) { if ((wordflag == 1) || (id_length_br == 1)) { //Follows a .word or is part of branch instruction kindstore[nextindex] = INT; valstore[nextindex] = tlist->first->token->value; nextindex++; if (wordflag == 1) wordflag = 0; else if (id_length_br == 1) { // next_reg_flag = 0; id_length_br--; } } else { //Invalid position of number fprintf(stderr, "ERROR: Invalid num position"); exit(0); } } else if (tlist->first->token->kind == LABEL) { //Label definition if ((next_reg_flag == 1) || (next_comma_flag == 1) || (id_length_asss > 0) || (id_length_br > 1)) { //Invalid position of label fprintf(stderr, "ERROR: Invalid label def. position"); exit(0); } if (validl(tlist->first->token->lexeme) && (contains(symtbl, tlist->first->token->lexeme) == 0)) { //valid and not in hash new = malloc(size * sizeof(char)); strcpy(new, tlist->first->token->lexeme); insert(symtbl, new, adrcount); //inserts new label into table } else { //Not valid string or already is hash table fprintf(stderr, "ERROR: Not valid label def. or label redef."); exit(0); } } else if (tlist->first->token->kind == REGISTER) { if (tlist->first->token->value > 31) { //Invalid register number fprintf(stderr, "ERROR: Invalid register"); exit(0); } else if (next_reg_flag == 1) { kindstore[nextindex] = REGISTER; valstore[nextindex] = tlist->first->token->value; nextindex++; next_reg_flag = 0; if ((id_length_asss > 1) || (id_length_br > 1)) { next_comma_flag = 1; if (id_length_asss > 0) id_length_asss--; else if (id_length_br > 0) id_length_br--; } else { if (id_length_asss > 0) id_length_asss--; else if (id_length_br > 0) id_length_br--; } } else { //Invalid position for register fprintf(stderr, "ERROR: Invalid register position"); exit(0); } } else if (tlist->first->token->kind == ID) { if ((wordflag == 1) || (next_reg_flag == 1) || (next_comma_flag == 1) || (id_length_asss > 0) || (id_length_br > 1)) { //Invalid position for ID fprintf(stderr, "ERROR: Invalid ID position"); exit(0); } else if ((strcmp(tlist->first->token->lexeme, "jr") == 0) || (strcmp(tlist->first->token->lexeme, "jalr") == 0)) { //Token is jump reg. new = malloc(size * sizeof(char)); strcpy(new, tlist->first->token->lexeme); kindstore[nextindex] = ID; lexemestore[nextindex] = new; nextindex++; adrcount +=4; next_reg_flag = 1; id_length_asss = 1; } else if ((strcmp(tlist->first->token->lexeme, "add") == 0) || (strcmp(tlist->first->token->lexeme, "sub") == 0) || (strcmp(tlist->first->token->lexeme, "slt") == 0) || (strcmp(tlist->first->token->lexeme, "sltu") == 0)) { new = malloc(size * sizeof(char)); strcpy(new, tlist->first->token->lexeme); kindstore[nextindex] = ID; lexemestore[nextindex] = new; nextindex++; adrcount +=4; next_reg_flag = 1; id_length_asss = 5; } else if ((strcmp(tlist->first->token->lexeme, "bne") == 0) || (strcmp(tlist->first->token->lexeme, "beq") == 0)) { new = malloc(size * sizeof(char)); strcpy(new, tlist->first->token->lexeme); kindstore[nextindex] = ID; lexemestore[nextindex] = new; nextindex++; adrcount +=4; next_reg_flag = 1; id_length_br = 5; } else if ((strcmp(tlist->first->token->lexeme, "lis") == 0) || (strcmp(tlist->first->token->lexeme, "mflo") == 0) || (strcmp(tlist->first->token->lexeme, "mfhi") == 0)) { new = malloc(size * sizeof(char)); strcpy(new, tlist->first->token->lexeme); kindstore[nextindex] = ID; lexemestore[nextindex] = new; nextindex++; adrcount +=4; next_reg_flag = 1; id_length_asss = 1; } else { //Label as operand if ((wordflag == 1) || (id_length_br == 1)) { if (validlnoc(tlist->first->token->lexeme)) { new = malloc(size * sizeof(char)); strcpy(new, tlist->first->token->lexeme); kindstore[nextindex] = ID; lexemestore[nextindex] = new; if (wordflag == 1) { wordflag = 0; nextindex++; } else if (id_length_br == 1) { valstore[nextindex] = adrcount-4; //Stores the address of branch instruction nextindex++; //next_reg_flag = 0; id_length_br--; } } else { //Invalid label as operand fprintf(stderr, "ERROR: Invalid label as operand"); exit(0); } } else { //Invalid position of label as operand fprintf(stderr, "ERROR: Invalid label position as operand"); exit(0); } } } else { //Invalid tokennext fprintf(stderr, "ERROR: Unknown command"); exit(0); } /* //Print tokens in lines char* string = tokenToString(tlist->first->token); fprintf( stderr, " Token: %s\n", string ); free( string ); */ } free( tlist ); } /* Node* l = getAll(symtbl); while (l != NULL) { l->key = removecolon(l->key); l = l->next; } //print symtable Node* list = getAll(symtbl); while (list != NULL) { fprintf(stderr, "%s %d\n", list->key, list->value); list = list->next; } */ //Print value and lexeme arrays // fprintf(stderr, "%d %d %d %d %d", wordflag, next_reg_flag, next_comma_flag, id_length_asss, id_length_br); int max = nextindex; int L; int B; nextindex = 0; while (nextindex < max) { if (kindstore[nextindex] == INT) { dtob(valstore[nextindex]); nextindex++; } else if (kindstore [nextindex] == ID) { if (strcmp(lexemestore[nextindex], "jr") == 0) { print_j(valstore[nextindex+1], 0); //Print as jr nextindex += 2; } else if (strcmp(lexemestore[nextindex], "jalr") == 0) { print_j(valstore[nextindex+1], 1); //Print as jalr nextindex += 2; } else if (strcmp(lexemestore[nextindex], "add") == 0) { print_asssb(valstore[nextindex+1], valstore[nextindex+2], valstore[nextindex+3], 0); //Print as add nextindex += 4; } else if (strcmp(lexemestore[nextindex], "sub") == 0) { print_asssb(valstore[nextindex+1], valstore[nextindex+2], valstore[nextindex+3], 1); //Print as sub nextindex += 4; } else if (strcmp(lexemestore[nextindex], "slt") == 0) { print_asssb(valstore[nextindex+1], valstore[nextindex+2], valstore[nextindex+3], 2); //Print as slt nextindex += 4; } else if (strcmp(lexemestore[nextindex], "sltu") == 0) { print_asssb(valstore[nextindex+1], valstore[nextindex+2], valstore[nextindex+3], 3); //Print as sltu nextindex += 4; } else if (strcmp(lexemestore[nextindex], "beq") == 0) { if (kindstore[nextindex+3] == INT) { print_asssb(valstore[nextindex+1], valstore[nextindex+2], valstore[nextindex+3], -1); //Print as beq nextindex +=4; } else if (kindstore[nextindex+3] == ID) { L = mylookup(symtbl, lexemestore[nextindex+3]); if (L != 1) { B = valstore[nextindex+3]; print_asssb(valstore[nextindex+1], valstore[nextindex+2], (L-B-4)/4, -1); //Print as beq nextindex +=4; } else { //Use of undefined label fprintf(stderr, "ERROR: Use of undefined label, %s", lexemestore[nextindex+3]); exit(0); } } } else if (strcmp(lexemestore[nextindex], "bne") == 0) { if (kindstore[nextindex+3] == INT) { print_asssb(valstore[nextindex+1], valstore[nextindex+2], valstore[nextindex+3], -2); //Print as bne nextindex +=4; } else if (kindstore[nextindex+3] == ID) { L = mylookup(symtbl, lexemestore[nextindex+3]); if (L != 1) { B = valstore[nextindex+3]; print_asssb(valstore[nextindex+1], valstore[nextindex+2], (L-B-4)/4, -2); //Print as bne nextindex +=4; } else { //Use of undefined label fprintf(stderr, "ERROR: Use of undefined label, %s", lexemestore[nextindex+3]); exit(0); } } } else if (strcmp(lexemestore[nextindex], "lis") == 0) { fprintf(stderr, "lol1"); print_lmm(valstore[nextindex+1], 0); //Print as lis nextindex += 2; } else if (strcmp(lexemestore[nextindex], "mflo") == 0) { fprintf(stderr, "lol2"); print_lmm(valstore[nextindex+1], 1); //Print as mflo nextindex += 2; } else if (strcmp(lexemestore[nextindex], "mfhi") == 0) { fprintf(stderr, "lol3"); print_lmm(valstore[nextindex+1], 2); //Print as mfhi nextindex += 2; } else { //label L = mylookup(symtbl, lexemestore[nextindex]); //Searches for address of label def. in hash if (L != -1) { dtob(L); nextindex++; } else { //Use of undefined label fprintf(stderr, "ERROR: Use of undefined label, %s", lexemestore[nextindex]); exit(0); } } } } freeHashTable(symtbl); free(kindstore); free(valstore); free(lexemestore); return 0; }