parse.cpp

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

// Parse the source into a syntax tree
// 
// Written by bood, [e-mail], http://boodweb.126.com
// 2004-08-06

// Fixed a bug of the expression, now the negative sign can be
// dealt correctly
// bood, 2004-08-13

// BNF grammar of variable declaration is modified to support:
// 1. Continuous variable declaration in one statement
// 2. Variable initialization (but not for array)
// 3. Function declaration without definition
// 4. Fix stack overflow when parsing 'factor -> (expression)'
//
// Besides, structure of function definition is now changed to
// be more intuitive
//
// bood, 2005-01-22

// Bug Fix:
// Fix the empty statement bug in `stmt_list`
//
// bood, 2005-05-05

#pragma warning(disable:4786)

#include <list>
#include "global.h"
#include "scan.h"
#include "util.h"
#include "parse.h"

using namespace std;

TreeNode *declar_list();
TreeNode *declar();
TreeNode *function();
TreeNode *var_declar();
TreeNode *init_declarator();
TreeNode *params_type();
TreeNode *param_type_list();
TreeNode *param_type();
TreeNode *params();
TreeNode *param_list();
TreeNode *param();
TreeNode *compound_stmt();
TreeNode *local_declar();
TreeNode *stmt_list();
TreeNode *statement();
TreeNode *exp_stmt();
TreeNode *select_stmt();
TreeNode *while_stmt();
TreeNode *return_stmt();
TreeNode *exp();
TreeNode *simple_exp();
TreeNode *additive_exp();
TreeNode *term();
TreeNode *factor();
TreeNode *assign_exp();
TreeNode *call();
TreeNode *arg_list();
TreeNode *var();

void match(TokenType expected)
{
    if(bParseError)
        ParseError("Parse error, compilation stopped", lineno);
	if(token==expected) token=GetToken();
	else {
		ParseError(GetTokenString(expected)+" expected",lineno);
	}
}
//
// declaration-list → declaration-list declaration
//                     | declaration
//
// Declaration list is arranged in this way:  
/*
+----------+   +----------+   
| declar 1 |-->| declar 2 |-->...
+----------+   +----------+   
*/
TreeNode *declar_list()
{
	TreeNode *p=declar(),*q=p;
	while(token!=ENDFILE){
		q->pNext=declar();
		q=q->pNext;
	}
	return p;
}

//
// declaration → var-declaration | func-declaration | func-definition
//
// In nodes of declaration, TreeNode::kind=DECLAR, and different
// declarations are distinguished by TreeNode::childkind.declarK
//
// For var declaration, the following structure is used
/*
     +--------------+
     | v-declarlist | (VAR_DECLAR_LIST)
     +--------------+
             |   
  +----------------------+
  | init_declarator_list |
  +----------------------+
*/
TreeNode *declar()
{
	TreeNode *p = NULL;

	//forward looking to distinguish var-declare and func-declare
	list<TokenUnit>::iterator it = Backup();
	match(token);	//type specifier
	match(ID);		//ID
	if(token == LPAREN) {
		Restore(it);
		p=function();
	}
	else {
		p = NewNode(DECLAR);
		p->childkind.declarK = VAR_DECLAR_LIST;
		Restore(it);
		p->pChild[0] = var_declar();
	}
	return p;
}

// We parse function definition & declaration in one function
// So do params and params-type, see 'param' for detail
//
// func-definition → type-specifier ID (params) compound-stmt
// func-declaration → type-specifier ID ( params-type );
// type-specifier → int | void
/*
       +------------------+
       |     f-define     |
       +------------------+
        /        |       \
+-------+ +------------+  +-----------+
| param | | loc-declar |  | stmt-list |
+-------+ +------------+  +-----------+

       +------------------+
       |     f-declar     |
       +------------------+
               |       
        +-------------+  
        | params-list | 
        +-------------+
*/
TreeNode *function()
{
	TreeNode *p = NewNode(DECLAR);
    if(token==INT || token==VOID){
		p->tokenT = token;
		match(token);
		p->name=TokenString;
		match(ID);
		match(LPAREN);
		p->pChild[0]=params();
		match(RPAREN);

		// Notice that in definition parameters must have
		// a identifier, this will be checked later in analysis
		if(token==LBRACE) {	//func-definition
			p->childkind.declarK=FUNC_DEFINE;
			match(LBRACE);
			p->pChild[1]=local_declar();
			p->pChild[2]=stmt_list();
			match(RBRACE);
		}
		else if(token==SEMI) {	//func-declaration
			p->childkind.declarK=FUNC_DECLAR;
			match(SEMI);
		}
		else
			ParseError("; or { expected", lineno);
	}
	else ParseError("Type specifier expected", lineno);
	return p;
}

//
// var-declaration → type-specifier init-declarator-list
// init-declarator-list → init-declarator-list , init-declarator
//                       | init-declarator
// type-specifier → int | void
//
// init_declarator_list:
/*
+--------------+   +--------------+   
| var-declar 1 |-->| var-declar 2 |-->...
+--------------+   +--------------+   
*/
TreeNode *var_declar()
{
	TreeNode *p=NULL,*r=NULL;
	TokenType tokenT;
    if(token==INT || token==VOID){
		tokenT = token;
		match(token);
		r=p=init_declarator();
		p->tokenT = tokenT;
		while(token==COMMA) {
			match(COMMA);
			p->pNext = init_declarator();
			p=p->pNext;
			p->tokenT = tokenT;
		}
		match(SEMI);
	}
	else {
		ParseError("Declaration error",lineno);
	}
	return r;
}

// init-declarator → ID | ID=simple-expression | ID [ NUM ]
//
/*
      +------------+
      | var-declar |(VAR_DECLAR, name is var name)
      +------------+
            |   
  +----------------------+
  | assignment-expresion | 
  +----------------------+
  See function "assign_exp", but the array-sub-exp
  is always NULL, 'coz we do not support array
  initialization right now
*/
TreeNode * init_declarator()
{
	TreeNode *p=NewNode(DECLAR);
	p->name=TokenString;
	match(ID);
	if(token==ASSIGN) { // initialization while declaration
		p->childkind.declarK=VAR_DECLAR;
		match(token);
		p->pChild[0] = NewNode(EXP);
		p->pChild[0]->childkind.expK = ASSIGN_EXP;
		p->pChild[0]->name = p->name;
		p->pChild[0]->pChild[1] = simple_exp();
	}
	else if(token==LSQUAR) { // array declaration
		p->childkind.declarK=ARRAY_DECLAR;
		match(token);
		p->arraynum=atoi(TokenString.c_str());
		match(NUMBER);
		match(RSQUAR);
	}
	else p->childkind.declarK=VAR_DECLAR; // no initialization & not array
	return p;
}

//
// params → params-list | void
//
// If it's void then the pointer to params is set to NULL
TreeNode *params()
{
	TreeNode *p;
	if(token==VOID){
		p=NULL;
		match(token);
	}
	else{
		p=param_list();
	}
	return p;
}
//
// param-list → param-list , param | param
//
// This is the structure:
/*
+---------+   +---------+   
| param 1 |-->| param 2 |-->...
+---------+   +---------+   
*/
TreeNode *param_list()
{
	TreeNode *p=param(),*q=p;
	while(token==COMMA){
		match(COMMA);
		q->pNext=param();
		q=q->pNext;
	}
	return p;
}
// Here, we put the parsing of parameter-type and
// parameter together to make the program simple
//
// Therefor the parameter here may not have a
// corresponding identifier just for dealing with
// the func-declaration situation
//
// param → type-specifier ID | type-specifier ID []
//
TreeNode *param()
{
	TreeNode *p=NewNode(PARAM);
	if(token==INT || token==VOID)
	{
		p->tokenT=token;
		match(token);
		if(token==ID) {		// ID is optional in func-declaration
			p->name=TokenString;
			match(ID);
		}
		p->childkind.declarK=VAR_DECLAR;
        if(token==LSQUAR){	// array as parameter
			p->childkind.declarK=ARRAY_DECLAR;
			p->arraynum=0;
			match(token);
			match(RSQUAR);
		}
	}
	else bParseError=1;
    if(bParseError==1) {
        ParseError("Parameter declaration error",lineno);
    }
	return p;
}
//
// compound-stmt → {local-declarations statement-list}
//
// Structure:
/*
      +-----------+
      | comp-stmt |
      +-----------+
        /       \
+------------+  +-----------+
| loc-declar |  | stmt-list |
+------------+  +-----------+
*/
TreeNode *compound_stmt()
{
	TreeNode *p=NewNode(CSTMT);
	match(LBRACE);
	p->pChild[0]=local_declar();
	p->pChild[1]=stmt_list();
	match(RBRACE);
	return p;
}

//
// local-declarations → local-declarations var-declaration
//                       | empty
//
// The only different between local-declaration and general
// declaration is that the local one's cann't be function
// declaration
//
// Structure:
/*
+----------+   +----------+   
| declar 1 |-->| declar 2 |-->...
+----------+   +----------+   
*/
TreeNode *local_declar()
{
	TreeNode *p=NULL,*q=NULL,*r=NULL;
	while(token==INT || token==VOID){
		q = NewNode(DECLAR);
		q->childkind.declarK = VAR_DECLAR_LIST;
		q->pChild[0] = var_declar();
		if(r==NULL) r = q;
		else {p->pNext = q;p=q;}
		p=q;
	}
	return r;
}
//
// statement-list → statement-list statement | empty
// Structure:
/*
+--------+   +--------+   
| stmt 1 |-->| stmt 2 |-->...
+--------+   +--------+   
*/
TreeNode *stmt_list()
{
	TreeNode *p=NULL,*q=p;
	while(token!=RBRACE){
		if(p==NULL) {q=statement();p=q;}
		else {
			q->pNext=statement();

			//need a check here
			//make sure that it's not an empty statement
			//which has only an semicolon
			if(q->pNext!=NULL) q=q->pNext;
		}
	}
	return p;
}
//
// statement → expression-stmt | compound-stmt | selection-stmt