SLR1文法分析实验报告.docx
- 文档编号:7332137
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:40
- 大小:145.40KB
SLR1文法分析实验报告.docx
《SLR1文法分析实验报告.docx》由会员分享,可在线阅读,更多相关《SLR1文法分析实验报告.docx(40页珍藏版)》请在冰点文库上搜索。
SLR1文法分析实验报告
《编译原理》课程设计报告
—SLR
(1)分析的实现
学院计算机科学与技术专业计算机科学与技术学号
学生姓名
指导教师姓名
2015年12月26日
1.设计的目的与内容1
1.1课程设计的目的1
1.2设计内容1
1.3设计要求1
1.4理论基础1
2算法的基本思想2
2.1主要功能函数2
2.2算法思想3
SLR文法构造分析表的主要思想:
3
解决冲突的方法:
3
SLR语法分析表的构造方法:
4
3主要功能模块流程图5
3.1主函数功能流程图5
4系统测试6
5结论11
附录程序源码清单12
1.设计的目的与内容
1.1课程设计的目的
编译原理课程设计是计算机专业重要的教学环节,它为学生提供了一个既动手又动脑,将课
本上的理论知识和实际有机的结合起来,独立分析和解决实际问题的机会。
进一步巩固和复习编译原理的基础知识。
培养学生结构化程序、模块化程序设计的方法和能力。
提高学生对于编程语言原理的理解能力。
加深学生对于编程语言实现手段的印象。
1.2设计内容
构造LR(1分析程序,禾U用它进行语法分析,判断给出的符号串是否为该文法识别的句子,
了解LR(K)分析方法是严格的从左向右扫描,和自底向上的语法分析方法。
1.3设计要求
1)SLR(1分析表的生成可以选择编程序生成,也可选择手动生成;
2)程序要求要配合适当的错误处理机制;
3)要打印句子的文法分析过程。
1.4理论基础
由于大多数适用的程序设计语言的文法不能满足LR(0文法的条件,即使是描述一个实数变
量说明这样简单的文法也不一定是LR(O)文法。
因此对于LR(O规范族中有冲突的项目集(状态)
用向前查看一个符号的办法进行处理,以解决冲突。
这种办法将能满足一些文法的需要,因
为只对有冲突的状态才向前查看一个符号,以确定做那种动作,因而称这种分析方法为简单
的LR(1分析法,用SLR(1表示。
2算法的基本思想
2.1主要功能函数
classWF
WF(charsi[],chars2[],int
WF(conststring&si
const
string
&s2,intx,inty
bool
operator<(const
WF&a
)const
bool
operator==(const
WF&a)const
void
print()
};
class
Closure
void
print(stringstr
bool
operator
==(const
Closure&a
)const
void
make_item
()
void
dfs(const
string
&x)
void
make_first
()
void
append(conststring&stri
conststring
&str2
)
bool
_check(constvector >&id,conststringstr ) void make_follow '() void make_set () void make_V() void make_cmp (vector inti,charch) void make_go() void make_table () void print(stringsi string s2,strings3, string s4 s6, strings7 ) stringget_steps (int x) stringget_stk (vector }; strings5, string stringget_shift (WF&temp) voidanalyse(stringsrc) 2.2算法思想 SLF文法构造分析表的主要思想: 许多冲突性的动作都可能通过考察有关非终结符的FOLLOW集而获解决。 解决冲突的方法: 解决冲突的方法是分析所有含A和B的句型,考察集合FOLLOW(A和FOLLOW(B)如果这两 个集合不相交,而且也不包含b,那么当状态I面临输入符号a时,我们可以使用如下策略: 若a=b,则移进。 若a€FOLLOW(A),则用产生式A^a进行归约;若a€FOLLOW(B,则用产生式B^a进行归约;此外,报错*SLR的基本算法: 假定LR(0规范族的一个项目集I中含有m个移进项目 A1Ta? a131,A2fa? a2B2,…,Am^a? am3m; 同时含有n个归约项目 B1^a? B2fa? •••,B3^a 如果集合{a1,…,am},FOLLOW(B1,…,FOLLOW(Bn两两不相交(包括不得有两个FOLLOW 集合有#),则隐含在I中的动作冲突可以通过检查现行输入符号a属于上述n+1个集合中 的哪个集合而活的解决: 若a是某个ai,i=1,2,…,m,则移进。 若a€FOLLOW(Bi)i=1,2,…,m,则用产生式Bfa进行归约; 此外,报错 这种冲突的解决方法叫做SLR(1解决办法。 SLF语法分析表的构造方法: 首先把G拓广为G',对G'构造LR(O项目集规范族C和活前缀识别自动机的状态转换函 数GO。 函数ACTION和GOTO可按如下方法构造: 若项目A~a? bB属于Ik,GO(lk,a)=lj,a为终结符,置ACTION[k,a]为“把状态j和符号a移进栈”,简记为“sj”; 若项目A^a? 属于Ik,那么,对任何非终结符a,a€FOLLOW(A),置ACTION[k,a]为“用产 生式A^a进行归约”,简记为“rj”;其中,假定A^a为文法G'的第j个产生式 若项目S'tS? 属于Ik,则置ACTION[k,#]为可“接受”,简记为“acc”; 若GO(Ik,A)=lj,A为非终结符,则置GOTO[k,A]=j; 分析表中凡不能用规则1至4填入信息的空白格均填上“出错标志”。 语法分析器的初始状态是包含S't? S的项目集合的状态 SLR解决的冲突只是移进-规约冲突和规约-规约冲突 3主要功能模块流程图 3.1主函数功能流程图 图3.1程序主要流程 4系统测试 7 S->E 沌十T K->E+T"TE->T T->T+F T->T*F T->F T->F F-》㈤ F->(E) F->1 图4.1输入 Ir« *7\n4X S->$Eback: Oid: O S->E$back: 0id: l E->$E+TbackILid: 2 卜沌$+Tback: Lid: 3 £->E+$Tbackilid: 4 E->E+T$back: Lid: 5 E->$Tback: 2id: & E->T$back: 2id: 7 r->$rr*Fback: 3id: B T->T>Fback: 3id;9 T~back: 3id: 10 r->W$back: 3id: ll T->$Fback: 4id: 12 T->K$back: 4id: 13 F->$(E)back: 5id: 14 F->($E)back: 5id: 15 F->tejiback: 5id: 10 ^>CE)$back: 5id: 17 F->$iback: 6id: 18 F—>i$back: 6id: 19 图4.2项目表 FIRST®={(ni} FIRST(F)二{(,il FIRSTCS)-{(,il FIRST(T)-[Gil 图4.3FIRST集 牡*芈牢宋来农芈舸ki«k*Hi*ROLLO叩集啡=1=来*芈*半壮來芈來芈琳未朮 FOLLOV®)-优),十} FOLLOW(F>= FOLLOW(S)={ft} FOLLOV(T)=怕,),叽十} 图4.4FOLLOW集 cl^^ure-lO E->$E-^T E->ST F->$(E) F-〉$i S->$E T-〉$F t->$T*r cLosure-Il e->je+tE->JT F->$(E) F->$i F->(? E) T-)JF T->$T+F E->E$+T S->E$ closure-13 T-)F$ closure-14 E-〉T$ T-〉T$*F closure-I5 F->i$ closure-IO E->E$-HT F-XEJ) ■? Losure-I7 E->E+$T F->S(E) F_〉$i T->JF T->$T*F closure-18 F->$(E) F-》$i T->T+$F cLosure-19 F-〉(E)$ closur2-110 E-)E+T$ T->T$+F closure-ill T->T*F$ 图4.5CLOSURE表 EDGE io—c—it IO-E—12 10—F-—13 It>-T—14 10—1—15 IL—C—Il it—r—13 IL—T—14 11—1—15 11—I—16 12—---17 14—^—18 I&--h—17 16—)—19 IT—C—Il IT—13 17—1—15 17—T—no 19—C—T1 13—1—15 is—r—in no—*—ia 图4.6EDGE表 片町去• I J *1 4 E 1卩 15 T 1 - 0 n 厂 13 I 4 551 1 si 6 3 1 4 S5 2 a; ac-c 3 JU IN 茁 斗 H2 SH K2 R2 & HO K& 1 1 1 RC b 阳 ST 1 1 T Si 3 1 10 & si 11 8S R5 昉 Et5 ID R1 SH El 1 1 1 Etl 11 H3 舲1 R3 1 1 R3 图4.7LR(0)表 StkOE IuL_S'心 -.-U&rar.ioji .;Livy-Gt: )ck ftCTlDi CCTO 1 b shift Io SI 7 |乳 UiJHA shift bl 的 ■ Iflfti vi>+jB Ted-uee^F->iJ 15 R6 3 iw *i>+iff rectueE(T一J 1013 ■t *1>+lir shift ill her- £)*iff shift 丄抽 =5 1«Cr*i 蓝■du"(卩一》 |Q14^ Jll : - htr*F "田內仃一江*沪 lUJ31; 叮 £ & |i! (T rBchice(E~>T) 1014 V2 6 10 >+itf shift low I-J 11 1畑 +1F redlU£! ir(F->{tl) |O1« 3 12 IffF +if radsu^r |03 V1 4 13 IfT •”iU TRI^JCF1;卫一>T) h4 砒 ? -4 Ike -if sM£t |02 E7 _h ifl shift loir 注 HhG IT 二BjqhlQU(f~>i) iazra kb 3 17 juz*f q IO2T3 Ri 1」 19 ItfF*T « 匸日ckiE旧+T) 10271o Fl 2 19 血 H Accept |02 iCC 图4.8文法分析步骤 5结论 LR分析法是一种自下而上进行规范归约的语法分析方法。 这里L是指从左到右扫描输入符号串。 R是指构造最右推倒的逆工程。 这种分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。 附录程序源码清单 #inelude #inelude #include《algorithm〉 #inelude #inelude #inelude #inelude #inelude #inelude #inelude #include #defineMAX507 〃#defineDEBUG usingnamespacestd; #pragmawarning(disable: 4996) classWF { public: stringleft,right; intback; intid; WF(chars1[],chars2[],intx,inty) { left=s1; right=s2; back=x; id=y; WF(conststring 1&s1 conststring &s2,intx inty) { left =s1; right =s2; back =x; id=y; } bool operator <(const WF&a)const { if(left==a. left) return right J return left J } bool operator ==(const WF&a)const { return (left ==a.left )&&(right= : =a.right); } void print() { printf ("%s->%s\n",left.c_str(), right.c_str ()); } }; class Closure { public vector void print(stringstr ) { printf ("%-15s%-15s\n" "",str.c_ str()); for(inti=0;ivelement.size();i++) element[i].print(); } returnfalse booloperator==(constClosure&a)const{ if(a.element.size()! =element.size()) for(inti=0;i returntrue; } }; structContent { inttype; intnum; stringout; Content(){type=-1;} Content(inta,intb) : type(a),num(b){} }; vector map vector >>dic; map vector >>VN_set map bool> vis; stringstart ="S" J vector vector charCH='$'; intgo[MAX][MAX]; intto[MAX]; vector boolused[MAX]; Contentaction[MAX][MAX]; intGoto[MAX][MAX]; mapvstring,set mapvstring,set voidmake item() memset (to,-1,sizeof (-1)); for(int i=0;i size ();i++) VNset [wf[i].left ]. push_back(i); for(intj =0;j<=wf[i]. right. length();j++) { stringtemp =wf[i].right J temp.insert (temp.begin()+ j,CH); dic[wf[i]. left].push_back (items .size()); if(j) to[items.size()-1]=items .size() ); items.push_ _back(WF: wf[i]. left, temp,i,items } #ifdefDEBUG puts("- 项目表—— for(inti=0;i ;i++) for(int i=0;i size ();i++) .size printf("%s->%sback: %did: %d\n" items[i].left items[i].right.c_str(),items[i].back,items[i]. ())); "); ;_str(), id); break puts(” #endif voiddfs(conststring&x) { if(vis[x])return; vis[x]=1; vector for(int i=0; i ++) { string &left =wf[id[i]]. left string &right =wf[id[i]]. right for (intj =0;j .length ();j++) if(isupper (right [j])) { dfs (right .substr (j,1)); set >&temp =first [right .substr(j,1)]; set >: : iteratorit =temp .begin(); bool flag =true; for (;it ! =temp. end(); it++) { if(*it= ='~')flag =false; first [left ].insert (*it ); } if(flag)break } { first[left].insert (right[j]); else printf("FIRST(%s)={" it->first.c_str set ->second; set : iteratorit1 =temp.begin( boolflag=false; for(;it1! =temp.end ();it1++) ()); puts ("}"); voidmake_first() { { { #endif void append (const string &str1 const string &str2) { set vchar >&from =follow [str1 ]; set vchar >&to=follow [str2]; set >: : iteratorit =from .begin(); for (;it ! = from. e
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- SLR1 文法 分析 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)