《LR(1)实验报告(附代码)12956.pdf》由会员分享，可在线阅读，更多相关《LR(1)实验报告(附代码)12956.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实验三 LR(1)分析法 实验学时：4 实验类型：验证 实验要求：必修 一、实验目的 构造 LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解 LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验内容 对下列文法，用 LR（1）分析法对任意输入的符号串进行分析：(产生式有误，进行修改)（1）E-E+T（2）E-ET（E-T）（3）T-T*F（4）T-T/F(T-F)（5）F-(E)（6）F-i 三、实验目的 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例：
2、输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串 输出过程如下：步骤 状态栈 符号栈 剩余输入串 动 作 1 0#i+i*i#移进 i+i*i 的 LR 分析过程 步骤 状态栈 符号栈 输入串 动作说明 1 0#i+i*i#ACTION0,i=S5,状态 5 入栈 2 05#i+i*i#r6:Fi 归约,GOTO(0,F)=3 入栈 3 03#F+i*i#r4:TF 归约,GOTO(0,T)=3 入栈 4 02#T+i*i#r2:ET 归约,GOTO(0,E)=1 入栈 5 01#E+i*i#ACTION1,+=S6,状态 6 入栈 6 016#E+i*i#ACTION6,i=
3、S5,状态 5 入栈 7 0165#E+i*i#r6:Fi 归约,GOTO(6,F)=3 入栈 8 0163#E+F*i#r4:TF 归约,GOTO(6,T)=9 入栈 9 0169#E+T*i#ACTION9,*=S7,状态 7 入栈 10 01697#E+T*i#ACTION7,i=S5,状态 5 入栈 11 016975#E+T*i#r6:Fi 归约,GOTO(7,F)=10入栈 12 0169710#E+T*F#r3:TT*F 归约,GOTO(6,T)=9入栈 13 0169#E+T#r1:EE+T,GOTO(0,E)=1 入栈 14 01#E#Acc：分析成功 实验报告正文的内容：描
4、述 LR(1)语法分析程序的设计思想:定义项目的一般形式是A,a1a2ak，这样的一个项目称为一个 LR(k)项目。项目中的 a1a2ak 称为它的向前搜索符串(或展望串)，令 K=1,即为 LR(1)语法分析程序。在此，重新定义CLOSURE(I)的算法：项目集 I 的闭包 CLOSURE(I)构造方法：1.I 的任何项目都属于 CLOSURE(I)。2.若项目AB,a属于 CLOSURE(I)，B 是一个产生式，那么，对于 FIRST(a)中的每个终结符b，如果B,b原来不在 CLOSURE(I)中，则把它加进去。3.重复执行步骤 2，直至 CLOSURE(I)不再增大为止。GO()的算法
5、保持与 LR 语法分析程序一样，通过以下方法构造文法分析表：动作 ACTION 和状态转换 GOTO 构造如下：1.若项目Aa,b属于 Ik且 GO(Ik,a)Ij，a 为终结符，则置 ACTIONk,a为“sj”。2.若项目A，a属于 Ik，则置 ACTIONk,a为“rj”；其中假定 A为文法 G的第 j 个产生式。3.若项目SS,#属于Ik，则置ACTIONk,#为“acc”。4.若 GO(Ik，A)Ij，则置 GOTOk,A=j。5.分析表中凡不能用规则 1 至 4 填入信息的空白栏均填上“出错标志”。当具体面对输入串时，通过查表进行分析该进行何种动作。程序结构描述：函数调用格式、参数
6、含义、返回值描述、函数功能均在程序源代码出注释出来，在此不再赘述，详细含义请参照源代码 cpp 文件。详细的算法描述（程序执行流程图）:(1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR 分析器由三个部分组成：其中:SP 为栈指针，Si为状态栈，Xi为文法符号
7、栈。状态转换表用 GOTOi，X=j 表示，规定当栈顶状态为 i，遇到当前文法符号为 X 时应转向状态 j，X 为终结符或非终结符。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 减去R，并把 A 移入文法符号栈内，j=GOTOi
8、,A移进状态栈，其中 i 为修改指针后的栈顶状态。(3)接受 acc:当归约到文法符号栈中只剩文法的开始符号 S 时，并且输入符号串已结束即当前输入符是#，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。四、实验要求 本程序原本的设计思想与实验二相仿，但由于此种设计思想会导致程序灵活性大大降低，故对设计思想进行优化，在此，不在对原程序设计思想进行阐述，仅对改良后的程序设计思想进行阐述。该文法的 LR(1)分析表：算术表达式文法的 LR 分析表 状 态 ACTION GOTO i+*()#E T F 0 S5 S4 1 2
9、 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 S7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 本程序根据给出的 LR(1)文法分析表，构造 string 类的action126=S5,0,0,S4,0,0,ength()-3;for(int j=0;jN;j+)t(0)=;(Productioni-1.at(0);t(0)=S)actionit.erase(0,1);_str(),s);_str()，将
10、 actionit转换为整型 actionit.insert(0,S);t(0)=r)actionit.erase(0,1);_str(),s);_str()，将actionit转换为整型 actionit.insert(0,r);/将 r 添加回actionit else if(actionit=0)couttErrorendl;break;else if(actionit=acc)Output(s);coutacct 分析成功endl;break;else if(flag=false)break;int main()string s;cout*LR(1)分析*endl;cout本分析文法产生式为endl;for(int j=0;j6;j+)coutProductionjendl;cout*LR(1)分析*endl;char T;do cout输入字符串s;/输入要分析的字符串 cout*现进行如下分析*endl;cout步骤t状态栈t符号栈t剩余输入串t动作说明endl;Analyse(s);count=0;/记录当前进行处理的输入字符串字符位置 line=1;/记录处理的步骤数 stacktd=#;StatusNumber=1;while(!()();while(!()();cout是否继续分析,Y 或 y 继续T;while(T=y|T=Y);return 0;