/*
* 文件名称: 语法分析
* 摘 要: 对任意输入LL(1)文法的分析表及字符串，本程序能自动判断所给字符串是
* 否为该文法的句子，并能给出分析过程。
*/
#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[i]=st.top();
st.pop();
}
for(i=j-1;i>=0;i--)
{
cout<<ch[i];
st.push(ch[i]);
}
}
bool find(char c,char array[]) //查找函数，返回布尔值
{
int i;
bool flag=false;
for(i=0;i<100;i++)
{
if(c==array[i])
flag=true;
}
return flag;
}
int location(char c,char array[]) //定位函数,指出字符所在位置
{
int i;
for(i=0;i<100;i++)
{
if(c==array[i])
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[i],Vt))
{ cout<<"输入字符串有误!请重新输入!"<<endl;
goto opt0;
break;}
}
stack <char> st;
st.push('#');
st.push(Vn[0]); //#与识别符号入栈
j=0;
h=1;
w=str[0];
cout<<"步骤 "<<"分析栈 "<<"剩余输入串 "<<" 所用产生式"<<endl;
opt1:
cout<<h<<" "; //显示步骤
h++;
showstack(st); //显示分析栈中内容
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();
}
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) //查找二维数组中的产生式
error();
else
{
string str0=M[p][q];
cout<<" "<<X<<"-->"<<str0<<endl; //显示对应的产生式
if(str0=="$")
goto opt1;
else
{length=str0.size(); //逆序进栈
for(m=length-1;m>=0;m--)
{
st.push(str0[m]);
}
goto opt1;
}
}
}
}
}
main()
{
int i,k,n,r;
char Vn[100],Vt[100],select;
string M[100][100];
cout<<"* 文件名称: 语法分析"<<endl;
cout<<"* 摘 要: 对任意输入LL(1)文法的分析表及字符串，本程序能自动判断所给字符串是"<<endl;
cout<<"* 否为该文法的句子，并能给出分析过程。"<<endl;
cout<<"*--------------------------------------------------------------------*"<<endl;
cout<<endl<<endl;
opt2:
cout<<"请输入非终结符个数:";
cin>>n;
cout<<"请输入各终结符(#号表示结束)Vt[i]:";
for(i=0;i<100;i++)
{
cin>>Vt[i];
if(Vt[i]=='#')
{
r=i;
break;
}
}
for (i=0;i<n;i++)
{
cout<<"请输入非终结符Vn["<<i<<"]:";
cin>>Vn[i];
cout<<"请输入此非终结符对应各终结符的产生式右部(null或NULL表示出错;$表示空串):";
for(k=0;k<=r;k++)
{
cin>>M[i][k];
}
}
opt3:
cout<<"请输入要分析的字符串，且以#结束:";
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;
}
