实验三--LR(1)分析法实验报告

1、精选优质文档-倾情为你奉上实验三 LR(1)分析法一、实验目的 构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、LR（1）分析法实验设计思想及算法(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就

2、是由栈顶状态和当前输入符号所决定。u LR分析器由三个部分组成： u 其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi，X=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。u ACTIONi，a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进： actioni，a= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约：actioni，a=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去

3、掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。三、程序结构描述1、定义的变量string action126= "s5","error","error","s4","error",&quo

4、t;error", "error","s6","error","error","error","acc", "error","r2","s7","error","r2","r2", "error","r4","r4","error","r4",&qu

5、ot;r4", "s5","error","error","s4","error","error", "error","r6","r6","error","r6","r6", "s5","error","error","s4","error",&qu

6、ot;error", "s5","error","error","s4","error","error", "error","s6","error","error","s11","error", "error","r1","r7","error","r1&qu

7、ot;,"r1", "error","r3","r3","error","r3","r3", "error","r5","r5","error","r5","r5" ;string go123= "1","2","3", "error","error

8、","error", "error","error","error", "error","error","error", "8","2","3", "error","error","error", "error","9","3", "error",&

9、quot;error","10", "error","error","error", "error","error","error", "error","error","error", "error","error","error", ; /初始化预测分析表char Vt6='i','+',

10、9;*','(',')','#' 终结符表string LR6="E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"/LR文法stack<int>S; 状态栈stack<char>X; 符号栈char input10; 输入字符2、定义的函数int num(string s) 判断字符串中的数字void print(in

11、t i,char*c) 剩余输入串的输出int same(char a) 用于查找终结符void analyse() 分析程序四、程序源代码及运行结果#include<iostream>#include<stack>#include <stdlib.h>#include<string>using namespace std;/初始化预测分析表string action126= "s5","error","error","s4","error",&q

12、uot;error", "error","s6","error","error","error","acc", "error","r2","s7","error","r2","r2", "error","r4","r4","error","r4",&

13、quot;r4", "s5","error","error","s4","error","error", "error","r6","r6","error","r6","r6", "s5","error","error","s4","error",&

14、quot;error", "s5","error","error","s4","error","error", "error","s6","error","error","s11","error", "error","r1","r7","error","r1&

15、quot;,"r1", "error","r3","r3","error","r3","r3", "error","r5","r5","error","r5","r5" ;string go123= "1","2","3", "error","err

16、or","error", "error","error","error", "error","error","error", "8","2","3", "error","error","error", "error","9","3", "error"

17、,"error","10", "error","error","error", "error","error","error", "error","error","error", "error","error","error", ;char Vt6='i','+','*'

18、,'(',')','#'/终结符表string LR6="E->E+T","E->T","T->T*F","T->F","F->(E)","F->i"/LR文法stack<int>S; /状态栈stack<char>X; /符号栈char input10; /输入字符int num(string s) /判断字符串中的数字 int i; string str="

19、;" for(int j=0;j<s.length();j+) if(sj>='0'&&sj<='9') str=str+sj; i=atoi(str.c_str(); return i;void print(int i,char*c)/剩余输入串的输出 for(int j=i;j<10;j+) cout<<cj; cout<<'t' int same(char a) /用于查找终结符for(int i=0;i<6;i+)if (a=Vti) return i;/*分

20、析程序*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(

21、0);cout<<"步骤"<<'t'<<"状态栈"<<'t'<<"符号栈"<<'t'<<"输入串 "<<'t'<<"动作"<<endl;cout<<step+<<'t'<<str3<<'t'<<str2<<

22、9;t'print(point,input);cout<<"初始化"<<endl; /*初始化/*进入循环while(flag)state=S.top();ch1=inputpoint;m=same(ch1);str1=actionstatem;/*移进动作if(str10='s')n=num(str1);S.push(n);X.push(ch1);str2=str2+ch1;ch2=n+48;str3=str3+ch2;point+;cout<<step+<<'t'<<st

23、r3<<'t'<<str2<<'t'print(point,input);cout<<str1<<':'<<"移进"<<endl;/*归约动作else if(str10='r')n=num(str1);l=LRn-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(LRn-10);str2=str2+LRn-10;state=S.top();if(LRn-10='E')S.push(num(gostate0);ch2=num(gostate0)+48;str3=str3+ch2;else if(LRn-10='T')S.push(num(gostate1);ch2=num(gostate1)+48;str3=str3+ch2;else if(LRn-10='F') S.push(num(