parse.cpp

一个c语言的编译器的源代码

//              | iteration-stmt | return-stmt
TreeNode *statement()
{
	TreeNode *p;
	switch(token)
	{
	case LBRACE:
		p=compound_stmt();
		break;
	case IF:
		p=select_stmt();
		break;
	case WHILE:
		p=while_stmt();
		break;
	case RETURN:
		p=return_stmt();
		break;
	default:
		p=exp_stmt();
		break;
	}
	return p;
}
//
// expression-stmt → expression; | ;
TreeNode *exp_stmt()
{
	TreeNode *p=NULL;
	if(token!=SEMI) p=exp();
	match(SEMI);
	return p;
}

//
// selection-stmt → if (expression) statement
//                   | if (expression) statement else statement
//
// Structure:
// Note! statement2 can be NULL
/*
      +-----------+
      |  if-else  |
      +-----------+
     /      |     \
+-----+ +-------+ +-------+
| exp | | stmt1 | | stmt2 |
+-----+ +-------+ +-------+
*/
TreeNode *select_stmt()
{
	TreeNode *p=NewNode(STMT);
	p->childkind.stmtK=IF_STMT;
	match(IF);
	match(LPAREN);
	p->pChild[0]=exp();
	match(RPAREN);
	p->pChild[1]=statement();
	if(token==ELSE){
		match(ELSE);
		p->pChild[2]=statement();
	}
	return p;
}

//
// iteration-stmt → while (expression) statement
//
// Structure:
/*
      +------------+
      | while-stmt |
      +------------+
        /       \
+------------+  +-----------+
| expression |  | statement |
+------------+  +-----------+
*/
TreeNode *while_stmt()
{
	TreeNode *p=NewNode(STMT);
	p->childkind.stmtK=WHILE_STMT;
	match(WHILE);
	match(LPAREN);
	p->pChild[0]=exp();
	match(RPAREN);
	p->pChild[1]=statement();
	return p;
}

//
// return-stmt → return; | return expression;
//
// Structure:
// Note! expression may be NULL
/*
      +--------+
      | return |
      +--------+
          | 
    +------------+
    | expression |
    +------------+
*/
TreeNode *return_stmt()
{
	TreeNode *p=NewNode(STMT);
	p->childkind.stmtK=RETURN_STMT;
	match(RETURN);
	if(token!=SEMI) p->pChild[0]=exp();
	match(SEMI);
	return p;
}

//
// expression → assign-expression | simple-expression
//
// Here, we need a forward look to determine which
// deduction should be used, so the Backup&Restore
// functions are introduced(see scan.h for detail).
//
// The reason is that both assign-exp and simple-exp
// can begin with a var:
// head(assign-exp) -> head(var)
// head(simple-exp) -> head(add-op) -> head(term)
//                  -> head(factor) -> head(var)
//
TreeNode *exp()
{
	TreeNode *p,*t;
	if(token==ID){
		list<TokenUnit>::iterator
			&it=Backup();
        //forward looking...
        //
        //memory leak here, did not release the
        //space for the possible subscript
		t=var();delete t;
        if(token==ASSIGN) { //assignment
			Restore(it);
			p=assign_exp();
        }
        else{ //simple-expresion
			Restore(it);
			p=simple_exp();
		}
	}
	else p=simple_exp();
	return p;
}
//
// simple-expression → additive-expression relop additive-expression
// relop → <= | < | > | >= | == | !=
//
// Structure:
/*
      +------------+
      | simple-exp |(key=RELOP)
      +------------+
        /       \
+------------+  +-----------+
|  add-exp   |  |  add-exp  |
+------------+  +-----------+
*/
TreeNode *simple_exp()
{
	TreeNode *p,*q=additive_exp();
	if(token==LT || token==LTEQ || token==GT ||
		token== GTEQ || token==NEQ || token==EQ)
	{
		p=NewNode(RELOP);
		p->tokenT=token;
		p->name=TokenString;
		match(token);
		p->pChild[0]=q;
		p->pChild[1]=additive_exp();
	}
	else p=q;
	return p;
}
//
// additive-expression → additive-expression addop term
//                        | term
// addop → + | -
//
// Structure:
/*
      +------------+
      |   add-exp  |(key=OP)
      +------------+
        /       \
+------------+  +-----------+
|    term    |  |    term   |
+------------+  +-----------+
*/
TreeNode *additive_exp()
{
	TreeNode *p=term();
	while(token==PLUS || token==MINUS)
	{
		TreeNode *q=NewNode(OP);
		if(p!=NULL){
			q->tokenT=token;
			q->name=TokenString;
			match(token);
			q->pChild[0]=p;
			p=q;
			p->pChild[1]=term();
		}
	}
	return p;
}
//
// term → term mulop factor | factor
// mulop → * | /
//
// Structure:
/*
      +------------+
      |    term    |(key=OP)
      +------------+
        /       \
+------------+  +-----------+
|   factor   |  |   factor  |
+------------+  +-----------+
*/
TreeNode *term()
{
	TreeNode *p=factor();
	while(token==MUL || token==DIV)
	{
		TreeNode *q=NewNode(OP);
		if(p!=NULL){
			q->tokenT=token;
			q->name=TokenString;
			match(token);
			q->pChild[0]=p;
			p=q;
			p->pChild[1]=factor();
		}
	}
	return p;
}
//
// factor → (expression) | var | call | NUM | - factor
TreeNode *factor()
{
	TreeNode *p;
	list<TokenUnit>::iterator it;
    int flag = 1;
	switch(token)
	{
	case LPAREN:
		match(LPAREN);
		p=exp();
		match(RPAREN);
		break;
	case NUMBER:
		p=NewNode(NUM);
		p->name=TokenString;
		match(NUMBER);
		break;
	case ID:
        // Forward looking again...
		it=Backup();

        //another possible memory leak
        p=var();
		delete p;
		if(token==LPAREN) {
			Restore(it);
			p=call();
        }
		else{
			Restore(it);
			p=var();
		}
		break;

    // Negative sign is implemented by an expression that subtrated
    // by ZERO ...
    case MINUS:
        while(token==MINUS) {match(MINUS);flag=!flag;}
        p = NewNode(OP);
        p->tokenT = MINUS;
        p->name = "-";
        p->pChild[0] = NewNode(NUM);
        p->pChild[0]->name = "0";
        p->pChild[1] = factor();
        break;
	default:
		bParseError=1;
	}
    if(bParseError==1) {
        ParseError("Factor error",lineno);
    }
	return p;
}
//
// assign-expression → var=expression
//
// Structure:
// Note! The array-subscript may be NULL
/*
      +------------+
      |    assign  |(TokenName=var-name)
      +------------+
        /         \
+-------------+  +-----------+
|array-sub-exp|  |    exp    |
+-------------+  +-----------+
*/
TreeNode *assign_exp()
{
	TreeNode *p=var();
	p->kind=EXP;
	p->childkind.expK=ASSIGN_EXP;
	match(ASSIGN);
	p->pChild[1]=exp();
	return p;
}

//
// call → ID(arg-list)
//
// Structure:
// Note! expression may be NULL
/*
      +--------+
      |  call  |
      +--------+
          | 
    +------------+
    |  arg-list  |
    +------------+
*/
TreeNode *call()
{
	TreeNode *p=NewNode(CALL);
	p->name=TokenString;
	match(ID);
	match(LPAREN);
	p->pChild[0]=arg_list();
	match(RPAREN);
	return p;
}
//
// arg-list → arg-list,expression | expression
//
// Structure:
/*
+-------+   +-------+   
| arg 1 |-->| arg 2 |-->...
+-------+   +-------+   
*/
TreeNode *arg_list()
{
	if(token==RPAREN) return NULL;
	TreeNode *p=exp(),*q=p;
	p->pPrev=NULL;
	while(token==COMMA)
	{
		match(COMMA);
		q->pNext=exp();
		q->pNext->pPrev=q;
		q=q->pNext;
	}
	return p;
}
//
// var → ID | ID[expression]
//
// Structure:
/*
      +--------+
      |   var  |
      +--------+
          | 
   +-------------+
   |subscript-exp|
   +-------------+
*/
TreeNode *var()
{
	TreeNode *p=NewNode(REFER);
	p->name=TokenString;
	match(ID);
	if(token==LSQUAR){
		match(token);
		p->pChild[0]=exp();
		match(RSQUAR);
	}
	return p;
}

//
// program → declaration-list
TreeNode *parse()
{
	token=GetToken();
	return declar_list();
}