compiler.cpp

一个用VC++开发的Pascal编译器. 包括词法分析 语法分析 语义分析 中间代码生成 对学习编译原理的同学有很大用途

				break;
			}
			IDAssginPosition = LookUpRecord(IDAssgin);
			Advance();
			A();
			Statement S;
			S.Chain = 0 ;
			return S;
		}
		break;
	case IF://条件if语句
		{
			Statement S1,S2;
			BoolTable m_BE;
			Advance();
			if( Is(NOT) || Is(ID) || Is(LPAREN) ){//是BE的开始单词
				m_BE = BE();
				BackPatch(m_BE.TC, NXQ);//及时回填
			}
			else{//失配BE
				Error(CurStep, LeadBEExcept, CurLine);
			}
			if(Is(THEN)){//匹配then
				Advance();
				S1 = S();
			}
			else{//未匹配then出错
				Error(CurStep, ThenExcept, CurLine);
			}
			if(Is(ELSE)){	//if--then--else句型
				Advance();
				if( Is(IF) || Is(ID) || Is(WHILE) ||Is(LCUT) ){//是S的开始单词
					int q = NXQ;
					Gen(JMP, 0, 0, 0);//生成无条件跳转语句，待拉链回填
					BackPatch(m_BE.FC, NXQ);//回填布尔表达式的假出口
					S1.Chain = Merge(S1.Chain, q);//
					S2 = S();
					q = Merge(S1.Chain, S2.Chain);
					Statement S;
					S.Chain = q;
					return S;
				}
				else{//失配LeadS
					Error(CurStep, LeadSExcept, CurLine);
				}

			}
			else{				//if--then句型
				Statement S;
				S.Chain = Merge(S1.Chain, m_BE.FC);
				return S;
			}
		}
		break;
	case WHILE://while语句
		{
			int Quad = NXQ;
			BoolTable m_BE;
			Advance();
			if( Is(NOT) || Is(ID) || Is(LPAREN) ){//是BE的开始单词
				m_BE = BE();
				BackPatch(m_BE.TC, NXQ);
			}
			else{//失配BE
				Error(CurStep, LeadBEExcept, CurLine);
			}
			
			if(Is(DO)){//匹配do
				Advance();
				if( Is(IF) || Is(ID) || Is(WHILE) ||Is(LCUT) ){//是S的开始单词
					Statement m_S;
					m_S = S();
					BackPatch(m_S.Chain, Quad);
					Gen(JMP, 0, 0, Quad);
					Statement S;
					S.Chain = m_BE.FC;
					return S;					
				}
				else{//失配LeadS
					Error(CurStep, LeadSExcept, CurLine);
				}
			}
			else{//未匹配do出错
				Error(CurStep, DoExcept, CurLine);
			}
		}
		break;
	case LCUT://<S> →{<STL>}
		{
			Advance();
			STL();
			Statement SI ;
			SI.Chain = 0;
			if(Match(RCUT)){//匹配了右括号
				
				Advance();
				return SI;
			}
			else{//未匹配右括号
				Error(CurStep, RCUTExcept, CurLine);
			}
		}
		break;
	default://不是正常语句出错
		Error(CurStep, LeadSExcept, CurLine);
		break;
	}
	return DefaultS;
}

int CCompiler::AE()
{
	int EAplace = T();
	if (EAplace == -1){//表达式有误
		SkipToSEMI();
	}
	else{
		while(Is(PLUS)||Is(SUB)){//匹配+或-
			int type = m_dModel[ CurStep ].TokenType;
			Advance();
			int EBplace = T();
			int ERplace = NewTemp();
			Gen(type,EAplace,EBplace,ERplace);
			EAplace = ERplace;
		}
	}
	return EAplace;
}

BoolTable CCompiler::BE()
{
	BoolTable BE;
	BoolTable BEA;
	BEA = BT();
	while(Match(OR)){//匹配了|或
		Advance();
		BackPatch(BEA.FC,NXQ);//回填BEA.FC
		BoolTable BEB;
		BEB = BT();
		BEA.TC = Merge(BEA.TC,BEB.TC);//真出口拉链
		BEA.FC = BEB.FC;//假出口传递
	}
	BE = BEA ;
	return BE;
}


int CCompiler::T()
{
  	int	TAplace = F();
	if (TAplace == -1) return TAplace;//表达式有错误
	while(Is(TIMES)){
		Advance();
		int TBplace = F();
		int TRplace = NewTemp();
		Gen(TIMES, TAplace, TBplace, TRplace);
		TAplace = TRplace;
	}
	return TAplace;
}

int CCompiler::F()
{
	CString str = m_dModel[ CurStep ].TokenString;
	int TokenType = m_dModel[ CurStep ].TokenType;
	switch(TokenType){
	case LPAREN:
		{
			Advance();
			int Eplace = AE();
			if(Is(RPAREN)){//匹配右括号
				Advance();
				return Eplace;
			}
			else{//未匹配右括号出错
				Error(CurStep, RPARENExcept, CurLine);
				return -1;
			}
		}
		break;
	case ID:
		{
			if(Entry(m_dModel[ CurStep ].TokenString)==-1){
				//未定义的标志符出错
				Error(CurStep, UndeclaredId, CurLine);
				return -1;
			}
			Advance();
			return Entry(m_dModel[ CurStep-1 ].TokenString);
		}
		break;
	case INTNUM:
		{
			if(CurType == REAL) {//类型不匹配
				Error(CurStep, TypeUnsuited, CurLine);
				return -1;
			}
			Advance();
			int pos = Entry(m_dModel[ CurStep-1 ].TokenString);
			return	Entry(m_dModel[ CurStep-1 ].TokenString);
		}
		break;
	case REALNUM:
		{
			if(CurType == INTEGER) {//类型不匹配
				Error(CurStep, TypeUnsuited, CurLine);
				return -1;
			}
			Advance();
			return	Entry(m_dModel[ CurStep-1 ].TokenString);
		}
		break;
	case PLUS:
		{
			Error(CurStep, OperandExcept, CurLine);
			return -1;
		}
		break;
	case TIMES:
		{
			Error(CurStep, OperandExcept, CurLine);
			return -1;
		}
		break;
	case SUB:
		{
			Error(CurStep, OperandExcept, CurLine);
			return -1;
		}
		break;
	default ://不是合法单词出错
		break;
	}
	return -1;
}

BoolTable CCompiler::BT()
{
	BoolTable BT;
	BoolTable BTA;
	BTA = BF();
	while(Is(AND)){//匹配了&与
		Advance();
		BackPatch(BTA.TC, NXQ);//回填真出口
		BoolTable BTB = BF();
		BTA.FC = Merge(BTA.FC, BTB.FC);//假出口拉链
		BTA.TC = BTB.TC;
	}
	BT = BTA;
	return BT;
}

BoolTable CCompiler::BF()
{
	BoolTable BF;
	BF.TC = 0;
	BF.FC = 0;
	int TokenType = m_dModel[ CurStep ].TokenType;
	switch(TokenType){
	case LPAREN:
		{
			Advance();
			BF = BE();
			Match(RPAREN);//匹配右括号
			Advance();
			return BF;
		}
		break;
	case ID:
		{
			int arg1 = LookUpRecord(m_dModel[ CurStep ].TokenString);
			if(arg1==-1){
				//未定义的变量  出错
				Error(CurStep, UndeclaredId, CurLine);
			}
			Advance();
			int OP = m_dModel[ CurStep ].TokenType;
			if(OP>=EQ&&OP<=NE){//是比较符
				Advance();
				if(Match(ID)){//匹配了标志符
					int arg2 = 
						LookUpRecord(m_dModel[ CurStep ].TokenString);
					if(arg2==-1){
							//未定义的变量  出错
						Error(CurStep, UndeclaredId, CurLine);
					}
					Advance();
					BF.TC = NXQ;
					BF.FC = NXQ+1;
					Gen(OP, arg1, arg2, 0);
					Gen(JMP, 0, 0, 0);
					return BF;
				}
				else{//未匹配了标志符出错
					Error(CurStep, IDExcept, CurLine);
				}
			}
			else{//属于单个变量作为布尔元素
				BF.TC = NXQ;
				BF.FC = NXQ+1;
				Gen(JNZ, arg1, 0, 0);
				Gen(JMP, 0, 0, 0);
				return BF;
			}
		}
		break;
	case NOT:
		{
			Advance();
			BoolTable NBF;
			NBF = BE();
			BF.TC = NBF.FC;
			BF.FC = NBF.TC;
			return BF;
		}
		break;
	default ://不是合法BF出错
		break;
	}
	return BF;
}

void CCompiler::ROP()
{
	int TokenType = m_dModel[ CurStep ].TokenType;
	switch(TokenType){
	case EQ :
		{
			Advance();
			return;
		}
		break;
	case LT :
		{
			Advance();
			return;
		}
		break;
	case LE :
		{
			Advance();
			return;
		}
		break;
	case GT :
		{
			Advance();
			return;
		}
		break;
	case GE :
		{
			Advance();
			return;
		}
		break;
	case NE :
		{
			Advance();
			return;
		}
		break;
	default://绝对不会错调用时已确定是六种情况之一
		break;
	}
}

void CCompiler::A()
{
	CString str = "";
	int	type = m_dModel[ CurStep ].TokenType;
	str = m_dModel[ CurStep ].TokenString;
	Match(ASSIGN);//匹配:=
	Advance();
	int res = AE();
	Gen(ASSIGN,res,0,IDAssginPosition);
	return;
}

void CCompiler::FillSymbolRecord(int type)
{
	for(int i=0; i<m_Variable.size(); i++ )
	{
		SymbolRecord	m_Record;
		m_Record.Lines.clear();
		m_Record.Location = -1;
		m_Record.m_pValue = NULL;
		m_Record.TokenString = m_Variable[ i ];
		m_Record.TokenType = type;
		if(LookUpRecord(m_Variable[ i ])!=-1){//有重复项
			Error(i, IdRedefinition, CurLine);
		}
		else{
			m_SymbolRecord.push_back(m_Record);
		}
	}
}

int CCompiler::Entry(CString Name)
{
	if (LookUpRecord(Name) != -1){//查到纪录项
		return LookUpRecord(Name);
	}
	CString str = m_dModel[ CurStep-1 ].TokenString;
	if(m_dModel[ CurStep-1 ].TokenType == INTNUM){
		//不是标志符 是整形常数
		SymbolRecord	m_Record;
		m_Record.Lines.clear();
		m_Record.Location = -1;
		m_Record.m_pValue = NULL;
		m_Record.TokenString = Name;
		m_Record.TokenType = INTNUM;
		m_SymbolRecord.push_back(m_Record);
		int a = m_SymbolRecord.size();
		int	b = 0;
		return m_SymbolRecord.size()-1;
	}
	if(m_dModel[ CurStep ].TokenType == REALNUM){
		//不是标志符 是实型常数
		SymbolRecord	m_Record;
		m_Record.Lines.clear();
		m_Record.Location = -1;
		m_Record.m_pValue = NULL;
		m_Record.TokenString = Name;
		m_Record.TokenType = REALNUM;
		m_SymbolRecord.push_back(m_Record);
		return m_SymbolRecord.size();
	}
	return -1;
}

int CCompiler::Gen(int op, int arg1, int arg2, int result)
{
	m_QuadRuple.OP		= op;
	m_QuadRuple.arg1	= arg1;
	m_QuadRuple.arg2	= arg2;
	m_QuadRuple.result	= result;
	m_fourModel.push_back(m_QuadRuple);
	NXQ ++ ;
	return 0;
}

int CCompiler::NewTemp()
{
	return	--tempnum;
}

int CCompiler::LookUpRecord(CString Name)
{
	for(int i = 0 ; i < m_SymbolRecord.size(); i++){
		if((m_SymbolRecord[ i ].TokenString.Compare(Name)) == 0){
			//查到匹配项
			return	i;
		}
	}
	return -1;
}

int CCompiler::VariableLegal(CString token, int type)
{
	switch( type ){
		//-1只查找是否有定义,INTEGER查看变量是否是整形,
		//REAL查看变量是否是实形
	case -1:
		{
			int legal = LookUpRecord(token);
				//查找符号表,看是否被定义
			if(legal == -1){//未定义的变量
				return 0;
			}
		}
		break;
	case INTEGER:
		{
			int legal = LookUpRecord(token);
				//查找符号表,看是否被定义
			if(legal == -1) return 0;//未定义的变量
			if(m_SymbolRecord[ legal ].TokenType!=INTEGER)
				return 0;//定义了，但不是整型
		}
		break;
	case REAL:
		{
			int legal = LookUpRecord(token);
				//查找符号表,看是否被定义
			if(legal == -1) return 0;//未定义的变量
			if(m_SymbolRecord[ legal ].TokenType!=REAL)
				return 0;//定义了，但不是实型
		}
		break;
	default:
		break;
	}
	return 1;//合法变量，类型也合法。
}

void CCompiler::BackPatch(int p, int t)
//用四元式t回填以p为首的链，将所有四元式的result域改写为t的值
{
	int q = p ;
	while(q){
		int q1 = m_fourModel[q].result;
		m_fourModel[q].result = t;
		q = q1;
	}
	return;
}

int CCompiler::Merge(int p1, int p2)
//将链首分别为p1和p2的两条链合并为一条，并返回新链的链首
{
	int p = 0;
	if( !p2 ) return p1;//第二条链为空链
	else{
		//返回第二条链首
		p = p2 ;
		while(m_fourModel[ p ].result)
			p = m_fourModel[ p ].result;
		m_fourModel[ p ].result = p1;//拉链
		return p2;
	}		
}



BOOL CCompiler::Is(int type)
{
	if(m_dModel[ CurStep ].TokenType == type){
		CurToken = m_dModel[ CurStep ].TokenString;
		return TRUE;
	}
	return FALSE;
}

void CCompiler::Backward()
{
	CurStep-- ;
}

void CCompiler::SkipToSEMI()
{
	for(int m_step = CurStep; m_step<m_dModel.size(); m_step++){
		if(m_dModel[ m_step ].TokenType == SEMI){//是分号
			CurStep = m_step;
			return;
		}
	}
	return;
}