第5讲--语法分析下

1、CompilerPrinciples1u语法分析概述语法分析概述u自上而下语法分析自上而下语法分析u自下而上语法分析自下而上语法分析CompilerPrinciples2内容提要内容提要v基本问题基本问题vLR分析方法分析方法LR分析器LR分析表规范LR分析LALR分析二义文法的应用出错处理分析器的自动生成CompilerPrinciples3 前面已经谈了自下而上分析的基本思想，就是自左而右地扫描输入源程序单词符号串，并逐步进行自下而上的归约，直至规约到文法的开始符号；或者说，从树的末端开始，一步步向上归约，直至树根。这种构造树的过程与我们通常的从根开始构造的方法刚好是一个逆过程，因此这种树

2、又称为语法分析树。1 1. .基本问题基本问题CompilerPrinciples41.归约与语法分析树归约与语法分析树 上述思想可用如下的一个例子来说明：例 文法 GS: (1)SaAcBe (2)Ab (3)AAb (4)Bd显然，abbcde是该文法的一个句子，于是可如右构造其语法分析树：a ab bb bc cd de eA AA AB BS S* *该语法树的构造的确是一个“自左而右、自下而上”的过程，我们把这一类分析方法统称为“自下而上”的。CompilerPrinciples52.移进归约移进归约 在计算机上模拟以上的语法分析树的构造过程，可借助于一个符号栈来实现：输入串：输入串

3、： abbcde#abbcde#步骤：步骤：动作：动作：符号栈：符号栈：12345678910移进移进a a移进移进b b 归约归约b b 移进移进b b 归约归约AbAb移进移进c c 移进移进d d归约归约d d归约归约aAcBeaAcBe移进移进e e归约产归约产生式：生式：#a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S(2)(3)(4)(1)CompilerPrinciples6分析方法的基本思想v将待分析的符号串从左向右进行扫描，并将串中符号一个一个地移入栈中，边移入边分析；当栈顶符号串形成所给文法的某个产生式右部时就进行一次归约，即用该产生式的左部非终结

4、符替换相应右部符号串。把栈顶被归约的这一串符号称为可归约串。重复这一过程，若能归约到文法的识别符号，则该分析的符号串是该文法的句子，否则不是。分析过程中的关键问题分析过程中的关键问题如何找出栈顶当前可归约串的问题？包括：如何定义可归约串？如何识别可归约串？CompilerPrinciples7 为了寻找可归约串，先来看两个定义： (1)短语、直接短语和句柄： 令G是一个文法，S是开始符号，是文法G的一个句型，如果有 S * A且A +， 则称是句型相对于非终结符A的短语。 特别的，如果有A ，则称是句型相对于规则A的直接短语，一个句型的最左直接短语称为该句型的句柄。CompilerPrinci

5、ples8CompilerPrinciples9v 接下来我们介绍一种强大的自下而上语法分析技术，它可用于大多数CFG的语法分析，称为LR分析法。L表示从左至右扫描输入串，R表示构造一个最右推导的逆过程。v LR分析法比其他的“移进归约”法更加广泛，效率也不比它们差；比一般不带回溯的自上而下分析（如LL(1)分析）也要好一些，而且在自左而右扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。v 当然，要适应一般情况，分析器就得更加复杂。因此，LR分析器的手工构造工作量相当大，一般要借助于自动产生器。2 2.LR.LR分析法分析法CompilerPrinciples10 1.LR分析器

6、(1)概述： 根据前面的介绍我们知道：自下而上分析的中心思想是“移进归约”，关键问题就是“寻找规范句型的句柄”。当一貌似句柄的符号串呈现于分析栈顶时，如何确定用哪一个产生式来归约？这是我们一直未能解决的问题。 仔细分析问题产生的原因，我们会发现，在分析过程中我们没有利用到已处理的过程“历史资料”，也没有根据产生式去“瞻望”未来可能遇到的输入符号，而LR分析法就是在这些方面对“移进归约”进行改造的。 LRLR分析法的基本思想：根据分析法的基本思想：根据“历史资料历史资料”、“现实输入现实输入符号符号”以及对未来的以及对未来的“展望展望”等三个方面来确定栈顶的符号等三个方面来确定栈顶的符号是否构成

7、了相对于某一产生式的句柄。是否构成了相对于某一产生式的句柄。它是由Knuth在1965年首先提出的，后经Aho等人改造而成。CompilerPrinciples11 一个一个LRLR分析器实际上是一个带有分析栈的分析器实际上是一个带有分析栈的DFADFA 前面讲过，状态的变化可以反映出处理前后的经过，因此这儿我们应把“历史”和“展望”材料都综合为“状态”，存入分析栈，使得任何时候，栈顶都代表了从分析开始以来的全部“历史”和已推测出的“展望”。这样一来，在任何时候都可从栈顶来了解一切，栈顶状态和现行输入符号就唯一决定了LR分析器的每一步工作。 栈中每一项内容包括状态s和文法符号X两部分。栈的初始

8、值为(s0,#)。栈顶状态为sm，符号串X1X2Xm是至今已移进归约出的部分。 如下图所示：CompilerPrinciples12s s0 0s s1 1s sm m# #X X1 1X Xm mLRLR分析器分析器# #a an na ai ia a1 1输出输出输入串输入串分析栈分析栈分析表分析表LRLR分析器模型图分析器模型图ActionActionGotoGotoCompilerPrinciples13 分析表分析表 LR分析器的核心是一张分析表。这张表包括两部分：“动作”(Action)和“状态转换”(Goto) ，它们都是二维数组。Actions,a规定了状态s面临输入符号a时应

9、该采取什么动作；Gotos,X则指出状态s面对文法符号X（终结符或非终结符）时下一状态是什么。显然，Gotos,X定义了一个以文法符号为字母表的DFA。 CompilerPrinciples14 每一项Actions,a所规定的动作无非是下述四种可能之一：a.移进：把(s,a)的下一状态s=Gotos,a和输入符号a推进栈，下一输入符号变成现行输入符号；b.归约：指用某一产生式A进行归约。若|r,则把栈顶r个项托出，栈顶状态变成sm-r,然后把 (sm-r,A)的下一状态s=Gotosm-r,A和A进栈。归约动作不改变现行输入符号；（这意味着Xm-r+1 Xm=是一个相对于A的句柄）c.接受：

10、宣布分析成功，停止分析器的工作； d.报错：报告发现错误，调用出错处理程序扫描输入串就可以发现错误位置。CompilerPrinciples15 LR分析器的工作过程： 一个LR分析器的工作过程可以看成是栈里的状态序列、已归约串和输入串所构成的三元式的变化过程： 初始三元式： (s0, #, a1a2an#) 中间三元式： (s0s1.sm, #X1X2Xm, aiai+1an#) 接受: (s0sk,#X,#) (X为开始符号，而Actionsk,# 为接收) 分析器的下一步动作完全由sm和ai唯一决定，即执行Actionsm,ai。经执行每种可能的动作之后，三元式的变化情形是：Compil

11、erPrinciples16.若actionsm,ai为移进且s=gotosm,ai，则三元式变为： (s(s0 0s s1 1ssm ms, #Xs, #X1 1X X2 2XXm ma ai i, a, ai+1i+1aan n#)#).若actionsm,ai=A，则按产生式A进行归约，此时三元式变为： (s (s0 0s s1 1ssm-rm-rs s, #X, #X1 1X X2 2XXm-rm-rA, aA, ai ia ai+1i+1aan n#)#) 此处s s=gotos=gotosm-rm-r,A,A，r为的长度，=X=Xm-r+1m-r+1XXm m。.若actionsm

12、,ai为接受，则三元式不再变化，过程终止，分析成功。.若actionsm,ai为报错，则三元式的变化过程终止，报告错误。 LR分析器的工作过程就是一步一步地变换三元式，直至执行“接受”或“报错”为止。再看前面的例子：文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约归约(AAb) 6） #aA cde# 移进移进

13、 7） #aAc de# 移进移进B 8） # aAcd e# 归约归约(Bd) 9） #aAcB e# 移进移进11） #S # 接受接受S10） #aAcBe # 归约归约 这是前面讲过的对输入串这是前面讲过的对输入串abbcde#的移进的移进-规约分析过规约分析过程，下面我们来看如何用程，下面我们来看如何用LR分析法来分析该句子分析法来分析该句子步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1） # abbcde# 移进移进 0 S2 2） #a bbcde# 移进移进 02 S4 4） #aA bcde# 移进移进 023 S6 6） #aA cde# 移进移进 023 S5

14、7） #aAc de# 移进移进 0235 S8 9） #aAcB e# 移进移进 02357 S911） #S # 接受接受 01 acc 对输入串对输入串abbcde#的的LR分析分析过程：过程： 3） #ab bcde# 归约归约(Ab) 024 r2 3 5） #aAb cde# 归约归约(AAb) 0236 r3 3 8） # aAcd e# 归约归约(Bd) 02358 r4 710） #aAcBe # 归约归约(SaAcBe) 023579 r1 1状态栈状态栈ACTIONGOTOS Si i: :移进移进：将将下一下一状态状态i i和和现行现行输入符号输入符号进栈进栈；r ri

15、 i: :归约：用第归约：用第i i个产生式归约个产生式归约，同时状态栈与符号栈退出相，同时状态栈与符号栈退出相应的符号，并把应的符号，并把GOTOGOTO表相应状表相应状态和第态和第i i个产生式的个产生式的左部左部非终非终结符入栈。结符入栈。CompilerPrinciples19 (2) LR文法： 对于一个文法，如果能够构造出一张分析表，使得它的每个入口均是唯一的，则称该文法为LR文法。 注意：并非所以上下文无关文法都是LR文法，例： 二义性文法 SiCtS| |iCtSeS 直观上说，对于一个LR文法，当分析器对输入串进行自左而右扫描时，一旦句柄呈现于栈顶，就能及时对它进行归约。 一

16、个LR分析器有时需要“展望”未来的k个输入符号才能决定应采取什么样的“移进归约”决策。于是又有如下定义: 对于文法G，若能用一个每步顶多向前查看k个输入符号的LR分析器进行分析，则称之为LR(k)文法。但是对大多数的程序语言来说，k1就足够了。因此，我们只研究LR(0)和LR(1)。CompilerPrinciples202. 分析表的构造分析表的构造 (1)LR(0)分析表的构造 首先讨论一种只概括“历史”资料而不包含推测性“展望”材料的分析法LR(0)分析法。我们希望仅由这种简单状态就能识别呈现在栈顶的某些句柄。而LR(0)项目集就是这样的简单状态。 LR(0)项目集： a.字的前缀：字的

17、任意首部。如abc: a, ab, abc. b.活前缀：规范句型的一个前缀，它不含句柄之后的任何符号。之所以称之为活前缀，是因为在其右边添加一些终结符号后就可以形成规范句型。CompilerPrinciples21 在LR分析过程中的任何时候，栈里的文法符号（自栈底向上）X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型。反过来说，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着扫描过的部分没有错误。 这样来看，如果我们能构造出一个FA，它能识别某文法G的所有活前缀，那么我们就可以通过这个FA来构造G的LR分析表了，为此我们定义“项目” (item) ： Comp

18、ilerPrinciples22 c.LR(0)项目：文法G的每一个产生式的右部添加一个圆点称为G的一个LR(0)项目（简称项目）。 例如，产生式AXYZ对应四个项目： AXYZ AXYZ AXYZ AXYZ 当然，A只对应一个项目：A 。在计算机中，每个项目可用一个整数对表示：第一个整数代表产生式编号，第二个指出圆点的位置。 CompilerPrinciples23 实际上，项目反映了分析过程中某时刻我们看到产生式的多大部分。如AXYZ 意味着我们希望能从后面输入串看到可以从XYZ推导出的符号串。AXYZ意味着我们已经从输入串看到了从X推导出的符号串，并希望能进一步看到YZ推出的符号串。v

19、为了方便，我们把形如A的项目称为“归约项目”，开始符号S的归约项目S称为“接受”项目。形如Aa的项目，称为“移进”项目；形如AB的项目则称为“待约”项目，其中aVT, BVN 。这儿介绍项目是为了以项目作为要构造的FA的状态。 CompilerPrinciples24构造识别活前缀的DFA .通过项目构造一个NFA ： a.把项目编号，所有编号构成NFA的状态集； b.以开始符号S S所对应的项目S S 为唯一初态 c.若项目i为：XXXX1 1XXi-1i-1X Xi iXXn n而项目j为： XX XX1 1XXi iX Xi+1i+1XXn n ，则从i到j画一条标记为X Xi i的 弧

20、；若XiVN，则从状态i画弧到所有的Xi 状态； d.除初态外的任何状态都认为是终态（活前缀识别 态）。 .用子集法把NFA确定化为DFA建立LR分析算法的基础。 下面我们来看一个例子：CompilerPrinciples25v例例 文法文法GS: (0)S (0)SE (1) EaA (2) EbBE (1) EaA (2) EbB (3)AcA (4) Ad (5) BcB (6) Bd (3)AcA (4) Ad (5) BcB (6) Bd 它的项目有：它的项目有： 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad

21、10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. BdCompilerPrinciples26(1)(1)构造构造NFANFA1 13 311112 24 46 65 57 79 98 810101212171714141515161618181313E Ea aA Ac cA Ad db bB Bc cB Bd dCompilerPrinciples27(2)(2)确定化确定化0: 0: S E EaA EbB2:2:EaA AcA Ad 3:3:EbB BcB Bd 4:4:AcA AcA Ad 5:5:Bc

22、B BcB Bd E Eb ba ac cc cA Ad dd dA AB Bd dd dB B1:1:SE8:8:AcA10: 10: Ad6: 6: EaA7:7:EbB11: 11: Bd9:9:BcBc cc cCompilerPrinciples28v下面我们来一起做一个练习：E - E + TE - TT - T * FT - FF - ( E )F - id构造这个文法的识别活前缀的自动机，并试着构造其分析表。CompilerPrinciples29v DFA的项目集的全体称为文法GS的LR(0)项目集规范族；也就是说：构成识别一个文法G的活前缀的DFA的项目集的全体，称为G的L

23、R(0)项目集规范族。这样一来，如果我们都能构造出LR(0)项目集规范族的话，就可以直接构造识别文法的活前缀的DFA了。下面我们就简单谈一下通过构造LR(0)项目集规范族来构造DFA的方法。 LR(0)项目集规范族的构造建立DFA的另一方法 a.为使“接受状态”唯一且易于识别，构造文法G的拓广文法G: 引进一个新的初态S VN=VNS , VT=VT , P=PSS 很显然，L(G)=L(G)。CompilerPrinciples30 b. 定义项目集定义项目集I I的闭包的闭包CLOSURE(I):CLOSURE(I): .I .I的任何项目都属于的任何项目都属于CLOSURE(I)CLOS

24、URE(I)； . .若若AB属于属于CLOSURE(I)CLOSURE(I)，那么，对任何，那么，对任何关于关于B的产生式的产生式B，项目，项目B也属于也属于CLOSURE(I)CLOSURE(I)； . .重复执行上述步骤直至重复执行上述步骤直至CLOSURE(I)CLOSURE(I)不再增大不再增大为止；为止； c. 定义状态转换函数定义状态转换函数GO: 对于项目集对于项目集I I和文法符号和文法符号X X(V(VN NVVT T),GO(I,X)=),GO(I,X)=CLOSURE(J),CLOSURE(J),其中其中: : J= J=任何形如任何形如AX的项目的项目AXII 也就是

25、说，也就是说，J J是由是由I I中那些中那些X X左边有圆点的项目，左边有圆点的项目，把圆点右移一个位置所得的项目的集合。把圆点右移一个位置所得的项目的集合。 CompilerPrinciples31 d. 通过闭包和状态转换函数，则我们很容易就可以求出G的LR(0)项目集规范族： PROCEDURE ITEMSETS(G); BEGIN C:= CLOSURE( SS ) ; REPEAT FORFOR C中的每个项目集I和G中的每个符号X DODO IFIF GO(I,X)非空且不属于C THENTHEN 把GO(I,X)放入C族中 UNTIL C不再增大 END (详见参考书)Comp

26、ilerPrinciples32 有效项目 我们希望从识别文法的活前缀的DFA建立LR分析器，因此需要研究这个DFA的每个项目集（状态）中的项目的不同作用。 a.a.若有规范推导S*A12 ( (VT*) ) ，则称项目A1 12 2对活前缀1 1是有效的。 直观上说，若归约项目A1对活前缀1是有效的，则是说应把1归约为A;若若A12对活前缀1是有效的，则说明句柄尚未形成，故应移进。 对每个活前缀r，都可以构造它的有效项目集。这个集合刚好就是从DFA的初态出发，经读出r后而到达的那个项目集。CompilerPrinciples33 b.定理： 任何时候分析栈中的活前缀X X1 1X X2 2X

27、Xm m的有效项目集正是栈顶状态Sm所代表的那个项目集。 这是LR分析理论的一条基本定理。实际上，栈顶的项目集（状态）体现了栈里的一切有用信息。 这儿需要指出的是，对同一活前缀，有可能存在若干项目对它都是有效的，而且要做的事情各不相同，互相冲突。这种冲突通过向前多看几个输入符号，或许可以解决。但是对于非LR文法，这种冲突是无法解决的。关于这点，以后再详细介绍。 下面再来看一下前面那个例子:CompilerPrinciples34v例：例：文法文法GS: SE EaA EbBE EaA EbB AcA Ad BcB Bd AcA Ad BcB Bd 识别其活前缀的识别其活前缀的DFADFA的一部

28、分如下图所示：的一部分如下图所示： 我们说我们说bcbc是一个活前缀，是一个活前缀，DFADFA从从0 0状态开始读出状态开始读出bcbc后后到达到达5 5状态，这个状态集对状态，这个状态集对bcbc是有效的。是有效的。0: 0: SE EaA EbB3:3:EbB BcB Bd 5:5:BcB BcB Bd 7:7:EbB11:11:Bd9:9:BcBb bc cB Bd dd dB Bc cCompilerPrinciples35 LR(0)LR(0)文法的定义文法的定义： 若一个文法G的拓广文法G的活前缀识别自动机中的每个状态不存在下述情况： a.既含移进项目又含归约项目； b.含有多个

29、归约项目 则称G是一个LR(0)文法。 也就是说，LR(0)文法规范族的每个项目集不包含任何冲突项目。 LR(0)LR(0)分析表的构造：分析表的构造： 现在我们通过DFA来构造LR(0)分析表，也就是通过项目集规范族C=I0,I1,In和函数GO，使用如下算法来构造：CompilerPrinciples36v 我们用每个项目集我们用每个项目集I Ik k的下标的下标k k作为分析器的状态。特别地，作为分析器的状态。特别地，令含有令含有SS的项目集的项目集I Ik k的下标的下标k k作为初态。于是如下构造子作为初态。于是如下构造子表表ActionAction、GotoGoto： . .若项目

30、若项目Aa I Ik k且且GO(IGO(Ik k,a)=I,a)=Ij j,a,aVT, 则置则置ActionActionk,ak,a为为“把把(j,a)(j,a)移进栈移进栈”，简记为，简记为“s sj j”； . .若项目若项目A I Ik k，那么对任意，那么对任意a aVT(或或#)，置置 ActionActionk,ak,a为为“用产生式用产生式A进行归约进行归约”，简记为，简记为 “ “r rj j”；( (设设A是文法是文法G的第的第j j个产生式个产生式) ) . .若项目若项目SS I Ik k，则置，则置ActionActionk,#k,#为为“接受接受”，简记为，简记为

31、 “acc”； . .若若GO(IGO(Ik k,A)=I,A)=Ij j，A AVN,则则GotoGotok,A=k,A=j j； . .分析表中凡不能用上述分析表中凡不能用上述4 4规则填入信息的空白格均置规则填入信息的空白格均置“报报 错标志错标志”； CompilerPrinciples37例上述文法例上述文法 GGS 其其LR(0)LR(0)分析表如右分析表如右: :(0) S(0) SE E (1) EaA (1) EaA (2) EbB(2) EbB(3) AcA (3) AcA (4) Ad (4) Ad (5) BcB(5) BcB(6) Bd(6) BdCompilerPr

32、inciples38 (2)SLR分析 问题的提出：LR(0)分析要求条件很苛刻，即使是定义算术表达式这样的简单文法，要想使识别其活前缀的DFA的每个状态都不含冲突项目也不可能。因此，有必要研究一种带带一点一点“展望展望”材料材料的LR分析法，也就是要检查一下下一个输入符号。 例如，I=Xbb,A,A,B,B ，第一个项目为移进项目，第二、三项是归约项目。到底应该采取哪种动作是不清楚的。如果我们分析一下该文法中所有含A,B的句型，考察Follow(A)和Follow(B)，若Follow(A) Follow(B)=且且都不含有都不含有b，则问题就解决了。当状态I面临输入a时，我们就可以采取如下

33、的“移进归约”策略： .若a=b,则移进； .若aFollow(A),则用A来归约；来归约； .若aFollow(B),则用B来归约；来归约； .此外，报错。CompilerPrinciples39一般而言，若一般而言，若LR(0)LR(0)规范族的一个项目集规范族的一个项目集I I中含有中含有m m个移进项目和个移进项目和n n个归约项目：个归约项目： I= A I= A1 1aa1 11 1, , A A2 2aa2 22 2.A Am maam mm m, , B B1 1,B,B2 2,.B,.Bn n ， 若集合：若集合： a a1 1,a,a2 2, ,.a am m Follow

34、(BFollow(B1 1) ).Follow(BFollow(Bn n)=)=，则则通过查看现行输入符号通过查看现行输入符号a a属于哪个集合就可以解决属于哪个集合就可以解决问题。问题。 .若若a=aa=ai i (i=1,2,m) , (i=1,2,m) ,则移进；则移进； . .若若a aFollow(Bi) (i=1,2,n),(i=1,2,n),则用则用Bi来来 归约；归约； . .此外，报错。此外，报错。 这种方法称为这种方法称为SLR(1)SLR(1)解决法解决法。CompilerPrinciples40 SLR分析表的构造 这个构造算法与LR(0)分析表的构造算法基本类似，只有

35、些许改动之处：若项目A Ik，那么对任意aVT且aFollow(A)，置Actionk,a为“用产生式A进行归约”，简记为“r rj j”； （详见参考书） 按照上述算法构造出的分析表，如果不含多重入口，则称之为G的SLR分析表；G称为一个SLR(1)文法，使用SLR分析表的分析器称为SLR分析器。每个SLR文法都是无二义的，但也存在许多无二义文法不是SLR(1)的,因为没有足够多的“展望”信息。 （例见参考书）CompilerPrinciples41 (3)规范LR分析法 前面我们定义LR(0)项目时，并没有牵扯到任何“展望”信息。只要DFA的某状态中含有归约项目A，那么当栈顶出现串时，我们

36、就能用A进行归约。现在我们想使每个状态含有较多的“展望”信息，这将有助于克服动作冲突和无效归约。为此，我们对项目重新定义： LR(k)项目：形如A,a1a2.ak的项目。 其中，A是一个LR(0)项目，每个aiVT。而a1a2.ak称为该LR(k)项目的向前搜索串（展望串）。类似的，A, a1a2.ak称为LR(k)归约项目，而AX, a1a2.ak或者是LR(k)移进项目(XVT)，或者是LR(k)待约项目(XVN)。CompilerPrinciples42v 可以想到，向前搜索串只是对LR(k)归约项目有意义，而对任何移进或待约没有作用。由于对大多数程序语言的语法来说，一般向前搜索一个符号

37、就可以确定“移进”或“归约”，因此，我们只对k1的情况感兴趣。 有效项目有效项目：一个LR(1)项目A,a对于活前缀=是有效的，如果存在： S* *A A 其中a是的第一个符号,或者 =, a=# 。 例例 考虑文法：SBB BaBb 它有一个规范推导S* *aaBabaaaBab, ,我们看到项目BaB,a对于活前缀=aaa是有效的。因为，=aa,A=B, =ab,=a,=b。同样，项目BaB,#对于活前缀Baa是有效的。 R RR RR RR RCompilerPrinciples43 构造有效的LR(1)项目集族思想同LR(0)项目规范集族 a.a.构造有效构造有效LR(1)LR(1)项

38、目集的闭包项目集的闭包：设I是一个项目集, .I的任何项目CLOSURE(I)； .若项目AB,aCLOSURE(I), B是一个产生式，则对于任何终结符bFIRST(a),B,b CLOSURE(I)； .重复步骤，直至CLOSURE(I)不再增大为止 。CompilerPrinciples44CompilerPrinciples45c.c.文法文法G G 的的LR(1)LR(1)项目集族项目集族C C的构造算法的构造算法： PROCEDURE ITEMSETS(GPROCEDURE ITEMSETS(G );); BEGIN BEGIN C:= CLOSURE( S C:= CLOSURE

39、( S S,# ) ;S,# ) ; REPEAT REPEAT FOR C FOR C中的每个项目集中的每个项目集I I和和G G 中的每个符中的每个符 号号X DOX DO IF GO(I,X) IF GO(I,X)非空且不属于非空且不属于C THENC THEN 把把GO(I,X)GO(I,X)放入放入C C族中族中 UNTIL CUNTIL C不再增大不再增大 ENDENDCompilerPrinciples46 规范规范LR(1)LR(1)分析表的构造分析表的构造与与LR(0)LR(0)基本上一样：基本上一样：.若项目若项目 Aa,b I Ik k且且GO(IGO(Ik k,a)=I

40、,a)=Ij j,a,aVT, 则置则置Actionk,aActionk,a为为 “ “s sj j”；.若若 A ,aI Ik k，则置，则置Actionk,aActionk,a为为 “ “r rj j”；.若若 S S ,#I Ik k，则置，则置Actionk,#Actionk,#为为 “acc”；.若若GO(IGO(Ik k,A)=I,A)=Ij j，A AVN,则则GotoGotok,A=k,A=j j；.分析表中凡不能用上述分析表中凡不能用上述4 4规则填入信息的空白格均置规则填入信息的空白格均置“报错标志报错标志”； 按照上述算法构造出的分析表，如果不含多重入口，则称之为G的LR

41、(1)分析表；G称为一个LR(1)文法，使用这种分析表的分析器称为规范的LR(1)分析器。显然，每个SLR(1)文法都是LR(1)文法。CompilerPrinciples47 (4)LALR分析表的构造（向前分析表的构造（向前LR） 前面介绍的SLR分析和规范LR分析都是通过“展望”信息来解决冲突的，但出发点不完全一样。前者仅对归约项才向前搜索，而后者是任何时候都向前搜索，显然SLR(1)分析表的状态要比LR(1)分析表少一些。像早期的Algol语言的SLR(1)分析表只要几百个状态，而其LR(1)分析表却要几千个状态。因此，用SLR分析更经济。但我们知道，LR (1)分析的能力要比SLR(

42、1)强很多。 于是，就有了这两者的一种折衷：LALR分析法。就状态数来说， LALR分析表同于SLR，因而也比规范LR分析表小得多；就功能来说，LALR要比SLR强，比规范LR分析要差。CompilerPrinciples48v 从自动机的角度来看，LALR似乎有点像把LR分析法最小状态化，其思想就是通过合并那些仅仅搜索符号串不同而其余完全相同的项目集。当然这样一来，ACTION表肯定要做相应的变动，但GO函数是无需变动的，因为它自身就会随项目集的变化而变化。为此，我们提出“同心”的概念： 两个LR(1)项目集是同心的：除去搜索符号串之后，这两个LR(1)项目集是完全相同的。实际上，一个心就是

43、一个LR(0)项目集。 我们知道，一个LR(1)文法的LR(1)项目集族是不存在冲突的，那么经过合并之后，会不会出现新的冲突呢？有可能！CompilerPrinciples49 a.同心合并不会导致同心合并不会导致“移进归约移进归约”冲突冲突。 因为如果存在这种冲突，则意味着对于当前的输入符号a，合并后的项目集中有一个项目A ,a要求归约动作，而另一项目B a,b 要求把a移进，这两个项目既然同处于合并后的一个集合之中，这就意味着在合并之前，必有某个c使得A ,a和和B a,c 同处于合并前的某个集合中，这样一来就说明了原来的LR(1)项目集中就已有“移进归约”冲突了，显然与我们的假设相矛盾。

44、因此，我们说同心集的合并决不会导致“移进归约”冲突。 CompilerPrinciples50 b.同心集合并可能导致新的同心集合并可能导致新的“归约归约归约归约”冲突。冲突。 例如，考虑文法G： (0) SS (1) SaAdbBdaBebAe (2) Ac (3) Bc 可以验证G是一个LR(1)文法。在G的LR(1)项目集族C中，对活前缀ac有效的项目集为： AcAc ,d ,d, BcBc ,e ,e，对活前缀bc有效的项目集为：AcAc ,e ,e, BcBc ,d ,d。显然这两个项目集同心且不含冲突。然而，同心集合并后则变成新项目集：AcAc ,d/e ,d/e, BcBc ,d

45、/e ,d/e。如此一来，当面临d,e时就不知道该用AcAc还是BcBc来归约，也就是有了“归约归约”冲突。CompilerPrinciples51 LALRLALR分析表的构造分析表的构造 基本思想：先构造基本思想：先构造LR(1)LR(1)项目集族，再合项目集族，再合并同心集。并同心集。 这儿要求： a.LR(1)项目集族不存在冲突； b.合并后的集族不含“归约归约”冲 突。 这个算法的步骤不再详细列出，请查阅参考书。CompilerPrinciples52v 对于正确的输入串，LR和LALR分析器工作基本一致，但有错误时，LALR可能比LR多做些不必要的规约，但是不会移进更多的符号，这就

46、保证了能准确地指出错误的位置，这一点与LR(1)是等效的。v 用同心合并来构造LALR分析表，虽简单明了，但太费存储空间。为此，人们又提出另一种构造LALR分析表的方法：造核法。v 关于项目集的核：一个项目集的核是此集中所有圆点不在最左边的项目组成的，但初态项目集的核有且只有S S S,#S,#项目。CompilerPrinciples53CompilerPrinciples54 (5)二义文法的应用二义文法的应用 通过前面的介绍，我们知道二义文法产生的分析表都含有多重入口，因此给我们的分析带来很多麻烦。人们已经证明：任何二任何二义文法都不是义文法都不是LR文法，因而也决不是文法，因而也决不是

47、SLR或或LALR文法文法。 但是二义文法也不是一无是处，某些二义文法还是非常有用的。例如： G1: EE+EE*E(E)i G2: EE+TT TT*FF F(E)iCompilerPrinciples55 G1与G2相比，有两个明显的好处 .如果要改变算符的优先关系或结合规则，G1不需做任何变动； .G1的分析表状态数比G2少，因为后者的单非产生式要占用不少状态； 既然二义文法有这样的好处，我们就要想办法利用它。这里我们就探讨一下如何使用LR分析法的基本思想，附加一些条件，来分析二义文法所定义的语言。 我们以文法G1为例来说明问题。它的LR(0)项目集规范族如下图所示：CompilerPr

48、inciples56I I0 0:E EEE EE+E EE+E EE EE* *E E E(E) E(E) Ei EiI I1 1:E EEE EE+E EE+E EE EE* *E EI I4 4:EE+E:EE+E EE+E EE+E EE EE* *E E E(E) E(E) Ei EiI I3 3:Ei:EiI I2 2:E(E):E(E) EE+E EE+E EE EE* *E E E(E) E(E) Ei EiI I7 7:E EE+EE+E EE+E EE+E EE EE* *E EI I5 5:E EE E* *EE EE+E EE+E EE EE* *E E E(E) E(

49、E) Ei EiI I8 8:E EE E* *EE EE+E EE+E EE EE* *E EI I6 6:E(E):E(E) EE+E EE+E EE EE* *E EI I9 9:E(E):E(E)E E+ +i i( ( (i iE E* *i iE E+ +E E* *i i( (* *) )+ +* *+ +CompilerPrinciples57v 从图中可以看到，在状态I1时，EE要求接受，而EE+E,EE*E要求移进，这种冲突可以使用SLR方法予以解决查看FOLLOW(E)。(= ?)(= ?)v 再看状态I7,EE+E要求规约，而EE+E, EE*E要求移进+或*，这个冲突

50、却不是SLR方法能够解决的。 ( ? ) 这种冲突只有借助于其他条件才能得到解决，也就是要使用算符优先级和结合规则的有关信息了。 下面来看个例子：CompilerPrinciples58 考虑输入串i+i*i，在处理了i+i之后，分析器进入状态I7,这时分析栈的内容为#0E1+4E7,剩余输入串为*i#。此时就产生了问题：到底是执行r1还是s5呢？ 假定*的优先级比+高，则就应该把*移进栈，也就是执行s5。拓广文法拓广文法G: G: (0)EE (0)EE (1)EE+E(1)EE+E(2)E(2)EE E* *E E(3)E(3)E(E)(E)(4)E(4)Ei ii+i*i# 同样对于i+

51、i+i，栈到达#0E1+4E7时，根据+左结合性质，应该先规约后进栈。把这些问题都解决了之后，我们就可以构造分析表了。CompilerPrinciples59文法文法GG对应的对应的LRLR分析表分析表CompilerPrinciples60 (6)LR分析中的出错处理分析中的出错处理 在LR分析过程中，出现下列情况：输入情况既不能移进栈顶，栈顶也不能规约，就意味着发现了语法错误，应该调用相应的出错处理子程序。 处理的方法分为两类：第一类多半使用插入、删除或修改的方法，试图消除错误；如果不可能采用这种方法，则采用第二类方法：检查到某一个不合适的短语，它不能与任一非终结符可能推导出的符号串相匹配

52、，则将其当作非法语句跳过。也就是说，分析器试图将错误局部化，以便能够继续分析工作。 CompilerPrinciples61短语级错误恢复：将语法错误局部化。v思想：LR分析器在访问Action表时，若遇到一个出错表项，就立即报告错误。它不会把出错点的符号进栈。因此，假定本该由某个A推导出的串含有语法错误，则发现错误时，该串的一部分已经进栈，剩余部分仍在输入串中。分析器试图从栈中退出一些符号，并跳过若干输入符号，然后恢复正常的分析过程。v恢复策略：从栈顶开始退栈，退出若干个状态和文法符号，直至找到某个状态s，有Gotos,A=s，把s进栈；然后丢弃若干个输入符号，直到找到A的一个合法后继符号a

53、为止，将其置为当前输入符号。v实现：检查LR分析表的每个出错项，并根据语言的使用情况确定最可能出现的错误，然后为该表项编写一个适当的错误恢复例程，来修复栈顶。 CompilerPrinciples62文法文法GG对应的对应的LRLR分析表（包含出错处理子程序）分析表（包含出错处理子程序）CompilerPrinciples63v上表中各个错误处理子程序的工作是：e1 将一个假想的i进栈，把3状态置为栈顶状态 错误信息：“缺少运算对象”e2 删除当前输入符号 ) 错误信息：“右括号不配对”e3 将一个假想的+进栈，把4状态置为栈顶状 态，错误信息：“缺少操作符”e4 把 ）进栈，把9状态置为栈顶

54、状态 错误信息：“缺少 ）”CompilerPrinciples64 (7)分析表的自动产生分析表的自动产生 这一节我们来介绍另一个编译程序编写系统YACCYet Another Compiler Compiler。它是美国Bell实验室的S.C.Johnson等人在1974年研制开发的。该系统可以根据用户提供的文法（可能二义的）和算符优先级、结合性等辅助信息，自动产生出LALR分析表。当然，若文法是LALR(1)的，就无需辅助信息，否则，辅助信息必不可少。 CompilerPrinciples65 终结符和产生式的优先级 YACC解决冲突的方法是给每个产生式和终结符都赋以一定的优先级。若A不

55、特别赋以优先级，则认为该产生式与出现在串的最右终结符优先级相同。显然在不涉及冲突时也就没必要管这些优先级了，一旦面临输入符号a时发生了“移进-规约”冲突，则必须比较a与A的优先级。 例：文法G: SiSeSiSa 显然，该文法类似于if-then-else结构，它的LR(0)项目集族如下图：CompilerPrinciples66v 在上图中可以清楚地看到，I4状态存在移进-规约冲突。按照通常的习惯，else应与最近的一个then相结合，因此当if C then S呈现于栈顶并面临else时，应该移进。于是我们就规定e的优先级高于i，则SiS的优先级就低于e，分析器在I4时就会执行移进，冲突也就