a.cpp

编译原理语法分析(LL1文法) 编译原理语法分析(LL1文法)

#include<map>
#include<vector>
#include<string>
#define N 100
using namespace std;
map<string,int> ter;
map<string,int> unter;
string terminal[N];                         //终结符
string unterminal[N];                       //非终结符
char bnf[N][N]; 
char temp[N];
int M[N][N];
struct node{
	bool terminal;
	int id;
};
vector<node> lead[N];
node stack[N*10];
int top;                                      //栈顶
int main()
{
	int i=0,len,cntbnf,cntter,cntunter,t1,t2;
	bool flag=true;
	node newnode;
	string s1,s2;
	char c;
	ter.clear();
	unter.clear();
	memset(M,-1,sizeof(M));                  //置分析表所有项为error
	freopen("Unterminal.txt","r",stdin);
	i=0;
	while(scanf("%s",temp)!=EOF)              //输入非终结符
	{
	//	printf("%s\n",temp);
		unterminal[i]=temp;
		unter[unterminal[i]]=i++;
	}
	cntunter=i;
	freopen("Terminal.txt","r",stdin);
	i=0;
	while(scanf("%s",temp)!=EOF)              //输入终结符
	{
	//	printf("%s\n",temp);
		terminal[i]=temp;
		ter[terminal[i]]=i++;
	}
	cntter=i;
	freopen("Grammar.txt","r",stdin);
	i=0;
	while(scanf("%s",temp)!=EOF)            //输入产生式
	{
		s1=temp;
		t1=i;
		lead[t1].clear();
		len=strlen(temp);
		strcpy(bnf[i],temp);
		bnf[i][len++]=' ';
		bnf[i][len++]='-';
		bnf[i][len++]='>';
		scanf("%*s");
		c=getchar();
		while(c!='\n')
		{
			scanf("%s",temp);
			s2=temp;
			if(ter.find(s2)!=ter.end())
			{
				newnode.terminal=true;
				newnode.id=ter[s2];
			}
			else if(unter.find(s2)!=unter.end())
			{
				newnode.terminal=false;
				newnode.id=unter[s2];
			}
			lead[t1].push_back(newnode);
			bnf[i][len++]=' ';
			strcpy(bnf[i]+len,temp);
			len+=strlen(temp);
			c=getchar();
		}
	//	printf("%s\n",bnf[i]);
		++i;
	}
	cntbnf=i;
	freopen("analysis.txt","r",stdin);        
	while(scanf("%s",temp)!=EOF)              //输入分析表
	{
		s1=temp;
		scanf("%*s");
		scanf("%s",temp);
		s2=temp;
		scanf(" : %d",&M[unter[s1]][ter[s2]]);
	}
	freopen("token.txt","r",stdin);                          //输入记号流
	stack[0].terminal=true;
	stack[0].id=-1;
	stack[1].terminal=false;
	stack[1].id=0;
	top=1;
out:
	while(scanf("%s",temp)!=EOF)
	{
begin:;
		s1=temp;
		if(stack[top].terminal)
		{
		//	printf("%d %d\n",stack[top].id,ter[s1]);
			if(stack[top].id!=ter[s1])
			{
				printf("%s error\n",temp);
				flag=false;
			}
			else top--;
		}
		else
		{
			t1=stack[top].id;
			t2=ter[s1];
		//	printf("%d %s\n",t1,temp);
			if(M[t1][t2]==-1)
			{
				printf("error %s\n",temp);
				flag=false;
				goto out;
			}
			printf("%s\n",bnf[M[t1][t2]]);
			t1=M[t1][t2];
			len=lead[t1].size();
			--top;
			for(i=len-1;i>=0;--i)
			{
				if(lead[t1][i].terminal==true&&lead[t1][i].id==3)
					continue;
				stack[++top].id=lead[t1][i].id;
				stack[top].terminal=lead[t1][i].terminal;
			}
			goto begin;
		}
	}
	if(flag&&top==0)
		printf("Accept\n");
	else printf("Error\n");
	return 0;
}