河南工业大学实验报告
课程名称 编译原理 _ 实验项目 实验四 LR(1)分析法 院 系 信息科学与工程学院 专业班级 计科F1505班 姓 名 李 杰 学 号 201516010118 指导老师 阎 娟 日 期 2018.5.14 批改日期 成 绩
一.实验目的
1．掌握LR(1)分析法的基本原理 2．掌握LR(1)分析表的构造方法 3．掌握LR(1)驱动程序的构造方法
二.实验内容及要求
构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
根据某一文法编制调试LR（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对LR（1）分析法的理解。 程序输入/输出示例：
对下列文法，用LR（1）分析法对任意输入的符号串进行分析：
（0）S’->E （1）E->E+T （2）E->E-T （3）E-> T （4）T->T*F （5）T->T/F （6）T->F （7）F->(E) （8）F->i 输出的格式如下：
(1)LR（1）分析程序，编制人：姓名，学号，班级 (2)输入一以#结束的符号串(包括+-*/（）i#)：在此位置输入符号串 (3)输出过程如下：
步骤 状态栈 符号栈 动作 剩余输入串 1
0 # i+i*i# 移进
(4)输入符号串为非法符号串(或者为合法符号串)
备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。 (2) 在此位置输入符号串为用户自行输入的符号串。
注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照； 4．可采用的其它的文法。
三.实验过程
1LR分析器由三个部分组成： ○
(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。 LR分析器结构： 输入串XXX…#
Xn n1 总控程序 输出
。 。
。 。
。 。 ACTION GOTO
X1 1 表 表
# 0
其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j
表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：移进，归约，接受acc，出错
2LR(1)语法分析程序的设计思想: ○
定义项目的一般形式是[A→·, a1a2…ak] ，这样的一个项目称为一个LR(k)项目。项目中的 a1a2…ak 称为它的向前搜索符串(或展望串)，令K=1,即为LR(1)语法分析程序。在此，重新定义CLOSURE(I)的算法：
项目集I 的闭包CLOSURE(I)构造方法： 1. I的任何项目都属于CLOSURE(I)。
2. 若项目[A→·B, a]属于CLOSURE(I)，B→ 是一个产生式，那么，对于FIRST(a) 中的每个终结符b，如果[B→·, b]原来不在CLOSURE(I)中，则把它加进去。
3. 重复执行步骤2，直至CLOSURE(I)不再增大为止。
GO()的算法保持与LR语法分析程序一样，通过以下方法构造文法分析表： 动作ACTION和状态转换GOTO构造如下： 1. 若项目[A→·a, b]属于Ik且GO(Ik, a)＝Ij， a为终结符，则置ACTION[k, a]为 “sj”。
2. 若项目[A→·，a]属于Ik，则置ACTION[k, a]为 “rj”；其中假定A→为文法G的第j个产生式。
3. 若项目[S→S·, #]属于Ik，则置ACTION[k, #]为 “acc”。 4. 若GO(Ik，A)＝Ij，则置GOTO[k, A]=j。
5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。 当具体面对输入串时，通过查表进行分析该进行何种动作。
设计思想的流程图为：
0，#分别入状态栈和符号栈 置ip指向w#的第一个符号 令s是状态栈栈顶， a是ip所指向的符号 是 action[s，a]=Ss’ 否 把a和s’分别推入符号栈和状态栈；使ip前进到下一个字符 action[s,a]=reduce A->β 是 否 分别从栈顶弹出|β|个符号，令s’是当前栈顶状态，把a和goto[s’,A]先后推入栈中，输出产生式A->β Action[A,a]=acc是 否 出错处理
结束
3该实验文法对应的LR(1)分析表 ○
状态 i 0 1 2 3 4 5 6 7 8 9 10 11 S5 S5 S5 S5 + S6 r2 r4 r6 S6 r1 r3 r5 * S7 r4 r6 S7 r3 r5 ACTION ( S4 S4 S4 S4 ) r2 r4 r6 S11 r1 r3 r5 # acc r2 r4 r6 r1 r3 r5 E 1 8 GOTO T 2 2 9 F 3 3 3 10 4数据结构 ○
string action[12][6]={\"S5\表 \"0\ \"0\ \"0\ \"S5\ \"0\ \"S5\ \"S5\ \"0\ \"0\ \"0\ \"0\
int gotoarr[12][3]={1,2,3, //GOTO表 0,0,0, 0,0,0, 0,0,0, 8,2,3, 0,0,0, 0,9,3, 0,0,10, 0,0,0, 0,0,0, 0,0,0, 0,0,0};
char vt[6]={'i','+','*','(',')','#'}; //存放终结符 char vn[3]={'E','T','F'}; //存放非终结符
string Production[6]={\"E->E+T\//产生式集合
int count=0;//记录当前进行处理的输入字符串字符位置 int line=1;//记录处理的步骤数 bool flag=false;
int StatusNumber=1;//栈中状态数
string stacktd=\"#\";//记录符号栈中内容 int Status[50]={0};//记录状态栈 stack 5函数设计 ○ void Judge(int &i,int j,char arr[],char ch,string s) //判断输入串是否由文法终结符组成 void Outputstatus() //输出状态集 void Outputstring(string s) //输出未处理的字符串 void Output(string s) //输出步骤、状态集、符号集、输入串 void Shift(int i,string s) //移进函数S void Goto(stack void Reduction(int i,string s) //归约函数R void Analyse(string s) //具体分析函数 6分析函数的具体实现 ○ void Analyse(string s){//具体分析函数 Stack.push('#');//初始化 s=s+\"#\"; int t=-1;//记录ch在数组vt的位置 while(count if(action[i][t]!=\"acc\"&&action[i][t]!=\"0\"){ if(action[i][t].at(0)=='S'){ status.push(0); } } } else if(flag==false) break; } action[i][t].erase(0,1); //删除action[i][t]的首字母S Shift(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str()) action[i][t].insert(0,\"S\");//将S添加回action[i][t] } action[i][t].erase(0,1);//删除action[i][t]的首字母r Reduction(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str())，将 action[i][t].insert(0,\"r\");//将r添加回action[i][t] }} ， 将 action[i][t]转换为整型 else if(action[i][t].at(0)=='r'){ action[i][t]转换为整型 else if(action[i][t]==\"0\"){ cout<<\"\Error\"< 7接受acc的情况 ○ 出错情况 四.实验总结（心得） 1.实验体会 通过本次实验，掌握了LR(1)分析法的基本原理和LR(1)分析表的构造方法，进一步加深了对于LR(1)分析法的理解与应用。程序中使用构造action[]及Goto[]表来存储LR(1)分析表的内容,对于不同的产生式，只需修改其对应的action表，Goto表，终结符及非终结符表即可，大大提高了程序分析的灵活性。 2.思考部分 此程序涉及的表达式并没有完全包括实验报告中给出的那9个表达式，做了一 点点的偷工减料，删去了E-E->T,T->T*F,应为如果加上这两个表达式的话，构造出来的项目太多，不便于在草稿纸上画出它的LR(1)项目集和转换函数，从而得到LR(1)分析表，望老师谅解。 因篇幅问题不能全部显示，请点此查看更多更全内容