parse.c

1.小型编译器 2。支持整数

/****************************************************/
/* 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 int	level = 0;

static TokenType token; /* holds current token */
static ExpType	saveType;

/* function prototypes for recursive calls */
static TreeNode * stmt_list(void);
static TreeNode * stmt(void);
static TreeNode * if_stmt(void);
static TreeNode * repeat_stmt(void);
static TreeNode * while_stmt(void);
static TreeNode * assign_stmt(void);
static TreeNode * read_stmt(void);
static TreeNode * write_stmt(void);
static TreeNode * return_stmt(void);
static TreeNode * exp(void);
static TreeNode * simple_exp(void);
static TreeNode * term(void);
static TreeNode * factor(void);

static TreeNode * program(void);
static TreeNode * dec_list(void);
static TreeNode * dec(void);
static TreeNode * var_dec(void);
static TreeNode * fun_dec(void);
static TreeNode * fun_def(void);
ExpType type_spec(void);
static TreeNode * id_list(void);
static TreeNode * params(void);
static TreeNode * param_list(void);
static TreeNode * param(void);
static TreeNode * comp_stmt(void);
static TreeNode * local_dec(void);
static TreeNode * args(void);
static TreeNode * arg_list(void);
static TreeNode * var(void);


static void syntaxError(const 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 * program(void)
{
	printf("program begin\n");
	TreeNode * t = dec_list();
	return t;
}

TreeNode * dec_list(void)
{
	printf("dec_list begin\n");
	TreeNode * t = dec();
  	TreeNode * p = t;
  	while ((token!=ENDFILE)&& (token!=END))
  	{ 
  		TreeNode * q;
    	q = dec();
    	if (q!=NULL) {
      		if (t==NULL) 
				t = p = q;
      		else /* now p cannot be NULL either */
      		{ 
      			p->sibling = q;
        		p = q;
      		}
    	}
  	}
 	return t;
}

TreeNode * dec(void)
{
	printf("dec begin\n");
	TreeNode * t = NULL;

	if(token==ENDFILE){
		printf("token is ENDFILE\n");
		return NULL;
	}

	if(token == SEMI){
		match(SEMI);
		token = getToken();
		return NULL;
	}

	ExpType type = type_spec();
	if(type == Void){
		syntaxError("unexpected type spec -> ");
        printToken(token,tokenString);
        token = getToken();
		return NULL;
	}
	//保存tokenString
	static char *oldName;
	oldName = copyString(tokenString);
	
	match(ID);
	
	if(token == LP){
		printf("function begin\n");
		//函数说明
		match(LP);
		t = newDecNode(FunDefK);
		t->attr.name = oldName;
		t->level = level;
		printf("function name: %s\n", t->attr.name);
		t->type = type;
		
		level++;
		TreeNode * p = params();
		level--;
		
		t->child[0] = p;
		match(RP);
		TreeNode * s = comp_stmt();
		t->child[1] = s;
				
		return t;
	} else if(token == SEMI){
		printf("single var dec begin\n");
		//单个变量说明
		t = newDecNode(VarK);
		t->type = type;
		t->level = level;

		TreeNode * p;
		p = newExpNode(IdK);
		p->attr.name = oldName;
		p->type = type;
		p->level = level;

		printf("%s level : %d\n", oldName, level);
		
		t->child[0] = p;
		token = getToken();
		return t;
		
	} else if(token == COMMA){
		printf("muti var dec begin\n");
		//多个变量说明
		t = newDecNode(VarK);
		t->type = type;
		t->level = level;

		TreeNode * s = newExpNode(IdK);
		s->attr.name = oldName;
		s->type = type;
		s->level = level;

		t->child[0] = s;
		
	  	TreeNode * p = s;
	  	while (token!=SEMI)
	  	{ 
	  		TreeNode * q;
	    	match(COMMA);
			printf("tokenString:%s\n", tokenString);
	    	q = var();
	    	if (q!=NULL) {
	      		if (s==NULL) 
					s = p = q;
	      		else /* now p cannot be NULL either */
	      		{ 
	      			printf("p is not null!\n");
	      			p->sibling = q;
	        		p = q;
	      		}
	    	}
	  	}
		match(SEMI);
		return t;
	} else {
		//错误
		syntaxError("unexpected dec type spec -> ");
        printToken(token,tokenString);
        token = getToken();
		return NULL;
	}
  	return t;
}

TreeNode * var(void)
{
	printf("var begin\n");
	if(token == ID){
		//TreeNode * t = newDecNode(VarK);
		TreeNode * t = newExpNode(IdK);
		//type
		t->type = saveType;
		t->level = level;
	    t->attr.name = copyString(tokenString);
		
		if(strcmp(tokenString, "y") == 0)
			printf("y level : %d\n", level);
		
		token = getToken();
		return t;
	} else {
		syntaxError("unexpected var name -> ");
        printToken(token,tokenString);
		token = getToken();
		return NULL;
	}
}

ExpType type_spec(void){
	//token为ID
	ExpType	type;
  	switch (token) {
    	case NUM : 
			type = Integer;
			break;
    	case DNUM : 
			type = Double;
			break;
		case SCHAR : 
			type = Char;
			break;
    	default : 
			type = Void;
            break;
  	} /* end case */
	saveType = type;
	token = getToken();
  	return type;
}

TreeNode * params(void)
{
	printf("params begin\n");
	TreeNode * t = param_list();
	return t;
}

TreeNode * param_list(void){
	printf("param_list begin\n");
	TreeNode * t = param();
	TreeNode * p = t;
	while ((token!=ENDFILE) && (token!=END) && (token!=RP))
  	{ 
  		TreeNode * q;
    	match(COMMA);
    	q = param();
    	if (q!=NULL) {
      		if (t==NULL) 
				t = p = q;
      		else /* now p cannot be NULL either */
      		{ 
      			p->sibling = q;
        		p = q;
      		}
    	}
  	}
 	return t;
}

TreeNode * param(void){
	printf("param begin\n");
	ExpType type = type_spec();
	if(type == Void){
		syntaxError("param unexpected type spec -> ");
        printToken(token,tokenString);
        token = getToken();
		return NULL;
	}
	//保存tokenString
	char *oldName = copyString(tokenString);
	
	match(ID);
	TreeNode * t = newDecNode(ParamK);
	t->type = type;
	t->level = level;
	t->attr.name = oldName;
	return t;
}

TreeNode * comp_stmt(void){
	printf("comp_stmt begin\n");
	match(LFP);
	level++;
	
	TreeNode * t = newDecNode(CompK);
	TreeNode * p = local_dec();
	TreeNode * q = stmt_list();
	t->child[0] = p;
	t->child[1] = q;

	level--;
	match(RFP);	
	//if(token == SEMI)
	//	match(SEMI);
	return t;
}

TreeNode * local_dec(void){
	printf("local_dec begin\n");
	if((token != NUM)&&(token != FNUM)&&(token != SCHAR))
		return NULL;
	
	TreeNode * t = var_dec();
  	TreeNode * p = t;
  	while ((token!=ENDFILE) && (token!=END))
  	{ 
  		if((token != NUM)&&(token != FNUM)&&(token != SCHAR))
			return t;
			
  		TreeNode * q;
    	match(COMMA);
    	q = var_dec();
    	if (q!=NULL) {
      		if (t==NULL) 
				t = p = q;
      		else /* now p cannot be NULL either */
      		{ 
      			p->sibling = q;
        		p = q;
      		}
    	}
  	}
 	return t;
}

TreeNode * var_dec(void){
	printf("var_dec begin\n");
	ExpType type = type_spec();
	if(type == Void){
		syntaxError("param unexpected type spec -> ");
        printToken(token,tokenString);
        token = getToken();
		return NULL;
	}
	TreeNode * t = newDecNode(VarK);
	t->type = type;
	t->level = level;

	TreeNode * s = var();
	t->child[0] = s;
	TreeNode * p = s;
	
	while ((token!=ENDFILE) && (token!=END)&&(token != SEMI))
  	{ 
  		TreeNode * q;
    	match(COMMA);
    	q = var();
    	if (q!=NULL) {
      		if (s==NULL) 
				s = p = q;
      		else /* now p cannot be NULL either */
      		{ 
      			p->sibling = q;
        		p = q;
      		}
    	}
  	}
	match(SEMI);
	return t;
}


TreeNode * stmt_list(void)
{ 
	printf("stmt_list begin\n");
	TreeNode * t = stmt();
  	TreeNode * p = t;
  	while ((token!=ENDFILE) && (token!=END) && (token!=RFP))
  	{ 
  		TreeNode * q;
    	match(SEMI);
    	q = stmt();
    	if (q!=NULL) {
      		if (t==NULL) 
				t = p = q;
      		else /* now p cannot be NULL either */
      		{ 
      			p->sibling = q;
        		p = q;
      		}
    	}
  	}
 	return t;
}

TreeNode * stmt(void)
{
	printf("stmt begin\n");
	TreeNode * t = NULL;
  	switch (token) {
    	case IF : 
			t = if_stmt(); 
			break;
    	case ID : 
			t = assign_stmt(); 
			break;
    	case WHILE : 
			t = while_stmt(); 
			break;
		case LFP:
			t = comp_stmt();
			break;
		case RETURN:
			t = return_stmt();
			break;
		case RFP:
			break;
    	default : 
			syntaxError("unexpected token -> ");
            printToken(token,tokenString);
            token = getToken();
            break;
  	} /* end case */
  	return t;
}

TreeNode * return_stmt(void)
{
	printf("return_stmt begin\n");
	match(RETURN);
	TreeNode * t;
	if(token == SEMI){
		t = newStmtNode(ReturnK);
		t->child[0] = NULL;
		return t;
	} else {
		t = newStmtNode(ReturnK);
		TreeNode * p = exp();
		t->child[0] = p;
		match(SEMI);
		return t;
	}
}

TreeNode * if_stmt(void)
{
	TreeNode * t = newStmtNode(IfK);
  	match(IF);
  	if (t!=NULL) 
		t->child[0] = exp();
	t->child[1] = stmt_list();
  	if (token==ELSE) {
    	match(ELSE);
    	if (t!=NULL) 
			t->child[2] = stmt_list();
  	}
  	return t;
}

TreeNode * while_stmt(void)
{
	printf("while_stmt begin\n");
	TreeNode * t = newStmtNode(WhileK);
  	match(WHILE);
  	if (t!=NULL) {
		t->child[0] = exp();
		t->child[1] = stmt();
  	}
  	return t;
}

TreeNode * assign_stmt(void)
{
	printf("assign_stmt begin\n");
	TreeNode * t = newStmtNode(AssignK);
  	if ((t!=NULL) && (token==ID))
    	t->attr.name = copyString(tokenString);
  	match(ID);
  	match(ASSIGN);
  	if (t!=NULL) 
		t->child[0] = exp();
  	return t;
}

TreeNode * exp(void)
{
	printf("exp begin\n");
	TreeNode * t = simple_exp();
  	if ((token==LT)||(token==EQ)) {
    	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] = simple_exp();
 	}
  	return t;
}

TreeNode * simple_exp(void)
{
	printf("simple_exp begin\n");
	TreeNode * t = term();
  	while ((token==PLUS)||(token==SUB))
  	{
  		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)
{
	printf("term begin\n");
	TreeNode * t = factor();
  	while ((token==MUT)||(token==DIV))
  	{ 
  		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)
{
	printf("factor begin\n");
	TreeNode * t = NULL;
  	switch (token) {
    	case NUM :
	      	t = newExpNode(NumK);
	      	if ((t!=NULL) && (token==NUM))
	        	t->attr.val.i = atoi(tokenString);
	      	match(NUM);
	     	break;
    	case ID :
      		t = newExpNode(IdK);
      		if ((t!=NULL) && (token==ID))
        		t->attr.name = copyString(tokenString);
      		match(ID);
      		break;
    	case LP :
      		match(LP);
      		t = exp();
      		match(RP);
      		break;
    	default:
      		syntaxError("unexpected token -> ");
      		printToken(token,tokenString);
      		token = getToken();
      		break;
    	}
  	return t;
}

/****************************************/
/* the primary function of the parser   */
/****************************************/
/* Function parse returns the newly 
 * constructed syntax tree
 */
TreeNode * parse(void)
{
	TreeNode * t;
  	token = getToken();
  	//t = stmt_list();
  	t = program();
  	if (token!=ENDFILE)
    	syntaxError("Code ends before file\n");
  	return t;
}