yufa.cpp

对已给语言文法

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

#include <string.h>

#ifndef COMMON_H
#define COMMON_H

typedef enum{
	ERROR, UNKNOWN,
	LEXER_DONE,	// success!
	IF, THEN, ELSE, WHILE, DO, BEGIN, END,	//9
	ID, NUM,	//11
	AND, OR,
	LT, LE, GT, GE, EQ,	//18
	ASSIGN, PLUS, MINUS, MUL, DIV,	//23
	LP, RP, SEMI
}TokenType;


typedef struct{
	TokenType type;
	char *name;
}Token;


typedef enum{
	INERROR,
	START,
	DONE,
	INID,
	INNUM,
	INLE,	// LT & LE
	INGE,	// GT & GE
	INEQ,	// EQ & ASSIGN
	INCOMMENT
}ScannerState;


typedef enum{
	ST_ERROR,
	ST_NORMAL,	// undefined, but not error
	ST_EXP,	// expression
	ST_IF, ST_THEN, ST_WHILE, ST_ASSIGN, ST_BEGIN
}StatementType;

#endif




class SyntaxTreeNode{
private:
	TokenType type;
	int value;	// identifiers will be given distinguish values.
	SyntaxTreeNode *left, *right, *child3;
	
public:
	SyntaxTreeNode();
	SyntaxTreeNode(TokenType t, int val);
	~SyntaxTreeNode();
	
	void setType(TokenType t);
	void setValue(int val);
	
	TokenType getType();
	int getValue();
	
	void addLeft(TokenType t, int val);
	// add the subtree n to this tree's left
	void addLeft(SyntaxTreeNode *n);
	
	void addRight(TokenType t, int val);
	// add the subtree n to this tree's right
	void addRight(SyntaxTreeNode *n);
	
	void addChild3(TokenType t, int val);
	// add the subtree n to this tree's child3
	void addChild3(SyntaxTreeNode *n);
	
	SyntaxTreeNode* getRootNode();
	
	SyntaxTreeNode* getLeft();
	SyntaxTreeNode* getRight();
	SyntaxTreeNode* getChild3();
	
	friend class SyntaxTree;
};

class SyntaxTree{
private:
	SyntaxTreeNode *root;
	void display(SyntaxTreeNode *n, int tabcount, FILE *fo=stdout);
	
public:
	SyntaxTree(TokenType t, int val=0);
	// set root node with n.
	SyntaxTree(SyntaxTreeNode *n);
	SyntaxTree(SyntaxTree *tree);
	SyntaxTree();	// with root.type = ERROR
	~SyntaxTree();
	
	void display(FILE *fo=stdout);
	
	void setRootNode();
	void setRootNode(TokenType t, int val=0);
	// set root node with n.
	void setRootNode(SyntaxTreeNode *n);
	
	void addLeft(TokenType t, int val=0);
	// add the subtree n to this tree's left
	void addLeft(SyntaxTree *n);
	
	void addRight(TokenType t, int val=0);
	// add the subtree n to this tree's right
	void addRight(SyntaxTree *n);
	
	void addChild3(TokenType t, int val=0);
	// add the subtree n to this tree's child3
	void addChild3(SyntaxTree *n);
	
	SyntaxTreeNode* getRootNode();
	
	SyntaxTree* getLeft();
	SyntaxTree* getRight();
	SyntaxTree* getChild3();

};


class Lexer{
private:
	char *src;
	int length;
	int index;
	char *buf;
	
public:
	Lexer(char *filename);
	Lexer();
	~Lexer();
	void reset();	// rewind index
	bool isReady();
	bool isFinished();
	char *getSrc();
	int getIndex();
	
	void setSrc(char *s, int len);
	
	Token nextToken();
};

class Parser{
private:
	Lexer *lexer;
	Token currentToken;

	Token nextToken();
	
	SyntaxTree* Statement();
	SyntaxTree* Assign();
	SyntaxTree* Expression();
		SyntaxTree* T();
		SyntaxTree* F();
	SyntaxTree* Condition();
	SyntaxTree* Boolean();
		SyntaxTree* T2();
		SyntaxTree* F2();
	SyntaxTree* While();
	SyntaxTree* Begin();
	SyntaxTree* Block();

	void printError(const char *error);

public:
	Parser(char* sourcefile);
	
	Parser();
	
	~Parser();
	
	void reset();
	
	void printError();
	
	SyntaxTree* parse();
	
	void setLexer(Lexer *srclexer);
	
};
/************************************************************SyntaxTreeNode**************/




SyntaxTreeNode::SyntaxTreeNode(){
	type = ERROR;
	value = 0;
	left = right = child3 = NULL;
}
SyntaxTreeNode::SyntaxTreeNode(TokenType t, int val){
	type = t;
	value = val;
	left = right = child3 = NULL;
}

SyntaxTreeNode::~SyntaxTreeNode(){
	if(left != NULL){
		delete left;
	}
	if(right != NULL){
		delete right;
	}
	if(child3 != NULL){
		delete child3;
	}
}

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

void SyntaxTreeNode::setType(TokenType t){
	type = t;
}

TokenType SyntaxTreeNode::getType(){
	return type;
}

void SyntaxTreeNode::setValue(int val){
	value = val;
}

int SyntaxTreeNode::getValue(){
	return value;
}


void SyntaxTreeNode::addLeft(TokenType t, int val){
	left = new SyntaxTreeNode(t, val);
}
void SyntaxTreeNode::addLeft(SyntaxTreeNode *n){
	left = n;
}


void SyntaxTreeNode::addRight(TokenType t, int val){
	right = new SyntaxTreeNode(t, val);
}
void SyntaxTreeNode::addRight(SyntaxTreeNode *n){
	right = n;
}


void SyntaxTreeNode::addChild3(TokenType t, int val){
	child3 = new SyntaxTreeNode(t, val);
}
void SyntaxTreeNode::addChild3(SyntaxTreeNode *n){
	child3 = n;
}


SyntaxTreeNode* SyntaxTreeNode::getLeft(){
	return left;
}

SyntaxTreeNode* SyntaxTreeNode::getRight(){
	return right;
}

SyntaxTreeNode* SyntaxTreeNode::getChild3(){
	return child3;
}





/************************************************************SyntaxTree***********/




char* tokenToString(TokenType type);

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

SyntaxTree::SyntaxTree(TokenType t, int val){
	root = new SyntaxTreeNode(t, val);
}
SyntaxTree::SyntaxTree(SyntaxTreeNode *n){
	setRootNode(n);
}
SyntaxTree::SyntaxTree(SyntaxTree *tree){
	setRootNode(tree->getRootNode());
}
SyntaxTree::SyntaxTree(){
	setRootNode();
}

SyntaxTree::~SyntaxTree(){
	if(root != NULL){
		delete root;
	}
}

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

void SyntaxTree::display(SyntaxTreeNode *n, int tabcount, FILE *fo){
	static int tab[200];	// is it enough?
	
	SyntaxTreeNode * node = n;
	if(node == NULL) return;
	
	if(node->type == NUM){
		fprintf(fo, "%-3d", node->value);
	}else{
		fprintf(fo, "%-3s", tokenToString(node->type));
	}
		
	if(node->left != NULL){
		tab[tabcount] = 1;
	}
	
	if(node->right != NULL){
		fprintf(fo, "---");
		this->display(node->right, tabcount + 1, fo);
	}
	
	if(node->left != NULL){
		fprintf(fo, "\n");
		for(int i=0;i<tabcount;i++){
			if(tab[i] == 1){
				fprintf(fo, "|%5s", "");
			}else{
				fprintf(fo, "%6s", "");
			}
		}
		fprintf(fo, "+-----");
		tab[tabcount] = 0;
		this->display(node->left, tabcount + 1, fo);
	}
	
}

void SyntaxTree::display(FILE *fo){
	if(fo == NULL){
		fo = stdout;
		printf("\nFILE* NULL, will write to STDOUT.\n\n");
	}
		
	fprintf(fo, "\n");
	this->display(root, 0, fo);
	fprintf(fo, "\n");
}


void SyntaxTree::setRootNode(TokenType t, int val){
	root = new SyntaxTreeNode(t, val);
}
void SyntaxTree::setRootNode(SyntaxTreeNode *n){
	if(n == NULL){
		root = new SyntaxTreeNode();
	}else{
		root = n;
	}
}
void SyntaxTree::setRootNode(){
	root = new SyntaxTreeNode();
}


void SyntaxTree::addLeft(TokenType t, int val){
	root->left = new SyntaxTreeNode(t, val);
}
void SyntaxTree::addLeft(SyntaxTree *n){
	if(n == NULL) return;
	root->left = n->getRootNode();
}


void SyntaxTree::addRight(TokenType t, int val){
	root->right = new SyntaxTreeNode(t, val);
}
void SyntaxTree::addRight(SyntaxTree *n){
	if(n == NULL) return;
	root->right = n->getRootNode();
}


void SyntaxTree::addChild3(TokenType t, int val){
	root->child3 = new SyntaxTreeNode(t, val);
}
void SyntaxTree::addChild3(SyntaxTree *n){
	if(n == NULL) return;
	root->child3 = n->getRootNode();
}


SyntaxTreeNode* SyntaxTree::getRootNode(){
	return root;
}


SyntaxTree* SyntaxTree::getLeft(){
	if(root->left == NULL)
		return NULL;
	else
		return new SyntaxTree(root->left);
}

SyntaxTree* SyntaxTree::getRight(){
	if(root->right == NULL)
		return NULL;
	else
		return new SyntaxTree(root->right);
}


SyntaxTree* SyntaxTree::getChild3(){
	if(root->child3 == NULL)
		return NULL;
	else
		return new SyntaxTree(root->child3);
}

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

char* tokenToString(TokenType type){
	char *s = NULL;
	switch(type){
		case ID:
			s = "ID";
			break;
		case NUM:
			s = "NUM";
			break;
		case IF:
			s = "if";
			break;
		case THEN:
			s = "thn";
			break;
		case ELSE:
			s = "els";
			break;
		case WHILE:
			s = "whl";
			break;
		case DO:
			s = "do";
			break;
		case BEGIN:
			s = "blk";
			break;
		case END:
			s = "end";	// "end"
			break;
		case ASSIGN:
			s = "'='";
			break;
		case EQ:
			s = "==";
			break;
		case LT:
			s = "'<'";
			break;
		case GT:
			s = "'>'";
			break;
		case PLUS:
			s = "'+'";
			break;
		case MUL:
			s = "'*'";
			break;
		case MINUS:
			s = "'-'";
			break;
		case DIV:
			s = "'/'";
			break;
		case OR:
			s = "'|'";
			break;
		case AND:
			s = "'&'";
			break;
		default:
			s = "undef";
	}
	return s;
}





/************************************************************Lexer************/


#define MAXRESERVED 7
#define TOKENBUFSIZE 64

void getSingleOperator(char c, Token &token);
void keywordLookup(Token &token);


static Token ReservedWords[MAXRESERVED] = {
	{IF, "if"},
	{THEN, "then"},
	{ELSE, "else"},
	{WHILE, "while"},
	{DO, "do"},
	{BEGIN, "begin"},
	{END, "end"}
};


Lexer::Lexer(char *filename){
	buf = new char[TOKENBUFSIZE];
	FILE *fp = fopen(filename, "r");
	index = 0;
	if(fp==NULL){
		src = NULL;
		printf("\n\n********************************************\n");
		printf("* FATAL ERROR! LEXER COULD NOT OPEN FILE!!!\n");
		printf("* %s : No such file.\n", filename);
		printf("********************************************\n\n");
		length = 0;
	}else{
		int i = 0;
		while(fgetc(fp)!=EOF){
			i++;
		}
		length = i;
		src = new char[i+1];
		
		rewind(fp);
		i = 0;
		while(src[i] = fgetc(fp)){
			if(src[i] == EOF){
				src[i] = '\0';
				break;
			}
			i++;
		}
	
		fclose(fp);
	}
}

Lexer::Lexer(){
}

Lexer::~Lexer(){
	delete[] src;
}

void Lexer::reset(){
	index = 0;
}

bool Lexer::isFinished(){
	return (index == length - 1);
}

bool Lexer::isReady(){
	return (src != NULL);
}

char* Lexer::getSrc(){
	return src;
}

void Lexer::setSrc(char *s, int len){
	src = s;
	index = 0;
	length = len;
	buf = new char[TOKENBUFSIZE];
}

int  Lexer::getIndex(){
	return index;
}


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


Token Lexer::nextToken(){
	Token token;
	ScannerState state = START;
	int bufindex = 0;
	bool next = true;	// index++
	char c;
	
	if(index==length-1){
		token.type = ERROR;
		token.name = "NO CHAR LEFT.";
		return token;
	}
	
	c = src[index];
	while(c==' ' || c=='\n' || c=='\r' || c=='\t'){
		index ++;
		c = src[index];
	}
	
	// get started
	if((c>='a' && c<='z') || (c>='A' && c<='Z')){
		state = INID;
		token.type = ID;
		buf[bufindex++] = c;
	}else if(c>='0' && c<='9'){
		state = INNUM;
		token.type = NUM;
		buf[bufindex++] = c;
	}else if(c=='='){
		state = INEQ;
	}else if(c=='<'){
		state = INLE;
	}else if(c=='>'){
		state = INGE;
	}else{
		state = DONE;
		getSingleOperator(c, token);
	}
	index ++;
	
	while(state!=DONE){
		c = src[index];
		switch(state){
			case INEQ: