#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<string.h>
#include<stdio.h>
#define Q 20
#define N 7
#define M 6
#define P 4
int  table[M][N];     //表table和表content合起來為預測分析表
char content[N][P];     //存放預測分析表中用到的表達式,如'->TE'等

void inittable()     //初始化table表
{
	for(int i=1;i<M;i++)
		for(int j=1;j<N;j++)
			table[i][j]=-1;   //出錯位均為-1
		table[1][1]=table[1][4]=0;
		table[2][2]=1;
		table[3][1]=table[3][4]=2;
		table[4][3]=3;
		table[5][4]=4;
		table[5][1]=5;
		table[2][5]=table[2][6]=table[4][2]=table[4][5]=table[4][6]=6;
}
void initcontent()     //初始化產生式表
{
for(int i=0;i<N;i++)
  for(int j=0;j<P;j++)
	  content[i][j]='\0';
  content[0][0]='T';content[0][1]='S';content[0][2]='\0';      //S代替E'
  content[1][0]='+';content[1][1]='T';content[1][2]='S';content[1][3]='\0';
  content[2][0]='F';content[2][1]='Y';content[2][2]='\0';   //  Y代替T'
  content[3][0]='*';content[3][1]='F';content[3][2]='Y';content[3][3]='\0';
  content[4][0]='(';content[4][1]='E';content[4][2]=')';content[4][3]='\0';  
  content[5][0]='i';content[5][1]='\0';
  content[6][0]='$';content[6][1]='\0';       //$代表空串
}
int row(char ch)     //判斷字符所處的行號
{
	switch(ch){
	case 'E':return 1;
	case 'S':return 2;
	case 'T':return 3;
	case 'Y':return 4;
	case 'F':return 5;
	default :return 0;
}
}
int col(char ch)     //判斷字符所處的列號
{
	switch(ch){
	case 'i':return 1;
	case '+':return 2;
	case '*':return 3;
	case '(':return 4;
	case ')':return 5;
	case '#':return 6;
	default :return 0;
}
}
void analy(char *s)                //分析
{
	int p=0,cx=1,q;
	int i,j;
	char stack[M];      //分析棧
	inittable();       //初始化
	initcontent();     //初始化
	stack[p++]='#';stack[p++]='E';    //初始化堆棧
	while(s)
	{
		j=col(*s);
		i=row(stack[--p]);
		if(j==0)       //表明預測分析表中的列項中沒有該非終結符
		{
			cout<<cx<<"\t";
			int k=0;
			while(k<=p)
				cout<<stack[k++];
			cout<<"\t\t"<<s<<setw(25-strlen(s))<<*s<<"不是該文法的終結符!"<<endl;
			exit(1);
		}
		if(i==0)
		{          //說明是終結符
			if(stack[p]==*s)     //與棧頂元素匹配
			{
				cout<<cx++<<"\t";
				int k=0;
		  while(k<=p)
			  cout<<stack[k++];
		  if(*s=='#')      //是結束的符號
		  {
			  cout<<"\t\t"<<s<<setw(25-strlen(s))<<"接受!"<<endl;
			  exit(0); 
		  }
		  cout<<"\t\t"<<s<<setw(25-strlen(s))<<*s<<"匹配!"<<endl;
		  s++;   //輸入串自減
	  }
	  else {
		  cout<<cx<<"\t";     //說明是終結符,但不是該文法的終結符
		  int k=0;
		  while(k<=p)
			  cout<<stack[k++];
		  cout<<"\t\t"<<s<<setw(25-strlen(s))<<*s<<"不匹配!"<<endl;
          exit(1);
	  }
  }
  else if(table[i][j]==-1)   //分析表中沒有對照的項,表明出錯
  {
	  cout<<cx<<"\t";
	  int k=0;
	  while(k<=p)
		  cout<<stack[k++];
	  cout<<"\t\t"<<s<<setw(25-strlen(s))<<*s<<"不匹配!"<<endl;
	  exit(1);
  }
  else{q=table[i][j];
  cout<<cx++<<"\t";
  int k=0;
  while(k<=p)
	  cout<<stack[k++];
  cout<<"\t\t"<<s<<setw(25-strlen(s))<<stack[p]<<"->";
  k=0;
  while(content[q][k]!='\0')     //將表達式輸出
  {
	  cout<<content[q][k];
	  k++;
  }
  cout<<'\n';
  k--;
  if(content[q][k]!='$')         //將產生式入棧
	  for(;k>=0;k--)
		  stack[p++]=content[q][k];
  }
}
} 
void main()
{
	int flag=1;
	while(flag)
	{
		char *str,c;
		cout<<"......實驗二:LL(1)分析文法......\n給定的LL(1)文法為:\nE->E+T|T\nT->T*F|F\nF->i|(E)\n";
		cout<<"請輸入分析串:\n";
		str=new char[Q];
		cin>>str;  
		cout<<"步驟\t分析棧\t\t剩余輸入串\t\t所用產生式\n";
		analy(str);
		cout<<"繼續?(y/n)\n"<<endl;
		c=getchar();
		if((c=='y')||(c=='Y'))
			flag=1;
		else
			flag=0;
	}
	cout<<"其中S代表次E'，Y代表T'."<<endl;
}