prase.cpp

内含源代码和编译实验报告

/******************************************************************
** 文件名: prase.cpp

** 描  述: 这是一个完整的文法分析器，实现C-语言的语法树建立。在真正生成
**         代码的执行过程中，语法分析与扫描是在一步中完成的。
**         构造语法树的BNF文法将各函数的注释中给出。
******************************************************************/
#include "globals.h"
#include "scan.h"
#include "prase.h"
#include "ExternGla"

/*********************************************
**类的静态成员初始化，这是整棵语法树的根结点，
**代表被分析的整个程序。
*********************************************/
CTreeNode *CPraser::m_program=NULL;

/**********************************************
**构造函数，当一个语法分析器被构造时，他完成两项
**工作：创建一个扫描器，开始对程序进行文法分析。
**文法分析中抛出的错误最终都将在这里得到处理。
************************************************/
CPraser::CPraser(){
	try{
		m_indentno=-4;
		m_EnEndexp=ESEMI;
		m_Enforexp=ERROR;						//辅助标志的初始化。
		m_pScaner=new CScaner;					//创建扫描器。
		if(!m_pScaner) throw bad_alloc();
		cout<<"Building syntax tree..."<<endl;
		program();								//进行文法分析。
	}
	catch (bad_alloc){									//处理堆分配异常。
		cout<<"Can't be allocated in heap, the programme must be terminated."<<endl;
		exit(1);}
	catch (CInvalid_type& pa_Invalid_type){				//程序文法错误处理。
		pa_Invalid_type.Type_error();
		exit(1);}
	catch (...){
		cout<<"Something error,the program was terminated.";
		exit(1);}
}

/***********************************
**析构函数通过调用Delete_program
**回收语法树的堆空间。
************************************/
CPraser::~CPraser(){
	delete m_pScaner;
	Delete_program(m_program);
}

void CPraser::Delete_program(CTreeNode *t){
	if(t!=NULL){
		Delete_program(t->m_pbrother);
		Delete_program(t->m_pchild[0]);
		Delete_program(t->m_pchild[1]);
		Delete_program(t->m_pchild[2]);
		delete t;
	}
	return;
}

/****************************************************
**第一个文法：program->declaration_list;
**程序由声明的序列组成，声明可以包括函数与全局变量。
****************************************************/
void CPraser::program(void){
	m_Entoken=m_pScaner->getToken();
	m_program=declaration_list();				//文法分析从这里开始。
	if(AllFlags.m_iTraceParse)					//如果只进行文法分析，则打印出分析结果。
		PrintTree(m_program);
}

/************************************************************************
**第二文法：declaration_list->declaration_list　declaration|declaration;
**          该函数不合规范，把一些判断处理提上前来做了，并运用迭代替换了
**          递归。
************************************************************************/ 
CTreeNode *CPraser::declaration_list(void){
	CTreeNode *first_declare=NULL,*temp=NULL,*temp2=NULL;
	while((m_Enfirst=m_Entoken)!=ENDFILE){
		m_Entoken=m_pScaner->getToken();
		if(m_Enfirst>FLOAT || m_Enfirst<VOID)			//声明序列的第一个字符必为内置类型。
			throw CInvalid_type(AllGlobals.lineno,"missing storage-class or type specifiers");
		temp=declaration();
		MAKELINK								//宏，把声明序列组织成兄弟链表。
	}
	return first_declare;						//返回兄弟链表的表头，即源程序中的第一个函数。
}

/********************************************************************
**文法：declaration->var_declaration|fun_declaration
**　　　声明可以是函数声明，也可以是全局变量声明。
**      两者的区别只有读到第三个标识('('与';')才可以看到。本来这里可以加
**      两层递归来实现，考虑到效率问题，这里一下读取三个标识。
**      m_Entoken的作用是保证每次都向前多读一个，方便判断。
***********************************************************************/
CTreeNode *CPraser::declaration(void){
	strcpy(m_strScope,"Global");			//作用域范围初始化为全局。
	CTreeNode *t=NULL;
	m_EnSecond=m_Entoken;						//第一个标识在上层已被读取，这里读第二个。
	strcpy(m_strIDname, m_pScaner->GettokenString());
	m_Entoken=m_pScaner->getToken();
	if(m_EnSecond!=ID)							//声明序列中，第二个标识肯定为ID。
		throw CInvalid_type(AllGlobals.lineno,"syntax error in declaration.");
	m_Enthird=m_Entoken;						//读第三个。
	if(m_Enthird==LLPAREN)		t=fun_declaration();	//根据第三个标识即可判定。
	else if(m_Enthird==SEMI)	t=var_declaration();
	else 
		throw CInvalid_type(AllGlobals.lineno,"missing ';' after identifier");
	return t;
}

/********************************************************************
** 文法：fun-declaration->type-specifier ID(params) compound-stmt
**       type-specifier：返回值类型，（已作为判定）。
**       ID:             函数名。　　（已被读取）。
**       params          参数表。
**       compound-stmt   函数体（复合语句序列）。
**       在建树时，函数名，返回类型保存在结点上，参数表与函数体作为两个
**       子结点。
**********************************************************************/
CTreeNode *CPraser::fun_declaration(void){
	CTreeNode *p;
	m_Entoken=m_pScaner->getToken();
	CTreeNode *t=newNode(FuncK);				//创建函数结点。
	strcpy(m_strScope,m_strIDname);				//接下来的结点的作用域在这个函数内。
	p=t->m_pchild[0]=params();
	if(p) p->m_pfather=t;
	while(p && p->m_pbrother){
		p=p->m_pbrother;
		p->m_pfather=t;
	}
	match(LGPAREN, "missing '{'");				//括号，分号之类符号必须匹配掉。
	p=t->m_pchild[1]=compound_stmt();
	if(p) p->m_pfather=t;						//为兄弟链表中的每个结点指明它们的父结点。
	while(p && p->m_pbrother){
		p=p->m_pbrother;
		p->m_pfather=t;
	}
	return t;
}

/********************************************************************
**文法：var_declaration->type_specifier ID;
**      变量声明可直接建立结点。
********************************************************************/
CTreeNode *CPraser::var_declaration(void){
	CTreeNode *t=newNode(DeclK);
	m_Entoken=m_pScaner->getToken();
	return t;
}

/*******************************************************************
** 文法：params->params, param|param
**		 param->type_specifier ID|E(表示空);
**        该函数再次以迭代来替换递归，并处理了两句文法，函数有点零乱。
*********************************************************************/
CTreeNode *CPraser::params(void){
	CTreeNode *first_declare=NULL, *temp=NULL,*temp2=NULL;
	m_Enfirst=m_Entoken;
	m_Entoken=m_pScaner->getToken();
	//处理空参数表，按照定义，空参数只能写成(),不可写成(void)
	if(m_Enfirst==RLPAREN) return first_declare;	
	if(m_Entoken==RLPAREN)
		throw CInvalid_type(AllGlobals.lineno,"Bad parameter table.");
	while(m_Enfirst<=FLOAT && m_Enfirst>=VOID){	//顺序处理参数表，只到读到的不是内置数据类型。
		if((m_EnSecond=m_Entoken)!=ID)
			throw CInvalid_type(AllGlobals.lineno,"Invalid parameter.");
		strcpy(m_strIDname, m_pScaner->GettokenString());  //这个是相应的参数名。
		temp=newNode(ParaK);		//获得了参数名与参数类型，建一结点。
		temp->m_pbrother=first_declare;
		first_declare=temp;
		m_Entoken=m_pScaner->getToken();
		if(m_Entoken==RLPAREN)		break; //耗去参数间的逗号，遇到右括号则结束。
		else if(m_Entoken==COMMA){
			m_Entoken=m_pScaner->getToken();
			m_Enfirst=m_Entoken;
			m_Entoken=m_pScaner->getToken();}
		else 
			throw CInvalid_type(AllGlobals.lineno,"Bad parameter table.");
	}
	m_Entoken=m_pScaner->getToken();
	return first_declare;				//参数表返回为函数结束的一个子结点。
}

/****************************************************************
**  文法：compound_stmt->{loal_declarations statement_list}
**        第一个循环处理：local_declarations
**        第二个处理：statement_list->statement_list statement|empty
**        该函数再次以迭代替换递归，影响了对文法表现的直观性。
**        statement->selection_stmt|expression|iteration_stmt......
**        (包括switch中的所有情况。)
********************************************************************/
CTreeNode *CPraser::compound_stmt(void){
	CTreeNode *temp=NULL,*first_declare=NULL,*temp2=NULL;
	while(1){
		m_Enfirst=m_Entoken;
		if(m_Enfirst<=FLOAT && m_Enfirst>=VOID)	//第一个是内置数据类型，则必为声明，否则转入statement.
			temp=local_declarations();
		else	break;
		MAKELINK								//宏，把声明序列组织成兄弟链表。
	}
	while(1){
		strcpy(m_strIDname, m_pScaner->GettokenString());//可能为ID名字，先拷贝备用。
		if(m_Entoken==RGPAREN)	break;					 //右大括号表示函结束。
		switch(m_Enfirst=m_Entoken){
			case IF:		temp=selection_stmt();	break;
			case NUM:
			case NOT:		temp=expression();		break;
			case WRITEB:
			case WRITED:	temp=write_stmt();		break;
			case ID:		temp=subcompound_stmt();break;
			case WHILE:		temp=iteration_stmt();	break;
			case FOR:		temp=iteration2_stmt();	break;
			case GOTO:		temp=jump_stmt();		break;
			case BREAK:		temp=break_stmt();		break;
			case CONTINUE:	temp=continue_stmt();	break;
			case RETURN:	temp=return_stmt();		break;
			default:
				throw CInvalid_type(AllGlobals.lineno,"syntax error.");
		}
		MAKELINK	
	}
	match(RGPAREN,"missing '}'");					//函数结束，把右大括号匹配掉。
	return first_declare;
}

/******************************************************************
**文法：subcompound_stmt=address|call_func|expression
**      expression中对扫描的速度有特殊要求，须向前退一个。
******************************************************************/
CTreeNode *CPraser::subcompound_stmt(void){
	CTreeNode *t=NULL; TokenType temp;
	strcpy(m_strIDname, m_pScaner->GettokenString());
	m_Enforexp=m_Entoken;				//继续向前扫描前，当前记号可能有用(若为表达式),保留。
	m_Entoken=m_pScaner->getToken();	//向前扫描一个。
	if(m_Entoken==COLON){
		m_Enforexp=ERROR;				//判定不是表达式，则前一个保留的记号无用，可抛去。
		t=address();}
	else{
		temp=m_Entoken; 
		m_Entoken=m_Enforexp; 
		m_Enforexp=temp;				//表达式中，前一个记号有用，并且将当前记号退一个。
		t=expression();}
	return t;
}

/*******************************************************************
**文法：address->ID;
*******************************************************************/
CTreeNode *CPraser::address(void){
	m_Enfirst=VOID;							//作为地址标号的ID没有数据类型属性。
	CTreeNode *t=newStmtNode(AddressK);
	t->m_pchild[0]=newExpNode(IdK);
	if(t->m_pchild[0]) t->m_pchild[0]->m_pfather=t;
	match(COLON,"   ");
	return t;
}

/***************************************************************
**文法：call_func->ID(args);
***************************************************************/
CTreeNode *CPraser::call_func(void){
	m_Enfirst=VOID;	
	CTreeNode *p;
	CTreeNode *t=newStmtNode(CallK);
	t->m_pchild[0]=newExpNode(IdK);
	if(t->m_pchild[0]) t->m_pchild[0]->m_pfather=t;
	p=t->m_pchild[1]=args();
	if(p) p->m_pfather=t;
	while(p && p->m_pbrother){
		p=p->m_pbrother;
		p->m_pfather=t;
	}
	return t;
}

/***********************************************************
**文法：args=arsgs,expression|empty;
**      这是函数调用语句的实参表，以迭代替换递归。
***********************************************************/
CTreeNode *CPraser::args(void){
	CTreeNode *temp=NULL,*first_declare=NULL,*temp2=NULL;
	if(m_Enforexp!=ERROR){	//m_Enforexp不为ERROR，说明它保留着下一个记号，不必从文件中读取了。
		READSYMBOL}
	else{
		m_Entoken=m_pScaner->getToken();
		strcpy(m_strIDname, m_pScaner->GettokenString());
		m_Enforexp=m_pScaner->getToken();}
	READSYMBOL
	if(m_Entoken==RLPAREN)
		return first_declare;							//函数调用的参数表为空。
	while(m_Entoken==ID || m_Entoken==NUM){
		m_EnEndexp=ECOMMA;									//指示表达式必须以','结尾
		temp=expression();
		MAKELINK;
		if(m_EnEndexp==ERPAREN){
			m_EnEndexp=ESEMI;				//接到已读到)的通知，说明实参表读完。恢复缺省。
			return first_declare;
		}
		m_Entoken=m_Enforexp;
		strcpy(m_strIDname, m_pScaner->GettokenString());
		m_Enforexp=ERROR;
	}
	throw CInvalid_type(AllGlobals.lineno,"syntax error.");
}

/*************************************************************
**文法：local_declarations->local_declarations var_declaration|empty
**      由于上层函数处理得过多，这个函数也不完全符合文法。
****************************************************************/
CTreeNode *CPraser::local_declarations(void){
	m_Entoken=m_pScaner->getToken();
	strcpy(m_strIDname, m_pScaner->GettokenString());
	CTreeNode *t=NULL;
	m_EnSecond=m_Entoken;
	if(m_EnSecond!=ID)
		throw CInvalid_type(AllGlobals.lineno,"syntax error in declaration.");
	t=var_declaration();
	match(SEMI,"missing ';'");
	return t;
}
		
/***********************************************************
** 文法：selection_stmt->if(expression)compound_stmt
**							|if(expression)compound_stmt else compound_stmt
*************************************************************/
CTreeNode *CPraser::selection_stmt(void){
	CTreeNode *t=newStmtNode(IfK);
	CTreeNode *p;
	m_Entoken=m_pScaner->getToken();
	match(LLPAREN, "missing '(' befor 'if'");
	m_EnEndexp=ERPAREN;							//指示下一个表达式将以)结尾。
	t->m_pchild[0]=expression();
	if(t->m_pchild[0]) t->m_pchild[0]->m_pfather=t;
	match(LGPAREN,"missing '{' after 'if'");
	p=t->m_pchild[1]=compound_stmt();
	if(p) p->m_pfather=t;
	while(p && p->m_pbrother){
		p=p->m_pbrother;
		p->m_pfather=t;
	}
	if(m_Entoken==ELSE){
		match(ELSE, " ");
		match(LGPAREN, "missing '{' after 'else'");
		p=t->m_pchild[2]=compound_stmt();
		if(p) p->m_pfather=t;
		while(p && p->m_pbrother){
			p=p->m_pbrother;
			p->m_pfather=t;
		}
	}
	return t;
}

/**************************************************************
**文法:　write_stmt->writeb(expression); | writed(expresstion);
***************************************************************/
CTreeNode *CPraser::write_stmt(void){
	CTreeNode *t;
	if(m_Entoken==WRITEB)
		t=newStmtNode(WritebK);
	else if(m_Entoken==WRITED)
		t=newStmtNode(WritedK);
	m_Entoken=m_pScaner->getToken();
	match(LLPAREN, "missing '(' befor 'if'");
	m_EnEndexp=ERPAREN;							//指示下一个表达式将以)结尾。
	t->m_pchild[0]=expression();
	if(t->m_pchild[0]) t->m_pchild[0]->m_pfather=t;
	match(SEMI,"missing ';' after expression");
	return t;
}

/************************************************************
**文法： iteration_stmt->while (expression){compound_stmt}
*************************************************************/
CTreeNode *CPraser::iteration_stmt(void){
	CTreeNode *t=newStmtNode(WhileK);
	CTreeNode *p;
	m_Entoken=m_pScaner->getToken();
	match(LLPAREN, "missing '(' after 'while'");
	m_EnEndexp=ERPAREN;							//指示下一个表达式将以)结尾。
	t->m_pchild[0]=expression();
	if(t->m_pchild[0]) t->m_pchild[0]->m_pfather=t;
	match(LGPAREN,"missing '{' after 'while'");
	p=t->m_pchild[1]=compound_stmt();
	if(p) p->m_pfather=t;
	while(p && p->m_pbrother){
		p=p->m_pbrother;
		p->m_pfather=t;
	}
	return t;
}

/*************************************************************
**文法：iteration2_stmt->for(var=expression;expression;var=expression)
**															{compound_stmt}
****************************************************************/
CTreeNode *CPraser::iteration2_stmt(void){