东北大学秦皇岛分校编译原理课件第二章第七章

东北大学秦皇岛分校编译原理课件第二章第七章

ID:40018290

大小:418.50 KB

页数:51页

时间:2019-07-17

东北大学秦皇岛分校编译原理课件第二章第七章_第1页
东北大学秦皇岛分校编译原理课件第二章第七章_第2页
东北大学秦皇岛分校编译原理课件第二章第七章_第3页
东北大学秦皇岛分校编译原理课件第二章第七章_第4页
东北大学秦皇岛分校编译原理课件第二章第七章_第5页
资源描述:

《东北大学秦皇岛分校编译原理课件第二章第七章》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第7章LR分析法7.1LR类分析法LR分析法根据当前分析栈和输入串来确定句柄。LR分析过程是一种规范归约过程。LR分析法适用于大多数无二义性的上下文无关文法。常用的LR分析法有:(1)LR(0)分析法(2)SLR(1)分析法(3)LALR(1)分析法(4)LR(1)分析法LR(K)的含义:L表示由左向右处理输入;R表示生成了最右推导;数字K表示使用了先行的K个符号。LR分析法同样要用到先行集合(FIRST集合)和后跟集合(FOLLOE集合)。SLR(1)是“简单LR(1)”的简写,是对LR(1)分析的改进。LALR(1)即先行LR(1),是比SLR(1)分析稍微强大但却比一般LR(1)分析简

2、单的方法。S→EE→T

3、E+TT→int

4、(E)Reduce:如能找到一产生式A→w且栈中的内容是qw(q可能为空),则可以将其归约为qA。即倒过来用这个产生式。如上例,若栈中内容是(int,我们使用产生式T→int并把栈中内容归约为(TShift:如不能执行一个归约且在输入串中还有token,就把它从输入串移到栈中。如上例,假定栈中内容是(,输入中还有int+int)#.不能对(执行一个归约,因为它不和任何产生式的右端匹配,所以把输入的第一个符号移到栈中,于是栈中内容是(int,而余留的输入是+int)#。Reduce的一个特殊情况:栈中的全部内容w归约为开始符号S(即施用S→w),且没有

5、余留输入了,意味着已成功分析了整个输入串.移进归约分析中还会出现一种情况,就是出错,比如当前的token不能构成一个合法句子的一部分,例如上面的文法,试分析int+)时就会发生错误。STACKREMAININGINPUTPARSERACTION1(int+int)#Shift2(int+int)#Shift3(int+int)#Reduce:T→int4(T+int)#Reduce:E→T5(E+int)#Shift6(E+int)#Shift7(E+int)#Reduce:T→int8(E+T)#Reduce:E→E+T9(E)#Shift10(E)#Reduce:T→(E)11T#Red

6、uce:E→T12E#Reduce:S→E13S#(E+T)#Reduce:E→E+Twhy?不用E→T(E)#若使用了E→T,在栈中形成的(E+E不是规范句型的活前缀(viableprefixes)(E+E不能和任何产生式的右端匹配(E+E)不是规范句型活前缀:是规范句型(右句型)的前缀,但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导规范句型规范归约最右推导:在推导的任何一步αβ,其中α、β是句型,都是对α中的最右非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型G[S]:S→EE→E+T

7、TT→(E)

8、intSET(E)(E+T

9、)(E+int) (T+int)(int+int)规范归约假定α是G的一个句子,称序列αn,αn-1…,α0是α的一个规范归约如果该序列满足:(1)αn=α(2)α0为文法的开始符号(3)对任何j,0

10、遇到的文法符号时,说明输入串不是该文法的一个句子,则报错。LR分析器一个LR分析器由3个部分组成:(1)总控程序:也称驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表(或分析函数):不同的文法其分析表不同,同一文法采用的LR分析器不同时,分析表也将不同。分析表由动作表(ACTION)和状态转换表(GOTO)组成,在计算机里常用二维数组表示。(3)分析栈:包括文法符号栈和相应的状态栈。都为先进后出栈。分析器的动作由栈顶状态和当前输入符号决定。LR分析器的关键部分是LR分析表的构造。LR分析器模型总控程序outputInput#SiXm…S1…X1S0#栈状态文法符号ACTIONGO

11、TOLR分析表产生式表SP:栈指针S[i]:状态栈X[i]:文法符号栈SP文法要求shift-reduceorreduce-reduce冲突(conflicts)分析程序不能决定是shift还是reduce或者分析程序归约时有多个产生式可选例子(danglingelse):S→ifEthenS

12、ifEthenSelseS如输入ifEthenifEthenSelseS分析某一时刻,栈的内容:ifEthenifE

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。