parse.c

根据编译器的基本原理

/****************************************************/
/* 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; /* holds current token */

/* function prototypes for recursive calls */
static TreeNode * program(void);
static TreeNode * declarations(void);
static TreeNode * varlist(ExpType dtype);
static TreeNode * decl(void);
static TreeNode * stmt_sequence(void);
static TreeNode * statement(void);
static TreeNode * while_stmt(void);
static TreeNode * if_stmt(void);
static TreeNode * repeat_stmt(void);
static TreeNode * assign_stmt(void);
static TreeNode * read_stmt(void);
static TreeNode * write_stmt(void);
static TreeNode * exp(void);
static TreeNode * boolexp(void);
static TreeNode * expression(void);
static TreeNode * exp1(void);
static TreeNode * exp2(void);
static TreeNode * aexp(void);
static TreeNode * term(void);
static TreeNode * factor(void);
static TreeNode * bexp(void);
static TreeNode * bterm(void);
static TreeNode * bfactor(void);
static TreeNode * b(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 * program(void)
{
	TreeNode*t=declarations();
	TreeNode*q=stmt_sequence();
	TreeNode*p=NULL;
	if(t==NULL)return q;
	else
	{
		for(p=t;p->sibling!=NULL;)p=p->sibling;
		p->sibling=q;
		return t;
	}
}

TreeNode * declarations(void)
{
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	TreeNode*q=NULL;
	while(token==INT||token==BOOL||token==STRING)
	{
		switch(token)
		{
		case INT:
			p=newStmtNode(IntK);
			p->type=Integer;
			match(INT);
			break;
			//p=newExpNode(IdK);
			//match(ID);
		case BOOL:
			p=newStmtNode(BoolK);
			p->type=Boolean;
			match(BOOL);
			break;
		case STRING:
			p=newStmtNode(StringK);
			p->type=String;
			match(STRING);
			break;
		default:
			syntaxError("unexpected token -> ");
			printToken(token,tokenString);
			token = getToken();
			break;
		}
		p->child[0]=varlist(p->type);
		match(SEMI);
		if(t==NULL)
		{
			t=p;
		}
		else 
		{
			q->sibling=p;
		}
		q=p;
	}
	return t;
}

TreeNode * varlist(ExpType dtype)
{
	TreeNode*t=newExpNode(IdK);
	TreeNode*p=NULL;
	TreeNode*q=NULL;
	if(t!=NULL)
	{
		t->attr.name=copyString(tokenString);
		t->type=dtype;
	}
	match(ID);
	q=t;
	while(token==COMMA)
	{
		match(COMMA);
		p=newExpNode(IdK);
		if(p!=NULL)
		{
			p->attr.name=copyString(tokenString);
			t->type=dtype;
		}
		match(ID);
		q->sibling=p;
		q=p;
	}
	return t;
}

TreeNode * stmt_sequence(void)
{ 
	TreeNode * t = statement();
	TreeNode * p = t;
	while ((token!=ENDFILE) && (token!=END) && (token!=ELSE) && (token!=UNTIL) && (token!=WHILE))
	{ 
		TreeNode * q;
		match(SEMI);
		q = statement();
		if (q!=NULL) 
		{
			if (t==NULL) t = p = q;
			else /* now p cannot be NULL either */
			{ 
				p->sibling = q;
				p = q;
			}
		}
	}
	return t;
}

TreeNode * statement(void)
{ 
	TreeNode * t = NULL;
	switch (token) 
	{
    case IF:		t = if_stmt(); break;
    case REPEAT:	t = repeat_stmt(); break;
    case ID:		t = assign_stmt(); break;
    case READ:		t = read_stmt(); break;
    case WRITE:		t = write_stmt(); break;
	case DO:		t = while_stmt();break;
    default :		syntaxError("unexpected token -> ");
					printToken(token,tokenString);
					token = getToken();
					break;
	} /* end case */
	return t;
}

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

TreeNode * while_stmt(void)
{
	TreeNode * t = newStmtNode(WhileK);
	match(DO);
	if(t!=NULL) t->child[0] = stmt_sequence();
	match(WHILE);
	if(t!=NULL) t->child[1] = exp();
	return t;
}

TreeNode * repeat_stmt(void)
{ 
	TreeNode * t = newStmtNode(RepeatK);
	match(REPEAT);
	if (t!=NULL) t->child[0] = stmt_sequence();
	match(UNTIL);
	if (t!=NULL) t->child[1] = exp();
	return t;
}

TreeNode * assign_stmt(void)
{ 
	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 * read_stmt(void)
{ 
	TreeNode * t = newStmtNode(ReadK);
	match(READ);
	if ((t!=NULL) && (token==ID))
		t->attr.name = copyString(tokenString);
	match(ID);
	return t;
}

TreeNode * write_stmt(void)
{ 
	TreeNode * t = newStmtNode(WriteK);
	match(WRITE);
	if (t!=NULL) t->child[0] = exp();
	return t;
}

TreeNode * exp(void)
{ 
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	TreeNode*q=NULL;
	switch(token)
	{
	case NOT:
	case TR:
	case FAL:	t=boolexp();break;
	case ID:
		t=newExpNode(IdK);
		if(t!=NULL)
			t->attr.name=copyString(tokenString);
		match(ID);
		p=expression();
		if(p!=NULL)
		{
			for(q=p;q->child[0]!=NULL;)q=q->child[0];
			q->child[0]=t;
			t=p;
		}
		break;
	case NUM:
		t=newExpNode(ConstK);
		if(t!=NULL)
			t->attr.val=atoi(tokenString);
		match(NUM);
		p=expression();
		if(p!=NULL)
		{
			for(q=p;q->child[0]!=NULL;)q=q->child[0];
			q->child[0]=t;
			t=p;
		}
		break;
	case LPAREN:
		match(LPAREN);
		t=exp();
		match(RPAREN);
		p=expression();
		if(p!=NULL)
		{
			for(q=p;q->child[0]!=NULL;)q=q->child[0];
			q->child[0]=t;
			t=p;
		}
		break;
	case STR:
		t=newExpNode(StrK);
		t->attr.str=copyString(tokenString);
		match(STR);
		break;
	default:
		syntaxError("unexpected token -> ");
		printToken(token,tokenString);
		token = getToken();
		break;
	}
	return t;
}

TreeNode * boolexp(void)
{
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	switch(token)
	{
	case TR:
		t=newExpNode(BK);
		t->attr.val=TRUE;
		match(TR);
		break;
	case FAL:
		t=newExpNode(BK);
		t->attr.val=FALSE;
		match(FAL);
		break;
	case NOT:
		t=newExpNode(OpK);
		t->attr.op=NOT;
		match(NOT);
		t->child[0]=bfactor();
		break;
	default:
		syntaxError("unexpected token -> ");
		printToken(token,tokenString);
		token = getToken();
		break;
	}
	while(token==AND)
	{
		p=newExpNode(OpK);
		if (p!=NULL) 
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
			match(AND);
			p->child[1] = bfactor();
		}
	}
	while(token==OR)
	{
		p=newExpNode(OpK);
		if (p!=NULL) 
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
			match(OR);
			p->child[1] = bterm();
		}
	}
	return t;
}

TreeNode * expression(void)
{
	TreeNode*t=NULL;
	if(token==PLUS||token==MINUS||token==TIMES||token==OVER||token==LT
		||token==GT||token==EQ||token==NLT||token==NGT)
		t=exp1();
	else if(token==AND||token==OR)
		t=exp2();
	return t;
}

TreeNode * exp1(void)
{
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	TreeNode*q=NULL;
	TreeNode*m=NULL;
	while(token==TIMES||token==OVER)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=token;
		match(token);
		t->child[1]=factor();
		p=t;
	}
	while(token==PLUS||token==MINUS)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=token;
		match(token);
		t->child[1]=term();
		p=t;
	}
	if(token==LT||token==GT||token==EQ||token==NLT||token==NGT)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=token;
		match(token);
		t->child[1]=aexp();
		if(token==AND||token==OR)
		{
			p=exp2();
			if(p!=NULL)
			{
				for(q=p;q->child[0]!=NULL;)q=q->child[0];
				q->child[0]=t;
				t=q;
			}
		}
	}
	return t;
}
TreeNode * exp2(void)
{
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	while(token==AND)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=AND;
		match(AND);
		t->child[1]=bfactor();
		p=t;
	}
	while(token==OR)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=OR;
		match(OR);
		t->child[1]=bterm();
		p=t;
	}
	return t;
}
TreeNode * aexp(void)
{
	TreeNode*t=term();
	TreeNode*p=NULL;
	while(token==PLUS||token==MINUS)
	{
		p=newExpNode(OpK);
		p->child[0]=t;
		p->attr.op=token;
		match(token);
		p->child[1]=term();
		t=p;
	}
	return t;
}
TreeNode * term(void)
{
	TreeNode*t=factor();
	TreeNode*p=NULL;
	while(token==TIMES||token==OVER)
	{
		p=newExpNode(OpK);
		p->child[0]=t;
		p->attr.op=token;
		match(token);
		p->child[1]=factor();
		t=p;
	}
	return t;
}
TreeNode * factor(void)
{ 
	TreeNode * t = NULL;
	switch (token) 
	{
	case NUM :
		t = newExpNode(ConstK);
		if ((t!=NULL) && (token==NUM))
			t->attr.val = atoi(tokenString);
		match(NUM);
		break;
    case ID :
		t = newExpNode(IdK);
		if ((t!=NULL) && (token==ID))
			t->attr.name = copyString(tokenString);
		match(ID);
		break;
    case LPAREN :
		match(LPAREN);
		t = aexp();
		match(RPAREN);
		break;
    default:
		syntaxError("unexpected token -> ");
		printToken(token,tokenString);
		token = getToken();
		break;
	}
	return t;
}
TreeNode * bexp(void)
{
	TreeNode*t=bterm();
	TreeNode*p=NULL;
	while(token==OR)
	{
		p=newExpNode(OpK);
		p->child[0]=t;
		p->attr.op=OR;
		match(OR);
		p->child[1]=bterm();
		t=p;
	}
	return t;
}
TreeNode * bterm(void)
{
	TreeNode*t=bfactor();
	TreeNode*p=NULL;
	while(token==AND)
	{
		p=newExpNode(OpK);
		p->child[0]=t;
		p->attr.op=AND;
		match(AND);
		p->child[1]=bfactor();
		t=p;
	}
	return t;
}
TreeNode * bfactor(void)
{
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	TreeNode*q=NULL;
	switch (token) 
	{
	case NUM :
		t = newExpNode(ConstK);
		if ((t!=NULL) && (token==NUM))
			t->attr.val = atoi(tokenString);
		match(NUM);
		p=b();
		if(p!=NULL)
		{
			for(q=p;q->child[0]!=NULL;)q=q->child[0];
			q->child[0]=t;
			t=p;
		}
		break;
    case ID :
		t = newExpNode(IdK);
		if ((t!=NULL) && (token==ID))
			t->attr.name = copyString(tokenString);
		match(ID);
		p=b();
		if(p!=NULL)
		{
			for(q=p;q->child[0]!=NULL;)q=q->child[0];
			q->child[0]=t;
			t=p;
		}
		break;
    case LPAREN:
		match(LPAREN);
		t = aexp();
		match(RPAREN);
		p=b();
		if(p!=NULL)
		{
			for(q=p;q->child[0]!=NULL;)q=q->child[0];
			q->child[0]=t;
			t=p;
		}
		break;
	case TR:
		t=newExpNode(BK);
		t->attr.val=TRUE;
		match(TR);
		break;
	case FAL:
		t=newExpNode(BK);
		t->attr.val=FALSE;
		match(FAL);
		break;
	case NOT:
		t=newExpNode(OpK);
		t->attr.op=NOT;
		match(NOT);
		t->child[0]=bfactor();
		break;
    default:
		syntaxError("unexpected token -> ");
		printToken(token,tokenString);
		token = getToken();
		break;
	}
	return t;
}
TreeNode * b(void)
{
	TreeNode*t=NULL;
	TreeNode*p=NULL;
	TreeNode*q=NULL;
	TreeNode*m=NULL;
	while(token==TIMES||token==OVER)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=token;
		match(token);
		t->child[1]=factor();
		p=t;
	}
	while(token==PLUS||token==MINUS)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=token;
		match(token);
		t->child[1]=term();
		p=t;
	}
	if(token==LT||token==GT||token==EQ||token==NLT||token==NGT)
	{
		t=newExpNode(OpK);
		t->child[0]=p;
		t->attr.op=token;
		match(token);
		t->child[1]=aexp();
	}
	return t;
}


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