最新【考研计算机专业课】天津大学 编译原理讲义 LR分析法(共14张PPT课件).pptx

《最新【考研计算机专业课】天津大学 编译原理讲义 LR分析法(共14张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】天津大学 编译原理讲义 LR分析法(共14张PPT课件).pptx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.3 LR分析法分析法LR分析法是一种分析法是一种(y zhn)自下向上自下向上、自左向右自左向右的分析方法。的分析方法。 LR分析法采用分析法采用(ciyng)最一般的最一般的移进移进归约归约方法。方法。 LR分析法在自左向右扫描分析法在自左向右扫描(somio)输入串时能够输入串时能够及时的及时的发现语法错误发现语法错误，并能准确的指出错误位置。，并能准确的指出错误位置。第一页，共十四页。LR分析程序分析程序分析表分析表产生器产生器文法文法分析表分析表总控总控程序程序分析表分析表输入输入输出输出单词输入串单词输入串语句的识别语句的识别第二页，共十四页。例例，文法，文法G的产生式的产生式为

2、为: : ET| |E+TTF| |T*FF(E)| |iT+i3 E+i3 E+FE+TEi1*i2+i3 F*i2+i3 T*i2+i3 T*F+i3回顾回顾: 规范规约规范规约(最左规约最左规约最右推导最右推导(tudo)的逆过程的逆过程)的的关键问题是寻找关键问题是寻找句柄句柄。第三页，共十四页。LR分析法的分析法的基本基本(jbn)思想思想就是就是:一方面记住已移进和规约出的整个一方面记住已移进和规约出的整个(zhngg)符号串，即符号串，即记住记住“历史历史”；另一方面根据所用的产生式，推测未来另一方面根据所用的产生式，推测未来(wili)可能碰到的输入符号，即可能碰到的输入符号，

3、即对对未来未来进行进行“展望展望”。希望能够根据所记载的希望能够根据所记载的“历史历史”和和“展望展望”以及以及“现实现实”的输的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。某一产生式的句柄。在规范规约过程中，在规范规约过程中，第四页，共十四页。根据根据(gnj)“展望展望”的程度，一个的程度，一个LR分析器可以产生分析器可以产生若干不同的分析表。若干不同的分析表。 LR(0) 基本基本(jbn)LR SLR 简单简单(jindn)LR LR(1) 规范规范LR LALR 向前向前LR第五页，共十四页。4.3.1

4、LR分析分析(fnx)过程过程LR分析器分析器实质实质是一个带先进后出存储器是一个带先进后出存储器(栈栈)的的确定确定(qudng)有限状有限状态自动机态自动机；将将“历史历史”和和“展望展望”材料综合的抽象成某些材料综合的抽象成某些(mu xi)“状态状态”；S0S1S2Sm-1SnSm第六页，共十四页。栈顶栈顶S0S1SmX1Xm#状态状态S栈栈符号符号T栈栈分析栈用来分析栈用来(yn li)存放状态，栈里的每个状态概括了从分析开存放状态，栈里的每个状态概括了从分析开始直到某一规约阶段的全部始直到某一规约阶段的全部“历史历史”和和“展望展望”材料。材料。第七页，共十四页。 ACTIONGO

5、TO I+*()#ETF0S5 S4 1231 S6 acc 2 r2S7 r2r2 3 r4r4 r4r4 4S5 S4 8235 r6r6 r6r6 6S5 S4 937S5 S4 108 S8 S11 9 r1S7 r1r1 10 r3r3 r3r3 11 r5r5 r5r5 第八页，共十四页。LR分析器的核心部分分析器的核心部分(b fen)是一张分析是一张分析表。表。分析分析(fnx)表包括两部分表包括两部分:“动作动作”(ACTION)表表: 二维数组，二维数组，ACTIONk，a规定了当状态规定了当状态 k 面临面临(minlng)输入符号输入符号 a 时应采取什么动作。时应采取

6、什么动作。“状态转换状态转换”(GOTO)表表: 二维数组，二维数组，GOTOk，X规定了状态规定了状态k面对文法符号面对文法符号(终结符或非终结符终结符或非终结符)时下一个状态是什么。时下一个状态是什么。第九页，共十四页。ACTIONK，a的值有四种的值有四种(s zhn)情况情况:3.接受接受: 设设LR分析表中分析表中ACTIONk，a=acc说明，当说明，当S栈顶状态栈顶状态为为k，现行输入符号为，现行输入符号为a，总控程序根据，总控程序根据“k”和和“a”查查LR分分析表得析表得: ACTIONk，a=accacc说明语法分析成功。说明语法分析成功。4.报错报错: 设设ACTIONk

7、，a=空白，总控程序若按空白，总控程序若按“k”和和“a”查查表得表得: ACTIONk，a=空白空白说明语法分析出错，所给输入串不是本文法的句子。说明语法分析出错，所给输入串不是本文法的句子。1.移进移进: 设表中设表中ACTIONk，a= Sj，当，当S栈顶状态为栈顶状态为k，现行，现行输入符号为输入符号为a，总控程序根据，总控程序根据“k”和和“a”查查LR(0)分析表，分析表，得得:此时，此时，Sj表示表示j j状态进状态进S栈，栈，a进进T栈栈( (文法符号栈文法符号栈) )。ACTIONk，a= Sj第十页，共十四页。按按ACTIONmn，a= rj的要求的要求(yoqi): S栈

8、栈应删除栈顶应删除栈顶p个状态个状态: mn-p+1mn删除后，删除后，S栈成为栈成为: m1mn-p T栈栈中中x1x2xp归约成归约成A，即，即，T栈栈栈栈(zhn zhn)顶删除顶删除p个文个文法符号，非终极符法符号，非终极符A进进T栈；栈； 若若GOTOmn-p，A=j，则状态，则状态(zhungti)(zhungti)j进进S栈。栈。2.规约规约: 设设LR表中表中ACTIONmn，a=rj，其中，其中，rj表示使用文法的第表示使用文法的第j个产生个产生式式AX1X2Xk进行规约；进行规约；mn表示表示LR表的一个状态。表的一个状态。假设总控程序按假设总控程序按S栈顶状态栈顶状态mn

9、和现行输入符号和现行输入符号a查查LR分析表，得分析表，得:此时，此时，S栈的状态一定为栈的状态一定为: m1,mn-p+1,mn文法符号文法符号T栈的符号一定为栈的符号一定为: x1x2xpACTIONmn，a= rj第十一页，共十四页。动作动作输入串输入串aT栈栈S栈栈移进移进*i+i#i#0规约，规约，Fii+i#*#i 05规约，规约，TFi+i#*#F03移进移进i+i#*#T02移进移进+i#i#T*027规约，规约，Fii#+#T*i0275规约，规约，TT*Fi#+#T*F02710规约，规约，ETi#+#T02移进移进i#+#E01移进移进#i#E+016规约，规约，Fi#E

10、+i0165规约，规约，TF#E+F0163规约，规约，EE+T#E+T0169接受。接受。#E01例例，输入，输入(shr)(shr)串串i i*i+ii+i的分析过程的分析过程 第十二页，共十四页。LR文法文法(wnf)一个文法，如果能构造一个文法，如果能构造(guzo)一张分析表，使得它的每个入口均一张分析表，使得它的每个入口均是唯一确定的，则我们将这个文法称为是唯一确定的，则我们将这个文法称为LR文法文法。一个一个LR分析器有时需要分析器有时需要“展望展望”未来的未来的k个输入符号才能决定采取什么个输入符号才能决定采取什么样的样的“移进移进规约规约”决策。一个文法决策。一个文法(wnf

11、)，如果每步至多向前展望未来，如果每步至多向前展望未来k个符号，则相应的文法称为个符号，则相应的文法称为LR(k)文法文法。 LR方法比方法比LL(1)方法更具一般化。方法更具一般化。 二义性文法不是二义性文法不是LRLR文法。文法。 第十三页，共十四页。内容(nirng)总结4.3 LR分析法。LR分析法在自左向右扫描输入串时能够及时的发现语法错误(cuw)，并能准确的指出错误(cuw)位置。例，文法G的产生式为: ET|E+T。另一方面根据所用的产生式，推测未来可能碰到的输入符号，即对未来进行“展望”。根据“展望”的程度，一个LR分析器可以产生若干不同的分析表。 若GOTOmn-p，A=j，则状态j进S栈。,mn-p+1,。文法符号T栈的符号一定为:。*i+i#。i+i#。LR文法第十四页，共十四页。