parser.cpp

c语言编写

						Continue=1;
						for(int ExpPos=i+1;Continue&&Exp[Count_NTerm][Choice][ExpPos];ExpPos++)//生成First(Xi+1Xi+2……)
						{
							if(IsTerm(Exp[Count_NTerm][Choice][ExpPos]))//Xj是终结符
							{
									for(int j=0;TempFirst[j];j++)//依次检查TempFirst，如果没有存在就添加
										if(TempFirst[j]==Exp[Count_NTerm][Choice][ExpPos])
											break;
									TempFirst[j]=Exp[Count_NTerm][Choice][ExpPos];
									Continue=0;
							}
							else if(Exp[Count_NTerm][Choice][ExpPos]!=NullToken)
							{
								Continue=0;
								for(int FirstChoice=0;FirstChoice<12;FirstChoice++)//每一个First(Xj)中的元素
								{
									if(First[Exp[Count_NTerm][Choice][ExpPos]-OFFSET][FirstChoice][0])
									{
										if(InFirst(Exp[Count_NTerm][Choice][ExpPos]-OFFSET,FirstChoice,NullToken))//空字在first集合里
											Continue=1;
										for(int CurPos=0;First[Exp[Count_NTerm][Choice][ExpPos]-OFFSET][FirstChoice][CurPos];CurPos++)///当前X的所有first元素(except nulltoken)
										{
											if(First[Exp[Count_NTerm][Choice][ExpPos]-OFFSET][FirstChoice][CurPos]!=NullToken)
											{
												for(int j=0;TempFirst[j];j++)//依次检查TempFirst，如果没有存在就添加
													if(TempFirst[j]==First[Exp[Count_NTerm][Choice][ExpPos]-OFFSET][FirstChoice][CurPos])
														break;
												TempFirst[j]=First[Exp[Count_NTerm][Choice][ExpPos]-OFFSET][FirstChoice][CurPos];
											}
										}
									}
								}
							}
						}
						if(Continue)//还是生成TempFirst
						{
								for(int j=0;TempFirst[j];j++)//依次检查TempFirst，如果没有NullToken就添加
									if(TempFirst[j]==NullToken)
										break;
								TempFirst[j]=NullToken;
						}
						for(int CurPos=0;TempFirst[CurPos];CurPos++)
							if(!InFollow(Exp[Count_NTerm][Choice][i]-OFFSET,TempFirst[CurPos])&&TempFirst[CurPos]!=NullToken)
							{
								change=1;
								AddFollow(Exp[Count_NTerm][Choice][i]-OFFSET,TempFirst[CurPos]);
							}
						if(Have(TempFirst,NullToken,V_shop))
							for(CurPos=0;Follow[Count_NTerm][CurPos]!=NullToken;CurPos++)
								if(!InFollow(Exp[Count_NTerm][Choice][i]-OFFSET,Follow[Count_NTerm][CurPos]))
								{
									change=1;
									AddFollow(Exp[Count_NTerm][Choice][i]-OFFSET,Follow[Count_NTerm][CurPos]);
								}
						for(int i=0;i<30;i++)
							TempFirst[i]=0;
					}
				}
	}
}

void Parser::GenParsingTable()
{	
	for(int Count_NTerm=1;Count_NTerm<=NUM_NTERM;Count_NTerm++)//for every non-terminals
		for(int Choice=0;Exp[Count_NTerm][Choice][0];Choice++)//for every choice of each non-term
		{
			//CurToken=First[Count_NTerm][Choice][0];
			for(int CurPos=0;First[Count_NTerm][Choice][CurPos];CurPos++)//检查First 集合以0为结束；
				if(First[Count_NTerm][Choice][CurPos]!=NullToken)
					M[Count_NTerm][First[Count_NTerm][Choice][CurPos]]=Choice;//M[A][a]=Choice
			if(InFirst(Count_NTerm,Choice,NullToken))//如果空符在first集合中，则检查follow集合，以-1结束（因为$可在follow集合中）
			{
				for(int CurPos=0;Follow[Count_NTerm][CurPos]!=NullToken;CurPos++)//
					M[Count_NTerm][Follow[Count_NTerm][CurPos]]=Choice;
			}
		}
}
TreeNode* Parser::NewNode(int type)
{
//	int a;
	TreeNode* NewNode=new TreeNode;
	NewNode->Type=type;
	NewNode->child=NULL;
	NewNode->sibling=NULL;

	return NewNode;	
}


void Parser::Parsing()
{
	int NullFlag=1;
	for(int i=0;i<=NUM_TERM;i++)
		if(M[1][i]!=NonOp)//分析表是否可以启动
			NullFlag=0;
	if(NullFlag)//分析表无效
		return ;
	TreeNode* CurNode;
	CStack s;//CString str;
	stack.Push(NewNode(V_shop));
	RootNode=NewNode(program);
	stack.Push(RootNode);
	int CurToken=getToken();  //读进第一个单词
	int flag = TRUE;
	while (flag)
	{
		if(!stack.Empty())//弹出栈顶符号
		{ 
			CurNode = stack.Pop(); 
		
		}  
		else
		{	
			CurToken=getToken();  
		}
		if (IsTerm(CurNode->Type))  //终结符
		{
			if (CurNode->Type == CurToken) 
			{
				switch(CurToken)
				{
				case NUM:
					CurNode->attr.val=atoi(tokenString);
					break;
				case ID:
				case IF:
				case ELSE:
				case INT:
				case RETURN:
				case WHILE:
				case VOID:
				//	a=1;
					CurNode->attr.name=copyString(tokenString);
					break;
				default:
					;
				}
				CurToken=getToken();
			}
			else{ 
				Err();
				return ;
			}
		}
		else if(CurNode->Type == V_shop)//V_shop为分析栈的结束符，ENDFILE为token队的终结
		{	
			if(CurToken==ENDFILE) 
				flag = FALSE;
			else{ 
				Err();
				return ;
			}
		}
		else if(M[CurNode->Type-OFFSET][CurToken]!=NonOp)//parsing table不空，替换
			/*
			 *	注意我们生成的M与课本不同，其内容是序号为CurNode->Type的
			 *	非终结符的表达式中第几个选项。
			 */
		{
			int i = 0;
			TreeNode* TempNode=CurNode;
			do{	
				if(Exp[CurNode->Type-OFFSET][M[CurNode->Type-OFFSET][CurToken]][i]!=NullToken)//空字不压栈
				{
				//	TempNode=NewNode(Exp[CurNode->Type-OFFSET][M[CurNode->Type-OFFSET][CurToken]][i]);
					
					if(!i)
					{
						TempNode->child=NewNode(Exp[CurNode->Type-OFFSET][M[CurNode->Type-OFFSET][CurToken]][i]);//第一个符号为原先节点的子节点
						TempNode=TempNode->child;
					}
					else
					{
						TempNode->sibling=NewNode(Exp[CurNode->Type-OFFSET][M[CurNode->Type-OFFSET][CurToken]][i]);;//其他添加为兄弟
						TempNode=TempNode->sibling;
					}
						
					if(!s.Push(TempNode))
					{
						printf("Stack Overflow");
						return ;
					}
					
				}
				i++;
			}while (Exp[CurNode->Type-OFFSET][M[CurNode->Type-OFFSET][CurToken]][i]!=0);//直至替换完成
			while(!s.Empty()) 
				if(!stack.Push(s.Pop()))
				{
					printf("Stack Overflow");
					return ;
				}
		}
		else{ 
				Err();//err
				return ;
			}
	}

}
void Parser::PrintTree(FILE* listing,TreeNode* Node)
{
	
	//TreeNode* CurNode;
	if(Node)
	{
	
		if(IsTerm(Node->Type))
				switch(Node->Type)
				{
					case IF:
					case ELSE:
					case INT:
					case RETURN:
					case WHILE:
					case VOID:
					//	fprintf(listing,"reserved word");
						fprintf(listing,"reserved word: %s",Node->attr.name);
						break;
					case ASSIGN:fprintf(listing,"=");break;
					case LT: fprintf(listing,"<");break;
					case LTOREQ: fprintf(listing,"<=");break;
					case BI: fprintf(listing,">");break;
					case BIOREQ: fprintf(listing,">=");break;
					case EQ: fprintf(listing,"==");break;
					case NEQ: fprintf(listing,"!=");break;
					case PLUS: fprintf(listing,"+");break;
					case MINUS: fprintf(listing,"-");break;
					case TIMES: fprintf(listing,"*");break;
					case OVER: fprintf(listing,"/");break;
					case SEMI: fprintf(listing,";");break;
					case COMA: fprintf(listing,"','");break;
					case LROUNDBRA: fprintf(listing,"'('");break;
					case RROUNDBRA: fprintf(listing,"')'");break;
					case LSQUARPAREN: fprintf(listing,"[");break;
					case RSQUARPAREN: fprintf(listing,"]");break;
					case LBRAC: fprintf(listing,"{");break;
					case RBRAC: fprintf(listing,"}");break;
					case LCOM: fprintf(listing,"/*");break;
					case RCOM: fprintf(listing,"*/");break;
					case ENDFILE:fprintf(listing,"EOF");break;
					case NUM:
						fprintf(listing,"NUM: %d\n",Node->attr.val);
						break;
					case ID:
						fprintf(listing,"ID: %s",Node->attr.name);
						break;
					case ERROR:
						fprintf(listing,"ERROR");
						break;
					default:
						fprintf(listing,"Unknown: %d",Node->Type);
			}
		else
		{
				switch(Node->Type)
				{
					case program:	fprintf(listing,"program");		break;
					case declaration_list:	fprintf(listing,"declaration_list");break;	
					case declaration:	fprintf(listing,"declaration");	break;		
					case var_declaration:fprintf(listing,"var_declaration");	break;	
					case type_specifier	:fprintf(listing,"type_specifier");		break;	
					case fun_declaration:fprintf(listing,"fun_declaration");	break;
					case params	:		    fprintf(listing,"params");	break;
					case param_list:		fprintf(listing,"param_list");break;	
					case param	:			fprintf(listing,"param");	break;
					case compound_stmt:		fprintf(listing,"compound_stmt");	break;
					case local_declarations	:fprintf(listing,"local_declarations");	break;
					case statement_list:	fprintf(listing,"statement_list");	break;
					case statement	:		fprintf(listing,"statement");	break;
					case expression_stmt:	fprintf(listing,"expression_stmt");	break;
					case selection_stmt	:	fprintf(listing,"selection_stmt");	break;
					case iteration_stmt:	fprintf(listing,"iteration_stmt");	break;
					case return_stmt:		fprintf(listing,"return_stmt");	break;
					case expression:		fprintf(listing,"expression");	break;
					case var:				fprintf(listing,"var");	break;
					case simple_expression:	fprintf(listing,"simple_expression");break;	
					case relop:				fprintf(listing,"relop");	break;
					case additive_expression:fprintf(listing,"additive_expression");break;	
					case addop:				fprintf(listing,"addop");	break;
					case term:				fprintf(listing,"term");	break;
					case mulop:				fprintf(listing,"mulop");	break;
					case factor:			fprintf(listing,"factor");	break;
					case call:				fprintf(listing,"call");	break;
					case args:				fprintf(listing,"args");	break;
					case args_list:			fprintf(listing,"args_list");	break;
					/*for left factoring*/
					case _declaration:		fprintf(listing,"_declaration");	break;
					case _param:			fprintf(listing,"_param");	break;
					case _selection_stmt:	fprintf(listing,"_selection_stmt");break;	
					case _return_stmt:		fprintf(listing,"_return_stmt");	break;
					case _var:				fprintf(listing,"_var");	break;
					case _simple_expression:fprintf(listing,"_simple_expression");break;	
					/*for left recursion removal*/
					case _declaration_list:	fprintf(listing,"_declaration_list");	break;
					case _param_list:		fprintf(listing,"_param_list");	break;
					case _local_declarations:fprintf(listing,"_local_declarations");break;	
					case _statement_list:	fprintf(listing,"_statement_list");	break;
					case _additive_expression:	fprintf(listing,"_additive_expression");break;	
					case _term	:			fprintf(listing,"_term");	break;
					case _args_list	:		fprintf(listing,"program");	break;
					case _val:				fprintf(listing,"_val");	break;
					case _op_but_assign:	fprintf(listing,"_op_but_assign");	break;
					case _expression_ID:  	fprintf(listing,"_expression_ID");	break;
					case _expression_var:	fprintf(listing,"_expression_var");		break;
					case _expression_call:	fprintf(listing,"_expression_call");	break;
				}
		
		}
		
		if(Node->child)
		{
			dep++;
			fprintf(listing,"\n");	
			for(int i=0;i<dep;i++)
				fprintf(listing,"    ");		
			fprintf(listing,"(");
			PrintTree(listing,Node->child);	
			fprintf(listing,"\n");
			for(int j=0;j<dep;j++)
				fprintf(listing,"    ");	
			fprintf(listing,")");	
	//		fprintf(listing,"\n");
			dep--;
		}
		if(Node->sibling)
		{
			fprintf(listing,",");
			fprintf(listing,"\n");
			for(int i=0;i<dep;i++)
				fprintf(listing,"    ");
			fprintf(listing," ");
			PrintTree(listing,Node->sibling);
		}
		
	
	}	
}

void Parser::PrintTree(FILE* listing)//按中序遍历输出分析树
{
	fprintf(listing,"按中序遍历输出分析树：\n");
	if(RootNode!=NULL)
	{
		dep=0;
		fprintf(listing,"(");
		//fprintf(listing,"\n");
		PrintTree(listing,RootNode);
		fprintf(listing,"\n");
		fprintf(listing,")");
	}
	else
		fprintf(listing,"Tree Empty!\n");
}