#include<iostream>
#include<stdio.h>
#include <string>
#include <stack>

using namespace std;

void showstack(stack< char > st)
{
 int i,j;
 char ch[100];
 j=st.size();
 for(i=0;i<j;i++)
 {
        ch=st.top();
  st.pop();
 }
    for(i=j-1;i>=0;i--)
 {
  cout<<ch;
  st.push(ch);
 }
}
bool find(char c,char array[])                     //查找函數(shù)，返回布爾值
{ 
 int i;
    bool flag=false;
 for(i=0;i<100;i++)
 {
  if(c==array)
   flag=true;
 }
 return flag;
}
int location(char c,char array[])                  //定位函數(shù),指出字符所在位置
{
 int i;
 for(i=0;i<100;i++)
 {
  if(c==array)
   return i;
 }
}
void error()
{
   cout<<"                    出錯!"<<endl;
}
void analyse(char Vn[],char Vt[],string M[100][100])
{
   int i,j,m,p,q,length,t,h;
   char w,X;
   string str;
opt0:
   cin>>str;
   for(i=0;i<str.size();i++)
   {
    if(!find(str,Vt))
    {  cout<<"輸入字符串有誤!請重新輸入!"<<endl;
    goto opt0;
    break;}
   }
   stack <char> st;
   st.push('#');                                  
   st.push(Vn[0]);                  //#與識別符號入棧
   j=0;
   h=1;
   w=str[0];
   cout<<"步驟            "<<"分析棧                "<<"剩余輸入串           "<<" 所用產(chǎn)生式"<<endl;
opt1:
   cout<<h<<"                ";                    //顯示步驟
   h++;
   showstack(st);                                   //顯示分析棧中內(nèi)容
   cout<<"                      ";
    for(t=j;t<str.size();t++)
 {
  cout<<str[t];                              //顯示剩余字符串
 }
   X=st.top();                             //上托棧頂符號放入X
   st.pop();
    if(find(X,Vt)&& X!='#')
   {
    if(X==w)                                    //分析棧的棧頂元素和剩余輸入串的第一個元素相比較
    {     
     cout<<"                   "<<X<<"匹配"<<endl;
    j++;
     w=str[j];
     goto opt1;
    }
    else 
     error();//追查ZhuiCha.com網(wǎng)絡(luò)技術(shù) 版權(quán)所有
 }
   else 
   {
    if(X=='#')
    {
         if(X==w)
   { 
    cout<<"                    "<<"接受!"<<endl<<endl;       
   }
       else
    error();
    }
       else  
    {
       p=location(X,Vn);
          q=location(w,Vt);
    string S1("NULL"),S2("null");
         if(M[p][q]==S1 || M[p][q]==S2)                                             //查找二維數(shù)組中的產(chǎn)生式
          error();
          else
    {   
          string str0=M[p][q]; 
        cout<<"                  "<<X<<"-->"<<str0<<endl;       //顯示對應(yīng)的產(chǎn)生式
    if(str0=="$")
     goto opt1;
    else
    {length=str0.size();                                //逆序進(jìn)棧
            for(m=length-1;m>=0;m--)
      {
           st.push(str0[m]);
      }
           goto opt1;//追查ZhuiCha.com網(wǎng)絡(luò)技術(shù) 版權(quán)所有
    }
    }
    }
   }
}
//TianDiGe.com 天地格　 版權(quán)歸原作者所有
//TianDiGe.com 天地格　提示：
//本代碼為網(wǎng)絡(luò)轉(zhuǎn)載
//不保證完全編譯通過
//實際上 放置代碼的目的主要參考里面的數(shù)據(jù)結(jié)構(gòu)以及大體流程，代碼還是自己寫出來得好。

main()
{   
 int i,k,n,r;
    char Vn[100],Vt[100],select;
    string M[100][100];
    cout<<"* 文件名稱: 語法分析"<<endl;
    cout<<"* 摘    要: 對任意輸入LL(1)文法的分析表及字符串，本程序能自動判斷所給字符串是"<<endl;
       cout<<"* TianDiGe.com"<<endl;
    cout<<"*           否為該文法的句子，并能給出分析過程。"<<endl;
    cout<<"*--------------------------------------------------------------------*"<<endl;
    cout<<endl<<endl;
 opt2: 
 cout<<"請輸入非終結(jié)符個數(shù):";
 cin>>n;
 cout<<"請輸入各終結(jié)符(#號表示結(jié)束)Vt:";
 for(i=0;i<100;i++)
 {
  cin>>Vt;
  if(Vt=='#')
  {
   r=i;
   break;
  }
 }
    for (i=0;i<n;i++)
 {
  cout<<"請輸入非終結(jié)符Vn["<<i<<"]:";
  cin>>Vn;
        cout<<"請輸入此非終結(jié)符對應(yīng)各終結(jié)符的產(chǎn)生式右部(null或NULL表示出錯;$表示空串):"; 
  for(k=0;k<=r;k++)
  {
   cin>>M[k];
  }
 }
opt3:
    cout<<"請輸入要分析的字符串，且以#結(jié)束:";
    analyse(Vn, Vt, M);
    cout<<"             ************************請選擇***********************"<<endl;
    cout<<"                                  1: 輸入字符串"                  <<endl;
    cout<<"                                  2: 輸入新分析表"                <<endl;
    cout<<"                                  0: 退  出"                      <<endl;
opt4:
    cin>>select;
    switch(select)
 {
        case '1': {goto opt3;break;}
        case '2': {goto opt2;}
        case '0': {break;}
        default:  {cout<<"輸入錯誤!請重新選擇:"<<endl;
             goto opt4;
          break;}
 }
    return 0;
}