/*
对下列文法，用LL（1）分析法对任意输入的符号串进行分析：
（1）E->TG
（2）G->+TG|-TG
（3）G->ε
（4）T->FS
（5）S->*FS|/FS
（6）S->ε
（7）F->(E)
（8）F->i
输出的格式如下：
(1)LL（1）分析程序，编制人：
(2)输入一以#结束的符号串(包括+-* /（）i#)：在此位置输入符号串
(3)输出过程如下：
步骤 分析栈 剩余输入串 所用产生式
1 E i+i*i# E->TG
(4)输入符号串为非法符号串(或者为合法符号串)
备注：
(1)在"所用产生式"一列中如果对应有推导则写出所用产生式；
如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为"分析出错"；
若成功结束则写为"分析成功"。
(2) 在此位置输入符号串为用户自行输入的符号串。
(3)上述描述的输出过程只是其中一部分的。
注意：1.表达式中允许使用运算符（+-* /）、分割符（括号）、字符i，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，
同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
*/
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int IsTerminal(char A) //判断是否为终结符，若是终结符，则返回1；
{ //若是非终结符，则返回0；否则，返回2.
if (A=='i'||A=='+'||A=='-'||A=='*'||A=='/'
||A=='('||A==')'||A=='#')
return 1;
else if(A=='E'||A=='G'||A=='T'||A=='S'||A=='F')
return 0;
else return 2;
}
string M(char A,char a) //分析表的矩阵表示
{
if(A=='E'&&a=='i') return "TG";
else if(A=='E'&&a=='(') return "TG";
else if(A=='G'&&a=='+') return "+TG";
else if(A=='G'&&a=='-') return "-TG";
else if(A=='G'&&a==')') return "e";
else if(A=='G'&&a=='#') return "e";
else if(A=='T'&&a=='i') return "FS";
else if(A=='T'&&a=='(') return "FS";
else if(A=='S'&&a=='+') return "e";
else if(A=='S'&&a=='-') return "e";
else if(A=='S'&&a=='*') return "*FS";
else if(A=='S'&&a=='/') return "/FS";
else if(A=='S'&&a==')') return "e";
else if(A=='S'&&a=='#') return "e";
else if(A=='F'&&a=='i') return "i";
else if(A=='F'&&a=='(') return "(E)";
else return "Error!";
}
int main() //主函数
{
stack<char> stk;
cout<<"LL（1）分析程序\n\n编制人：tenk QQ:448674216 "<<endl;
string In;
while(1)
{
cout<<"\n输入一以#结束的符号串(包括+-* /（）i#)：\n"<<endl;
cin>>In;
string str1=" ",str2;
int n=0;
char pre;
stk.push('#');
stk.push('E');
str2="#E";
cout<<"步骤\t\t"<<"符号栈\t\t"<<"输入串\t\t"<<"所用产生式"<<endl;
cout<<n<<"\t\t"<<str2<<"\t\t"<<In<<"\t\t"<<str1<<endl;
while(stk.top()!='#')
{
n++;
if(IsTerminal(stk.top())==0)//栈顶元素是非终结符
{
str1=M(stk.top(),In[0]);
pre=stk.top();
stk.pop();
str2.erase(str2.length()-1,1);
if (str1=="Error!") //出错
{
cout<<str1<<endl;
break;
}
else if(str1 != "e")
{
for(int i=str1.length()-1;i>=0;i--)
{stk.push(str1[i]);str2=str2+str1[i];}
}
cout<<n<<"\t\t"<<str2<<"\t\t"<<In<<"\t\t"<<pre<<"->"<<str1<<endl;
}
else if(IsTerminal(stk.top())==1)//栈顶元素是终结符
{
if(stk.top()==In[0])
{
stk.pop();
str2.erase(str2.length()-1,1);
In.erase(0,1);
cout<<n<<"\t\t"<<str2<<"\t\t"<<In<<"\t\t"<<" "<<endl;
}
else {cout<<"Error!"<<endl;break;}//出错
}
else {cout<<"Error!"<<endl;break;}//出错
}
if(stk.top()=='#'&&In[0]=='#')
cout<<"\n输入串为合法符号串！"<<endl;
else cout<<"\n输入串为非法符号串！"<<endl;
}
return 0;
}
