《编译原理第七章》由会员分享，可在线阅读，更多相关《编译原理第七章（50页珍藏版）》请在金锄头文库上搜索。
1、第8章 LR(k)分析方法,8.1 分析方法的逻辑结构及分析过程 8.2 LR(0)分析表的构造 8.3 SLR(1)分析表的构造 8.4 LR(1)分析表的构造 8.5 LALR(1)分析表的构造,LR(k)分析方法是指从左向右扫描和自底向上的语法分析。每次根据当前符号或最多向前看k个符号唯一地确定是归约还是继续读 。,一般来说，凡是上下文无关文法描述的程序设计语言都可以用LR方法进行有效的分析，而且还能在分析过程中及时准确地发现输入符号串的语法错误。,通常的程序设计语言一般均能由LR(1)文法产生,而且能由LR(k)产生的语言也可以由LR(1)文法来产生。因此，我们通常只考虑LR(0)和L
2、R(1)两种情况。,在本章中我们先后介绍LR(0), SLR(1), LR(1)和LALR(1)分析方法。,8.1 LR分析方法的逻辑结构及分析过程,LR方法也是通过求句柄逐步归约进行语法分析。,句柄在运算符优先数法中是通过运算符的优先关系而求得的；在LR方法中，则是通过求可归前缀而求得的。,1. 活前缀与可归前缀,活前缀与可归前缀,符号串的前缀是指符号串的任意首部，包括,空串。,若是含句柄的活前缀，并且每个句柄是的后缀或本身，则称是可归规范前缀或可归前缀(含有句柄的活前缀)。,活前缀不含句柄之右的任何符号。 是规范句型的左起部分，到当前句柄为止。如果在其右边加上终结符号串后就可以成为一个规范
3、句型。,S:=S S:=CbBA A:=Aab A:=ab B:=C B:=Db C:=a D:=a 对于句子ababab有规范推导，见下面的语法树：,S,S,例如，设有文法GS:,规范句型ababab的活前缀为a，可归前缀为此a，时句柄也是a；,规范句型Cbabab的活前缀为C、Cb、Cba， 可归前缀为Cba，此时句柄为a；,规范句型CbDbab的活前缀为CbD、CbDb,可归前缀为CbDb，此时句柄为Db；,规范句型CbBab活前缀为CbB、CbBa、CbBab，可归前缀为CbBab，此时的句柄为ab;,规范句型CbBA的活前缀为CbBA，可归前缀为CbBA，此时亦为CbBA;,规范句型
4、S的活前缀为S，可归前缀为S，此时句柄亦为S。,又例如，设有文法GA： A:=aBCb B:=BaC B:=b C:=c 对于句子abaccb。,可归前缀的求法：,设某文法有可归前缀 A ，AVn 若有规则 A:=u u V* 则u也是文法的可归前缀。,例如，设有文法GS:S:=aAc A:=Abb A:=b,文法的所有可归前缀构成的集合称为文法的可归前缀集,其可归前缀集可用自动机来表示，称之为可归前缀图。,从初始状态S0到任一状态形成的符号串构成了某规范句型的活前缀；,从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可归前缀。,2. LR分析方法的逻辑结构,LR分析方法的逻辑结构：
5、,设有输入串a1a2a3an，LR分析方法的逻辑结构图如下：,栈顶,分析栈中每项都包括状态栈Si和文法符号栈xi两部分。,LR分析器包括两个部分，一个总控程序和一张分析表。,不同文法的LR分析器的总控程序都是一样的，只是分析表不同，因此LR分析表是LR分析方法的核心。总控程序根据具体的分析表来决定起下一步的处理动作。,LR分析的基本原理：把每个句柄(某个产生式的右部)的识别过程划分为若干状态。每个状态下，从左向右地识别句柄中的一个符号，每,个状态识别句柄的一部分符号。,也就是，在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法符号及当前输入符号，按分析表完成相应的分析工作。,
6、由此可见，构造LR分析器的主要工作是构造分析表,LR分析表的组成：,LR分析表由分析动作(ACTION)表和状态转换(GOTO)表组成。,1). 分析动作表,在分析动作表中，其元素由action(si,aj)来表示。action(si,aj)表示当前分析栈的状态栈栈顶元素为si，文法符号栈栈顶元素为aj(当前输入符号)时，所执行的动作。,这个动作可分为四种: 移进(S)、归约(r)、接受(acc)和出错(error)。,2). 状态转换表,gotosi,xj指出栈顶状态为si，文法符号为aj时应转到的下一状态。,3. LR分析过程,LR分析步骤： 在讲述LR的分析步骤之前，我们假设分析,表已经
7、成功构造。,下面我们给出LR分析的具体步骤：,将初始状态S0和句子的左界符#分别进分析栈中的状态栈和符号栈；,根据栈顶状态和当前输入符号查动作表，然后分别做如下动作：,移进；当前输入符号进符号栈，根据状态转换表，得到的新的状态进状态栈。继续扫描，从而下一个符号变成当前输入符号。,归约；按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态栈顶n个元素同时相应退栈。归约后的文法符号进符号栈，,查状态转换表，得到的新状态进状态栈。,接受；分析成功，终止分析。,出错；报告出错信息。,重复第2步的工作，直到接受或出错。,LR分析流程图(P192图8-4)。,具体分析过程 下面我们以具体的例子来
8、说明LR方法的分析过程：,设有文法GL： 1) L:=E,L 2) L:=E 3) E:=a 4) E:=b,上述文法表述的是单个a和b及由逗号分隔的任意个a和b所组成的所有符号串的集合。,这里我们直接给出该文法的分析表(P192图8-3)。,ri表示按第i个产生式进行归约；,Si表示把当前输入符号移进符号栈，且第i个状态进状态栈；,i表示转第i个状态，即第i个状态进状态栈；,表中未填内容的空白则表示分析动作为出错。,下面我们以输入串 #a,b,a# 为例，具体讲述LR分析过程。,可见#a,b,a#符合所给的文法规则。,8.2 LR(0)分析表的构造,LR(0)分析是当k=0时的LR(k)分析
9、方法。在分析的每一步只要根据当前栈顶状态就能确定,完成何种分析动作。,基本概念：,项目：对于文法G，其产生式右部带有特殊符号“”，则称之为文法的一个LR(0)项目，简称项目。有时也称为配置式。,特殊符号也可以用“.”，并且要加在产生式右部的任何地方，表示一个位置。,项目集：若干个项目组成的集合称为项目集，又称为配置集合。,后继符号：项目中紧跟在特殊符号“”后面的符号称为该项目的后继符号。,后继符号表示下一时刻读到的符号。有如下两种情况：,后继符号为终结符号和非终结符号,例如，对应于产生式: E:=E+T,有四个项目：E:=E+T E:=E+T E:=E+T E:=E+T,这一类的后继符号为：
10、E:=E+T的后继符号为E,E:=E+T的后继符号为+ E:=E+T的后继符号为T,后继符号为空 规定：该项目的后继符号为带有“#”的相应产生式，用来表示下一时刻将按指定的产生式进行归约。,后继符号集 定义：项目集中诸项目的后继符号所组成的集合称为后继符号集。,状态内容 分成是基本(BASIC)部分和闭包(CLOSURE)部分。,设Si是Sk关于符号 X的后继状态，则求BASIC(Si)和CLOSURE(Si)的方法：,1).BASIC(Si)的计算： BASIC(Si)=A:=X| A:=XSk,2).CLOSURE(Si)的计算： .BASIC(Si)CLOSURE(Si)；,.若A:=Y
11、CLOSURE(Si), 且YVn则Y:=rCLOSURE(Si), r为符号串；,.重复直到CLOSURE(Si)不再增加为止。,例如，对于文法GS: S:=A A:=aAb A:=c 设其开始状态为S0，则求S0的状态内容。,项目类型 项目类型有三类归约项目、移进项目和待归项目。,归约项目： A:= 此时已把分析结束，已在栈顶,从而可按相应的产生式进行归约。,移进项目： A:=X ，XVt 此时把X移进文法符号栈。,待约项目： A:=X ，XVn 此时等待从余留的输入符号中进行归约而得到X。,项目集的相容性 满足以下条件的项目集称为相容的项目集：,无移进项目和归约项目并处；,无多个归约项目
12、并存。,例如，项目集： A:= , B:= A:= , B:= ,状态描述序列和状态转换图：,.在某一状态的项目集中，不同的项目，其后,状态描述序列,查看完毕,在状态描述序列中，必须遵守以下规则：,.不同状态的项目集中，有若干个与前面对应相同的项目，其后继状态与前面相同时，则后继状态相同。,例如，有文法GS： (1) S:=A (2) S:=B (3) A:=aAb (4) A:=c (5) B:=aBb (6) B:=d,我们先对文法进行拓展，增加一条规则: (0) S:=S (1) S:=A (2) S:=B (3) A:=aAb (4) A:=c (5) B:=aBb (6) B:=d,
13、继符号相同时，则后继状态相同；,状态转换图,由上面的状态描述序列可见，其项目集是相容的。,查看相容的定义,注意：对于一个文法G，若其状态描述序列中的状态项目集是相容的，则称G为LR(0)文法。,LR(0)分析表的构造：,首先，设有状态转换函数 GO(Si, X)=Sj 表示当前状态为Si，输入符号为X时的后继状态为Sj 。,LR(0)分析表的构造规则： 设有文法GS, 则LR(0)分析表的构造规则为：,对于A:=XSi , GO(Si, X)=Sj , 若XVt , 则置 actionSi, X=Sj 若XVn , 则置 gotoSi, X=j,对于A:=Si , 若A:=是文法的第j个产生式
14、，则对所有的 XVt ,均置 actionSi, X=rj,对于S:=Si , 则置 actionSi, #=acc,其它情况均置出错。,LR(0)分析表 设有文法GS, 则LR(0)分析表的构造规则为：,应用举例 用上述分析表对输入串 #aacbb# 进行分析，过程如书表8-6所示。,8.3 SLR(1)分析表的构造：,问题的提出： 只有当文法G的每一个状态项目集相容是才为LR(0)文法。,当文法的状态项目集不相容时, 就会出现不确定的动作，此时LR(0)分析方法就已经无法解决了。,SLR(1)方法是一种简单的LR(1)方法，它用从左到右向前看一个符号来解决冲突动作。,SLR(1)与LR(1)方法的区别：SLR(1)的向前看的符号是在出现冲突时才确定向前看的符号。,而LR(1)方法则是在一开始就确定向前看的符 号。,SLR(1)分析表的构造方法思想：,SLR(1)分析表的构造思想： 在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。,例如，对于状态Si，假设其项目集为 Si=B, A, C 其中是首符号为终结符的符号串。,
