编译原理总结7_语法4

1、1什么是什么是LR(k)LR(k)分析分析: : L L：从左到右扫描：从左到右扫描 R R：最右推导的逆过程（最左归约）：最右推导的逆过程（最左归约） k k：为作出分析决定而向前看的输入符号的个数：为作出分析决定而向前看的输入符号的个数 是一种规范归约过程是一种规范归约过程 LR(k) LR(k)分析技术分析技术KnuthKnuth于于19651965年首先提出年首先提出4.7 LR4.7 LR分析法分析法2q 适用范围广适用范围广，适用于多数无二义性，适用于多数无二义性2 2型文法型文法q 分析分析效率高效率高，报错及时报错及时q 可以可以自动生成自动生成q 手工实现手工实现工作量大工作

2、量大LRLR分析法的优缺点分析法的优缺点优点优点缺点缺点4.7 LR4.7 LR分析法分析法3LRLR分析器的逻辑结构：分析器的逻辑结构：分析栈、分析表、总控程序分析栈、分析表、总控程序LRLR分析器的逻辑结构和工作过程分析器的逻辑结构和工作过程栈栈# #S S0 0X X1 1S S1 1X Xm mS S1 1文法符号文法符号状态状态输入输入#总控程序总控程序ACTION GOTOLRLR分析表分析表产生式表产生式表输出输出4.7 LR4.7 LR分析法分析法4分析表的种类：四类分析表的种类：四类SLR(1)SLR(1)分析表分析表( (简单简单LRLR分析表分析表) ) LR(0)LR(

3、0)分析表分析表构造简单构造简单, ,最易实现最易实现, ,大多数上下文无关文法都可以大多数上下文无关文法都可以构造出构造出SLRSLR分析表，所以具有较高的实用价值。使分析表，所以具有较高的实用价值。使用用SLRSLR分析表进行语法分析的分析器叫分析表进行语法分析的分析器叫SLRSLR分析器。分析器。对文法的限制较大，无实用价值，对文法的限制较大，无实用价值，是构造其它是构造其它LRLR分析表的基础。分析表的基础。（重点掌握）（重点掌握）4.7 LR4.7 LR分析法分析法5LR(1)LR(1)分析表分析表( (规范规范LRLR分析表分析表) )适用文法类最大适用文法类最大, ,几乎所有上下

4、文无关文法几乎所有上下文无关文法都能构造出都能构造出LR(1)LR(1)分析表，但其分析表体积分析表，但其分析表体积太大，实用价值不大。太大，实用价值不大。LALR分析表分析表(超前超前LR分析表分析表) 这种表适用的文法类及其实现上难易在这种表适用的文法类及其实现上难易在LR(1)LR(1)和和SLR(1)SLR(1)两种之间，比较实用。使用两种之间，比较实用。使用LALRLALR分分析表进行语法分析的分析器叫析表进行语法分析的分析器叫LALRLALR分析器。分析器。说明：四种分析表对应四类文法说明：四种分析表对应四类文法4.7 LR4.7 LR分析法分析法6LR(0)LR(0)分析法分析法

5、l LR(k)LR(k)分析法通过分析法通过活前缀活前缀来帮助确定句柄来帮助确定句柄活前缀：活前缀：规范句型中不含句柄右边任何符号的前缀规范句型中不含句柄右边任何符号的前缀规范句型规范句型：通过规范推导（规约）得到的句型：通过规范推导（规约）得到的句型前缀前缀：句型的任意首部：句型的任意首部 如如 abc abc 的前缀有的前缀有, a, b, ab, abc, a, b, ab, abc4.7 LR4.7 LR分析法分析法7LR分析器的工作过程分析器的工作过程逐步产生文法的规范句型逐步产生文法的规范句型活前缀活前缀的过程的过程当栈顶形成当栈顶形成句柄句柄时，立即进行归约时，立即进行归约4.7

6、 LR4.7 LR分析法分析法8活前缀与句柄的关系活前缀与句柄的关系为刻划产生式右部符号已有多大一部分为刻划产生式右部符号已有多大一部分被识别，用项目来指示位置被识别，用项目来指示位置项目项目: :产生式的右部添加一个圆点产生式的右部添加一个圆点 活前缀已含有句柄的活前缀已含有句柄的全部全部符号符号AA 的右部的右部 已出现在栈顶，可以已出现在栈顶，可以归约归约 AA 活前缀只含有句柄的活前缀只含有句柄的部分部分符号符号AA 1 1 2 2的右部子串的右部子串 1 1已出现在栈顶，正期待已出现在栈顶，正期待从剩余输入串中能看到由从剩余输入串中能看到由 2 2推出的符号串推出的符号串 AA 1

7、1 2 2 活前缀活前缀不含有不含有句柄的任何符号句柄的任何符号期望从剩余输入串中能看到由某产生式期望从剩余输入串中能看到由某产生式AA 的右部的右部 所推出的符号串所推出的符号串 AA 4.7 LR4.7 LR分析法分析法9项目的直观意义项目的直观意义: :在分过程中的某一时刻已经规约的在分过程中的某一时刻已经规约的 部分和等待规约部分部分和等待规约部分【例例】文法文法GSGS：SaS|bSaS|b 写出其所有的写出其所有的LR(0)LR(0)项目。项目。 SSaSaS，SaSaS S，SaSSaS，SSb b，SbSb一个产生式对应的项目个数是右部符号长度加一个产生式对应的项目个数是右部符

8、号长度加1 1产生式产生式AA 的项目个数只有一个，即的项目个数只有一个，即AA 4.7 LR4.7 LR分析法分析法10项目分为四类项目分为四类圆点后面是终结符，表示栈内是句柄的一部分，圆点后面是终结符，表示栈内是句柄的一部分，期待从输入串中移进一个符号，以形成句柄。期待从输入串中移进一个符号，以形成句柄。 移进项目：移进项目：AAaa 待约项目：待约项目：AABB圆点后面是非终结符的项目，表示栈内是句柄的一部分，圆点后面是非终结符的项目，表示栈内是句柄的一部分，为了形成句柄，期待从剩余的输入串中进行归约而得到为了形成句柄，期待从剩余的输入串中进行归约而得到，然后才能继续分析，然后才能继续分

9、析A A的右部。的右部。4.7 LR4.7 LR分析法分析法11项目分为四类项目分为四类 归约项目：归约项目：AA 圆点在最后，表示栈顶的部分内容已构成所期望的句柄，圆点在最后，表示栈顶的部分内容已构成所期望的句柄，应使用产生式应使用产生式AA进行归约。进行归约。 接受项目：接受项目：SS特殊的归约项目，使用产生式特殊的归约项目，使用产生式SS进行归约，进行归约，表示整个句子已经分析完毕，分析成功，也即输表示整个句子已经分析完毕，分析成功，也即输入串为该文法的句子。入串为该文法的句子。4.7 LR4.7 LR分析法分析法12构造识别活前缀的构造识别活前缀的DFA（1 1）求出文法的所有项目，按

10、一定规则构造）求出文法的所有项目，按一定规则构造NFANFA， 再确定化为再确定化为DFADFA（2 2）直接构造）直接构造DFADFA（重点掌握）（重点掌握） 有两种方法有两种方法4.7 LR4.7 LR分析法分析法13构造活前缀的方法一：构造活前缀的方法一：NFANFADFA DFA （1 1）设所有）设所有LR(0)LR(0)项目分别对应项目分别对应NFANFA的一个状态，其中含有文的一个状态，其中含有文 法开始符号的产生式法开始符号的产生式S SSS的第一个项目（的第一个项目（S SS S）作为）作为 NFANFA的唯一初态，归约项目对应为终态。的唯一初态，归约项目对应为终态。 （2

11、2）若状态）若状态i i和和j j中的中的LR(0)LR(0)项目出自同一条产生式，只是圆项目出自同一条产生式，只是圆 点的位置相差一个符号，即：点的位置相差一个符号，即： i i为：为：XXXX1 1X X2 2X Xi-1i-1X Xi iX Xn n j j为：为：XXXX1 1X X2 2X Xi-1i-1X Xi iX Xi+1i+1X Xn n 则从状态则从状态i i到状态到状态j j连一条标记为连一条标记为X Xi i的箭弧，说明在状态的箭弧，说明在状态 i i下，识别了符号下，识别了符号X Xi i后，后，NFANFA从状态从状态i i转换为状态转换为状态j j。4.7 LR4

12、.7 LR分析法分析法14构造活前缀的方法一：构造活前缀的方法一：NFANFADFA DFA 4.7 LR4.7 LR分析法分析法（3 3）若状态）若状态i i为待约项目，即：为待约项目，即： i i为：为：AA B B 则也会有以非终结符则也会有以非终结符B B为左部的相关项目及其相应状为左部的相关项目及其相应状 态，如状态态，如状态k k，k k为：为：BB 则从状态则从状态i i到状态到状态k k连一条标记为连一条标记为 的箭弧。的箭弧。154.7 LR4.7 LR分析法分析法构造活前缀的方法二：直接构造构造活前缀的方法二：直接构造DFADFA 方法一：方法一：工作量大工作量大，不适用，

13、不适用 方法二：分析方法二：分析DFADFA状态的项目集之间、项目集内的项目之间状态的项目集之间、项目集内的项目之间 的的规律规律性，性，直接构造直接构造出出DFADFAq 若项目集中有若项目集中有YY X X ，另一项目集中有，另一项目集中有YY X X ，则这，则这 两个项目集之间必有一条两个项目集之间必有一条X X弧。如，弧。如，I I0 0 和和I I1 1、I I2 2、I I3 3等。等。q 若项目集中有若项目集中有AA B B ，则必有，则必有BB，其中，其中BB是产是产 生式。如，生式。如，I I0 0 和和 I I2 2。16先给出两个定义：先给出两个定义： A. A. 项目

14、集闭包函数项目集闭包函数closureclosure B. B. 状态转移函数状态转移函数GOGO4.7 LR4.7 LR分析法分析法A. A. 项目集闭包函数项目集闭包函数closure(I)closure(I) （1 1）每一个）每一个I I中的项目都加进中的项目都加进closure(I)closure(I)； （2 2）若）若AABclosure(I) Bclosure(I) 且且 BB产生式，若产生式，若 BBclosure(I)closure(I)，则将，则将BB加进加进closure(I)closure(I)； （3 3）重复执行（）重复执行（2 2）直到）直到closure(I)

15、closure(I)不再增大为止。不再增大为止。17【例例】（0 0）SSS S （1 1）SSSS （2 2）SSaS aS （3 3）SaSaS S （4 4）SaSSaS （5 5）SSb b （6 6）SbSb4.7 LR4.7 LR分析法分析法I= SI= SS S closure(I)=closure(I)=？ S SS , SS , SaS , SaS , Sb b 练习：练习：I= SaI= SaSS closure(I)= closure(I)=？ Sa SaS , SS , SaS , SaS , Sb b 18B. B. 状态转移函数状态转移函数GOGO，X X是文法符号

16、是文法符号 GO(I,X)=closure(J)GO(I,X)=closure(J) J= J=形如形如AXAX的项目的项目|A|AXIXI求求GO (I , b )=?GO (I , b )=?GO(I,b)=closure(SbGO(I,b)=closure(Sb)=Sb)=Sb 【例例】（0 0）SSS S （1 1）SSS S （2 2）S SaS aS （3 3）S Sa aS S （4 4）S SaSaS （5 5）S Sb b （6 6）S Sb b求求GO (I , a )=?GO (I , a )=?GO(I,a)=closure(SaGO(I,a)=closure(SaS)

17、=SaS)=SaS,SS,SaS,SaS,Sbb例：例：I= SI= SS , SS , SaS , SaS , Sb b 4.7 LR4.7 LR分析法分析法19GO(I,X) GO(I,X) 的直观意义是的直观意义是: :从状态从状态I(I(项目集项目集) )出发，经过出发，经过X X弧弧 所应该到达的状态所应该到达的状态( (项目集项目集) )。在在LRLR分析中，若分析中，若I I中有圆点位于中有圆点位于X X左边的项目左边的项目AAXX， 则当分析器从输入符号串中识则当分析器从输入符号串中识别出文法符号后，分析器要进入后续状态。别出文法符号后，分析器要进入后续状态。4.7 LR4.7

18、 LR分析法分析法204.7 LR4.7 LR分析法分析法直接构造直接构造DFA的思想的思想q 从从S SS S开始，得到开始，得到DFADFA的的初态项目集初态项目集q 然后通过状态转换函数然后通过状态转换函数GOGO求其所有的求其所有的后继项目集后继项目集算法算法C=closure(SC=closure(SS ); S ); do for(Cdo for(C中的每个项目集中的每个项目集I I和每个符号和每个符号X X if(GO(I,X) if(GO(I,X)非空非空, ,且不在且不在C C中中) ) 把把GO(I,X)GO(I,X)加入加入C C中中; ; while( C while(

19、 C增大增大) ) return C;return C;214.7 LR4.7 LR分析法分析法LR(0)LR(0)分析表的构造分析表的构造（1 1）若）若AA a a IIk k，且，且GO(IGO(Ik k,a)=I,a)=Ij j(aV(aVT T) )，则置，则置ACTIONk,a=sACTIONk,a=sj j；（2 2）若）若AA IIk k，则对任意终结符，则对任意终结符a a（包括（包括# #）置）置ACTIONk,a=rACTIONk,a=rj j （j j为产生式为产生式AA 的编号）；的编号）；（3 3）若项目）若项目SSSSIIk k，则置，则置ACTIONk,#=ac

20、cACTIONk,#=acc；（4 4）若）若GO(IGO(Ik k,A)=I,A)=Ij j(AV(AVN N) )，则置，则置GOTOk,A=jGOTOk,A=j；（5 5）不能用上述方法填入内容的单元置为）不能用上述方法填入内容的单元置为“出错标志出错标志”（用空白表示）。（用空白表示）。 22状状态态ACTIONACTION表表GOTOGOTO表表a ab b# #S S0 0S2S2S3S31 11 1accacc2 2S2S2S3S34 43 3r2r2r2r2R2R24 4r1r1r1r1r1r14.7 LR4.7 LR分析法分析法LR(0)LR(0)分析表的构造分析表的构造I

21、I0 0:S:SS S S SaSaS S Sb bI I1 1:S:SSSI I3 3:S:SaaS SI I2 2:S:SaaS S SSaSaS S Sb bI I4 4:S:SaSaSS Sb ba aS Sb ba a234.7 LR4.7 LR分析法分析法【例例】文法文法GSGS ： （1 1）S SSS （2 2）SaS|bSaS|b 构造构造LR(0)LR(0)分析表。分析表。（1 1）写出文法）写出文法G G的拓广文法的拓广文法G G；（2 2）写出文法）写出文法GG的基本的基本LR(0)LR(0)项目；项目；（3 3）利用函数）利用函数closureclosure和和GOG

22、O，求出相应的项目集规范族，求出相应的项目集规范族C C； （4 4）构造识别文法）构造识别文法GG所有活前缀的所有活前缀的DFADFA；（5 5）根据）根据DFADFA构造构造LR(0)LR(0)分析表。分析表。24或存在或存在归约归约归约归约冲突：冲突：A. BA. B. .一个项目集中存在一个项目集中存在移进移进- -归约归约冲突：冲突：A.a BA.a B . .LR(0)LR(0)分析表具有多重定义入口分析表具有多重定义入口, ,分析动作不唯一分析动作不唯一LR(0)LR(0)分析法存在的问题分析法存在的问题4.7 LR4.7 LR分析法分析法254.7 LR4.7 LR分析法分析法

23、SLR(1)SLR(1)分析法分析法 若若LR(0)LR(0)项目集规范族中有项目集项目集规范族中有项目集I Ik k含移进含移进- -归约或归约归约或归约- -归约冲突归约冲突 I Ik k=X.b=X.b，A A. .，B B. 若若FOLLOW(A)FOLLOW(B)=FOLLOW(A)FOLLOW(B)= ，FOLLOW(A)b=FOLLOW(A)b= ，FOLLOW(B)b=FOLLOW(B)b= 则解决冲突的则解决冲突的SLR(1)SLR(1)技术：技术：对于归约项目向前查看一个符号对于归约项目向前查看一个符号ACTIONACTIONk,b=k,b=移进移进对对a a FOLLOW(A)FOLLOW(A) 则则 ACTIONACTIONk,a=k,a=用用A A归约归约对对a a FOLLOW(BFOLLOW(B) ) 则则 ACTIONA