编译原理算符优先分析C++源代码.doc

(完整word版)编译原理算符优先分析C++源代码
算符优先分析器源代码：
#include<iostream>
#include<iomanip>
#define MAX 100
using namespace std;
struct Stack //符号栈
{
char data[MAX];
int top;
};
char Terminal[6]={';','(',')','a','+','#'}; //终结符集合
char Table[6][6]={ //算符优先关系表
{'>', '<', '>', '<', '>', '>'},
{'<', '<', '=', '<', '<', '!'},
{'>', '>', '>', '!', '>', '>'},
{'>', '>', '>', '!', '>', '>'},
{'<', '<', '>', '<', '>', '!'},
{'<', '<', '!', '<', '!', '='}
};
//判断是否为终结符，是返回其所在位置i，否则返回-1
int Is_Vt(char ch,char Terminal[6])
{
int i;
for(i=0;i<6;i++)
{
if(ch==Terminal[i]) //输入符为终结符
return i;
}
return -1;
}
//读入输入串，返回其长度
int Getchar(int length,char String[MAX])
{
int i;
cout<<"*****输入字符串的长度length=";
cin>>length;
cout<<endl<<"*****该输入串为：";
for(i=0;i<length;i++)
cin>>String[i];
return length;
}
void PrintStack(Stack &st, int top) //输出栈中的内容
{
for(int i=0;i<=top;i++)
cout<<st.data[i] << " ";
cout << "\t\t";
}
int main()
{
Stack st;
int length=0,Len,k;
char String[MAX],ch;
Len=Getchar(length,String); //获得输入串
int j=0;
ch=String[j]; //指向第一个输入符
st.top=0;st.data[st.top]='#'; //将‘#’入栈
cout<<endl<<"**************************分析过程**************************"<<endl;
cout<<"符号栈"<<setw(15)<<"当前符号"<<setw(15)<<"剩余输入串"<<setw(20)<<"移进或归约"<<endl; //输出格式
while(st.top!=1 || ch!='#')
{
if(Is_Vt(ch,Terminal)!=-1) //输入符为终结符
{
k=Is_Vt(ch,Terminal); //获取分析表Table的第二个下标
int m,t; //t指向终结符在栈中的位置
if(Is_Vt(st.data[st.top],Terminal)!=-1) //栈顶为终结符
{
m=Is_Vt(st.data[st.top],Terminal);//获取分析表Table的第一个下标
t=st.top;
}
else //栈顶为非终结符，看top-1
{
m=Is_Vt(st.data[st.top-1],Terminal);//获取分析表Table的第一个下标
t=st.top-1;
}
if(Table[m][k]=='<' || Table[m][k]=='=') //栈顶符号的优先级小于等于输入符号，压栈
{
PrintStack(st,st.top); //输出栈中内容
cout<<ch<<setw(10); //输出当前符号
for(int p=j+1;p<=Len;p++) //输出剩余输入串
cout<<String[p];
cout<<"\t\t\t"<<"移进"<<endl; //输出下一步进行的操作
st.top++;
st.data[st.top]=ch; //输入符移进栈中
j++;
ch=String[j]; //指向下一输入符

}
else if(Table[m][k]=='!') //两终结符的优先关系不确定
{
cout<<endl<<"***分析出错!***"<<endl;
return 0;
}
else //栈顶符号的优先级大于输入符，归约
{
int q; //表示分析表Table的行
if(Is_Vt(st.data[t-1],Terminal)!=-1) //终结符相邻符号也是终结符
{
q=Is_Vt(st.data[t-1],Terminal);//获得分析表Table的行
t=t-1; //获得分析表Table的列
}
else //t-1位置是一个非终结符
{
q=Is_Vt(st.data[t-2],Terminal);
t=t-2;
}
while(Table[q][m]!='<')
{
m=q;
if(Is_Vt(st.data[t-1],Terminal)!=-1) //终结符相邻符号也是终结符
{
q=Is_Vt(st.data[t-1],Terminal);//获得分析表Table的行
t=t-1; //获得分析表Table的列
}
else //t-1位置是一个非终结符
{
q=Is_Vt(st.data[t-2],Terminal);
t=t-2;
}
}
PrintStack(st,st.top);
cout<<ch<<setw(10);
for(int p=j+1;p<=Len;p++)
cout<<String[p];
cout<<"\t\t\t"<<"归约"<<endl;
st.top=t+1;
st.data[st.top]='N';
}
}
else
{
cout<<endl<<"***该输入串不是文法的句子!***"<<endl;
return 0;
}
}
PrintStack(st,st.top);
cout<<ch<<setw(10);
for(int p=j+1;p<=Len;p++)
cout<<String[p];
cout<<"\t\t\t"<<"接受"<<endl;
cout<<endl<<"***分析成功：该输入串是文法的句子!***"<<endl;
return 0;
}

运行结果：