实验三 LR(1)分析法
一、实验目的 构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
二、LR（1）分析法实验设计思想及算法
(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。
(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
LR分析器由三个部分组成：
其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：
(1)移进：
action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
(2)归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
三、程序结构描述
1、定义的变量
string action[12][6]={
{"s5","error","error","s4","error","error"},
{"error","s6","error","error","error","acc"},
{"error","r2","s7","error","r2","r2"},
{"error","r4","r4","error","r4","r4"},
{"s5","error","error","s4","error","error"},
{"error","r6","r6","error","r6","r6"},
{"s5","error","error","s4","error","error"},
{"s5","error","error","s4","error","error"},
{"error","s6","error","error","s11","error"},
{"error","r1","r7","error","r1","r1"},
{"error","r3","r3","error","r3","r3"},
{"error","r5","r5","error","r5","r5"}
};
string go[12][3]={
{"1","2","3"},
{"error","error","error"},
{"error","error","error"},
{"error","error","error"},
{"8","2","3"},
{"error","error","error"},
{"error","9","3"},
{"error","error","10"},
{"error","error","error"},
{"error","error","error"},
{"error","error","error"},
{"error","error","error"},
}; //初始化预测分析表
char Vt[6]={'i','+','*','(',')','#'}; 终结符表
string LR[6]={"E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"};//LR文法
stack<int>S; 状态栈
stack<char>X; 符号栈
char input[10]; 输入字符
2、定义的函数
int num(string s) 判断字符串中的数字
void print(int i,char*c) 剩余输入串的输出
int same(char a) 用于查找终结符
void analyse() 分析程序
四、程序源代码及运行结果
#include<iostream>
#include<stack>
#include <stdlib.h>
#include<string>
using namespace std;
//初始化预测分析表
string action[12][6]={
{"s5","error","error","s4","error","error"},
{"error","s6","error","error","error","acc"},
{"error","r2","s7","error","r2","r2"},
{"error","r4","r4","error","r4","r4"},
{"s5","error","error","s4","error","error"},
{"error","r6","r6","error","r6","r6"},
{"s5","error","error","s4","error","error"},
{"s5","error","error","s4","error","error"},
{"error","s6","error","error","s11","error"},
{"error","r1","r7","error","r1","r1"},
{"error","r3","r3","error","r3","r3"},
{"error","r5","r5","error","r5","r5"}
};
string go[12][3]={
{"1","2","3"},
{"error","error","error"},
{"error","error","error"},
{"error","error","error"},
{"8","2","3"},
{"error","error","error"},
{"error","9","3"},
{"error","error","10"},
{"error","error","error"},
{"error","error","error"},
{"error","error","error"},
{"error","error","error"},
};
char Vt[6]={'i','+','*','(',')','#'};//终结符表
string LR[6]={"E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"};//LR文法
stack<int>S; //状态栈
stack<char>X; //符号栈
char input[10]; //输入字符
int num(string s){ //判断字符串中的数字
int i;
string str="";
for(int j=0;j<s.length();j++){
if(s[j]>='0'&&s[j]<='9') str=str+s[j];
}
i=atoi(str.c_str());
return i;
}
void print(int i,char*c)//剩余输入串的输出
{
for(int j=i;j<10;j++)
cout<<c[j];
cout<<'\t';
}
int same(char a){ //用于查找终结符
for(int i=0;i<6;i++){
if (a==Vt[i]) return i;
}
}
///**********分析程序*******************
void analyse(){
bool flag=true; //循环条件
int step=1,point=0,state=0; //步骤、指针、状态
char ch1,ch2;
int m,n,l; //用于判断终结符,分析表,表达式右部的长度
string str1; //用于判断对应分析表中的符号
string str2="#",str3="0"; //记录符号栈的所有元素
cout<<"请输入要规约的字符串："<<endl;
cin>>input;
X.push('#');
S.push(0);
cout<<"步骤"<<'\t'<<"状态栈"<<'\t'<<"符号栈"<<'\t'<<"输入串 "<<'\t'<<"动作"<<endl;
cout<<step++<<'\t'<<str3<<'\t'<<str2<<'\t';
print(point,input);
cout<<"初始化"<<endl; //*************初始化
//************进入循环
while(flag){
state=S.top();
ch1=input[point];
m=same(ch1);
str1=action[state][m];
//***********移进动作
if(str1[0]=='s'){
n=num(str1);
S.push(n);
X.push(ch1);
str2=str2+ch1;
ch2=n+48;
str3=str3+ch2;
point++;
cout<<step++<<'\t'<<str3<<'\t'<<str2<<'\t';
print(point,input);
cout<<str1<<':'<<"移进"<<endl;
}
//**********归约动作
else if(str1[0]=='r'){
n=num(str1);
l=LR[n-1].length()-3;
for(int i=1;i<=l;i++) {S.pop();
str3=str3.substr(0,str3.length()-1);
X.pop();
str2=str2.substr(0,str2.length()-1);
}
X.push(LR[n-1][0]);
str2=str2+LR[n-1][0];
state=S.top();
if(LR[n-1][0]=='E'){S.push(num(go[state][0]));
ch2=num(go[state][0])+48;
str3=str3+ch2;
}
else if(LR[n-1][0]=='T'){S.push(num(go[state][1]));
ch2=num(go[state][1])+48;
str3=str3+ch2;
}
else if(LR[n-1][0]=='F') {S.push(num(go[state][2]));
ch2=num(go[state][2])+48;
str3=str3+ch2;
}
cout<<step++<<'\t'<<str3<<'\t'<<str2<<'\t';
print(point,input);
cout<<str1<<':'<<LR[n-1]<<"归约"<<endl;
}
//*********出错
else if(str1=="error"){
cout<<"ERROR"<<"程序错误，分析结束！！！"<<endl;
flag=false;
}
//**********分析成功
else if(str1=="acc"){cout<<"分析成功，终止程序"<<endl;
flag=false;
}
}
}
int main(){
analyse();
return 0;
}
测试：i*i+i
结果：
五、实验总结
此次课程设计中受益良多，从一开始的不知道从何入手，再到决定用的编程言、设计程序流程、调试，最后到程序运行成功。较好的文法分析器是功能全面的能自动构造其项目集和转换函数并构造分析表，然后进行分析的程序，但是实现LR（1）文法的自动分析程序对我来说很困难，最后决定直接输出分析表，而让程序实现对输入符号串的分析，在编程过程中也遇到了很多困难，如对某些终结符的动作或是规约函数的实现，最后通过请教同学和上网查找参考资料，都得到了解决。虽然我做的程序功能很简单，而且借鉴的地方不是很清楚具体细节，但是是我参与并动手了的成果，感觉很有收获。最后也感各位课设指导老师的悉心指导