parser.cpp

c语言编写

#include "globals.h"
#include "util.h"
//#include "Stack.h"
#include "Parser.h"
#include <stdio.h>
#include "scan.h"

Parser::Parser()//完成对数组的初始化，并生成first，follow集合，分析表
{
	int Gram[NUM_NTERM+1][12][30]=
	{
		{{0}},//0,这个没用到
		{
			{declaration_list,0},{0}
		},//1
		{
			{declaration,_declaration_list},{0}
		},//2
		{
			//declaration
			{type_specifier,ID,_declaration,0},{0}//{var_declaration,0},{fun_declaration,0},{0}
		},//3
		{
			//var-declaration
			{SEMI,0},{LSQUARPAREN,NUM,RSQUARPAREN,SEMI,0},{0}
		},//4
		{
			//type-specifier
			{INT,0},{VOID,0},{0}
		},//5
		{
			//fun-declaration
			{LROUNDBRA,params,RROUNDBRA,compound_stmt,0},{0}
		},//6
		{
			{param_list,0},{VOID,0},{0}
		},//7
		{
			{param,_param_list,0},{0}
		},//
		{
			{type_specifier,ID,_param,0},{0}
		},//9
		{
			{LBRAC,local_declarations,statement_list,RBRAC,0},{0}
		},//10
		{
			{type_specifier,ID,var_declaration,_local_declarations,0},{NullToken,0},{0}
		},//
		{
			{statement,_statement_list,0},{NullToken,0},{0}
		},//12
		{
			//statement
			{expression_stmt,0},{compound_stmt,0},{selection_stmt,0},{iteration_stmt,0},{return_stmt,0},{0}
		},//
		{
			//expression_stmt
			{expression,SEMI,0},{SEMI,0},{0}
		},//14
		{
			//selection_stmt
			{IF,LROUNDBRA,expression,RROUNDBRA,statement,_selection_stmt,0},{0}
		},//
		{
			//iteration_stmt,
			{WHILE,LROUNDBRA,expression,RROUNDBRA,statement,0},{0}
		},//16
		{
			//return_stmt
			{RETURN,_return_stmt,0},{0}
		},//
		{
			{ID,_expression_ID,0},
			{NUM,_expression_call,0},
			{LROUNDBRA,expression,RROUNDBRA,_expression_call,0},
			{0}
		},//18
		{
			//var
			{ID,_var,0},{0}
		},//
		{
			//simple_expression
			{additive_expression,_simple_expression,0},{0}
		},//20
		{
			//relop
			{LTOREQ,0},{LT,0},{BI,0},{BIOREQ,0},{EQ,0},{NEQ,0},{0}
		},//
		
		{
			//additive_expression
			{term,_additive_expression,0},{0}
		},//22
		{
			//addop
			{PLUS,0},{MINUS,0},{0}
		},//
		{
			//term
			{factor,_term},{0}
		},//24
		{
			//mulop
			{TIMES,0},{OVER,0},{0}
		},//
		{
			//factor
			{LROUNDBRA,expression,RROUNDBRA,0},{ID,_val,0},{NUM,0},{0}//{ID,call,0},
		},//26
		{
			//call
			{LROUNDBRA,args,RROUNDBRA,0},{0}//{ID,LROUNDBRA,args,RROUNDBRA,0},{0}
		},//
		{
			//args
			{args_list,0},{NullToken,0},{0}
		},//28
		{
			//args-list
			{expression,_args_list,0},{0}
		},//
		{
			//_declaration
			{var_declaration,0},{fun_declaration,0},{0}
		},//30
		{
			{LSQUARPAREN,RSQUARPAREN,0},{NullToken,0},{0}
		},//
		{
			//_selection_stmt
			{NullToken,0},{ELSE,statement,0},{0}
		},//32
		{
			//_return_stmt
			{SEMI,0},{expression,SEMI,0},{0}
		},//33
		{
			//_var
			{LSQUARPAREN,expression,RSQUARPAREN,0},{NullToken,0},{0}
		},//34
		{
			//_simple_expression
			{relop,additive_expression,_simple_expression,0},{NullToken,0},{0}
		},//35
		{
			//_declaration_list
			{declaration,_declaration_list,0},{NullToken,0},{0}
		},//36
		{
			{COMA,param,_param_list,0},{NullToken,0},{0}
		},//
		{
			{type_specifier,ID,var_declaration,_local_declarations,0},{NullToken,0},{0}
		},//38
		{
			{statement,_statement_list,0},{NullToken,0},{0}
		},//
		{
		//	_additive_expression
			{addop,term,_additive_expression,0},{NullToken,0},{0}
		},//40
		{
			//_term
			{mulop,factor,_term,0},{NullToken,0},{0}
		},//
		{
			//_arg_list
			{COMA,expression,_args_list,0},{NullToken,0},{0}
		},//42
		{
			//_val
			{LSQUARPAREN,expression,RSQUARPAREN,0},{LROUNDBRA,args,RROUNDBRA,0},{NullToken,0},{0}
		},//43
		{
		//_op_but_assign
			{EQ,0},
			{NEQ,0},
			{LT,0},
			{LTOREQ,0},
			{BI,0},
			{BIOREQ,0},
			{PLUS,0},
			{MINUS,0},
			{TIMES,0},
			{OVER,0},{0}
		},//44
		{
		//_expression_ID
			{LSQUARPAREN,expression,RSQUARPAREN,_expression_var,0},
			{LROUNDBRA,args,RROUNDBRA,_expression_call,0},
			{ASSIGN,expression,0},
			{_op_but_assign,simple_expression,0},
			{NullToken,0},
			{0}
		},//45
		{
		//_expression_var
			{ASSIGN,expression,0},
			{_op_but_assign,simple_expression,0},
			{NullToken,0},{0}
		},//46
		{
		//_expression_call
			{_op_but_assign,simple_expression,0},
			{NullToken,0},{0}
		},//47
	};

	for(int i=1;i<NUM_NTERM+1;i++)
		for(int j=0;j<NUM_TERM+1;j++)
		//	for(int k=0;k<20;k++)
				M[i][j]=NonOp;//-1表示无操作
	for(i=0;i<NUM_NTERM+1;i++)
		for(int j=0;j<12;j++)
			for(int k=0;k<30;k++)
			{
				First[i][j][k]=V_shop;
				Follow[i][k]=NullToken;
				Exp[i][j][k]=Gram[i][j][k];
			}
	int p=_expression_call;
	p=	program;
	RootNode=NULL;
	GenFirst();
	GenFollow();
	GenParsingTable();
}
Parser::~Parser()
{
}
void Parser::Err()
{
	fprintf(listing,"Mission failed!\nSyntax Error at line %d\n",lineno);

	exit(1);
}
int Parser::IsTerm(int type)
{
	if(type>=1&&type<=50)
		return 1;
	else
		return 0;
}
int Parser::InFirst(int Count_NTerm,int Choice,int Token)
{
	for(int i=0;First[Count_NTerm][Choice][i];i++)
		if(Token==First[Count_NTerm][Choice][i])
			return 1;
	return 0;
}
void Parser::AddFirst(int Count_NTerm,int Choice,int Token)
{
	for(int i=0;First[Count_NTerm][Choice][i];i++)
		if(First[Count_NTerm][Choice][i]==Token)
			return;
	First[Count_NTerm][Choice][i]=Token	;
}
void Parser::GenFirst()
{
	int change=1;
//	int lock;//锁
	while(change)
	{
		change=0;
		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
			{
				int k=0;
				int Continue=1;
				while(Continue&&Exp[Count_NTerm][Choice][k])
				{
					if(IsTerm(Exp[Count_NTerm][Choice][k]))//是终结符
					{
						if( !InFirst(Count_NTerm,Choice,Exp[Count_NTerm][Choice][k]) )//不在原来first集合中
						{	
							change=1;
							AddFirst(Count_NTerm,Choice,Exp[Count_NTerm][Choice][k]);
						}
						Continue=0;
					}
					/*很有问题呀……*/
					else if(Exp[Count_NTerm][Choice][k]!=NullToken)//如果不是终结符，找每一个First元素
					{
						Continue=0;
						/*first集中的每个选项是和每个A->@对应的，检查每个选项可得A的所有first元素*/
						for(int FirstChoice=0;FirstChoice<12;FirstChoice++)
						{
							if(First[Exp[Count_NTerm][Choice][k]-OFFSET][FirstChoice][0])
							{
								if(InFirst(Exp[Count_NTerm][Choice][k]-OFFSET,FirstChoice,NullToken))//空字在first集合里
									Continue=1;
								for(int CurPos=0;First[Exp[Count_NTerm][Choice][k]-OFFSET][FirstChoice][CurPos];CurPos++)
								{
								//	if(!lock)//change的值没变过
									if(!InFirst(Count_NTerm,Choice,First[Exp[Count_NTerm][Choice][k]-OFFSET][FirstChoice][CurPos]) &&First[Exp[Count_NTerm][Choice][k]-OFFSET][FirstChoice][CurPos]!=NullToken)
									{
											change=1;
											//lock=1;//锁起来	
											AddFirst(Count_NTerm,Choice,First[Exp[Count_NTerm][Choice][k]-OFFSET][FirstChoice][CurPos]);
									}
								}
							}
						}
					}
					k++;
				}
				if(Continue &&!InFirst(Count_NTerm,Choice,NullToken))
				{
					change=1;
					AddFirst(Count_NTerm,Choice,NullToken);
				}
			}
	}
}
int Parser::InFollow(int Count_NTerm,int Token)
{
	for(int Pos=0;Follow[Count_NTerm][Pos]!=NullToken;Pos++)
		if(Token==Follow[Count_NTerm][Pos])
			return 1;
	return 0;
}

void Parser::AddFollow(int Count_NTerm,int Token)
{
	for(int Pos=0;Follow[Count_NTerm][Pos]!=NullToken;Pos++)
		if(Token==Follow[Count_NTerm][Pos])
			return;
	Follow[Count_NTerm][Pos]=Token;
}
int Parser::Have(int* list,int Token,int end)
{
	for(int i=0;list[i]!=end;i++)
		if(list[i]==Token)
			return 1;
	return 0;
}

void Parser::GenFollow()
{
	int change=1;
	int TempFirst[30];//Xi+1Xi+2……的first集合
	for(int i=0;i<30;i++)
		TempFirst[i]=0;
	AddFollow(1,V_shop);
	while(change)
	{
		change=0;
		int Continue=1;
		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
				for(int i=0;Exp[Count_NTerm][Choice][i];i++)
				{
					if(!IsTerm(Exp[Count_NTerm][Choice][i])&&Exp[Count_NTerm][Choice][i]!=NullToken)
					{