《SLR文法分析实验报告.docx》由会员分享，可在线阅读，更多相关《SLR文法分析实验报告.docx（29页珍藏版）》请在课桌文档上搜索。
1、目录1设计的目的与内容11.1课程设计的目的11.2设计内容11.3设计要求11.4理论基础12算法的基本思想22.1主要功能函数22.2算法思想3SLR文法构造分析表的主要思想：3解决冲突的方法：3SLR语法分析表的构造方法：43主要功能模块流程图53.1主函数功能流程图54系统测试65 结论11附录 程序源码清单121 设计的目的与内容1.1课程设计的目的编译原理课程设计是计算机专业重要的教学环节,它为学生提供了一个既动手又动脑,将课本上的理论知识和实际有机的结合起来,独立分析和解决实际问题的机会.l 进一步巩固和复习编译原理的基础知识.l 培养学生结构化程序、模块化程序设计的方法和能力.
2、l 提高学生对于编程语言原理的理解能力.l 加深学生对于编程语言实现手段的印象.1.2设计内容构造LR分析程序,利用它进行语法分析,判断给出的符号串是否为该文法识别的句子,了解LRK分析方法是严格的从左向右扫描,和自底向上的语法分析方法.1.3设计要求1) SLR分析表的生成可以选择编程序生成,也可选择手动生成；2) 程序要求要配合适当的错误处理机制；3) 要打印句子的文法分析过程.1.4理论基础由于大多数适用的程序设计语言的文法不能满足LR文法的条件,即使是描述一个实数变量说明这样简单的文法也不一定是LR文法.因此对于LR规范族中有冲突的项目集用向前查看一个符号的办法进行处理,以解决冲突.这
3、种办法将能满足一些文法的需要,因为只对有冲突的状态才向前查看一个符号,以确定做那种动作,因而称这种分析方法为简单的LR分析法,用SLR表示.2算法的基本思想2.1主要功能函数class WFWFWFbooloperatorconstbooloperator=constvoid print;class Closurevoid printbooloperator=const;voidmake_itemvoiddfsvoidmake_firstvoid appendbool _checkconst vector& id,const string strvoidmake_followvoidmake_
4、setvoidmake_Vvoidmake_cmpvector& cmp1,inti,charchvoidmake_govoidmake_tablevoid printstringget_stepsstringget_stkvectorstkstringget_shiftvoidanalyse2.2算法思想SLR文法构造分析表的主要思想：许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决.解决冲突的方法：解决冲突的方法是分析所有含A和B的句型,考察集合FOLLOW和FOLLOW,如果这两个集合不相交,而且也不包含b,那么当状态I面临输入符号a时,我们可以使用如下策略：若a=b,
5、则移进.若aFOLLOW,则用产生式A进行归约；若aFOLLOW,则用产生式B进行归约；此外,报错*SLR的基本算法：假定LR规范族的一个项目集I中含有m个移进项目A1a11,A2a22,Amamm；同时含有n个归约项目B1,B2,B3,如果集合 a1, am,FOLLOW,FOLLOW两两不相交包括不得有两个FOLLOW集合有#,则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中的哪个集合而活的解决：若a是某个ai,i=1,2,m,则移进.若aFOLLOW,i=1,2,m,则用产生式Bi进行归约；此外,报错这种冲突的解决方法叫做SLR解决办法.SLR语法分析表的构造方法：
6、首先把G拓广为G,对G构造LR项目集规范族C和活前缀识别自动机的状态转换函数GO.函数ACTION和GOTO可按如下方法构造：若项目Ab属于Ik,GO= Ij,a为终结符,置ACTIONk,a为把状态j和符号a移进栈,简记为sj；若项目A属于Ik,那么,对任何非终结符a,aFOLLOW,置ACTIONk,a为用产生式A进行归约,简记为rj；其中,假定A为文法G的第j个产生式若项目SS属于Ik,则置ACTIONk,#为可接受,简记为acc；若GO= Ij,A为非终结符,则置GOTOk, A=j；分析表中凡不能用规则1至4填入信息的空白格均填上出错标志.语法分析器的初始状态是包含SS的项目集合的状
7、态SLR解决的冲突只是移进-规约冲突和规约-规约冲突3主要功能模块流程图出错接受产生Follow合集产生First合集产生项目表输入分析串WF开始3.1主函数功能流程图退出程序,并告知用户分析结果构造LR分析表图3.1程序主要流程4系统测试图4.1输入图4.2项目表图4.3FIRST集图4.4 FOLLOW集图4.5CLOSURE表图4.6 EDGE表图4.7 LR表图4.8文法分析步骤5结论LR分析法是一种自下而上进行规范归约的语法分析方法.这里L是指从左到右扫描输入符号串.R是指构造最右推倒的逆工程.这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多.附录程序源码清
8、单#include #include #include #include #include #include #include #include #include #include #include #define MAX 507/#define DEBUGusingnamespacestd;#pragma warningclass WFpublic:string left, right;int back;int id;WFleft= s1;right= s2;back= x;id= y;WFleft= s1;right= s2;back= x;id= y;booloperatorconsti
9、freturn right a.right;return left a.left;booloperator=constreturn&;void printprintf%sn,left.c_str,right.c_str;class Closurepublic:vector element;void printprintf%-15s%-15sn,str.c_str;forinti=0;ielement.size;i+elementi.print;booloperator=constifa.element.size!=element.sizereturnfalse;forinti=0;ia.ele
10、ment.size;i+ifcontinue;elsereturnfalse;returntrue;struct Contentint type;intnum;string out;Content type =-1;Content:type,num;vectorwf;mapstring, vectordic;mapstring, vectorVN_set;map vis;string start =S;vector collection;vector items;char CH =$;int goMAXMAX;int toMAX;vector V;bool usedMAX;Content ac
11、tionMAXMAX;intGotoMAXMAX;mapstring, set first;mapstring, set follow;voidmake_itemmemsetto,-1,sizeof;forinti=0;iwf.size;i+VN_setwfi.left.push_back;forinti=0;iwf.size;i+forint j =0; j =wfi.right.length;j+string temp =wfi.right;temp.inserttemp.begin+ j, CH;dicwfi.left.push_backitems.size;iftoitems.size
12、-1=items.size;items.push_backWFwfi.left, temp,i,items.size;#ifdef DEBUG puts;forinti=0;iitems.size;i+printf%s back:%d id:%dn, itemsi.left.c_str, itemsi.right.c_str, itemsi.back, itemsi.id;puts;#endifvoiddfsifreturn;visx=1;vector& id =VN_setx;forinti=0;iid.size;i+string& left =wfidi.left;string& righ
13、t =wfidi.right;forint j =0; j right.length;j+ifisupperdfsright.substr;set& temp = firstright.substr;set:iterator it =temp.begin;bool flag =true;for; it !=temp.end; it+if flag =false;firstleft.insert;ifbreak;elsefirstleft.insert;break;voidmake_firstvis.clear;mapstring, vector:iterator it2 =dic.begin;
14、for; it2 !=dic.end; it2+iffirstcontinue;elsedfsfirst;#ifdef DEBUG puts;mapstring, set:iterator it =first.begin;for; it !=first.end; it+printfFIRST=, it-first.c_str;set& temp = it-second;set:iterator it1 =temp.begin;bool flag =false;for; it1 !=temp.end; it1+ifprintf;printf;flag=true;puts;#endifvoid a
15、ppendset& from = followstr1;set& to = followstr2;set:iterator it =from.begin;for; it !=from.end; it+to.insert;bool _checkconst vector& id,const string strforinti=0;iid.size;i+int x = idi;ifreturntrue;returnfalse;voidmake_followwhilebool goon =false;mapstring, vector:iterator it2 =VN_set.begin;for; i
16、t2 !=VN_set.end; it2+vector& id = it2-second;forinti=0;iid.size;i+bool flag =true; WF&tt=wfidi;string& left =tt.left;const string& right =tt.right;forint j =right.length-1; j =0; j-ifisupperifinttx= followright.substr.size;appendleft,right.substr;int tx1 = followright.substr.size;iftx goon =true;if_
17、checkflag=false;forint k = j +1; k right.length; k+ifisupperstringidd=right.substr;set& from = firstidd;set& to = followright.substr;set:iterator it1 =from.begin;inttx= followright.substr.size;for; it1 !=from.end; it1+ifto.insert;int tx1 = followright.substr.size;iftx goon =true;if_checkbreak;elsein
18、ttx= followright.substr.size;followright.substr.insert;int tx1 = followright.substr.size;iftx goon =true;break;else flag =false;ifbreak;#ifdef DEBUG puts;mapstring, set:iterator it =follow.begin;for; it !=follow.end; it+printfFOLLOW=, it-first.c_str;set& temp = it-second;temp.insert;set:iterator it1
19、 =temp.begin;bool flag =false;for; it1 !=temp.end; it1+ifprintf;printf;flag=true;puts;#endifvoidmake_setbool hasMAX;forinti=0;iitems.size;i+if Closure temp;string&str= itemsi.right;vector& element =temp.element;element.push_back;size_t x =0;forx =0; x str.length; x+ifbreak;memsethas,0,sizeof;hasi=1;
20、ifx !=str.length-1queue q;q.pushstr.substr;while!q.emptystring u =q.front;q.pop;vector& id =dicu;forsize_t j =0; j id.size;j+inttx= idj;ififcontinue;hastx=1;ifisupperq.pushitemstx.right.substr;element.push_back;collection.push_back;forsize_ti=0;icollection.size;i+map temp;forsize_t j =0; j collectio
21、ni.element.size;j+stringstr= collectioni.elementj.right;size_t x =0;for; x str.length; x+ifbreak;ifx =str.length-1continue;int y =strx +1;int ii;str.erasestr.begin+ x;str.insertstr.begin+ x +1, CH; WF cmp=WF;forsize_t k =0; k items.size; k+ifii= k;break;memsethas,0,sizeof;vector& element = tempy.ele
22、ment;element.push_back;hasii=1;x+;ifx !=str.length-1queue q;q.pushstr.substr;while!q.emptystring u =q.front;q.pop;vector& id =dicu;forsize_t j =0; j id.size;j+inttx= idj;ififcontinue;hastx=1;ifisupperq.pushitemstx.right.substr;element.push_back;map:iterator it =temp.begin;for; it !=temp.end; it+coll
23、ection.push_backsecond;forsize_ti=0;icollection.size;i+sortcollectioni.element.begin, collectioni.element.end;forsize_ti=0;icollection.size;i+forsize_t j =i+1; j collection.size;j+ifcollection.erasecollection.begin+ j;#ifdef DEBUGputs;stringstream sin;forsize_ti=0;icollection.size;i+sin.clear;string
24、 out;sinclosure-I out;collectioni.print;puts;#endifvoidmake_Vmemsetused,0,sizeof;forsize_ti=0;iwf.size;i+string&str=wfi.left;forsize_t j =0; j str.length;j+ifcontinue;usedstrj=1;V.push_back;string& str1 =wfi.right;forsize_t j =0; j str1.length;j+ifcontinue;usedstr1j=1;V.push_back;sortV.begin,V.end;V
25、.push_back;voidmake_cmpvector& cmp1,inti,charchforsize_t j =0; j collectioni.element.size;j+stringstr= collectioni.elementj.right;size_t k;fork =0; k str.length; k+ifbreak;ifk !=str.length-1&strk +1=chstr.erasestr.begin+ k;str.insertstr.begin+ k +1, CH; cmp1.push_backWF;sortcmp1.begin, cmp1.end;void
26、make_gomemsetgo,-1,sizeof;int m =collection.size;forsize_t t =0; t V.size; t+charch= Vt;forinti=0;ivector cmp1;make_cmp;#ifdef DEBUGcout cmp1.sizeendl;#endififcmp1.size=0continue;forint j =0; j vector cmp2;forsize_t k =0; k collectionj.element.size; k+string&str= collectionj.elementk.right;size_t x;
27、forx =0; x str.length; x+ifbreak;if cmp2.push_backWF;sortcmp2.begin, cmp2.end;#ifdef DEBUGcout cmp2.sizeendl;#endifbool flag =true;ifcmp2.size!= cmp1.sizecontinue;#ifdef DEBUGcout cmp1.sizeendl;#endifforsize_t k =0; k cmp1.size; k+ifcontinue;else flag =false;#ifdef DEBUGcoutout endl;#endififgoich= j
28、;#ifdef DEBUGputs;stringstream sin;string out;forinti=0;iforint j =0; j forint k =0; k ifsin.clear;sinIi-I out;printf%sn,out.c_str;#endifvoidmake_tablememsetGoto,-1,sizeof;forsize_ti=0;icollection.size;i+forsize_t j =0; j V.size;j+charch= Vj;int x = goich;ifcontinue;if!isupperactionich= Content;else
29、Gotoich= x;/write r and acc to the table forinti=0;icollection.size;i+forint j =0; j collectioni.element.size;j+ WF&tt= collectioni.elementj;iftt.righttt.right.length-1= CHifactioni#= Content;elseforint k =0; k V.size; k+int y = Vk;if!followtt.left.countcontinue;actioniy= Content;#ifdef DEBUG puts-L
30、R分析表-;printf;forinti=1;iV.size;i+printf;puts;forinti=0;iV.size+1*10;i+printf;puts;stringstream sin;forinti=0;icollection.size;i+printf;forint j =0; j V.size;j+charch= Vj;ifisupperifprintf;elseprintf;elsesin.clear;ifprintf;else Content& temp = actionich;ifsinS;ifsinR;ifsinacc;ifsintemp.out;printf%7s%
31、3s,temp.out.c_str,|;puts;forinti=0;iV.size+1*10;i+printf;puts;#endifvoid printprintf%-15s|%-15s%-15s%-20s|%-15s%-15s%-15sn, s1.c_str, s2.c_str, s3.c_str, s4.c_str, s5.c_str, s6.c_str, s7.c_str;stringget_stepsstringstream sin;sin ret;return ret;templatestringget_stkvectorstkstringstream sin;forinti=0;istk.size;i+sinstki;
