实验三--LR分析法实验报告

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)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减

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

4、, 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 go123= 1,2,3, error,error,error, error,error,error, error,error,er

5、ror, 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 Vt6=i,+,*,(,),#; 终结符表string LR6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/LR文法stackS; 状态栈stackX; 符号栈char input10; 输入字符2、定义的函数int num(string s) 判断字符串中的数字void prin

6、t(int i,char*c) 剩余输入串的输出int same(char a) 用于查找终结符void analyse() 分析程序四、程序源代码及运行结果#include#include#include #includeusing namespace std;/初始化预测分析表string action126= 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,erro

7、r, 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 go123= 1,2,3, error,error,error, error,error,error, error,error,error, 8,2,3, error,error,error,

8、 error,9,3, error,error,10, error,error,error, error,error,error, error,error,error, error,error,error, ;char Vt6=i,+,*,(,),#;/终结符表string LR6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/LR文法stackS; /状态栈stackX; /符号栈char input10; /输入字符int num(string s) /判断字符串中的数字 int i; string str=; for(int j=0;j=0&sj=9) str=str+s

9、j; i=atoi(str.c_str(); return i;void print(int i,char*c)/剩余输入串的输出 for(int j=i;j10;j+) coutcj; coutt; int same(char a) /用于查找终结符for(int i=0;i6;i+)if (a=Vti) return i;/*分析程序*void analyse() bool flag=true; /循环条件 int step=1,point=0,state=0; /步骤、指针、状态 char ch1,ch2; int m,n,l; /用于判断终结符,分析表,表达式右部的长度string s

10、tr1; /用于判断对应分析表中的符号string str2=#,str3=0; /记录符号栈的所有元素cout请输入要规约的字符串：input;X.push(#);S.push(0);cout步骤t状态栈t符号栈t输入串 t动作endl;coutstep+tstr3tstr2t;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(

11、ch1);str2=str2+ch1;ch2=n+48;str3=str3+ch2;point+;coutstep+tstr3tstr2t;print(point,input);coutstr1:移进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;st

12、ate=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(gostate2);ch2=num(gostate2)+48;str3=str3+ch2;coutstep+tstr3tstr2t;print(point,input);coutstr1:LRn-1归约endl;/*出错else if(str1=error)coutERROR程序错误，分析结束！endl;flag=false;/*分析成功else if(str1=acc)cout分析成功，终止程序endl;flag=false;int main() analyse(); return 0; 测试：i*i+i结果：五、实验总结此次课程设计中受益良多，从一开始的不知道从何入手，再到决定用的编程言、设计程序流程、调试，最后到程序运行成功。较好的文法分析器是功能全面的能自动构造其项目集和转换函