#define N 100
#include<iostream.h>
#include<string.h>
#include<stdio.h>
 static char a[N];  /*存放輸入的語句*/
 static char str[N]; /*存放構成單詞符號的字符串*/
 static int b[N];
 static char copy[N][N];
 static char ch;
 static int i=0;
 static int j=0;
 static int m;
 static int n;
 int p;
 int h[14][14];
 int l[14][14];
struct list   //定義結點
{
  int data;
  list *next;
};
class stack//定義棧類
{
private:
list *ptr;
public:
stack()
{ ptr=NULL;
}
void push(int i);
int pop();
};
void stack::push(int x)
{   list *q=new list;
	q->data=x;
	q->next=ptr;
	ptr=q;
}
int stack:: pop()
{list *p;
int value;
value=ptr->data;
p=ptr;
ptr=ptr->next;
delete p;
return value;
}
//***************詞法分析程序***********************


 int word()
 {	 
  if((a[i]>=65&&a[i]<=90)||(a[i]>=97&&a[i]<=122))
  {/* 識別標識符和關鍵字*/
   ch=a[i];
   str[j]=ch;
   i++;
   j++;
  while((a[i]>=65&&a[i]<=90)||(a[i]>=97&&a[i]<=122 )||(a[i]>=48&&a[i]<=57))
   {ch=a[i];
   str[j]=ch;
   i++;
   j++;
   }
    if(a[i]!=' ')
    i--;/*使i回調*/
  if(strcmp(str,"if")==0||strcmp(str,"IF")==0)
  return(2);
  else if(strcmp(str,"then")==0||strcmp(str,"THEN")==0)
  return(3);
  else if(strcmp(str,"else")==0||strcmp(str,"ELSE")==0)
  return(4);
  else if(strcmp(str,"AND")==0||strcmp(str,"and")==0)
  return(5);
  else if(strcmp(str,"or")==0||strcmp(str,"OR")==0)
  return(6);
  else if(strcmp(str,"not")==0||strcmp(str,"NOT")==0)
  return(7);
  else return(1);
 } 
 else if(a[i]>=48&&a[i]<=57)
 {/*識別常數*/
   ch=a[i];
   str[j]=ch;
   i++;
   j++;
  while((a[i]>=48&&a[i]<=57)&&i<N)
   {
	ch=a[i];
   str[j]=ch;
   i++;
   j++;
   }
   if(a[i]!=' ')
   i--;
   return(8);
 }
 else if(a[i]=='<')
 {ch=a[i];
   str[j]=ch;
	 i++;
	 j++;
 if(a[i]=='=')
  {ch=a[i];
   str[j]=ch;
  return(10);
 }
 else
  { i--;
   return(9);
  }
} 
 else if(a[i]=='>')
 {ch=a[i];
   str[j]=ch;
	 i++;
	 j++;
 if(a[i]=='=')
  {ch=a[i];
   str[j]=ch;
  return(12);
 }
 else
  { i--;
   return(11);
  }
}
 else if(a[i]=='!')
 {ch=a[i];
   str[j]=ch;
	 i++;
	 j++;
 if(a[i]=='=')
  {ch=a[i];
   str[j]=ch;
  return(13);
 }
 else
  { i--;
   return(-1);
  }
}
else if(a[i]=='=')
 {ch=a[i];
   str[j]=ch;
	 i++;
	 j++;
 if(a[i]=='=')
  {ch=a[i];
   str[j]=ch;
  return(15);
 }
  else
  { i--;
   return(14);
  }
}
else if(a[i]=='(')
   {ch=a[i];
   str[j]=ch;
   return(17);
   }
 else if(a[i]==')')
   {ch=a[i];
   str[j]=ch;
  return(18);
   }
 else if(a[i]==' ')
 {
	 return(16);
 }
 else
	 return (-1);
}
int bn()
 { int k=0;
 while(k<strlen(a))
 {
 b[n]=word();
 if(b[n]==16)
 { i++;
   k=i;
   n--;
 }
 else if(b[n]!=-1)
 { 
   i++;
   k=i;
   strcpy(copy[n],str);
   cout<<str<<"<"<<b[n]<<">"<<"  ";
 }
 else
 {
  cout<<endl;
  cout<<"error！詞法分析器分析到第"<<n+1<<"個單詞符號這里發現錯誤！"<<endl;
  return (-1);
  break;
 }
  n++; 
for(m=0;m<N;m++)
 str[m]='\0';
 j=0;
 }
 }
//*****************語法分析程序*******************


 stack A,B;
 void inserth(int i,int j)
 {if(!h[i][j])
 {
  h[i][j]=1;
 A.push(h[i][j]);
 }
 }
void insertl(int i,int j)
 {if(!l[i][j])
 {
   l[i][j]=1;
  B.push(l[i][j]);
 }
 }
int sentence_judge()
{
 if(b[0]==2)
 {
	 if(b[1]==1)
 {
		 if(b[2]==3)
 {
			 if(b[3]==1)
 {
				 if(b[4]==14)
 {
					 if(b[5]==8)
 {
						 if(b[6]==4)
  {
							 if(b[7]==1)
 {
								 if(b[8]==14)
 {
									 if(b[9]==8)
    return (1);
 else 
   return (-1);
 }
 else 
    return (-1);
 }
else 
    return (-1);
 }
 else 
    return (-1);
 }
else 
    return (-1);
 }
else 
    return (-1);
 }
else 
   return (-1);
 }
else if((b[2]==9)||(b[2]==11)||(b[2]==15))
 {
			 if(b[3]==1)
 {
				 if(b[4]==3)
 {
					 if(b[5]==1)
 {
						 if(b[6]==14)
  {
							 if(b[7]==8)
 {
								 if(b[8]==4)
 {
									 if(b[9]==1)
  {
									 if(b[10]==14)
 	 {
									 if(b[11]==8)								 
                                    return (2);
 else 
   return (-1);
 }
 else 
   return (-1);
 }
 else 
   return (-1);
 }
 else 
    return (-1);
 }
else 
    return (-1);
 }
 else 
    return (-1);
 }
else 
    return (-1);
 }
else 
    return (-1);
 }
else 
   return (-1);
 }
 else 
    return (-1);
	 }
	 else 
		 return(-1);
 }
 else 
	 return(-1);
}
 void sentence()
 {
  char c[][N]={"S→if E then B else B","E→id1 A id2｜id1","A→<｜>｜==","B→id1=num"};
  char d[][N]={"S","E","A","B","if","then","else","id1","id2","<",">","==","=","num"};//非終結符4個，終結符10個
  char e[][N][N]={{"S","→","if","E","then","B","else","id1","=","num","#"},{"E","→","id1","A", "id2","｜","id1","#"},{"A","→","<","｜",">","｜","==","#"},{"B","→","id1","=","num","#"}};
  int  f[N][N];
  int  g[N][N];//存放關系，1代表＝關系，2代表<關系，3代表>關系
  int k,n;
  i=0;
  g[1][5]=1;g[2][8]=1;
  g[3][6]=1;g[4][2]=1;
  g[4][7]=2;g[5][3]=1;
  g[5][7]=2;g[6][3]=1;
  g[6][7]=2;g[7][2]=1;
  g[7][5]=3;g[7][9]=2;
  g[7][10]=2;g[7][11]=2;
  g[7][12]=1;g[8][5]=3;
  g[9][8]=3;g[10][8]=3;
  g[11][8]=3;g[11][13]=1;
  g[13][6]=3;
  cout<<"條件語句的文法如下："<<endl;
  for(i=0;i<4;i++)
	  cout<<c[i]<<endl;
  
  //**********求非終結符號的FIRST集和LAST集***************


   for(j=0;j<4;j++)
 {
	for(i=0;i<4;i++)
	{	if(strcmp(e[j][0],d[i])==0)
		for(k=0;k<14;k++)
				if(strcmp(e[j][2],d[k])==0)
           				inserth(i,k);
	}                                           
 }
 for(j=0;j<4;j++)
  {       
	  for(k=0;k<8;k++)
	  {
	  if(strcmp(e[j][k],"｜")==0)
	  {
	    for(i=0;i<4;i++)
		{	
			if(strcmp(e[j][0],d[i])==0)
		      for(m=0;m<14;m++)
			     if(strcmp(e[j][k+1],d[m])==0)
	                inserth(i,k+1);
		}
	 }				  
	 }
  }
    for(j=0;j<4;j++)
 {
	n=0;
	while(strcmp(e[j][n],"#")!=0)
		n++;
	for(i=0;i<4;i++)
	{	if(strcmp(e[j][0],d[i])==0)
		for(k=0;k<14;k++)
		{
			if(strcmp(e[j][n-1],d[k])==0)
           			insertl(i,k);
		}
	}
 }
 for(j=0;j<4;j++)
  {       
	  for(k=0;k<8;k++)
	  {
	  if(strcmp(e[j][k],"｜")==0)
	  {
	    for(i=0;i<4;i++)
		{	
			if(strcmp(e[j][0],d[i])==0)
		      for(m=0;m<14;m++)
			     if(strcmp(e[j][k-1],d[m])==0)
	                insertl(i,k-1);
		}
	 }				  
	 }
 }
 //*******************利用FIRST集和LAST集求出優先關系****************************


 for(j=0;j<4;j++)
 {
	 for(i=2;i<10;i++)
 {
		 if(strcmp(e[j][i],"｜")!=0&&strcmp(e[j][i+1],"｜")!=0&&strcmp(e[j][i+1],"#"))
		 {
			 for(k=0;k<14;k++)
		      if(strcmp(e[j][i],d[k])==0)
			   f[j][k]=1;
		 }
       	
	 }
 }
 cout<<"構造簡單優先關系表如下："<<endl;
 cout<<"    ";
 for(i=0;i<14;i++)
	 cout<<d[i]<<" ";
 cout<<endl;
 cout<<d[0]<<endl;
 cout<<d[1]<<"               "<<"="<<endl;
 cout<<d[2]<<"                            "<<"="<<endl;
 cout<<d[3]<<"                    "<<"="<<endl;
 cout<<d[4]<<"    "<<"="<<"                   "<<"<"<<endl;
 cout<<d[5]<<"      "<<"="<<"               "<<"<"<<endl;
 cout<<d[6]<<"      "<<"="<<"               "<<"<"<<endl;
 cout<<d[7]<<"     "<<"="<<"        "<<">"<<"              "<<"<"<<" "<<"<"<<" "<<"<"<<"  "<<"="<<endl;
 cout<<d[8]<<"              "<<">"<<endl;
 cout<<d[9]<<"                            "<<">"<<endl;
 cout<<d[10]<<"                            "<<">"<<"            "<<"="<<endl;
 cout<<d[11]<<"                           "<<">"<<endl;
 cout<<d[12]<<endl;
 cout<<d[13]<<"              "<<">"<<endl;
 if(sentence_judge()!=-1) //sentence_judge()進行規約
	 cout<<"輸入的句子符合語法要求！";
else
	 cout<<"輸入的句子不符合語法要求！";
}
//***********************中間代碼生成，輸出三地址碼*******************************


void code()
{ 
   if(sentence_judge()==1)
   {
	   cout<<"L1: "<<"if "<<copy[1]<<"   goto L2\n";
       cout<<"                   goto L3\n";
	   cout<<"L2: "<<copy[3]<<copy[4]<<copy[5]<<"\n";
	   cout<<"             goto Lnext\n"<<endl;
	   cout<<"L3: "<<copy[7]<<copy[8]<<copy[9]<<"\n";
	   cout<<"              goto Lnext\n"<<endl;
	  cout<<"Lnext:\n"<<endl;  
   }
   else
	   if(sentence_judge()==2)
	   {
       cout<<"L1:  if "<<copy[1]<<copy[2]<<copy[3]<<" goto L2\n";
	   cout<<"            goto L3\n"<<endl;
       cout<<"L2: "<<copy[5]<<copy[6]<<copy[7]<<"\n";
	   cout<<"         goto Lnext\n"<<endl;
       cout<<"L3: "<<copy[9]<<copy[10]<<copy[11]<<"\n";
	   cout<<"         goto Lnext\n"<<endl;
       cout<<"Lnext:\n "<<endl;
	   }
}
//******************************主函數*************************************


 int main()
{
 int value;
 cout<<"--------IF THEN ELSE-------"<<endl;
 cout<<"請輸入條件語句："<<endl;
 gets(a); /*輸入一個句子*/
 cout<<endl;
 cout<<"詞法分析分析出的單詞及其對應的編碼如下："<<endl;
 value=bn();
 cout<<endl<<endl;
 if(value!=-1)
 {
 sentence();
 }
 cout<<endl;
  if(sentence_judge()!=-1)
  {
	  cout<<"進行語義分析輸出的三地址碼如下："<<endl;
      code();
  }
return 0;
}