教育学LR分析法.pptx
《教育学LR分析法.pptx》由会员分享,可在线阅读,更多相关《教育学LR分析法.pptx(85页珍藏版)》请在咨信网上搜索。
1、第七章第七章 LR LR 分析法分析法 1965年,年,D.knuth首先提出了首先提出了LR(K)文法及文法及LR(K)分析技术。分析技术。LR(K)分析是指自左向右扫描和自底向上的语法分析,且分析是指自左向右扫描和自底向上的语法分析,且在分析的每一步,只须根据分析栈中当前已移进和归约出的在分析的每一步,只须根据分析栈中当前已移进和归约出的全部文法符号,并至多再向前查看全部文法符号,并至多再向前查看K个输入符号,就能确定个输入符号,就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作(是移进输入
2、符号成。从而也就可以确定所应采取的分析动作(是移进输入符号还是按某产生式进行归约)。还是按某产生式进行归约)。当前扫描到当前扫描到Xn+1,向前查看向前查看k个符号,来确定是把个符号,来确定是把Xn+1移进栈,还是把移进栈,还是把XiXn作为句柄进行归约。作为句柄进行归约。1)要归约时,则根据某产生式要归约时,则根据某产生式UXiXi+1Xn进行归约:进行归约:#X1X2Xi-1UXn+1Xn+2Xn+k#例:例:#X1X2Xi Xn Xn+1Xn+2Xn+kXn+k+1#栈顶栈顶(续页)(续页)LR(0)表示在每一步分析时都不用向前输入符号表示在每一步分析时都不用向前输入符号LR(1)表示在
3、每一步分析时都向前看一个输入符号来决定当表示在每一步分析时都向前看一个输入符号来决定当 前的动作。前的动作。SLR(1)表示简单的表示简单的LR(1),即只在动作不唯一的地方向前看,即只在动作不唯一的地方向前看一个符号,在动作唯一时则不向前看输入符号。一个符号,在动作唯一时则不向前看输入符号。2)要移进时,即把要移进时,即把Xn+1进栈,并读下一符号:进栈,并读下一符号:#X1X2XiXnXn+1 Xn+2Xn+k#在栈中在栈中当前扫描符当前扫描符栈顶栈顶7.1 LR7.1 LR分析概论分析概论一一.LR分析器的逻辑结构及工作过程分析器的逻辑结构及工作过程 从逻辑上来说,一个从逻辑上来说,一个
4、LR分析器如图分析器如图7.1 所示。所示。输入串输入串#aia1SpX1#S1S0 XmSm总总 控控 程程 序序输出输出ACTION 表表GOTO 表表其中其中S栈为状态栈栈为状态栈 X栈为符号栈栈为符号栈栈栈产生式产生式 表表图图7.1 LR分析器的逻辑结构分析器的逻辑结构 即一个即一个LR(k)分析器主要由:总控程序,分析栈(状态栈分析器主要由:总控程序,分析栈(状态栈和符号栈)输入队列和分析表组成。一般来说所有和符号栈)输入队列和分析表组成。一般来说所有LR分析器分析器的总控程序基本上是大同小异。只有分析表各不相同。一般的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种
5、不同的分析表的构造方法。主要讨论三种不同的分析表的构造方法。第一种称为规范第一种称为规范LR分析表构造法。用此法构造的分析表分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法,但实现代价比较高。功能最强而且也适合于很多文法,但实现代价比较高。第二种称为简单第二种称为简单LR(即即SLR)分析表构造法。这是一种比较分析表构造法。这是一种比较容易实现的方法。但容易实现的方法。但SLR分析表的功能太弱,而且对某些文法分析表的功能太弱,而且对某些文法可能根本就构造不出相应的可能根本就构造不出相应的SLR分析表。分析表。第三种称为向前第三种称为向前LR(即(即LALR)分析表构造法。这种方法)
6、分析表构造法。这种方法构造的分析表功能介于规范构造的分析表功能介于规范LR分析表分析表SLR分析表之间。这种表分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。适用于绝大多数程序语言的文法。而且也可以设法有效的实现。二、二、LR 分析器的分析过程如下:分析器的分析过程如下:1.首先将初始状态首先将初始状态 S0及句子的左界限及句子的左界限#分别压入状态栈和符号栈中。分别压入状态栈和符号栈中。则用栈顶状态则用栈顶状态Sm和当前扫描符和当前扫描符 ai组成符号对(组成符号对(Sm,ai)去查去查分析动作表,根据分析动作表,根据ACTIONSm,ai的指示完成相应的分析动作。
7、的指示完成相应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一:表中每一表元素所规定的动作仅能是下列四种动作之一:S0S1 S2 Sm Sm+1 ai+1 ai+2 an#X1 X2 Xm ai 2.设在分析中的某一步,分析栈及余留的输入串为如下格局:设在分析中的某一步,分析栈及余留的输入串为如下格局:S0S1 Sm ai ai+1an#X1 Xm (1)ACTIONSm,ai=Sm+1 (移进)(移进)表明句柄尚未在栈顶形成,此时正期待移进输入符号以便形成表明句柄尚未在栈顶形成,此时正期待移进输入符号以便形成句柄。故将当前的输入符号和表元素句柄。故将当前的输入符号和表元素Sm+1
8、分别压入栈中,有分别压入栈中,有(2)ACTIONSm,ai=Rj (归约)归约)表明此时应按文法的第表明此时应按文法的第j个产生式个产生式A Xm-k+1Xm-k+2 Xm进行归约。即栈顶符号串进行归约。即栈顶符号串Xm-k+1Xm-k+2 Xm已成为当前句型的句已成为当前句型的句柄。所谓按第柄。所谓按第j个产生式归约,就是将分析栈中从顶向下的个产生式归约,就是将分析栈中从顶向下的k个符个符号退栈,然后将文法符号号退栈,然后将文法符号A压入符号栈中。此时分析的格局为:压入符号栈中。此时分析的格局为:S0S1 Sm-k ai ai+1an#X1 Xm-k A 然后以(然后以(Sm-k,A)去查
9、状态转移表,设去查状态转移表,设GOTOSm-k,A=Sl,则将则将此新状态压入状态栈中,则有如下格局:此新状态压入状态栈中,则有如下格局:S0S1 Sm-k Sl ai ai+1an#X1 Xm-k A (3)ACTIONSm,ai=acc(接受)(接受)表明当前的输入串已被成功地分析完毕,应停止分析器的工作。表明当前的输入串已被成功地分析完毕,应停止分析器的工作。其中其中Z为文法开始符号为文法开始符号S为使为使ACTIONS,#=acc的的 唯一状态(接受状态)唯一状态(接受状态)(4)ACTIONSm,ai=ERROR(空白)。(空白)。表明当前的输入串中含有错误,也应终止当前的分析工作
10、。表明当前的输入串中含有错误,也应终止当前的分析工作。转出错处理。转出错处理。3.重复上述第重复上述第2步的工作,直到分析栈顶出现步的工作,直到分析栈顶出现“接受状态接受状态”或或“出错状态出错状态“为止。对接受状态,分析栈的格局为:为止。对接受状态,分析栈的格局为:S0 S#Z 例:例:有文法有文法GS:1:SaAcBe e 2:Ab 3:AAb 4:Bd其其ACTION表和表和GOTO表表为:为:考察对输入串考察对输入串abbcde#的的分析过程。分析过程。r1r1r1r1r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2B
11、AS#dbecaGOTOACTION0123456789 S a A c B e e A b d b图图7.2 abbcde#的语法树的语法树对输入串对输入串abbcde#的分析过程为:的分析过程为:ACTION GOTO步骤步骤 状态栈状态栈 符号栈符号栈 输入流输入流 分析动作分析动作 下一状态下一状态1 0#abbcde#S2(0,a)2 02#a bbcde#S4(2,b)3 024#ab bcde#r2(4,b)GOTO2,A=34 023#aA bcde#S6(3,b)6 023#aA cde#S5(3,c)5 0236#aAb cde#r3(6,b)GOTO2,A=37 0235
12、#aAc de#S8(5,d)8 02358#aAcd e#r4(8,d)GOTO5,B=79 02357#aAcB e#S9(7,e)10 023579#aAcBe#r1(9,#)GOTO0,S=111 01#S#acc(1,#)图图7.3 abbcde#的分析过程的分析过程LR分析过程中的性质与特点:分析过程中的性质与特点:n栈中的文法符号串并上剩余的输入串构成一个右句型(规范句型)n当该右句型的句柄出现在栈顶时,归约,否则,移进n栈中的文法符号串是当前句型的前缀,该前缀不包含句型句柄后面的符号,称之为活前缀(Viable Prefixes)7.2 LR(0)分析表的构造分析表的构造为了给
13、出构造为了给出构造LR(0)分析表的算法,引出一些术语:分析表的算法,引出一些术语:1、规范句型的活前缀、规范句型的活前缀 前缀:前缀:一个符号串的前缀是指该串的任意首部(包括一个符号串的前缀是指该串的任意首部(包括)。)。例如例如 abc的前缀有:的前缀有:,a,ab,abc abcd的前缀有:的前缀有:,a,ab,abc,abcd 由此可知,对于符号串由此可知,对于符号串 而言,其前缀的数量为而言,其前缀的数量为+1。例:有文法例:有文法GS:SaAcBe e1 Ab2 这里在每条产生式后加上了产这里在每条产生式后加上了产 AAb3 生式的序号生式的序号i当进行推导时把当进行推导时把 Bd
14、4 序号带上,以便说明问题。序号带上,以便说明问题。对输入串对输入串abbcde e进行推导如下(最右推导):进行推导如下(最右推导):S aAcBe e1 aAcd4e e1 aAb3cd4e e1 ab2b3cd4e e1由此可知,由此可知,abbcde e是该文法的句子。由于是该文法的句子。由于LR方法是自底向上的方法是自底向上的分析,故应采用归约。分析,故应采用归约。最左归约为:最左归约为:ab2b3cd4e e1 用用2式归约式归约 aAb3cd4e e1 3 aAcd4e e1 4 aAcBe e1 1 S其中其中表示归约符表示归约符 从归约的过程可看出,每次归约时,归约前和归约后
15、的被从归约的过程可看出,每次归约时,归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型,而用哪个归约部分与剩余部分合起来仅构成文法的规范句型,而用哪个产生式归约仅取决于当前句型的前面部分;产生式归约仅取决于当前句型的前面部分;X1X2Xnp 其中其中Xi为文法的符号,为文法的符号,p为第为第p个产生式序号。个产生式序号。如上例中每次归约前句型的前面部分为:如上例中每次归约前句型的前面部分为:ab2 aAb3 aAcd4 aAcBe e1我们把规范句型的这种前端部分的串称为可归我们把规范句型的这种前端部分的串称为可归前缀。实际上,它们恰好是符号栈栈顶形成句前缀。实际上,它们恰好是符号
16、栈栈顶形成句柄时符号栈中的内容。柄时符号栈中的内容。SaAcBee1Ab2AAb3Bd4 这是因为一旦句型的句柄在符号栈顶形成,将会立即被归约这是因为一旦句型的句柄在符号栈顶形成,将会立即被归约之故。所以我们将把规范句型具有上述性质(即不含句柄之后的之故。所以我们将把规范句型具有上述性质(即不含句柄之后的任何符号)的前缀称之为任何符号)的前缀称之为可归前缀可归前缀。对各规范句型有前缀:对各规范句型有前缀:ab2b3cd4e1 ,a,abaAb3cd4e1 ,a,aA,aAbaAcd4e1 ,a,aA,aAc,aAcdaAcBe1 ,a,aA,aAc,aAcB,aAcBe可以发现前缀可以发现前缀
17、a,ab,aA,aAc是多个规范句型的前缀,因此我们可进是多个规范句型的前缀,因此我们可进一步一步把形成可归前缀前和形成可归前缀时的所有规范句型的前缀把形成可归前缀前和形成可归前缀时的所有规范句型的前缀都称为都称为活前缀活前缀。可归前缀:可归前缀:是指规范句型的一个前缀,这种前缀包含句柄且不是指规范句型的一个前缀,这种前缀包含句柄且不含句柄之后的任何符号。含句柄之后的任何符号。活前缀:活前缀:可归前缀的任意首部。特指在分析过程中对于在栈顶可归前缀的任意首部。特指在分析过程中对于在栈顶形成句柄之前和恰好形成句柄时,每一步中形成句柄之前和恰好形成句柄时,每一步中符号栈中的那些符符号栈中的那些符号组
18、成的符号串号组成的符号串。活前缀定义:活前缀定义:在前面例中对输入串在前面例中对输入串abbcde的归约分析过程中,在规范归约的归约分析过程中,在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串均过程中的任何时候只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀,它表明输入串的已被分析过的部分是该文为规范句型的活前缀,它表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。法某规范句型的一个正确部分。由此可形式地定义活前缀如下:由此可形式地定义活前缀如下:定义定义 7.1:若:若S *A 是是 文法文法G中的一个规范推导,中的一个规范推导,如果符号串如果符号串 是
19、是的前缀,则称的前缀,则称 是是G的一个活前缀。的一个活前缀。其中其中 S为为文法开始符号。文法开始符号。RRLRLR分析分析n分析过程可以看作是识别文法规范句型活前缀的过程。n只要每一时刻栈中的文法符号串是某规范句型的活前缀,则说明已分析的部分是正确的n一个文法的规范句型的所有活前缀构成一个语言,而且是正规语言,可以用一个 DFA 来识别n例子:文法GS:(1)S aAcBe(2)A b(3)A Ab(4)B d014235769SabAbcBed8*n每个状态都是活前缀的识别态,双圈状态是可归前缀(句柄)识别态,标识了*的状态是句子识别态分析句子的过程可以看作在上面这个 DFA 上运行的过
20、程014235769SabAbcBed8*(1)S aAcBe(2)A b(3)A Ab(4)B dn例子:步骤栈输入串ACTIONGOTO1#0abbcde#S2014235769SabAbcBed*8n例子:步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S4014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R23014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4b
21、cde#R234#0a2A3bcde#S6014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO1#0abbcde#S22#0a2bbcde#S43#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R33014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO3#0a2b4bcde#R234#0a2A3bcde#S65#0a2A3b6cde#R336#0a2A3cde#S5*014235769SabAbcBed8n例子:步骤栈输入串ACTIONGOTO4#0a2A3bcde#S65#0a2A3b6cde#R336
22、#0a2A3cde#S57#0a2A3c5de#S8*014235769SabAbcBed8n例子:步骤栈输入串ACTIONGOTO5#0a2A3b6cde#R336#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R47014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO6#0a2A3cde#S57#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3c5B7e#S9014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO7#0a2A3c5de#S88#0a2A3c5d8e#R479#0a2A3
23、c5B7e#S910#0a2A3c5B7e9#R11014235769SabAbcBed8*n例子:步骤栈输入串ACTIONGOTO8#0a2A3c5d8e#R479#0a2A3c5B7e#S910#0a2A3c5B7e9#R1111#0S1#Acc014235769SabAbcBed8*2、LR(0)项目)项目 由上述分析和定义可知,活前缀与句柄间的关系不外乎下由上述分析和定义可知,活前缀与句柄间的关系不外乎下述述 三种情况:三种情况:(1)活前缀中已含有句柄的全部符号(句柄的最后符号就是活前缀中已含有句柄的全部符号(句柄的最后符号就是 活前缀的最后符号)。活前缀的最后符号)。(2)活前缀中
24、只含有句柄的前部分符号(句柄的最左子串活前缀中只含有句柄的前部分符号(句柄的最左子串 为活前缀的最右子串)。为活前缀的最右子串)。(3)活前缀中全然不包含句柄的任何符号。活前缀中全然不包含句柄的任何符号。第一种情况表明:第一种情况表明:此时某一产生式此时某一产生式A的右部的右部已出现在符号已出现在符号栈顶,因此此时相应的分析动作应当是用此产生式进行归约。栈顶,因此此时相应的分析动作应当是用此产生式进行归约。第二种情况表明:第二种情况表明:形如形如A 1 2的产生式的的产生式的 右部子串已在符号右部子串已在符号栈栈顶,如栈栈顶,如 1,正期待着从余留的输入串中看到能由正期待着从余留的输入串中看到
25、能由推出的推出的 符符号串,即期待号串,即期待 2 进栈以便能进行归约。故此时分析动作是进栈以便能进行归约。故此时分析动作是“移移进进”当前输入符号。当前输入符号。第三种情况则意味着:第三种情况则意味着:期望从余留输入串中能看到由某产生式期望从余留输入串中能看到由某产生式A 的右部,即的右部,即 所代表的符号串所代表的符号串(即句柄即句柄)。所以此时分析的。所以此时分析的动作也是读输入符进符号栈。动作也是读输入符进符号栈。为了刻画在分析过程中,文法的一个产生式右部符号串有多大为了刻画在分析过程中,文法的一个产生式右部符号串有多大部分已被识别,我们可在该产生式的右部相应位置上加一个圆点部分已被识
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教育学 LR 分析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。