第七章LR分析.ppt

《第七章LR分析.ppt》由会员分享，可在线阅读，更多相关《第七章LR分析.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、nLR 分析方法：一种能根据当前分析栈中的符号串（状态）和向右顺序查看输入串k个符号就可唯一确定分析器的动作是移进还是归约以及用哪个产生式归约的自底向上语法分析算法。n是一种规范归约的过程。是一种规范归约的过程。n四种技术四种技术 LR(0)SLR(1)LR(1)LALR(1)第七章第七章 LR分析分析 第七章第七章 LR分析分析能力强能力强 几乎所有几乎所有CFG的语言结构都能用的语言结构都能用LR分析分析 不需要对文法附加条件不需要对文法附加条件难点难点 几乎不可能用手工编写几乎不可能用手工编写LR分析器分析器现实现实 有有LR分析器的生成器分析器的生成器(YACC)7.1 LR分析分析概

2、述概述 一个LR分析器由3个部分组成:总控程序总控程序;分析表分析表动作(ACTION)、状态转换(GOTO);分析栈分析栈文法符号栈，状态栈。7.1 LR分析分析概述概述ACTION表表告诉分析器：栈顶状态为i,当前输入符号是a时做什么？1.移进：ACTIONi,a=Sj2.归约：ACTIONi,a=rj (若第j条产生式为A)3.接受：ACTIONS,a=acc (S为文法起始符)4.报错：ACTIONi,a=errorGOTO表表 GOTOi,A=j 表示了当前栈顶状态为i，遇到文法符号A时，应转向新状态j。分析表的具体内容及含义：分析表的具体内容及含义：LR的分析流程 开始 初始状态0

3、和#入栈 读符号 根据栈顶状态和输入符号查分析动作表 归约?移进?接受?查状态转换表新状态入状态栈 按产生式i归约 根据产生式i的右部符号的个数，符号栈和状态栈相应元素出栈 产生式i的左部符号入栈 输入符号入符号栈 状态i入状态栈读符号分析结束 错误 YYYNNN7.1 LR分析分析概述概述 LR(0)文法 能力最弱，理论上最重要以例题6.1为例说明LR(0)分析过程 例：文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d 对输入串对输入串 abbcde#利用利用LR分析法进行分析。分析法进行分析。7.2 LR(0)分析分析表表 7.1 例例6.1文法的文法的LR(0)分析表

4、分析表Si:移进，将状态移进，将状态i和和输入符输入符进栈进栈ri:归约，用第归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第表相应状态和第i个产生式的个产生式的左部左部非终结符入栈。非终结符入栈。文法GS：(1)SaAcBe(2)Ab (3)AAb(4)Bd分析输入串分析输入串 abbcde#Step States.Syms.The rest of input Action Goto1 0#abbcde#s22 02#a bbcde#s43 024#ab bcde#r2 goto(2,A)=34 023

5、#aA bcde#s65 0236#aAb cde#r3 goto(2,A)=36 023#aA cde#s57 0235#aAc de#s88 02358#aAcd e#r4 goto(5,B)=79 02357#aAcB e#s910 023579#aAcBe#r1 goto(0,S)=111 01#S#acc对输入串对输入串 abbcde#的的LR 分析分析文法GS：(1)SaAcBe(2)Ab (3)AAb(4)Bd规范句型中规范句型中活前缀、可归前缀活前缀、可归前缀设t是一个规范句型，其中表示句柄，tVt*，如果=u1u2ur，那么称符号串 u1u2ui (其中1ir)是句型t的活前

6、缀活前缀。一个规范句型的活前缀可以有多个，但只有u1u2ur含有完整句柄，将其称为可归前缀可归前缀。7.2.1 活前缀和可归前缀活前缀和可归前缀解：由E+(i-i)的语法树可找出第一个i是句柄，那么=E+(i ,t=-i)因此活前缀为：E E，E+E+，E+(E+(，E+(iE+(i，其中 E+(i E+(i 是可归前缀。ET+E）E（T-ETii 语法树 7.2.1 活前缀和可归前缀活前缀和可归前缀例:文法 G:ET|E+T|E-T Ti|(E)找规范句型 E+(i-i)的活前缀和可归前缀。n 例题所得结论：例题所得结论：活前缀求法：活前缀求法：首先画出句型的语法树，并找出句柄，然后，从句型

7、的左边第一个符号开始，取长度分别为1、2、的符号串，直到包含句柄在内的符号串就是该句型所有的活前缀。而可归前缀就是最长的活前缀。注意：所有活前缀都不包括句柄右边的任何符号。注意：所有活前缀都不包括句柄右边的任何符号。7.2.1 活前缀和可归前缀活前缀和可归前缀7.2.1 活前缀和可归前缀活前缀和可归前缀n 为了便于LR分析的进行，还需对文法进行扩充：在原文法中增加一产生式 SS，其中S为原文法G的起始符，S为新引进的符号，拓广后文法在任何产生式的右部不出现拓广后文法在任何产生式的右部不出现S.例例:拓广文法拓广文法G:ET|E+T|ET Ti|(E)解：引入一个新的开始符号S，使得文法的开始符

8、号所在的规则唯一，这样得到拓广文法如下：SEET|E+T|ETTi|(E)可归前缀可以用穷自动机来识别可归前缀可以用穷自动机来识别（了解此法即可）（了解此法即可）主要思路：主要思路：将文法中的所有符号均看成是有穷自动将文法中的所有符号均看成是有穷自动机的输入，每当一个符号进栈则表示已经识别了该机的输入，每当一个符号进栈则表示已经识别了该符号，需进行状态转换；当识别出可归前缀时，等符号，需进行状态转换；当识别出可归前缀时，等价于在栈中已形成句柄。价于在栈中已形成句柄。7.2.2 识别活前缀的有限自动机识别活前缀的有限自动机 7.2.2 识别活前缀的有限自动机识别活前缀的有限自动机例:文法GS:S

9、S0SaAcBe1Ab2AAb3Bd4给出上文法对句子abbcde 的可归前缀构造识别可归前缀的构造识别可归前缀的DFA 解：对于句子 abbcde 可有以下最右推导过程：S=S0=aAcBe1=aAcd4e1=aAb3cd4e1=ab2b3cd4e1而规范归约(最左归约)就是上述过程的逆过程：ab2b3cd4e1=aAb3cd4e1=aAcd4e1=aAcBe1=S0=AA=并将规范句型并将规范句型的活前缀记为的活前缀记为r，则，则r与句柄有以下关系：与句柄有以下关系：1.活前缀已含有句柄的全部符号，表明产生式活前缀已含有句柄的全部符号，表明产生式A的的 右部右部已出现在栈顶已出现在栈顶2.

10、2.活前缀只含句柄的一部分符号表明活前缀只含句柄的一部分符号表明A1 12 2的右部子串的右部子串1 1已出现在栈顶，期待从输入串中看到已出现在栈顶，期待从输入串中看到2 2推出的推出的符号符号3.活前缀不含有句柄的任何符号，此时期望活前缀不含有句柄的任何符号，此时期望A的右部所的右部所推出的符号串推出的符号串R*R1.LR(0)项目项目(item)在右端某一位置有圆点的在右端某一位置有圆点的G的产生式称为项目。的产生式称为项目。例例如：如：SaAd 的所有项目为的所有项目为 SaAd;Sa Ad;SaAd;SaAd注意：注意：对于对于 A LR(0)项目只有项目只有A 7.2.4 LR(0)

11、项目集规范族的构造项目集规范族的构造2.项目的种类：项目的种类：移进项目移进项目：后继符号为终结符号，如EET。待约项目待约项目：后继符号为非终结符号，如EET和S E 归约项目归约项目：后继符号为空。如EET 和 SE 接受项目接受项目：文法开始符号S的归约项目。如SE7.2.4 LR(0)项目集规范族的构造项目集规范族的构造3.构造识别活前缀的构造识别活前缀的NFA把文法的所有产生式的项目都列出，并使每个项目都为NFA的一个状态。左端含文法识别符号的项目为初态，其余每个状态都为活前缀的识别态；圆点在最后的项目为句柄识别态；含文法起始符的产生式的句柄识别态为句子识别态。状态之间的转换关系按如

12、下规则确定：7.2.4 LR(0)项目集规范族的构造项目集规范族的构造3.构造识别活前缀的构造识别活前缀的NFA（续）（续）1)若若 i 项项目目为为：XX1X2Xi-1XiXn j 项项目目为为：XX1X2Xi-1 XiXi+1Xni 项目和 j 项目出于同一个产生式，对应于NFA为状态j的圆点只落后于状态i的圆点一个符号的位置，那么从状态i到状态j连一条标记为 Xi 的箭弧。7.2.4 LR(0)项目集规范族的构造项目集规范族的构造7.2.4 LR(0)项目集规范族的构造项目集规范族的构造2)若若 Xi为非终结符为非终结符，则也会有以它为左部的有关项目及其相应的状态，如果有项目形如i:XA

13、k:A 则从状态i画标记为的箭弧到状态k。3.构造识别活前缀的构造识别活前缀的NFA（续）（续）例题：构造识别文法G活前缀的NFA3.构造识别活前缀的构造识别活前缀的NFA（续）（续）7.2.4 LR(0)项目集规范族的构造项目集规范族的构造NFA7.2.4 LR(0)项目集规范族的构造项目集规范族的构造DFA4.LR(0)项目集规范族的构造项目集规范族的构造构成识别一个文法活前缀的构成识别一个文法活前缀的DFA项目集项目集(状态状态)的全体，称为的全体，称为这个文法的这个文法的LR(0)项目集规范族。项目集规范族。先构造NFA再确定化的方法工作量太大，有无省劲办法？7.2.4 LR(0)项目

14、集规范族的构造项目集规范族的构造 因而可以采用闭包运算来计算DFA一个状态的项目集。规律规律:若状态中包含形如若状态中包含形如AB的项目，则形如的项目，则形如B的项目也在此状态内的项目也在此状态内。例如：0状态中项目集为SE，EaA,EbB。n项目集的闭包运算项目集的闭包运算设设I为一项目集，为一项目集，I的闭包运算的闭包运算CLOSURE(I)定义如下：定义如下：I中的每一个项目都属于中的每一个项目都属于CLOSURE(I)。如项目如项目A1X2属于属于CLOSURE(I)，且，且X为非终结符号，为非终结符号，则将形式为则将形式为X的项目添加到的项目添加到CLOSURE(I)中。中。重复重复

15、(1)和和(2)，直到，直到CLOSURE(I)封闭为止。封闭为止。7.2.4 LR(0)项目集规范族的构造项目集规范族的构造例例:文法文法GE：EE，EE+T，ET，TT*F，TF，F(E)，Fi，设项目集，设项目集 I=EE，求，求CLOSURE(I)根据第根据第2条，将条，将 EE+T和和ET 加进加进CLOSURE(I)CLOSURE(I)=E E，EE+T，ET 根据第根据第3条，重复计算，直到条，重复计算，直到CLOSURE(I)封闭为止。封闭为止。将将TT*F和和TF加进加进CLOSURE(I)CLOSURE(I)=E E，EE+T，ET，TT*F，TF 将将F(E)和和F i，

16、加进，加进CLOSURE(I)中：中：CLOSURE(I)=EE,EE+T,ET,TT*F,TF,F(E),Fi 至此，至此，CLOSURE(I)封闭。封闭。解：根据解：根据闭包运算的第闭包运算的第1条，条，CLOSURE(I)=EE n 项目集的闭包运算项目集的闭包运算n 项目集之间的转换函数项目集之间的转换函数GO设设I是一个项目集，是一个项目集，X是任一文法符号，则项目集之间的转是任一文法符号，则项目集之间的转换用换用GOI,X函数表示为函数表示为：GOI,X=CLOSURE(J)其中其中J=任何具有任何具有AX的项目的项目|AXI，即为即为对项目集对项目集I中所有的项目进行读中所有的项

17、目进行读X操作的结果。并将操作的结果。并将CLOSURE(J)称为称为I的后继项目集。的后继项目集。7.2.4 LR(0)项目集规范族的构造项目集规范族的构造例：有项目集例：有项目集例：有项目集例：有项目集I=EE,E E+T,求求 GOI,+解解:在在I中挑出点后是中挑出点后是+的项目的项目:E E+T,将点移到将点移到+后面得后面得J=E E+T对对J进行闭包运算得进行闭包运算得 GO(I,+)=CLOSURE(J)=EE+T，TF，TT+F,F(E),Fi用状态图表示为：用状态图表示为：I:E E.E E.+T J:E E+.T,T.F T.T+F,F.(E),F.i+7.2.4 LR(

18、0)项目集规范族的构造项目集规范族的构造n 项目集之间的转换函数项目集之间的转换函数GO7.2.4 LR(0)项目集规范族的构造项目集规范族的构造n LR(0)项目集规范族的构造步骤项目集规范族的构造步骤1)置项目置项目SS为初态集的核，然后对核求闭包，为初态集的核，然后对核求闭包，Closure(SS)得到初态的项目集。得到初态的项目集。2)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数 Go(I,X)=Closure(J)求出新状态求出新状态J的项目集。的项目集。3)重复重复2)直到不出现新的项目集为止。直到不出现新的项目集为止。n小结：构造识别文法活前小

19、结：构造识别文法活前缀缀DFA的三种方法的三种方法根据形式定义求出活前缀的正规表达式，然后由此正规表根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造达式构造NFA再确定化为再确定化为DFA。求出文法的所有项目，按一定规则构造识别活前级的求出文法的所有项目，按一定规则构造识别活前级的NFA再确定化为再确定化为DFA。把拓广文法的第一个项目把拓广文法的第一个项目SS作作为初态集的核，通过求为初态集的核，通过求核的闭包和转换函数，求出核的闭包和转换函数，求出LR(0)项目集规范族，再由转换项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的函数建立状态之间的连接关系得到识别活前

20、缀的DFA。7.2.4 LR(0)项目集规范族的构造项目集规范族的构造5 LR(0)分析表的构造分析表的构造假假设设已构造出已构造出LR(0)项项目集目集规规范族范族为为C=I0,I1,In，其，其中中Ik为项为项目集的名字，目集的名字，k为为状状态态名，令包含名，令包含SS 项项目的目的集合集合Ik的下的下标标k为为分析器的初始状分析器的初始状态态。那么。那么LR(0)分析表的分析表的ACTION表和表和GOTO表可按照如下方法构造。表可按照如下方法构造。7.2.4 LR(0)项目集规范族的构造项目集规范族的构造7.2.4 LR(0)项目集规范族的构造项目集规范族的构造5 LR(0)分析表的

21、构造分析表的构造:1)若项目若项目A a属于属于Ik,且且GO(Ik,a)=Ij，其中，其中a为终结符，则置为终结符，则置ACTIONk,a为为“Sj”:“把状态把状态j和符号和符号a移进栈移进栈”。2)若项目若项目A 属于属于Ik，则对任何终结符则对任何终结符a，置置ACTIONk,a为为“rj”:“用文法中第用文法中第j条产生式条产生式A进行规约进行规约”；3)若项目若项目SS 属于属于Ik,则置则置ACTIONk,#为为“acc”;4)若若GO(Ik,A)=Ij，A为非终结符，则置为非终结符，则置GOTO(k,A)=j;5)分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格

22、均置上填入信息的空白格均置上“error”例例 GS为为:S a A c B e A b A Ab B d1)构造识别活前缀的构造识别活前缀的DFA 2)构造它的构造它的LR(0)分析表。分析表。3)给出输给出输入入符号串符号串 abbcde 和和 abbbce 的的LR(0)分析步骤。分析步骤。LR(0)项目集规范族的构造实例项目集规范族的构造实例GS拓广拓广为为:S S S a A c B e A b A Ab B dI I0:S S S a A c B e I I1:S S I I2:S a A c B e A b A AbI I3:S a A c B e A A bI I4:A b I

23、 I5:S a A c B e B dI I7:S a A c B eI I8:B d I I9:S a A c B e I I6:A A b SaAbbcBedGL=ab+cdeGS的的LR(0)分析表分析表Step states.Syms.The rest of inputAction Goto 1 0#abbcde#s2 2 02#a bbcde#s4 3 024#ab bcde#r2 3 4 023#aA bcde#s6 5 0236#aAb cde#r3 3 6 023#aA cde#s5 7 0235#aAc de#s8 8 02358#aAcd e#r4 7 9 02357#aA

24、cB e#s9 10 023579#aAcBe#r1 1 11 01#S#acc 对输入串对输入串abbcde#的分析过程的分析过程GS:(0)S S (1)S a A c B e (2)A b (3)A Ab (4)B dStep states.Syms.The rest of input Action Goto 1 0#abbce#s2 2 02#a bbce#s4 3 024#ab bce#r2 3 4 023#aA bce#s6 5 0236#aAb ce#r3 3 6 023#aA ce#s5 7 0235#aAc e#出错出错 对输入串对输入串abbce#的分析过程的分析过程GS:

25、(0)S S (1)S a A c B e (2)A b (3)A Ab (4)B d所以所以abbce#不是不是文法文法GS的的句子句子LR(0)文法小结文法小结定义形式一：定义形式一：按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分两部分的分析表，如果每个入口不含多重定义，则称之的分析表，如果每个入口不含多重定义，则称之为为LR(0)分析表。能构造分析表。能构造LR(0)分析表的文法称为分析表的文法称为LR(0)文法。文法。LR(0)文法是无二义的。文法是无二义的。n即即LR(0)文法同一项目集中不能出现以下情况文法同一项目集中不能出现以下情况定义形式二：定义形式二：对一个文法的对一个文法的LR(0)项目集规范族不存在移进项目集规范族不存在移进-归约，归约，或归约或归约-归约冲突时，称这个文法为归约冲突时，称这个文法为LR(0)文法文法。LR(0)文法小结文法小结