实验三--LR(1)分析法实验报告(共8页).docx

《实验三--LR(1)分析法实验报告(共8页).docx》由会员分享，可在线阅读，更多相关《实验三--LR(1)分析法实验报告(共8页).docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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,error, error,s6,error,error,error,acc, error,r2,s7,error,r2,r2, error,r4,r

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

5、rror,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 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) 判断字符串

6、中的数字void print(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,

7、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,error, 8,2,3, error

8、,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; /输入字符int num(string s) /判断字符串中的数字 int i; string str=; for(int j=0;j=0&sj

9、=9) str=str+sj; 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; /用于判断终结符,分析表,表达式

10、右部的长度string str1; /用于判断对应分析表中的符号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.pu

11、sh(n);X.push(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=s

12、tr2+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(gostate2);ch2=num(gostate2)+48;str3=str3+ch2;coutstep+tstr3tstr2t;print(point,input);coutstr1:LRn-1归约endl

13、;/*出错else if(str1=error)coutERROR程序错误，分析结束！endl;flag=false;/*分析成功else if(str1=acc)cout分析成功，终止程序endl;flag=false;int main() analyse(); return 0; 测试：i*i+i结果：五、实验总结此次课程设计中受益良多，从一开始的不知道从何入手，再到决定用的编程言、设计程序流程、调试，最后到程序运行成功。较好的文法分析器是功能全面的能自动构造其项目集和转换函数并构造分析表，然后进行分析的程序，但是实现LR（1）文法的自动分析程序对我来说很困难，最后决定直接输出分析表，而让程序实现对输入符号串的分析，在编程过程中也遇到了很多困难，如对某些终结符的动作或是规约函数的实现，最后通过请教同学和上网查找参考资料，都得到了解决。虽然我做的程序功能很简单，而且借鉴的地方不是很清楚具体细节，但是是我参与并动手了的成果，感觉很有收获。最后也感谢各位课设指导老师的悉心指导专心-专注-专业