cc

- proper Pratt parsing of expressions
- fixed some register saving around divs and muls

1 files changed, 118 insertions, 57 deletions

diff --git a/miniany/cc.c b/miniany/cc.c
index ccda806..4d26893 100644
--- a/miniany/cc.c
+++ b/miniany/cc.c
@@ -17,8 +17,8 @@ enum {
 	S_INT = 10,
 	S_IDENT = 20,
 	S_NUM = 30,
-	S_ERR = 40,
-	S_EOI = 41
+	S_EOI = 98,
+	S_ERR = 99
 };
 
 struct Scanner {
@@ -340,15 +340,16 @@ enum {
 	A_SUBTRACT,
 	A_MULTIPLY,
 	A_DIVIDE,
-	A_ASSIGN
+	A_ASSIGN,
+	A_ERR = 99
 };
 
 struct ASTnode {
-	int op;
-	struct ASTnode *left;
-	struct ASTnode *right;
-	int intval;		/* for A_INT_LITERAL */
-	struct Symbol *sym;	/* for A_IDENT */
+	int op;			/* node operation, one of the A_ enums */
+	struct ASTnode *left;	/* left side operand */
+	struct ASTnode *right;	/* right side operand (or empty for unary operations */
+	int intval;		/* value in case of A_INT_LITERAL */
+	struct Symbol *sym;	/* symbol in case of A_IDENT */
 };
 
 struct ASTnode *createASTnode( int op, struct ASTnode *left, struct ASTnode *right, int intval, struct Symbol *sym )
@@ -391,7 +392,7 @@ void freeASTnode( struct ASTnode *node )
 	free( (char *)node );
 }
 
-/* parser/compiler, no forward definitions */
+/* parser/compiler, no forward declarations */
 
 struct Parser {
 	int token;
@@ -399,6 +400,14 @@ struct Parser {
 	struct Scope *global_scope;
 };
 
+struct Generator {
+	struct Scanner *scanner;
+	char **regName;			/* names of the registers */
+	int *regFree;			/* free registers */
+	int spillReg;			/* index of the current spilled register */
+	int debug;			/* adds debug output to generated assembly */
+};
+
 struct Compiler {
 	struct Parser *parser;
 	struct Generator *generator;
@@ -416,14 +425,6 @@ enum {
 	NOREG = -1
 };
 
-struct Generator {
-	struct Scanner *scanner;
-	char **regName;
-	int *regFree;
-	int spillReg;
-	int debug;
-};
-
 struct Generator *createGenerator( struct Scanner *scanner )
 {
 	struct Generator *generator;
@@ -650,8 +651,10 @@ int genMul( struct Generator *generator, int leftreg, int rightreg )
 	if( leftreg == EAX ) {
 		reg = genBinary( "mul", generator, leftreg, rightreg, 1 );
 	} else {
-		genSaveReg( generator, EAX );
-		if( leftreg != EDX ) {
+		if( !generator->regFree[EAX] ) {
+			genSaveReg( generator, EAX );
+		}
+		if( leftreg != EDX && !generator->regFree[EDX] ) {
 			genSaveReg( generator, EDX );
 		}
 		if( rightreg == EAX ) {
@@ -672,10 +675,12 @@ int genMul( struct Generator *generator, int leftreg, int rightreg )
 		putreg( generator, leftreg );
 		putstring( ", eax" );
 		putnl( );
-		if( leftreg != EDX ) {
+		if( leftreg != EDX && !generator->regFree[EDX] ) {
 			genRestoreReg( generator, EDX );
 		}
-		genRestoreReg( generator, EAX );
+		if( !generator->regFree[EAX] ) {
+			genRestoreReg( generator, EAX );
+		}
 		reg = leftreg;
 	}
 	
@@ -689,8 +694,12 @@ int genDiv( struct Generator *generator, int leftreg, int rightreg )
 	if( leftreg == EAX ) {
 		reg = genBinary( "div", generator, leftreg, rightreg, 1 );
 	} else {
-		genSaveReg( generator, EAX );
-		genSaveReg( generator, EDX );
+		if( !generator->regFree[EAX] ) {
+			genSaveReg( generator, EAX );
+		}
+		if( !generator->regFree[EDX] ) {
+			genSaveReg( generator, EDX );
+		}
 		if( rightreg == EAX ) {
 			genSaveReg( generator, EBX );
 			putstring( "mov ebx, eax" );
@@ -711,8 +720,12 @@ int genDiv( struct Generator *generator, int leftreg, int rightreg )
 		putreg( generator, leftreg );
 		putstring( ", eax" );
 		putnl( );
-		genRestoreReg( generator, EDX );
-		genRestoreReg( generator, EAX );
+		if( !generator->regFree[EDX] ) {
+			genRestoreReg( generator, EDX );
+		}
+		if( !generator->regFree[EAX] ) {
+			genRestoreReg( generator, EAX );
+		}
 		reg = leftreg;
 	}
 	
@@ -823,10 +836,71 @@ void parserExpect( struct Parser *parser, int must, char *what )
 	}
 }
 
-struct ASTnode *parseExpression( struct Parser *parser )
+int parserTokenToOperator( struct Parser *parser, int token )
 {
-	struct ASTnode *node, *left, *right;
+	int op;
+	
+	op = A_ERR;	
+	switch( token ) {
+		case S_STAR:
+			op = A_MULTIPLY;
+			break;
+			
+		case S_SLASH:
+			op = A_DIVIDE;
+			break;
+			
+		case S_PLUS:
+			op = A_ADD;
+			break;
+			
+		case S_MINUS:
+			op = A_SUBTRACT;
+			break;
+			
+		default:
+			scannerPrintErrorHeader( parser->scanner );
+			putstring( "unknown operator token for token " );
+			putint( token );
+			putnl( );
+			exit( EXIT_FAILURE );		
+	}
+	
+	return op;
+}
+
+int parserOperatorPrecedence( struct Parser *parser, int operator )
+{
+	int precedence;
+	
+	precedence = 0;
+	switch( operator ) {
+		case A_MULTIPLY:
+		case A_DIVIDE:
+			precedence = 2;
+			break;
+			
+		case A_ADD:
+		case A_SUBTRACT:
+			precedence = 1;
+			break;
+			
+		default:
+			scannerPrintErrorHeader( parser->scanner );
+			putstring( "unknown operator precedence for operator " );
+			putint( operator );
+			putnl( );
+			exit( EXIT_FAILURE );		
+	}
+	
+	return precedence;
+}
+
+struct ASTnode *parseExpression( struct Parser *parser, int level )
+{
+	struct ASTnode *left, *right;
 	struct Symbol *sym;
+	int op;
 	
 	if( parser->token == S_EOI ) {
 		scannerPrintErrorHeader( parser->scanner );
@@ -846,7 +920,7 @@ struct ASTnode *parseExpression( struct Parser *parser )
 			putstring( "' in expression" );
 			putnl( );
 			exit( EXIT_FAILURE );
-		}			
+		}
 		left = createASTleafSym( A_IDENT, sym );
 	} else {
 		left = NULL;
@@ -859,35 +933,22 @@ struct ASTnode *parseExpression( struct Parser *parser )
 	}
 			
 	parser->token = getToken( parser->scanner );
-	if( parser->token == S_PLUS ) {
-		parser->token = getToken( parser->scanner );
-		right = parseExpression( parser );
-		node = createASTbinary( A_ADD, left, right );
-	} else if( parser->token == S_MINUS ) {
-		parser->token = getToken( parser->scanner );
-		right = parseExpression( parser );
-		node = createASTbinary( A_SUBTRACT, left, right );
-	} else if( parser->token == S_STAR ) {
-		parser->token = getToken( parser->scanner );
-		right = parseExpression( parser );
-		node = createASTbinary( A_MULTIPLY, left, right );
-	} else if( parser->token == S_SLASH ) {
+	if( parser->token == S_EOI || parser->token == S_SEMICOLON ) {
+		return left;
+	}
+	
+	op = parserTokenToOperator( parser, parser->token );
+	while( parserOperatorPrecedence( parser, op ) > level ) {
 		parser->token = getToken( parser->scanner );
-		right = parseExpression( parser );
-		node = createASTbinary( A_DIVIDE, left, right );
-	} else if( parser->token == S_EOI || parser->token == S_SEMICOLON ) {
-		node = left;
-	} else {
-		node = NULL;
-		scannerPrintErrorHeader( parser->scanner );
-		putstring( "unexpected token '" );
-		putint( parser->token );
-		putstring( "' in expression" );
-		putnl( );
-		exit( EXIT_FAILURE );
+		right = parseExpression( parser, parserOperatorPrecedence( parser, op ) );
+		left = createASTbinary( op, left, right );
+		if( parser->token == S_EOI || parser->token == S_SEMICOLON ) {
+			return left;
+                }
+		op = parserTokenToOperator( parser, parser->token );
 	}
 	
-	return node;
+	return left;
 }
 
 void parseDeclaration( struct Compiler *compiler )
@@ -932,7 +993,7 @@ void parseAssignment( struct Compiler *compiler )
 	}
 	right = createASTleafSym( A_LVIDENT, sym );
 	parserExpect( parser, S_EQUALS, "=" );
-	left = parseExpression( parser );
+	left = parseExpression( parser, 0 );
 	parserExpect( parser, S_SEMICOLON, ";" );
 	
 	node = createASTbinary( A_ASSIGN, left, right );
@@ -989,8 +1050,8 @@ int main( int argc, char **argv )
 	struct Compiler *compiler;
 
 	compiler = createCompiler( );
-/*	compiler->parser->scanner->debug = 1; */
-/*	compiler->generator->debug = 1; */
+	/* compiler->parser->scanner->debug = 1; */
+	/* compiler->generator->debug = 1; */
 	genPrologue( compiler );
 	compiler->parser->token = getToken( compiler->parser->scanner );
 	while( compiler->parser->token != S_EOI ) {