计科150201516010118李杰-编译原理试验四

河南工业大学实验报告课程名称 编译原理 一院 系 信息科学与工程学院姓 名 李杰 指导老师 阎娼 批改日期 实验项目实验四LR（1）分析法专业班级 计科F1505班 学号 201516010118 日期 2018.5.14 成绩 一.实验目的.掌握LR（1）分析法的基本原理.掌握LR（1）分析表的构造方法.掌握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#）：⑶输出过程如下：步骤状态栈符号栈剩余输入串动作10#i+i*i#移进(4)输入符号串为非法符号串(或者为合法符号串)备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为'分析出错”；若成功结束则写为“分析成功”。(2)在此位置输入符号串为用户自行输入的符号串。注意：1.表达式中允许使用运算符(+-*/)、分割符(括号)、字符i，结束符#；.如果遇到错误的表达式，应输出错误提示信息(该信息越详细越好)；.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；.可采用的其它的文法。三.实验过程Glr分析器由三个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器结构：其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i,X]=j表示，规定当栈顶状态为i,遇到当前文法符号为X时应转向状态j,X为终结符或非终结符。ACTION[i,a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：移进，归约，接受acc,出错0LR⑴语法分析程序的设计思想：定义项目的一般形式是[A-a-B，a1a2…ak],这样的一个项目称为一个LR(k)项目。项目中的a1a2…ak称为它的向前搜索符串(或展望串)，令K=1,即为LR(1)语法分析程序。在此，重新定义CLOSURE(I)的算法：项目集1的闭包CLOSURE(I)构造方法：.I的任何项目都属于CLOSURE(I)。.若项目用一a・B。，a］属于CLOSURE(I),B一己是一个产生式，那么，对于FIRST(pa)中的每个终结符b,如果［Bf-1,b］原来不在CLOSURE(I)中，则把它加进去。.重复执行步骤2,直至CLOSURE(I)不再增大为止。GO()的算法保持与LR语法分析程序一样，通过以下方法构造文法分析表：动作ACTION和状态转换GOTO构造如下：.若项目用一&-。'b］属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION［k,a］为“sj”。.若项目用一a-,a］属于Ik,则置ACTION［k,a］为“rj”；其中假定A-a为文法G的第j个产生式。.若项目£'-S-，划属于Ik,则置ACTION［k,#］为“acc”。.若GO(Ik,A)=Ij,则置GOTO［k,A］=j。.分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。当具体面对输入串时，通过查表进行分析该进行何种动作。设计思想的流程图为：Q该实验文法对应的LR⑴分析表状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5Q数据结构“ACTION表“ACTION表〃C〃 〃I-〃 〃I-〃 〃C〃 〃I-〃 〃I-〃10,r5,r5,0,r5,r5);intgotoarr[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}；charvt[6]={'i','+','*','(',')','#'}; //存放终结符charvn[3]={'E','T','F'}; //存放非终结符stringProduction[6]={〃E->E+T〃，〃E->T〃，〃T->T*F〃，〃T->F〃，〃F->(E)〃，〃F->i〃};〃产生式集合intcount=0;//记录当前进行处理的输入字符串字符位置intline=1;//记录处理的步骤数boolflag=false;intStatusNumber=1;//栈中状态数stringstacktd="#";//记录符号栈中内容intStatus[50]={0};//记录状态栈stack<char>Stack;//创建一个符号栈stack<int>status;//创建一个状态栈◎函数设计voidJudge(int&i,intj,chararr口，charch,strings)〃判断输入串是否由文法终结符组成voidOutputstatus()〃输出状态集voidOutputstring(strings)〃输出未处理的字符串voidOutput(strings)〃输出步骤、状态集、符号集、输入串voidShift(inti,strings)〃移进函数SvoidGoto(stack<int>st1,stack<char>st2,strings)//GoTo语句voidReduction(inti,strings)〃归约函数RvoidAnalyse(strings)〃具体分析函数G分析函数的具体实现voidAnalyse(strings){//具体分析函数Stack.push('#');//初始化status.push(0);s=s+〃#〃；intt=-1;//记录ch在数组vt的位置while(count<s.size()){inti=status.top();charch=s.at(count);Judge(t,6,vt,ch,s);if(flag==true){if(action[i][t]!="acc"&&action[i][t]!="0"){if(action[i][t].at(0)=='S'){

action[i][t].erase(0,1); 〃删除action[i][t]的首子母SShift(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str()),将action[i][t]转换为整型action[i][t].insert(0,"S");//将S添加回action[i][t]}elseif(action[i][t].at(0)=='r'){action[i][t].erase(0,1);//删除action[i][t]的首字母rReduction(atoi(action[i][t].c_str()),s);//atoi(action[i][t].c_str()),将action[i][t]转换为整型action[i][t].insert(0,"r");//将r添加回action[i][t]}}elseif(action[i][t]=="0"){cout<<"\tError”<<endl;break;}elseif(action[i][t]=="acc"){Output(s);cout<<"acc"<<"\t分析成功“<<endl;break;}}elseif(flag==false)break;}}07接受acc的情况m"E:\cod?blocks'漏评总理国驶四世i叭口phug香脸四,ese11505JJIR(L)分析程序，编制人：李杰.20151601011B.1505JJI迪示:轲星序只能游由JL)构成的字符串进行分析:口十i；呼ioo-ooo-o-o-o10111213141516171819o-5391_h_M0H6oo-ooo-o-o-o10111213141516171819o-5391_h_M0H6JI532nos88888444444444445771322n.oooo栈++i+F+T口「-.■4斗十4...JiF匚FiFTEEEEEEE*¥4fkfkfLfLFTT-TTTE■1■1-1■1+iDW>)+升粒1#讨避述#4力■1十■1B1■!!1\l...牛牛"1■!■!t—(-1++++■!-J4ff#rocessreturned0(OxD)execution动作KTIONC.|]=M,状态4A栈ACTION[4,1]=S5,状态5人栈r6:F->i归的，G口T口以FL?人袪i4:TCF归约,G口T口3,T)=2人栈虎:上”归约,GoT

ACTIONE8n-i：=S6,-hACTION[6,二]斐瓦伏否5人栈r日:F7i归约,GciT□®F)=W.榜r4：T-2归约三GciTog,T)=9人栈eLE->E+T归约，G口R@E：-E入栈ACnQN[&)]=S1L状态11人栈r5：”Mg归约.丘口丁口(。/1三3栈r4:T->F归为，GciTuCNT入栈ACTIONL2^.-S7,状态7人栈ACTION[7,i]=g[状态5人栈r6：F-：>i归约]GciTob.F)-]。入栈:r3:T->T*F•归约递:EQT归豹，@口T口&E)=l人栈acc 分析成功time：IE.S76s出错情况■"F：\codcHcck式编译案理庭晚四世in\Debugl实险叫ese,LR(1)jLR(1)jna，20151601011S,限示沐程序只能前由+ J),'i'构成的字符串进行分析剩余输入串树限示沐程序只能前由+ J),'i'构成的字符串进行分析剩余输入串树i十+1#率忖十+1#扇输入要分析的字符串d++iACTIQNE0,i］=S5n状态5人栈t$：F-：W¥勺，为T口QF)-认才玄r4:T-兄归阂，G口T口9T)=2人栈乩T［口机2产］=5/状态丫人栈time:time:6.128s四.实验总结(心得).实验体会通过本次实验，掌握YLR⑴分析法的基本原理和LR⑴分析表