parser.cpp

一个编译器

/**************************************************
* file: Parser.cpp
* date: 2006-04-12
* author: wuzuyang
* describe: parser
**************************************************/

//#define TRACE_DEBUG

#ifdef TRACE_DEBUG
	#define TRACE(FUNCTION) printf("%-16s token = %s\n", FUNCTION, currentToken.name);
#else
	#define TRACE(FUNCTION)
#endif


#include "Parser.h"
#include <stdio.h>
#include <stdlib.h>

Parser::Parser(char* sourcefile){
	lexer = new Lexer(sourcefile);
}

Parser::Parser(){
}

Parser::~Parser(){
	delete lexer;
}

void Parser::setLexer(Lexer *srclexer){
	lexer = srclexer;
}


Token Parser::nextToken(){
	currentToken = lexer->nextToken();
	return currentToken;
}

void Parser::reset(){
	lexer->reset();
}

void Parser::printError(const char *error){	// private method
	printf("%s when token = '%s'\n", error, currentToken.name);
}

void Parser::printError(){	// public method
	if(lexer->isReady())
		printf("\n*** ERROR BEFORE: ***\n%s", lexer->getSrc()+lexer->getIndex());
	else
		printf("Lexer is not ready!\n");
}

/*==================================================================*/

SyntaxTree* Parser::parse(){
	SyntaxTree* tree = NULL;
	if(lexer->isReady()){
		currentToken = lexer->nextToken();
		tree = Statement();
	}else{
		printf("no ready\n");
	}
	return tree;
}


SyntaxTree* Parser::Statement(){
	TRACE("in Statement();");
	
	SyntaxTree *tree = NULL;
	
	switch(currentToken.type){
		case LEXER_DONE:
			tree = new SyntaxTree(LEXER_DONE);
			break;
		case ID:
			this->nextToken();
			tree = Assign();
			if(tree != NULL){
				tree->addLeft(ID);
			}
			break;
		case WHILE:
			this->nextToken();
			tree = While();
			break;
		case BEGIN:
			this->nextToken();
			tree = Block();
			if(currentToken.type != END){
				tree =  NULL;
				this->printError("ERROR! begin without end");
			}
			//this->nextToken();
			this->currentToken.type = SEMI;
			break;
		case IF:
			this->nextToken();
			tree = Condition();
			break;
		default:
			tree = NULL;
			break;
	}
	
	TRACE("out Statement();");
	return tree;
}


SyntaxTree* Parser::Assign(){
	TRACE("in Assign();");
	
	SyntaxTree *tree = NULL;

	if(currentToken.type == ASSIGN){
		this->nextToken();
		SyntaxTree *temptree = Expression();
		
		if(temptree != NULL){
			tree = new SyntaxTree(ASSIGN);
			tree->addRight(temptree);
		}
	}else{
		this->printError("ERROR! Assignment statement expects '=';");
		return NULL;
	}
	
	TRACE("out Assign();");
	return tree;
}


SyntaxTree* Parser::Expression(){
	TRACE("in Expression();");

	SyntaxTree *temp = NULL;
	SyntaxTree *tree = T();

	if(tree == NULL){
		return NULL;
	}
	
	while(currentToken.type == PLUS || currentToken.type == MINUS){
		temp = new SyntaxTree(currentToken.type);
		temp->addLeft(tree);
		tree = temp;
		this->nextToken();
		
		temp = T();
		if(temp != NULL){
			tree->addRight(temp);
		}else{
			this->printError("ERROR! Behind '+';");
			return NULL;
		}
	}
	
	return tree;
}


SyntaxTree* Parser::T(){
	SyntaxTree *temp = NULL;
	SyntaxTree *tree = F();
	
	if(tree == NULL){
		return NULL;
	}
	
	while(currentToken.type == MUL || currentToken.type == DIV){
		temp = new SyntaxTree(currentToken.type);
		temp->addLeft(tree);
		tree = temp;
		this->nextToken();
		
		temp = F();
		if(temp != NULL){
			tree->addRight(temp);
		}else{
			this->printError("ERROR in T();");
			return NULL;
		}
	}
	
	return tree;
}


SyntaxTree* Parser::F(){
	SyntaxTree *tree = NULL;
	
	if(currentToken.type == ID){
		tree = new SyntaxTree(ID);
	}else if(currentToken.type == NUM){
		tree = new SyntaxTree(NUM, atoi(currentToken.name));
	}else{
		this->printError("ERROR! in F();");
	}
	
	this->nextToken();
	
	return tree;
}

/*==================================================================*/

SyntaxTree* Parser::Boolean(){
	TRACE("in Boolean();");

	SyntaxTree *temp = NULL;
	SyntaxTree *tree = T2();

	if(tree == NULL){
		return NULL;
	}
	
	while(currentToken.type == OR){
		temp = new SyntaxTree(OR);
		temp->addLeft(tree);
		tree = temp;
		this->nextToken();
		
		temp = T2();
		if(temp != NULL){
			tree->addRight(temp);
		}else{
			this->printError("ERROR! behind OR;");
			return NULL;
		}
	}
	
	TRACE("out Boolean();");
	return tree;
}


SyntaxTree* Parser::T2(){
	SyntaxTree *temp = NULL;
	SyntaxTree *tree = F2();

	if(tree == NULL){
		return NULL;
	}
	
	while(currentToken.type == AND){
		temp = new SyntaxTree(AND);
		temp->addLeft(tree);
		tree = temp;
		this->nextToken();
		
		temp = F2();
		if(temp != NULL){
			tree->addRight(temp);
		}else{
			this->printError("ERROR! behind AND;");
			return NULL;
		}
	}
	
	return tree;
}


SyntaxTree* Parser::F2(){
	SyntaxTree *temp = NULL;
	SyntaxTree *tree = Expression();
	
	if(tree == NULL){
		return NULL;
	}
	
	switch(currentToken.type){
		case LT:
			temp = new SyntaxTree(LT);
			break;
		case GT:
			temp = new SyntaxTree(GT);
			break;
		case EQ:
			temp = new SyntaxTree(EQ);
			break;
		default :
			break;
	}
	
	if(temp != NULL){
		this->nextToken();
		temp->addLeft(tree);
		tree = temp;
		temp = Expression();
		if(temp != NULL){
			tree->addRight(temp);
		}else{
			this->printError("ERROR! Relation Operator needs Expression behind;");
			return NULL;
		}
	}

	return tree;
}

/*==================================================================*/

SyntaxTree* Parser::While(){
	TRACE("in While();");

	SyntaxTree *tree = new SyntaxTree(WHILE);
	SyntaxTree *temp = Boolean();
	
	if(temp == NULL){
		this->printError("ERROR! in While(); Condition NULL;");
		return NULL;
	}
	tree->addLeft(temp);
	
	if(currentToken.type != DO){
		this->printError("ERROR! in While(); token.type!=DO;");
		return NULL;
	}
	this->nextToken();
	temp = Statement();

	if(temp == NULL){
		this->printError("ERROR! in While(); DO empty;");
		return NULL;
	}
	tree->addRight(temp);
	
	TRACE("out While();");
	return tree;
}


/*==================================================================*/

SyntaxTree* Parser::Begin(){
	return Block();
}

/*
	L = S(;S)* | <empsilon>
*/
SyntaxTree* Parser::Block(){
	TRACE("in Block();");

	SyntaxTree *tree = Statement();
	SyntaxTree *temp = new SyntaxTree(BEGIN);
	
	if(tree == NULL){
		//this->printError("WARNNING! Don't accept empty block.");
		return NULL;
		/*
		while(currentToken.type == SEMI){
			this->nextToken();
		}
		return new SyntaxTree(BEGIN);
		*/
	}
	temp->addLeft(tree);
	tree = temp;
	
//	temp = L2();

	while(currentToken.type == SEMI){
		this->nextToken();
	}
	temp = Block();

	if(temp != NULL){	// it couldn't be
		if(temp->getLeft() != NULL)
			tree->addRight(temp);
	}
	
	TRACE("out Block();");

	if(tree == NULL)
		return NULL;
	if(tree->getRight() == NULL)
		return tree->getLeft();
	else
		return tree;
}


/*==================================================================*/


SyntaxTree* Parser::Condition(){
	TRACE("in Condition();");
	
	SyntaxTree *tree = new SyntaxTree(IF);
	SyntaxTree *temp = Boolean();
	SyntaxTree *temp2 = NULL;
	
	if(temp == NULL){
		this->printError("ERROR! if without a boolean statement.");
		return NULL;
	}
	tree->addLeft(temp);
	
	if(currentToken.type != THEN){
		this->printError("ERROR! if without then.");
		return NULL;
	}
	this->nextToken();
	temp = Statement();
	
	if(temp == NULL){
		this->printError("ERROR! then without a statement.");
		return NULL;
	}
	
	temp2 = new SyntaxTree(THEN);
	temp2->addLeft(temp);
	
	//temp2 = temp;
	
	this->nextToken();
	if(currentToken.type == ELSE){
		TRACE("ELSE");
		this->nextToken();
		//temp = new SyntaxTree(BEGIN);
		//temp->addLeft(temp2);
		//temp2 = temp;
		
		temp = Statement();
		if(temp == NULL){
			this->printError("ERROR! else without a statement.");
			return NULL;
		}
		temp2->addRight(temp);
	}
	
	tree->addRight(temp2);
	
	TRACE("out Condition();");
	return tree;
}