lalr.cpp

为L语言设计一个语法分析器。 读入源程序

		{
			if(p->data.sentence[0]>=0)
			{				
				first_set.Insert(p->data.sentence[0]);
				continue;
			}//end if
			else{										//A->X1…Xn的情况
				for(int i=0;p->data.sentence[i]!=END;i++)
				{
					temp.MakeEmpty();
					First(p->data.sentence[i],temp);
					mid=temp;
					if(p->data.sentence[i+1]!=END)	mid.Remove(0);
					first_set.Add(mid);					
					mid.MakeEmpty();
					if(temp.Contains(0)) continue;	
					else break;					
				}
			}//end else
		}
	for(p=gn_list.first;p;p=p->link)
	{
		if(p->data.vn==symbol&&p->data.sentence[0]==symbol){//考虑A->A…的情况
			if(first_set.Contains(0))
			{
				FirstX(p->data.sentence+1,mid);
				first_set.Add(mid);
				mid.MakeEmpty();
			}
		}
	}
	first_set.DelRepeated();
}
//---------------------------------------------------------------
//-------------------FIRSTX集------------------------------------
void CGRAMMAR::FirstX(int *array,List<int> &first_set)	//First(X1…Xn)
{
	first_set.MakeEmpty();
	if(*array==END) return;
	List<int> temp;
	First(*array,temp);
	if(!temp.Contains(0))
	{
		first_set.Add(temp);
		return;
	}
	temp.Remove(0);
	first_set.Add(temp);
	FirstX(array+1,first_set);
	first_set.DelRepeated();
}
//---------------------------------------------------------------
//-------------------打印分析表----------------------------------
void CGRAMMAR::PrintTable()								
{
	int i;
	ListNode<CItem> *p;
	ofstream ofstr("table.txt");
  	ofstr<<"LALR(1)分析表:\n";
	for(i=0;i<(vtnum+vnnum+1);i++)	ofstr<<"________";
	ofstr<<"__"<<endl;
	for(i=0;i<vtnum;i++)	ofstr<<"\t"<<Decode(vt[i]);
	ofstr<<"\t#";
	for(i=0;i<vnnum;i++)	ofstr<<"\t"<<Decode(vn[i]);
	ofstr<<endl;
	for(i=0;i<(vtnum+vnnum+1);i++)	ofstr<<"________";
	ofstr<<"__"<<endl;
	ListNode<CItem> *pItem;
	for(i=1;i<=state_queue.count;i++)
	{
		ofstr<<"I"<<i<<"\t";
		pItem=state_queue.queue[i].first;

//---------------------------ACTION部分-------------------------------
		for(int j=0;j<vtnum;j++)					
		{
			if(pItem->data.IsReduce()&&pItem->data.string.Contains(vt[j]))
				ofstr<<"r"<<rule_list.GetCode(pItem->data);
			for(p=convert_list.first;p;p=p->link)
				if(p->data.sentence[0]==vt[j]&&p->data.vn==i)				
					ofstr<<"s"<<p->data.sentence[1]-1;
			ofstr<<"  \t";
		}
		if(pItem->data.IsReduce()&&pItem->data.string.Contains(5))
		{
			if(pItem->data.IsAccept())	ofstr<<"acc";
			else ofstr<<"r"<<rule_list.GetCode(pItem->data);
		}
		//---------------------------------------------------
		for(j=0;j<vtnum;j++)					
		{
			action_new[i-1][j][0] = NULL;
			action_new[i-1][j][0] = '\0';
			if(pItem->data.IsReduce()&&pItem->data.string.Contains(vt[j]))
			{
				action_new[i-1][j][0] = 'r';
				action_new[i-1][j][1] = rule_list.GetCode(pItem->data)+'0';
				action_new[i-1][j][2] = '#';
				action_new[i-1][j][3] = '\0';
			}
			for(p=convert_list.first;p;p=p->link)
				if(p->data.sentence[0]==vt[j]&&p->data.vn==i)				
				{
					action_new[i-1][j][0] = 'S';
					action_new[i-1][j][1] = p->data.sentence[1]-1+'0';
					action_new[i-1][j][2] = '#';
					action_new[i-1][j][3] = '\0';
				}
		}
		if(pItem->data.IsReduce()&&pItem->data.string.Contains(5))
		{
			if(pItem->data.IsAccept())
				{
					action_new[i-1][j][0] = 'a';
					action_new[i-1][j][1] = 'c';
					action_new[i-1][j][2] = 'c';
					action_new[i-1][j][3] = '\0';
				}
			else 
				{
					action_new[i-1][j][0] = 'r';
					action_new[i-1][j][1] = rule_list.GetCode(pItem->data)+'0';
					action_new[i-1][j][2] = '#';
					action_new[i-1][j][3] = '\0';
				}
		}
	
//---------------------------GOTO部分----------------------------------

		for(j=0;j<vnnum;j++)						
		{
			for(p=convert_list.first;p;p=p->link)
				if(p->data.sentence[0]==vn[j]&&p->data.vn==i)			
					ofstr<<p->data.sentence[1]-1;
			ofstr<<"\t";
		}
		ofstr<<endl;
		//-------------------------------------------------
		for(j=0;j<vnnum;j++)						
		{
			goto_new1[i-1][j] = 0;
			for(p=convert_list.first;p;p=p->link)
				if(p->data.sentence[0]==vn[j]&&p->data.vn==i)			
					goto_new1[i-1][j] = p->data.sentence[1]-1;
		}
		ofstr<<endl;
	}//end for
	cout<<endl;
	cout<<"LALR(1)分析表已写入table表";
	cout<<endl;
	cout<<endl;
	for(i=0;i<(vtnum+vnnum+1);i++)	ofstr<<"________";
	ofstr<<"__"<<endl;
	ofstr<<"\n规则列表已经写入文件rule.txt中"<<endl;
	ofstr.close();
}
//---------------------------------------------------------------
//----------------------CGRAMMAR类END------------------------------
//---------------------------------------------------------------
	ofstream outFile("generate.txt");

//-----------------确定规约产生式的函数---------------------
searchRule(int h)
{
	int firstnum;
	char ch;
	ifstream fin("rule.txt",ios::nocreate);	
	if(!fin){
		cout<<"file not found!\n";
		exit(0);
	}
	if(!outFile){
		cerr<< "cannot" << endl;
		exit(1);
	}
	fin >> firstnum;
	//fin >> ch;
	//cout << ch;
	while(firstnum != h)
	{
		fin.get(ch);
		while(ch != '\n')
			fin.get(ch);
		fin >> firstnum;
	}
	outFile << firstnum;
	fin.get(ch);
	while(ch != '\n')
	{
		outFile << ch;
		fin.get(ch);
	}
	outFile << endl;
}

//----------------------主函数-----------------------------------
//---------------------------------------------------------------
void main()
{
	CGRAMMAR gra;									
	gra.ToItemSet();							
	gra.PrintDFA();								
	gra.PrintRuleTable();						
	gra.PrintTable();							
	char vt_new[25]={'a','b','c','d',';','=','t','f',':',',','i','r','l','k','m','n','z','y','j','p','q','[',']','#'};           /*存放终结符*/
	char vn_new[10]={'S','M','C','L','V','X','Y','J','E','K'};                       
	FILE*fp;
	int a[100];
	char b[100],c[100],c1;
	int top1,top2,top3,top,m,n;
	int g,h,i,j,k,l,p,y,z,count;
	char x,copy[100],copy1[100];
	char buf[100];
	int flag[20];
	for(int s = 0; s < 20; s++)
		flag[s] = 0;
	int control = 0;
	top1=0;top2=0;top3=0;top=0;
	a[0]=0;
	y=a[0];  
	b[0]='#';
	count=0;
	z=0;
	/*------------------------------------
	printf("请输入表达式(#结束):\n");
	do{
		scanf("%c",&c1);
//		cin>>c1;
		c[top3]=c1;
		top3=top3+1;
	}while(c1!='#');//将表达式存入输入串
	*///------------------------------------------------------
	if((fp = fopen("save.txt","r"))==NULL){cout<<"can not open file"<<endl;}
	while(fgets(buf,100,fp))
	{
		if(!strcmp(buf,"program\n"))c[top3++]='a';
		else
		if(!strcmp(buf,"begin\n"))c[top3++]='b';
		else
		if(!strcmp(buf,"end\n"))c[top3++]='c';
		else
		if(!strcmp(buf,"const\n"))c[top3++]='d';
		else
		if(!strcmp(buf,"int\n"))c[top3++]='i';
		else	
		if(!strcmp(buf,"array\n"))c[top3++]='n';
		else		
		if(!strcmp(buf,"real\n"))c[top3++]='m';
		else		
		if(!strcmp(buf,"boolean\n"))c[top3++]='l';
		else
			if(!strcmp(buf,"if\n")){c[top3++]='j';flag[control++] = 1;cout << endl << control-1 << "$$$$$$" << flag[control-1] << "$$$$$$$" << endl;}
		else
		if(!strcmp(buf,"true\n"))c[top3++]='t';
		else
		if(!strcmp(buf,"false\n"))c[top3++]='f';
		else
			if(!strcmp(buf,"while\n")){c[top3++]='j';flag[control++] = 0;cout << endl << control-1 <<"$$$$$$" << flag[control-1] << "$$$$$$$" << endl;}
		else
		if(!strcmp(buf,"then\n"))c[top3++]='p';
		else
		if(!strcmp(buf,"do\n"))c[top3++]='p';
		else
		if(!strcmp(buf,"for\n"))c[top3++]='u';
		else
		if(!strcmp(buf,"to\n"))c[top3++]='v';
		else
		if(!strcmp(buf,"+\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"-\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"*\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"\\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"<\n"))c[top3++]='y';
		else
		if(!strcmp(buf,">\n"))c[top3++]='y';
		else
		if(!strcmp(buf,">=\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"<=\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"==\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"and\n"))c[top3++]='y';
		else
		if(!strcmp(buf,"or\n"))c[top3++]='y';
		else
		if(!strcmp(buf,":=\n"))c[top3++]=':',c[top3++]='=';
		else
		if(buf[0] =='%')c[top3++]='k';
		else
	//	if(buf[0] =='0'|buf[0] =='1'|buf[0] =='2'|buf[0] =='3'|buf[0] =='4'
	//		|buf[0] =='5'|buf[0] =='6'|buf[0] =='7'|buf[0] =='8'|buf[0] =='9'|)
		if(buf[0] =='1'|buf[0] =='2'|buf[0] =='3'|buf[0] =='4'|buf[0] =='5'|buf[0] =='6'|buf[0] =='7'|buf[0] =='8'|buf[0] =='9')
		{
			int k=1;
			int tag=0;
			while(buf[k] != '#')
			{
				k++;
				if(buf[k]=='.')
				{
					tag=1;
					break;
				}
			}
			if(tag)
				c[top3++]='r';
			else
				c[top3++]='z';
		}
			else c[top3++]=buf[0];
		cout<<top3<<":"<<buf<<endl;
	}
//	c[top3++]='#';
	fclose(fp);

	//------------------------------------------------------
	cout<<endl;
	printf("步骤\t状态栈\t\t符号栈\t\t输入串\t\t\t\n");
//	cout<<"步骤"<<"    "<<"状态栈"<<"         "<<"符号栈"<<"         "<<"输入串"<<"         "<<"action"<<"         "<<"goto"<<endl;
	do{
		y=z;m=0;n=0;                      /*y,z指向状态栈栈顶*/
		g=top;j=0;k=0;

		x=c[top];//x为当前字符

		count++;
		printf("%d\t",count);//输出步骤数
//		cout<<count<<"      ";
		while(m<=top1)
		{                    /*输出状态栈*/
			printf("%d",a[m]);
//			cout<<a[m];
            m=m+1;
		}
		printf("\t\t");

		while(n<=top2)
		{                    /*输出符号栈*/
			printf("%c",b[n]);
//			cout<<b[n];
            n=n+1;
		}
		printf("\t\t");

		while(g<=top3){      /*输出输入串*/
			printf("%c",c[g]);
//			cout<<c[g];
            g=g+1;
		}
		printf("\t\t");

		while(x!=vt_new[j]&&j<=26) j++;
		if(j==24&&x!=vt_new[j])
		{ 
			printf("error:unidentified vt~\n");
//			cout<<"error"<<endl;
		    return;
		}
    //    if(action_new[y][j]==NULL){
	//		printf("error\n");
	//		return;
	//	}
		else
			strcpy(copy,action_new[y][j]);
		if(copy[0]=='S')
		{                      /*处理移进*/
			z=copy[1]-'0';
            top1=top1+1;
			top2=top2+1;
			a[top1]=z;
			b[top2]=x;
			top=top+1;
			i=0;
			while(copy[i]!='#')
			{
				//cout<<copy[i];
				i++;
			}
			//cout << z;
			cout<<endl;
		}
		if(copy[0]=='r')
		{                      /*处理归约*/
			i=0;
			while(copy[i]!='#')
			{
				//cout<<copy[i];
				i++;
			}
			h=copy[1]-'0';

			strcpy(copy1,LR_new[h-1]);
			while(copy1[0]!=vn_new[k]) k++;
			l=strlen(LR_new[h-1])-4;
			top1=top1-l+1;
			top2=top2-l+1;
			y=a[top1-1];
			p=goto_new1[y][k];
			a[top1]=p;
			b[top2]=copy1[0];
			z=p;
			cout<<"       ";
//			cout<<p<<endl;
			cout <<h;    //确定规约用的产生式 
			searchRule(h);
			cout<<endl;
		}

		if(copy[0]!='r'&&copy[0]!='S'&&copy[0]!='a')
		{
			cout<<"error"<<endl;
			return;
		}
	}
	while(strcmp(action_new[y][j],"acc"));
	cout<<"succeed!"<<endl;
	ofstream outFile1("flag.txt");
	if(!outFile1){
		cerr<< "cannot" << endl;
		exit(1);
	}
	//outFile1 << control << endl;
	for(int r = 0; r < control; r++)
		outFile1 << flag[r] << endl;
}
//------------------------主函数END------------------------------
//---------------------------------------------------------------