parse.cpp

CMinus 小型编译器的词法分析与语法分析部分

/****************************************************/
/* File: parse.c                                    */
/* The parser implementation for the TINY compiler  */
/* Compiler Construction: Principles and Practice   */
/* Kenneth C. Louden                                */
/****************************************************/

#include "globals.h"
#include "util.h"
#include "scan.h"
#include "parse.h"

static TokenType token;

static TreeNode * declaration_list(void);
static TreeNode * declaration(void);
static TreeNode * params(void);
static TreeNode * param_list(void);
static TreeNode * param(void);
static TreeNode * compound_stmt(void);
static TreeNode * local_declarations(void);
static TreeNode * statement_list(void);
static TreeNode * statement(void);
static TreeNode * expession_stmt(void);
static TreeNode * selection_stmt(void);
static TreeNode * iteration_stmt(void);
static TreeNode * return_stmt(void);
static TreeNode * expression(void);
static TreeNode * expression_stmt(void);
static TreeNode * var(void);
static TreeNode * simple_expression(void);
static TreeNode * additive_expression(void);
static TreeNode * term(void);
static TreeNode * factor(void);
static TreeNode * call(void);
static TreeNode * args(void);
static TreeNode * arg_list(void);

static void syntaxError(char * message)
{ fprintf(listing,"\n>>> ");
  fprintf(listing,"Syntax error at line %d: %s",lineno,message);
  Error = TRUE;
}

static void match(TokenType expected)
{ if (token == expected) token = getToken();
  else {
    syntaxError("unexpected token -> ");
    printToken(token,tokenString);
    fprintf(listing,"      ");
  }
}

TreeNode * declaration_list(void)
{
	TreeNode * t = NULL;
	if(token == INT|| token == VOID)
	{
		t = declaration();
		TreeNode * p = t;
		while ((token != ENDFILE)&&(token == INT || token == VOID))
		{
			TreeNode * q = declaration();
			if (q != NULL)
			{
				if (t != NULL)	t = p = q;
				else
				{
					p->sibling = q;
					p = q;
				}
			}
		}
	}
	return t;
}

TreeNode * declaration(void)
{
	TreeNode * t = newDecNode();
	switch(token) {
	case INT:
		t->attr.type = "int";
		match(INT);
		break;
	case VOID:
		t->attr.type = "void";
		match(VOID);
		break;
	default:
		syntaxError("unexpected token in Type-> ");
		printToken(token,tokenString);
		token = getToken();
		break;
	}
	t->attr.name = copyString(tokenString);
	match(ID);
	switch(token) {
		case SEMI:
			match(SEMI);
			t->kind.dec = VarK;
			break;
		case LBRA:
			match(LBRA);
			t->kind.dec = ArrayK;
			t->child[0] = factor();
			match(RBRA);
			match(SEMI);
			break;
		case LPAREN:
			match(LPAREN);
			t->kind.dec = FunK;
			if (t != NULL)
				t->child[0] = params();
			match(RPAREN);
			if (t != NULL)
				t->child[1] = compound_stmt();
			break;
		default:
			syntaxError("unexpected token in Declaration -> ");
			printToken(token,tokenString);
			token = getToken();
			break;
	}
	return t;
}

TreeNode * params(void)
{
	TreeNode * t = newParamNode(Null);
	if (token == VOID)
	{
		t->attr.type = copyString(tokenString);
		match(VOID);
	}
	else if(token == INT)
		t->child[0] = param_list();
	else
	{
		syntaxError("unexpected token in Params -> ");
		printToken(token,tokenString);
		token = getToken();
	}
	return t;
}

TreeNode * param_list(void)
{
	TreeNode * t = param();
	TreeNode * p = t;
	while(token == COMMA)
	{
		match(COMMA);
		TreeNode * q = param();
		if(q != NULL)
		{
			if(t == NULL)	t = p = q;
			else
			{
				p->sibling = q;
				p = q;
			}
		}
	}
	return t;
}

TreeNode * param(void)
{
	TreeNode * t = newParamNode(Null);
	t->attr.type = copyString(tokenString);
	match(INT);
	t->kind.param = Var;
	t->attr.name = copyString(tokenString);
	match(ID);
	if (token == LBRA)
	{
		match(LBRA);	//识别数组;
		t->kind.param = Array;
		match(RBRA);
	}
	return t;
}

TreeNode * compound_stmt()
{
	TreeNode * t = newStmtNode(CompoundK);
	match(LBRACE);
	if((t != NULL)&&(token == INT || token == VOID))
		t->child[0] = local_declarations();
	if (t!=NULL)
		t->child[1] = statement_list();
	match(RBRACE);
	return t;
}

TreeNode * local_declarations(void)
{
	TreeNode * t = declaration();
	TreeNode * q =t;
	while(token == INT)
	{
		TreeNode * p = declaration();
		q->sibling=p;
		q=p;
	}
	return t;
}

TreeNode * statement_list(void)
{
	TreeNode * t = statement();
	TreeNode * q = t;
	while((token != RBRACE)&&(token != ENDFILE))
	{
		TreeNode *  p = statement();
		if(p!=NULL)
		{ 
			if(q==NULL)t=q=p;
			else
			{  
			q->sibling = p;
			q = p;}
			}
	}
	return t;
}

TreeNode * statement(void)
{
	TreeNode * t = NULL;
	switch(token){
		case LBRACE:	t = compound_stmt();break;
		case IF:	t = selection_stmt();break;
		case WHILE:	t = iteration_stmt();break;
		case RETURN:	t = return_stmt();break;
		case LPAREN:
		case ID:
		case NUM:
		case SEMI:
			t = expression_stmt();break;
		default:
			syntaxError("unexpected statement -> ");
			printToken(token,tokenString);
			token = getToken();
			break;
	}
	return t;
}

TreeNode * expression_stmt(void)
{
	TreeNode * t = newStmtNode(ExpressionK);
	if (token == SEMI){
		match(SEMI); 
	}
	else
	{
		t->child[0] = expression();
		match(SEMI);
	}
	return t;
}

TreeNode * selection_stmt(void)
{
	TreeNode * t = newStmtNode(SelectionK);
	match(IF);
	match(LPAREN);
	if(t != NULL)	t->child[0] = expression();
	match(RPAREN);
	if(t != NULL)	t->child[1] = statement();
	if(token == ELSE)
	{
		match(ELSE);
		if(t != NULL)	t->child[2] = statement();
	}
	return t;
}

TreeNode * iteration_stmt(void)
{
	TreeNode * t = newStmtNode(IterationK);
	match(WHILE);
	match(LPAREN);
	if(t != NULL)	t->child[0] = expression();
	match(RPAREN);
	if(t != NULL)	t->child[1] = statement();
	return t;
}

TreeNode * return_stmt(void)
{
	TreeNode * t = newStmtNode(ReturnK);
	match(RETURN);
	if(token == SEMI)
		match(SEMI);
	else 
	{
		t->child[0]=expression();
		match(SEMI);
	}
	return t;
}

TreeNode * expression(void)
{
	TreeNode * t = simple_expression();
	if(token==ASSIGN)
	{
		TreeNode * p = newExpNode(OpK);
		if (p!=NULL)
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
			match(token);
			t->child[1] = expression();
		}
		
	}
	return t;
}
TreeNode * var(void)
{
	TreeNode * t = newExpNode(IdK);
	t->attr.name = copyString(tokenString);
	match(ID);
	if(token == LBRA)
	{
		match(LBRA);
		t->child [0] = expression();
		match(RBRA);
	}
	return t;
}

TreeNode * simple_expression(void)
{
	TreeNode * t = additive_expression();
	if ((token == LT)||(token == LTEQ)||(token == GT)||(token == GTEQ)||(token == EQ)||(token ==NOEQ))
	{
		TreeNode * p = newExpNode(OpK);
		if(p != NULL)
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
		}
			match(token);
			if(t != NULL)
				t->child[1] = additive_expression();
	}
	return t;
}

TreeNode * additive_expression(void)
{
	TreeNode * t = term();
	while((token == PLUS)||(token == MINUS))
	{
		TreeNode * p = newExpNode(OpK);
		if (p !=NULL) 
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
			match(token);
			t->child[1] = term();
		}
	}
	return t;
}

TreeNode * term(void)
{
	TreeNode * t = factor();
	while ((token == TIMES) || (token == OVER))
	{ TreeNode * p = newExpNode(OpK);
	if (p != NULL) {
		p ->child[0] = t;
		p ->attr.op = token;
		t = p;
		match (token);
		p ->child[1] = factor();
	}
	}
	return t;
}

TreeNode * factor(void)
{
	TreeNode * t = NULL;
	char * varToken;
	switch(token) {
		case NUM:
			t = newExpNode(ConstK);
			if ((t != NULL)&&(token == NUM))
			{
				t->attr.val = atoi(tokenString);
				match(NUM);
			}
			break;
		case LPAREN:
			match(LPAREN);
			t = expression();
			match(RPAREN);
			break;
		case ID:
			{
			varToken = copyString(tokenString);
			match(ID);
			if(token == LBRA)
			{
					t = newExpNode(IdK);
					match(LBRA);
					t->attr.name = copyString(varToken);
					t->child[0] = expression();
					match(RBRA);
			}
			else if(token == LPAREN)
			{
					t = newExpNode(CallK);
					t->attr.name = copyString(varToken);
					match(LPAREN);
					t->child[0] = args();
					match(RPAREN);
			}
			else
			{
					t = newExpNode(IdK);
					t->attr.name = copyString(varToken);
			}
			}
			break;
		default:
			syntaxError("unexpected token in factor-> ");
			printToken(token,tokenString);
			token = getToken();
			break;
	}
	return t;
}

TreeNode * args(void)
{
	TreeNode * t = NULL;
	if (token != RPAREN)
		t = arg_list();
	return t;
}

TreeNode * arg_list(void)
{
	TreeNode * t = expression();
	TreeNode * p = t;
	while(token != RPAREN)
	{
		match(COMMA);
		TreeNode * q = expression();
		if(q != NULL)
		{
			if(t == NULL)	t = p = q;
			else
			{
				p->sibling = q;
				p = q;
			}
		}
	}
	return t;
}

/****************************************/
/* the primary function of the parser   */
/****************************************/

TreeNode * parse(void)
{ TreeNode * t;
  token = getToken();
  t = declaration_list();
  if (token!=ENDFILE)
    syntaxError("Code ends before file\n");
  return t;
}