/******************************************************************
** 文件名: 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){