doc.cpp

递归子程序法：对应每个非终结符语法单元编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始

#include<stdio.h>
#include<malloc.h>
#include<iostream.h>
#include<string.h>
#include"DOC.h"
/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
void create(stack &s)
{
	s.base=0;
	s.top=0;
}
void push(stack &s,char &p,char &a)
{
	s.array[s.top++] = p;
	s.array[s.top++] = a;
}
void push(stack &s,char &p)
{
	s.array[s.top++] = p;
}
void pop(stack &s,char &q)
{
	q = s.array[--s.top];
}
void pop(stack &s,char &q,char &a)
{
	a= s.array[--s.top];
	q = s.array[--s.top];
}
bool Empty(stack &s)
{
	if(s.top<=s.base)return true;
	else return false;
}
////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////
void InitializeVn()
{
	printf("请输入非终结符:");
	int i=0;
	char ch;   
	char temp[20];
	while((ch=getchar())!='\n')
	{
		temp[i]=ch;
		++i;
	}
	for(int j=0;j<i;j++)
	{
		Vn[j]=temp[j];
	}
	VnNum=i;
}
void InitializeVt()
{
	printf("请输入终结符:");
	int i=0;
	char ch;  
	char temp[20];
	while((ch=getchar())!='\n')
	{
		temp[i]=ch;
		++i;
	}
	for(int j=0;j<i;j++)
	{
		Vt[j]=temp[j];
	}
	VtNum=i;
}
void GetRule()
{
	printf("请输入文法个数:");
	cin>>rule_num;
	for(int i=0;i<rule_num;i++)
	{
		printf("请输入文法%d ",i);
		int count=0;
	    char ch;  
	    char temp[20];
	    while((ch=getchar())!='\n')
		{
			if(ch=='-')
			{
				ch=getchar();
				if(ch=='>')
				{
					ch=getchar();
				}
			}
			temp[count]=ch;
			count++;
		}
		rule[i].pLeft=temp[0];
		rule[i].pRightSize=count-1;
		for(int j=1;j<count;j++)
		{
			rule[i].pRight[j-1]=temp[j];
		}
		if(count==2)
		{
			rule[i].pRight[j]='$';//将$添加到对应的规则右部尾部
		}
	}
}
/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
int FindVnIndex(char a)
{
	int index=0;
	bool flag=false;
	for(int j=0;j<VnNum;j++)
	{
		if(Vn[j]==a)
		{
			flag=true;
		}
	}
	if(flag)
	{
		for(int i=0;i<VnNum;i++)
		{
			if(Vn[i]==a)
			{
				index=i;
			}
		}
	}
	else{index=-1;}
	return index;
}
int FindVtIndex(char a)
{
	int index=0;
	bool flag=false;
	for(int j=0;j<VtNum;j++)
	{
		if(Vt[j]==a)
		{
			flag=true;
		}
	}
	if(flag)
	{
		for(int i=0;i<VtNum;i++)
		{
			if(Vt[i]==a)
			{
				index=i;
			}
		}
	}
	else{index=-1;}
	return index;
}
void InsertF(stack &s,char &p,char &a)
{
	int p1=FindVnIndex(p);
	int a1=FindVtIndex(a);
	if(!F[p1][a1])
	{
		F[p1][a1] = true;
		push(s,p,a);
	}
}
void InsertL(stack &s,char &q,char &a)
{
	int q1=FindVnIndex(q);
	int a1=FindVtIndex(a);
	if(!L[q1][a1])
	{
		L[q1][a1] = true;
		push(s,q,a);
	}
}
void FirstVT(stack &s)
{
	char a0,a1;// 第一,第二,规则左部
	for(int i=0; i<VnNum; i++)
	{
		for(int j=0; j<VtNum; j++)
		{
			F[i][j] = false;
		}
	}
	for(int a=0; a<rule_num; a++)
	{
		a0=rule[a].pRight[0];
		a1=rule[a].pRight[1];
		if(a1=='$'&&FindVnIndex(a0)!= -1)//满足"A$"形式
		{
			continue;
		}
		else if(FindVtIndex(a0)!= -1)//存在此非终结符
		{
			InsertF(s,rule[a].pLeft, a0);
			continue;//结束这次循环
		}
		else if(FindVnIndex(a0) != -1 && FindVtIndex(a1) != -1)//满足(Ba.....)
		{
			InsertF(s,rule[a].pLeft,a1);
		}
	}
	while(!Empty(s))
	{
		char q, a;
		pop(s,q, a);
		for(i=0; i<rule_num; i++)
		{
			if(rule[i].pRight[0]  == q)
			{
				InsertF(s,rule[i].pLeft, a);
			}
		}
	}
}
void LastVT(stack &s)
{
	char a0,a1;
	for(int i=0; i<VnNum; i++)
	{
		for(int j=0; j<VtNum; j++)
		{
			L[i][j] = false;
		}
	}
	for(int a=0; a<rule_num; a++)
	{
		a0=rule[a].pRight[rule[a].pRightSize-1];
		a1=rule[a].pRight[rule[a].pRightSize-2];
		if(a0=='$'&&FindVnIndex(a1)!=-1)//满足(A$)形式
		{
			continue;
		}
		else if(FindVtIndex(a0) != -1)
		{
			InsertL(s,rule[a].pLeft, a0);
			continue;//结束这次循环
		}	
		else if(FindVnIndex(a0) != -1 &&FindVtIndex(a1) != -1)//满足(....aC形式)
		{
			InsertL(s,rule[a].pLeft, a1);
		}
	}
	while(!Empty(s))
	{
		char q, a;		
		pop(s,q,a);
		for(i=0; i<rule_num; i++)
		{
			if(rule[i].pRight[rule[i].pRightSize-1]  == q)
			{
				InsertL(s,rule[i].pLeft, a);
			}
		}
	}
}
//////////////////////////////////////////////////////////////////////////////////////
void DisplayFirstVT()
{
	char p, a;
	int row = VnNum;
	int col = VtNum;
	cout<<"FirstVT"<<"\n";
	for(int i=0; i<row; i++)
	{
		p = Vn[i];
		cout<<p<<"{";
		for(int j=0;j<col;j++)
		{
			if(F[i][j])
			{
				a=Vt[j];
				cout<<" "<<a<<" ";
			}
		}
		cout<<"}"<<'\n';
	}
}
void DisplayLastVT()
{
	char p, a;
	int row = VnNum;
	int col = VtNum;
	cout<<"LastVT"<<"\n";
	for(int i=0; i<row; i++)
	{
		p = Vn[i];
		cout<<p<<"{";
		for(int j=0;j<col;j++)
		{
			if(L[i][j])
			{
				a=Vt[j];
				cout<<" "<<a<<" ";
			}
		}
		cout<<"}"<<"\n";
	}
}
/*void DisplayTable()//显示除算符优先表
{
	printf("算符优先表");
	int row = VnNum;
	int col = VtNum;
	for(int i=0;i<col;i++)
	{
		cout<<"----+";
	}

	for(int j=0;j<col;j++)
	{
		cout<<" "<<Vt[j]<<"  |";
	}
}*/
//////////////////////////////////////////////////////////////////////////////////////
void Initialize()
{
	InitializeVn();
	InitializeVt();
	GetRule();
}
void OPT()
{
	for(int a=0;a<rule_num;a++)
	{
		for(int b=0;b<rule[a].pRightSize-1;b++)
		{
			char xa = rule[a].pRight[b];
			char xa1 =rule[a].pRight[b+1];
			int pxa = FindVtIndex(xa);
			int pxa1 =FindVtIndex(xa1);
		    if(pxa != -1 && pxa1 != -1)//xa,xa1为终结符(相邻为终结符则"=")
			{
				if(table[pxa][pxa1] == 0)
				{
					table[pxa][pxa1] = '=';
				}
				else
				{
					printf("不是算符优先文法");
					return;
				}
				continue;
			}
			if(b+2 < rule[a].pRightSize)//xa,xa2为终结符(形如aBb则"=")
			{
				char xa2 = rule[a].pRight[b+2];
				int pxa2 = FindVtIndex(xa2);
				if(pxa != -1 && pxa1 == -1 && pxa2 != -1)
				{
					if(table[pxa][pxa2] == 0)
					{
						table[pxa][pxa2] = '=';
					}
					else
					{
						printf("不是算符优先文法");
						return;
					}
				}
			}
			if(pxa != -1 && pxa1 == -1)//xa为终结符,xa1为非终结符
			{
				pxa1 = FindVnIndex(xa1);
				for(int k=0; k<VtNum; k++)
					if(F[pxa1][k])//非终结符xa1<FIRSTVT(xa) 
					{
						if(table[pxa][k] == 0)
							table[pxa][k] = '<';
						else
						{
							printf("不是算符优先文法");
							return;
						}
					}
				continue;
			}
			
			if(pxa== -1 && pxa1 != -1)//xa为非终结符,xa1为终结符
			{
				pxa = FindVnIndex(xa);
				for(int k=0; k<VtNum; k++)
				{
					if(L[pxa][k])
					{
						if(table[k][pxa1] == 0)
							table[k][pxa1] = '>';
						else
						{
							printf("不是算符优先文法");
							return;
						}
					}
				}
			}
		} 
	}
}

void Analyse()//分析规约(下推栈实现)
{
	printf("以下是分析过程:");
	printf("\n");
	char sym;//当前读入的字符
	int k=1;
	mstack[k]='#';
	int position=0;//当前字符位置
	int j=0;
	char Q;
	do
	{
		sym=Input[position];	
		if(FindVtIndex(mstack[k])!=-1)//存在终结符
		{
			j=k;
		}
		else
		{
			j=k-1;
		}
		while(table[FindVtIndex(mstack[j])][FindVtIndex(sym)]=='>')
		{
			do
			{
				Q=mstack[j];
				if(FindVtIndex(mstack[j-1])!=-1)
				{
					j=j-1;
				}
				else
				{
					j=j-2;
				}
			}while(table[FindVtIndex(mstack[j])][FindVtIndex(Q)]=='='||table[FindVtIndex(mstack[j])][FindVtIndex(Q)]=='>');
			for(int b=j+1;b<=k;b++)//把S[j+1]…S[k]归约为某个N
			{
				cout<<mstack[b]<<" ";
				mstack[b]='\0';
			}
			cout<<"规约为N"<<"\n";
			k=j+1;
			mstack[k]='N';
		}
		if(table[FindVtIndex(mstack[j])][FindVtIndex(sym)]=='<'||table[FindVtIndex(mstack[j])][FindVtIndex(sym)]=='=')
		{
			k=k+1;
			mstack[k]=sym;
			position++;
			cout<<sym<<"移进"<<"\n";
			if(table[FindVtIndex(mstack[j])][FindVtIndex('#')]=='=')
			{
				cout<<"输出正常!"<<"\n";
			}
		}
		else
		{
			cout<<"出错,规约失败!";
			break;
		}
	}while(sym!='#');
	if(mstack[2]=='N')
	{
		cout<<"规约成功!";
	}
}
///////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
void main()
{
	Initialize();
	stack s;
	create(s);
	FirstVT(s);
	DisplayFirstVT();
////////////////////////
	stack temp;
	create(temp);
	LastVT(temp);
	DisplayLastVT();
///////////////////////
	OPT();
///////////////////////
	memset(mstack,'\0',100);
	printf("请输入要分析的子句:");
	int a=0;
	char ch;
	while((ch=getchar())!='\n')//放入字符串数组中
	{
		Input[a]=ch;
		a++;
	}
	InputSize=a;//输入字符串个数
	Analyse();
	cout<<"\n";
	for(int i=0;i<VnNum;i++)
	{
		for(int j=0;j<VtNum;j++)
		{
			cout<<"["<<Vn[i]<<","<<Vt[j]<<"]"<<"="<<table[i][j]<<"  ";
		}
		cout<<"\n";
	}
}