《LR(k)分析方法-分析方法的逻辑结构及分析过程.ppt》由会员分享，可在线阅读，更多相关《LR(k)分析方法-分析方法的逻辑结构及分析过程.ppt（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)和LR(1)
2、两种情况。,在本章中我们先后介绍LR(0), SLR(1), LR(1)和LALR(1)分析方法。,8.1 LR分析方法的逻辑结构及分析过程,LR方法也是通过求句柄逐步归约进行语法分析。,句柄在运算符优先数法中是通过运算符的优先关系而求得的；在LR方法中，则是通过求可归前缀而求得的。,1. 活前缀与可归前缀,活前缀与可归前缀,符号串的前缀是指符号串的任意首部，包括,空串。,若是含句柄的活前缀，并且每个句柄是的后缀或本身，则称是可归规范前缀或可归前缀(含有句柄的活前缀)。,活前缀不含句柄之右的任何符号。 是规范句型的左起部分，到当前句柄为止。如果在其右边加上终结符号串后就可以成为一个规范句型。,
3、S:=SS:=CbBA A:=AabA:=abB:=CB:=DbC:=aD:=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;,规范句型S的活前缀为S，可归前
4、缀为S，此时句柄亦为S。,又例如，设有文法GA： A:=aBCb B:=BaC B:=b C:=c对于句子abaccb。,可归前缀的求法：,设某文法有可归前缀 A ，AVn若有规则 A:=u u V* 则u也是文法的可归前缀。,例如，设有文法GS:S:=aAcA:=AbbA:=b,文法的所有可归前缀构成的集合称为文法的可归前缀集,其可归前缀集可用自动机来表示，称之为可归前缀图。,从初始状态S0到任一状态形成的符号串构成了某规范句型的活前缀；,从初始状态S0到任一终止状态形成的符号串构成了某规范句型的可归前缀。,2. LR分析方法的逻辑结构,LR分析方法的逻辑结构：,设有输入串a1a2a3an，
5、LR分析方法的逻辑结构图如下：,栈顶,分析栈中每项都包括状态栈Si和文法符号栈xi两部分。,LR分析器包括两个部分，一个总控程序和一张分析表。,不同文法的LR分析器的总控程序都是一样的，只是分析表不同，因此LR分析表是LR分析方法的核心。总控程序根据具体的分析表来决定起下一步的处理动作。,LR分析的基本原理：把每个句柄(某个产生式的右部)的识别过程划分为若干状态。每个状态下，从左向右地识别句柄中的一个符号，每,个状态识别句柄的一部分符号。,也就是，在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法符号及当前输入符号，按分析表完成相应的分析工作。,由此可见，构造LR分析器的主要
6、工作是构造分析表,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的分析步骤之前，我们假设分析,表已经成功构造。,下面我们给出LR分
7、析的具体步骤：,将初始状态S0和句子的左界符#分别进分析栈中的状态栈和符号栈；,根据栈顶状态和当前输入符号查动作表，然后分别做如下动作：,移进；当前输入符号进符号栈，根据状态转换表，得到的新的状态进状态栈。继续扫描，从而下一个符号变成当前输入符号。,归约；按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态栈顶n个元素同时相应退栈。归约后的文法符号进符号栈，,查状态转换表，得到的新状态进状态栈。,接受；分析成功，终止分析。,出错；报告出错信息。,重复第2步的工作，直到接受或出错。,LR分析流程图(P192图8-4)。,具体分析过程下面我们以具体的例子来说明LR方法的分析过程：,设有文
8、法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,这一类的后继符号为： E:=E+T的后继符号为E,E:
10、=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:=YCLOSURE(Si), 且YVn
11、则Y:=rCLOSURE(Si), r为符号串；,.重复直到CLOSURE(Si)不再增加为止。,例如，对于文法GS: S:=A A:=aAb A:=c 设其开始状态为S0，则求S0的状态内容。,项目类型 项目类型有三类归约项目、移进项目和待归项目。,归约项目： A:= 此时已把分析结束，已在栈顶,从而可按相应的产生式进行归约。,移进项目： A:=X ，XVt 此时把X移进文法符号栈。,待约项目： A:=X ，XVn 此时等待从余留的输入符号中进行归约而得到X。,项目集的相容性 满足以下条件的项目集称为相容的项目集：,无移进项目和归约项目并处；,无多个归约项目并存。,例如，项目集： A:= ,
12、 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个产生式，则对所有的 XVt ,均置 ac
14、tionSi, 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)的向前看
15、的符号是在出现冲突时才确定向前看的符号。,而LR(1)方法则是在一开始就确定向前看的符号。,SLR(1)分析表的构造方法思想：,SLR(1)分析表的构造思想：在构造SLR(1)分析表时，根据不同的向前看符号，将Si中的各项目所对应的动作加以区分，从而即可使冲突动作得到解决。,例如，对于状态Si，假设其项目集为 Si=B, A, C其中是首符号为终结符的符号串。,对于归约项目：,A C 分别求其Follow(A)和Follow(C)。,对于移进项目： B 求其First()。,若集合Follow(A、Follow(C)、First()不相交，则对于任何a(aVt# )可按如下方法构造分析表就能解
16、决冲突：,对于BSi, aFirst(), 且GO(Si, a)=Sj 则置： actionSi, a=Sj,对于ASi, aFollow(A), 且A为文法的第j个产生式，则置： actionSi, a=rj,对于CSi, aFollow(C), 且C为文法的第k个产生式，则置： actionSi, a=rk,凡不能按上述方法填入的项均置出错。,SLR(1)分析表的构造规则： 设有文法GS, 则SLR(1)分析表的构造规则为：,对于AXSi , GO(Si, X)=Sj , 若XVt ,则置 actionSi, X=Sj 若XVn , 则置 gotoSi, X=j,对于归约项目ASi, 若A
17、为文法的第j个产生式则对于任何输入符号a, 若aFollow(A), 则置： actionSi, a=rj,对于SSi , 则置 actionSi, #=acc,其它情况均置出错。,对于给定的文法G，若按上述规则所构造的,分析表不含多重定义的元素,则称文法G为SLR(1)文法。,SLR(1)分析表：例如，文法GS为算术表达式的文法： (0) SE (1) EE+T (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,我们可以构造(见书P201图8-8)状态描述序列。其中，S2和S9两个项目集不相容。于是，,对于S2 有 S2 =ET, TT*F 下面求 Follow(
18、E)=#, +, )，于是Follow(E)与*不相交。,应用举例： 利用上述文法GS的SLR(1)分析表对输入串 #i+i*i# 进行分析。,8.4 LR(1)分析表的构造,问题的提出：,设有文法GS: (0) SS (1) SCbBA (2) AAab (3) Aab (4) BC (5) BDb (6) Ca (7) Da,由其状态描述序列(见图8-10)可得，项目集 : S10=SCbBA, AAab和项目集:,S9=Ca, Da 都是不相容的。,可用LR(1)方法来解决SLR(1)仍然出现的项目集的项目不相容且Follow和First相交的问题。,LR(1)分析表构造的思想：,只要输
19、入串的已扫描部分可保持可归约成一个活前缀，那就可判定所扫描的部分未出错。,LR(1)项目：,为解决SLR(1)方法无法解决的问题，我们在LR(0)项目中放置一个向前搜索的符号a，从而组成如下的形式： A, a, aFollow(A),我们把这样的项目称为LR(1)项目。,有效项目：,.若归约项目 A 对活前缀r=是有效的, 则说明应把符号串归约为A, 即把活前缀变为A。,1).SLR(0)有效项目：,.若移进项目 A 对活前缀r=是有效的, 则说明句柄尚未形成，下一步动作应该是移进。,说明：.当一个项目出现在几个不同的项目集中时,同一项目可能对好几个活前缀都是有效的。,.有可能存在这样的情形，
20、在一个项目集中，对同一个活前缀，存在若干项目对它都是有效的，而项目集却不相容。,2).LR(1)有效项目：,构造LR(1)分析表的思想：,对于上述例子的规范句型Cbabab, 根据定义，LR(1)项目Da, b对活前缀r=Cba有效。因此，应将栈顶文法符号a归约成D，而不应归约成C。,由此可见，在LR(1)分析表的构造过程中，要根据Si的项目集中的各个项目, 对活前缀有效情况，来确定相应的动作。,状态描述序列:,每一个状态也是由一个LR(1)项目集来表示的， 每一个项目集都是由若干个对相应的活前缀有效的LR(1)项目组成。,.Si中的任何LR(1)项目都属于CLOSURE(Si);,.设有项目
21、 AX, aCLOSURE(Si), XVn 则 X, bCLOSURE(Si), V*,其中，a为已知，b=First()。,.重复直到CLOSURE(Si)不再增加。,注意：每一个LR(1)项目与其后继项目有相同的向前的搜索符号。,注意：每一个LR(1)项目与其后继项目有相同的向前的搜索符号。,如：LR(1)项目 AX, a其后继项目 AX, a 具有相同的向前搜索符号a。,构造LR(1)项目的状态描述序列：,设有文法GS: (0) SS (1) SCbBA (2) AAab (3) Aab (4) BC (5) BDb (6) Ca (7) Da,Follow(S)=#Follow(S)
22、=Follow(S)=#Follow(A)=Follow(S)+First(ab)=#, aFollow(B)=First(A)=aFollow(C)=First(bBA)+Follow(B)=b, aFollow(D)=b,LR(1)分析表的构造规则: 对于文法GS，其LR(1)分析表的构造规则为：,.对于 AX, aSi , GO(Si, X)=Sj , 若XVt ,则置,actionSi, X=Sj 若XVn , 则置 gotoSi, X=j,.对于归约项目A, aSi, 若A为文法的第j个产生式，则对于任何输入符号a ,若aFollow(A), 则置： actionSi, a=rj,对于S, #Si , 则置 actionSi, #=acc,其它情况均置出错。,对于给定的文法G，若按上述规则所构造的分析表不含多重定义的元素，则称文法G为LR(1)文法。,LR(1)分析表的构造: 对于文法GS，其LR(1)分析表的构造为：,8.5 LALR(1)分析表的构造： LALR(1)分析表的构造与LR(1)分析表的构造相似，不同之处在于LALR(1)的状态部分把若干非等价状态进行合并而已。,