operation.h

LL(1)文法分析过程的可视化及教学应用研究

#include <iostream>
#include <fstream>
#include <cassert>
#include <iomanip>
#include <cstdlib>
#include <ctime>



#define LEN 200
#define L_STR 10000


using namespace std;

typedef struct Node
{
	char letter;
	int tag;
	int nultag;
}charNode;

class CGram
{
public:
    CGram();
	CGram(char *str);
	void initial();
	void re_initial();
	void save_grammar(char *str);
	CString change();
	void opt_G();
	CString get_first();
	CString get_follow();
	CString get_select();
	void tag_mark();
	CString creat_s();

	int tag[10];

	char begin_ch;
	char first[LEN][LEN];
	char follow[LEN][LEN];
	char select[LEN][LEN];
	int n,fw;
	int count_first[LEN];
	int count_follow[LEN];
	int count_select[LEN];
	charNode G[LEN][LEN];

	int vn[256];
	int vt[256];

private:

	void del_G(int i);
	void insert_G(int i);
	void swap_G(int a,int b);
	void add_str(char str1[],char str2[],int p);

	void add_first(char vn,int i);
	void add_follow(char vn,int k);
	void first_addto_follow(char vn,int k);

	int judge[LEN][256];
	int r_vn[256];

	int num[256];
	int nulchar[256];
	int add_vn[256];

	int ud;
};

CGram::CGram()
{
	initial();
}


CGram::CGram(char *str)
{
	initial();
	save_grammar(str);
}


void CGram::initial()
{
	int t1,t2;
	fw=0;
	n=0;
	ud=0;
	begin_ch=0;
	for(t1=0;t1<256;t1++)
	{
		num[t1]=0;
		nulchar[t1]=0;
		r_vn[t1]=0;
		vn[t1]=0;
		vt[t1]=0;
		add_vn[t1]=0;
	}

    for(t1=0;t1<10;t1++)
	{
		tag[t1]=0;
	}

	for(t1=0;t1<LEN;t1++)
		for(t2=0;t2<256;t2++)
			judge[t1][t2]=0;

	for(t1=0;t1<LEN;t1++)
	{
		for(t2=0;t2<LEN;t2++)
		{
			G[t1][t2].letter=0;
			G[t1][t2].tag=0;
			G[t1][t2].nultag=0;
			first[t1][t2]=0;
			follow[t1][t2]=0;
			select[t1][t2]=0;
		}
		count_first[t1]=0;
		count_follow[t1]=0;
		count_select[t1]=0;
	}

	for(t1=0;t1<256;t1++)
	{
		if(t1>='A'&&t1<='Z')
			vn[t1]=1;
		else
			vt[t1]=1;
	}
}


void CGram::re_initial()
{
	int t1,t2;
	fw=0;
	ud=0;
	for(t1=0;t1<256;t1++)
	{
		num[t1]=0;
		nulchar[t1]=0;
		r_vn[t1]=0;
		vn[t1]=0;
		vt[t1]=0;
//		add_vn[t1]=0;
	}

	for(t1=0;t1<LEN;t1++)
		for(t2=0;t2<256;t2++)
			judge[t1][t2]=0;

	for(t1=0;t1<LEN;t1++)
	{
		for(t2=0;t2<LEN;t2++)
		{
			first[t1][t2]=0;
			follow[t1][t2]=0;
			select[t1][t2]=0;
		}
		count_first[t1]=0;
		count_follow[t1]=0;
		count_select[t1]=0;
	}

	for(t1=0;t1<256;t1++)
	{
		if(t1>='A'&&t1<='Z')
			vn[t1]=1;
		else
			vt[t1]=1;
	}
}



void CGram::save_grammar(char *str)
{
	int i,k,j,sign=0;

	for(i=0,k=0;str[k];k++,i++)
	{
		if(sign==0)
		{
		    if(str[k]=='\n'||str[k]=='\r'||str[k]==' ')
			{
			    i--;
			    continue;
			}
		    if(vn[str[k]]==0||str[k+1]!='-'||str[k+2]!='>')
			{
			    initial();
			    tag[1]=1;
			    break;
			}
	
		    G[i][0].letter=str[k];

			if(i==0)begin_ch=str[k];

            k=k+3;
	        sign=1;
		}
		
		if(str[k]==' ')
		{
			i--;
			continue;
		}

		if(str[k]=='\n'||str[k]=='\r'||str[k]=='\0')
		{
			initial();
			tag[1]=1;
			break;
		}

		sign=0;


		for(j=1;str[k]!='\n'&&str[k]!='\0';k++,j++)
		{

			if(str[k]=='#')
			{
				initial();
				tag[2]=1;
				return;
			}
			if(str[k]=='\r'||str[k]==' ')
			{
				j--;
				continue;
			}

			if(str[k]=='|')
			{

				if(str[k+1]=='\r'||str[k+1]=='\n'||str[k+1]==' '||str[k+1]=='|'||str[k+1]=='\0')
				{
					initial();
					tag[1]=1;
					return;
				}

				G[i][0].tag=j-1;
				i++;
				G[i][0]=G[i-1][0];
				j=0;
				continue;
			}			
			
			G[i][j].letter=str[k];
		}
		G[i][0].tag=j-1;
	}
	n=i;

    if(n==0)tag[1]=1;

	tag_mark();
	opt_G();

	for(k=0;k<256;k++)
	{
		if(vn[k]==2)
		{
			for(i=0;i<n;i++)
				if(G[i][0].letter==k)break;
			if(i>=n)
			{
				initial();
				tag[3]=1;
				break;
			}
		}
	}

	for(i=0;i<n;i++)
		for(j=2;j<=G[i][0].tag;j++)
			if(G[i][j].letter=='@')
			{
				initial();
				tag[1]=1;
				break;
			}

	for(i=0;i<n;i++)
		if(G[i][0].tag==0)
			tag[1]=1;

}


CString CGram::change()
{
	int sign,i,k,j,l,s,t,c,e;
	char arr[LEN][LEN]={0};
	int a[LEN]={0};

	CString tt,tttt;
	int ti,tj,tk,tsign;
	CString str,tc;

	get_first();
	get_follow();
	get_select();


	str="原文法为:\r\n";
		for(tk=0;tk<fw;tk++)
		{
			tsign=0;
			for(ti=0;ti<n;ti++)
			{
				if(G[ti][0].letter==follow[tk][0])
				{
					if(tsign==0)
					{
						tsign=1;
						str+="    ";
						str+=follow[tk][0];
						str+="->";
					}

					for(tj=1;tj<=G[ti][0].tag;tj++)
						str+=G[ti][tj].letter;
					str+='|';

				}
			}
			str=str.Left(str.GetLength()-1);
			str+="\r\n";
		}
	str+="\r\n";

	ud=1;
	while(ud&&tag[4]!=1&&tag[0]!=0)
	{

		ud=0;
		re_initial();
		tag_mark();
		opt_G();

	for(k=0;k<fw;k++)
		for(i=0;i<n;i++)
			if(G[i][0].letter==follow[k][0])
			{
				sign=0;
				for(s=0;s<k;s++)
					if(G[i][1].letter==follow[s][0])
					{
						for(t=0;t<n;t++)
						{
							if(G[t][0].letter==follow[s][0])
							{
								ud=1;
								sign=1;

								insert_G(i+1);
								if(t>i)t++;
								if(G[t][1].letter!='@')
								{
								    for(j=1;j<=G[t][0].tag;j++)
									    G[i+1][j]=G[t][j];
								
									for(j=2;j<=G[i][0].tag;j++)
										G[i+1][j+G[t][0].tag-1]=G[i][j];

   								    G[i+1][0].tag=G[t][0].tag+G[i][0].tag-1;
								}
							   else
							   {
									for(j=2;j<=G[i][0].tag;j++)
									G[i+1][j-1]=G[i][j];
								    G[i+1][0].tag=G[i][0].tag-1;
									
									if(G[i+1][0].tag==0)
									{
										G[i+1][0].tag=1;
										G[i+1][1].letter='@';
									}
							   }
							   
							   G[i+1][0].letter=follow[k][0];
							}
						}
						if(sign==1)
						{
							del_G(i);
						    i--;
						}


	tt="";
    tttt="";
	
		for(tk=0;tk<fw;tk++)
		{
			tsign=0;
			for(ti=0;ti<n;ti++)
			{
				if(G[ti][0].letter==follow[tk][0])
				{
					if(tsign==0)
					{
						tsign=1;
						tt+="    ";
						tt+=follow[tk][0];
						tt+="->";
					}

					for(tj=1;tj<=G[ti][0].tag;tj++)
						tt+=G[ti][tj].letter;
					tt+='|';

				}
			}
			tt=tt.Left(tt.GetLength()-1);
			tt+="\r\n";
		}

	tttt="用左部为";
	tttt+=follow[s][0];
	tttt+="的产生式的右部\r\n代换左部为";
	tttt+=follow[k][0];
	tttt+="的产生式右部中的";
	tttt+=follow[s][0];
	tttt+="\r\n文法变为:\r\n";

	str+=tttt+tt;
	str+="\r\n";




					}

				if(G[i][0].letter==G[i][1].letter)
				{	

					tc=G[i][0].letter;
					tc+="->";
					for(tj=1;tj<=G[i][0].tag;tj++)
						tc+=G[i][tj].letter;
					
					if(add_vn[G[i][0].letter]==0)
					{
					for(t=0;t<256;t++)
				        if(vn[t]==1)
						{
							vn[t]=2;
							add_vn[G[i][0].letter]=t;
							for(c=0;c<n;c++)
							{
								if(G[c][0].letter==G[i][0].letter&&G[c][0].letter!=G[c][1].letter)
								{
									if(G[c][1].letter=='@')
									{
									    G[c][0].tag=1;
										G[c][1].letter=t;
									}

									else
									{									
								    	G[c][0].tag++;
									    G[c][G[c][0].tag].letter=t;
									}
																		
									if(i==0)e=c;
								}
							}

							for(j=1;j<=G[i][0].tag;j++)
								G[i][j]=G[i][j+1];
							G[i][0].letter=t;
							G[i][G[i][0].tag].letter=t;

							if(i==0)
							    swap_G(i,e);

							G[n][0].letter=t;
							G[n][0].tag=1;
							G[n][1].letter='@';
							n++;
							tag_mark();

	tt="";
    tttt="";
	
		for(tk=0;tk<fw;tk++)
		{
			tsign=0;
			for(ti=0;ti<n;ti++)
			{
				if(G[ti][0].letter==follow[tk][0])
				{
					if(tsign==0)
					{
						tsign=1;
						tt+="    ";
						tt+=follow[tk][0];
						tt+="->";
					}

					for(tj=1;tj<=G[ti][0].tag;tj++)
						tt+=G[ti][tj].letter;
					tt+='|';

				}
			}
			tt=tt.Left(tt.GetLength()-1);
			tt+="\r\n";
		}

	tttt="引入新非终结符";
	tttt+=t;
	tttt+="\r\n消除";
	tttt+=tc;
	tttt+="的左递归\r\n";
	tttt+="文法变为:\r\n";

	str+=tttt+tt;
	str+="\r\n";



							break;
						}
						if(t>=256)
						{
					        tag[4]=1;
							return str;
						}
					}
					else
					{
					
					tc=G[i][0].letter;
					tc+="->";
					for(tj=1;tj<=G[i][0].tag;tj++)
						tc+=G[i][tj].letter;

						for(j=1;j<=G[i][0].tag;j++)
							G[i][j]=G[i][j+1];
						t=add_vn[G[i][0].letter];
						G[i][0].letter=t;
						G[i][G[i][0].tag].letter=t;
					tag_mark();



	tt="";
    tttt="";
		for(tk=0;tk<fw;tk++)
		{
			tsign=0;
			for(ti=0;ti<n;ti++)
			{
				if(G[ti][0].letter==follow[tk][0])
				{
					if(tsign==0)
					{
						tsign=1;
						tt+="    ";
						tt+=follow[tk][0];
						tt+="->";
					}

					for(tj=1;tj<=G[ti][0].tag;tj++)
						tt+=G[ti][tj].letter;
					tt+='|';

				}
			}
			tt=tt.Left(tt.GetLength()-1);
			tt+="\r\n";
		}

	tttt="用已经引入的新非终结符";
	tttt+=t;
	tttt+="\r\n消除";
	tttt+=tc;
	tttt+="的左递归\r\n";
	tttt+="文法变为:\r\n";

	str+=tttt+tt;
	str+="\r\n";



					}


				}
			}
   

	tag_mark();
    opt_G();