资源目录
压缩包内文档预览：(预览前20页/共118页)
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第6章 LR分析技术,本章学习目标,LR(k)分析器是这样一种分析程序：它总是按从左到右的方式扫描输入串，并按照自底向上的方式进行归约。在这种分析过程中，它至多向前查看k个输入符号就能确定当前的动作是移进还是归约。本章要点： LR分析的基本原理 LR（0）分析表的构造 SLR（1）分析表的构造 LR（1）分析表的构造 LALR（1）分析表的构造,6.1 LR分析器的工作原理,自底向上分析方法是一种移进归约过程，当分析栈的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析方法的关键问题是在分析过程中如何确定句柄。LR分析方法根据当前分析栈中的符号串（通常用状态来表示）和向右顺序查看输入串的k（k0）个符号就能惟一确定句柄。LR分析方法的归约过程正是规范推导的逆过程，所以LR分析过程是一种规范归约。 LR(k)分析方法是1965 年Knuth提出的。括号中的 k表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（k）分析方法和自底向上的优先分析对文法的限制要少得多。也就是说对于大多数无二义性上下文无关文法描述的语言都可以用相应的LR分析器识别。而且这种方法还具有分析速度快，能准确、及时地指出出错位置等优点。它的主要缺点是对于一个实用语言文法分析器的构造工作量相当大，实现比较困难。,1LR分析的概述,一个LR分析器由三部分组成： （1）总控程序，也称为驱动程序。对所有的LR分析器总控程序是相同的。 （2）分析表或分析函数。不同的文法其分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两部分,，们都用二维数组表示。 （3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定。,其中SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态栈的内容按关系GOTOSi，X= Sj。其中X为终结符或非终结符。,图6-1 LR分析器的工作过程,ACTIONSi,a规定了栈顶状态为Si时遇到输入符号a应该执行的动作。动作有4种可能： （1）移进：当Sj=GOTOSi,a成立，则把Sj移入到状态栈，把a移到文法符号栈，其中i和j表示状态。 （2）归约：当在栈顶形成句柄为时，则用归约为相应的非终结符A，即当文法中有A的产生式，当的长度为（即|=）时，则从状态栈和文法符号栈中自栈顶向下去掉个符号，即栈指针SP减去；并把A移入文法符号栈，再把满足Sj=GOTOSi,A的状态移进状态栈，其中Si为修改后指针的栈顶状态。 （3）接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则分析成功。 （4）报错：当遇到状态为某一个状态下出现不该遇到的文法符号栈时，则报错。说明输入串不是该文法能接受的句子。,2LR分析举例,表达式文法GE如下所示，它对应的LR分析表如表6-1所示。 （1）EE+T （2）ET （3）TT*F （4）TF （5）F（E） （6）Fi,我们主要是关心的问题是如何由文法构造LR分析表。对于一个文法，如果能构造一张分析表，使得它的每一个入口均是惟一确定的，则称这个文法是LR 文法。对于一个LR文法，当分析器对输入串进行自左向右扫描时，一旦句柄呈现在栈顶，就能及时的对它实行归约。 在有些情况下，LR分析器需要“展望”和实际检查未来的k个输入符号才能决定对应采取什么样的“移进归约”决策。一般而言，一个文法如果能用一个每步最多向前检查k 个输入符号的LR分析器进行分析，则这个文法称为LR(k)文法。,6.2 LR(0)分析表的构造,LR(0)语法分析方法是其他构造LR分析的基础。进行LR分析主要完成的任务是设计出LR分析表。LR分析表的设计方法过程是：首先给出文法，根据文法构造出NFA和DFA。根据文法的DFA设计出LR分析表，根据分析表写出LR分析器的总控程序。设计LR分析表的方法有两种，第一种是采用活前缀的方法构造有限自动机，第二种是采用项目集规范族的方法构造有限自动机。,给出文法： （1）SaAcBe （2）Ab （3）AAb （4）Bd 采用LR(0)分析判断输入串abbcde#是否合法。,6.2.1 采用活前缀的方法构造有限自动机,用分析表的方法进行归约： （1）SaAcBe1 （2）Ab2 （3）AAb3 （4）Bd4 根据这个文法对输入串abbcde 进行判断，形成如下的推导过程。 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 判断出该输入串是该文法的句子。 它的逆过程最左归约（规范归约）则为： 当输入串为abbcde时，根据它的推导过程可以写为： ab2b3cd4e1 用产生式（2）归约 aAb3cd4e1 用产生式（3）归约 aAbcd4e1 用产生式（4）归约 aAbcde1 用产生式（1）归约 S,其中“”表示归约。从这里可以看出对于一个合法的句子而言，每次归约后得到的都是已归约部分和输入剩余部分合起来构成文法的规范句型。而用哪个产生式继续归约仅取决于当前句型的首部，例中每次归约前的句型的首部依次为： ab2 aAb3 aAbcd4 aAcBe1,这些符号正是在归约之前栈中的符号。当栈顶出现上述的符号串时，就采用相应的产生式进行归约，把句型的首部称为可归前缀。 我们再分析每个前部的前缀： ab2的前缀有,a,ab aAb3的前缀为,a,aA,aAb aAbcd4的前缀为,a,aA,aAb,aAbc,aAbcd aAcBe1的前缀为,a,aA,aAc, aAcB,aAcBe 我们把在规范句型中形成可归前缀之前包括可归前缀在内的所有的前缀称为活前缀。在规范归约的任何时刻，只要已分析过的部分即在符号栈内的符号串均为规范句型的活前缀，则表明输入串的已分析过的部分是该文法某规范句型的正确部分。,3识别活前缀的有限自动机,定义6.1 若S A是文法G的拓广文法G中的一个规范推导。符号串是的前缀，则称是G的一个活前缀。也就是说是规范句型的前缀，但是它的右端不超过该句型句柄的末端。 根据定义，一旦出现在符号栈的栈顶，则形成句柄，就用产生式A进行归约。 在LR分析过程中，并不是直接分析文法符号栈中的符号是否形成句柄。我们把终结符和非终结符都看成一个有限自动机的输入符号，每有一个符号进栈，就认为自动机识别一个符号，而状态进行了转换。当识别到了可归约前缀时，相当在栈顶形成了句柄，则认为到达识别句柄的终态。,我们将上面的文法进行拓广，文法表示成： （0）SS0 （1）SaAcBe1 （2）Ab2 （3）AAb3 （4）Bd4 现对句子abbcde的可归约前缀列出： S0 ab2 aAb3 aAbcd4 aAcBe1 构造出识别其活前缀的自动机如图6-2所示。,将该不确定的自动机确定化如图6-3。将该确定的有穷自动机的状态作为LR(0)分析表的状态，就可以画出LR(0)分析表。,6.2.2 采用项目的方法构造有限自动机 下面我们介绍几个项目集的概念。 1LR(0)项目的定义 文法G的每个产生式的右部的某个位置添加一个“”。例如，产生式Axyz包含4个项目： Axyz Axyz Axyz Axyz 而空产生式A，只有一个项目A。 直观地说，一个项目指明了在分析过程的某一个时刻一个产生式的状态，例如，上面的第一个项目指明，希望看到可从xyz推出的符号串；第二个项目则指明，已经看到了能从x推出的符号串，但希望进一步看到可以从yz推出的符号串。,已知文法 SE EaA|bB AcA|d BcB|d 该文法的项目有：,该文法的项目有： 1SE 10Ad 2SE 11EbB 3EaA 12EbB 4EaA 13EbB 5EaA 14BcB 6AcA 15BcB 7AcA 16BcB 8AcA 17Bd 9Ad 18 Bd,2LR项目的分类,我们可以根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种。 移进项目，形如Aa，其中和V*，aVT，即圆点后面为终结符的项目为移进项目，对应的状态为移进状态，分析时把a移进符号栈。 待约项目，形如AB，其中和V* ，BVN，即圆点后面为非终结符的项目为待约项目。它表明所对应的状态等待着分析完非终结符B所能推出的串归约成B，才能继续分析A的右部。 归约项目，形如A，其中V*，即圆点在最右端的项目称为归约项目。它表明一个产生式的右部已分析完成，句柄已形成，可以归约。 接受项目，形如S，其中V+，S为拓广文法，S为左部的产生式只有一个，因而它是归约项目的特殊情况，对应的状态为接受状态。我们规定S为初态。实际上接受项目中的为文法的开始符号。,3根据项目构造识别活前缀的NFA和DFA 将项目的编号作为自动机的状态，在构造识别活前缀的NFA时，遵循如下的原则，即假设有一个项目i为：XX1X2Xi-1 XiXn 而项目j为：XX1X2Xi-1 Xi Xi+1Xn,i,将上面文法的项目按上述的原则画出图6-6所示的NFA。将该NFA确定化变为DFA，见图6-7。将DFA的状态作为LR分析表的状态，构造出分析表。,6.2.3 采用文法的项目集规范族构造有限自动机,对于构造识别一个文法活前缀的DFA项目集的全体称为这个文法的LR(0)项目集规范族。在图6-7的方框内中项目就构成了项目集规范族。我们可以用一种简单直观的方式构造项目集规范族。 1LR（0）项目集规范族的构造 （1）CLOSURE（I）函数 如果I 是文法G的任一个项目集，那么定义和构造I的闭包CLOSURE（I）规则如下： 1)属于I的任何项目也属于CLOSURE（I ）。 2)若AB是指：在分析过程的某一个时刻，希望看到可从B推出的符号串；若有B，则将B加到CLOSURE(I)中，此时，称AB为该闭包的核。 3)重复上述步骤，直到CLOSURE(I)不在增大为止。,例如6.2 给出拓广文法： EE EE+T|T TT*F|F F(E)|id 假定I0= EE，那么CLOSURE(I)包含的项目如下： EE EE+T ET TT*F TF F(E) Fid,计算CLOSURE的过程为： procedure CLOSURE(I) begin repeat for I 中的每个形如AB的项目及G中的每个形如B的产生式 do if B不属于I then 将B加到I； until I不再增大为止； return I; end; （2）GOTO(I,X)函数。在构造分析表的时候常用到的第二个函数是GOTO函数。GOTO函数实质上是一个状态转换函数。GOTO(I,X)中的第一个I是一个项目集，第二个参数X是任一个文法的符号，GOTO（I，X）的函数的定义为： GOTO（I，X）=CLOSURE(所有形如AX的项目| AXI),例如6.3 给出拓广文法： EE EE+T|T TT*F|F F（E）|id 设I= EE，EE+T 那么GOTO(I，+)则由下面的项目组成项目集规范族。 EE+T TT*F TF F(E) Fid,LR(0)项目集规范族,利用CLOSURE和GOTO 函数就能构造出一个拓广文法的LR(0)项目集C。 构造的方法是： CLOSURE(J)=GO(I,X) 其中，I是一个项目集，X是一个文法符号。 项目集规范族的构造步骤如下： 置项目SS为初态集的核，然后对核求闭包，CLOSURE(SS)得到初态的项目集。 对初态集或其他所构造的项目集应用转换函数GOTO(I，X)=CLOSURE(J)，求出新状态J的项目集。 重复（2）直到不再出现新的项目集为止。,procedure items(G); begin C:=CLOSURE(SS) repeat for C中的 每个项目I和I中的每个紧邻接的“”后的不同的文法符号X do If GOTO(I,X)非空且不属于C then 将GOTO(I,X)加到C until C 不再增大为止。 end. 最终得到的C就是拓广文法的项目集规范族。,例如6.4给出拓广文法： SA|B AaAb|c B aBb|d 将该文法拓广为： （0）SS （1）SA （2）SB （3） AaAb （4）Ac （5）B aBb （6）B d 根据CLOSURE(I)函数设计出项目集规范族。,令I0=CLOSURE( SS)得到项目集规范族为: I0: SS SA AaAb Ac SB B aBb B d 考察I0的每一个项目中“”后面就是一个要识别的符号，则令X=S，A，B，a,c,d 利用GOTO（I0,X）,可以得到I0的后继项目集为：,I1=GOTO(I0,S)=CLOSURE( SS) I2=GOTO(I0,A)=CLOSURE( SA) I3=GOTO(I0,B)=CLOSURE( SB) I4=GOTO(I0,a)=CLOSURE( AaAb ,B aBb) = AaAb AaAb Ac B aBb B aBb B d I5: Ac I6: Bd I7=GOTO(I4,A)=CLOSURE( AaAb )= AaAb I9=GOTO(I4,B)=CLOSURE( B aBb )= B aBb I8=GOTO(I7,b)=CLOSURE( AaAb )= AaAb I10=GOTO(I9,b)=CLOSURE( B aBb )= B aBb,根据DFA构造文法的LR(0)分析表 LR(0)分析表是LR(0)分析器的重要组成部分。它是总控 程序分析动作的依据。对于不同的文法，LR(0)分析表不同，它是一个二维数组，行号表示状态号，列号为文法符号和“#”号，分析表的内容为两部分，一部分为ACTION表，它表示当前状态下所面临的输入符应做的动作是移进、归约、接受还是出错。动作表的行标号只包含终结符和“#”。另一部分为转换表，它表示在当前状态下面临文法符号时应转向的下一个状态。 假设已经构造出了识别活前缀的DFA，根据DFA构造文法的LR(0)分析表，构造步骤如下： C=I0,I1,I2,In 其中Ik为项目集的名字，令包含SS项目的集合Ik的下标为分析标的初始状态。那么分析表的,ACTION和GOTO表的构造步骤为： 若项目为Aa属于Ik，且转换函数GO(Ik，a)= Ij，当a为终结符时置ACTIONk,a为Sj，其动作的含义为终结符a移进符号栈，状态j进入状态栈，相当于状态k时遇到a转向状态j。 若项目A属于Ik，则对于任何终结符和“#”置ACTIONk,a和ACTIONk,#为“rj”，j为在文法G中某产生式A的序号。rj动作的含义是把当前文法符号栈顶的符号串归约为A，并将栈顶向下移动|a|的长度，符号栈中弹出|a|个符号，非终结符A变为当前面临的符号。 若GOTO(Ik，a)=Ij， 则置GOTO（k，A）为“j”，其中A为非终结符，表示当前状态为k，遇到文法符号A时，状态应转向j，因此A移入文法符号栈，j进入到状态栈。 若项目SS属于Ik，则置ACTIONk,#为“acc”，表示接受。 凡不能用上述方法添入的分析表的元素，均应该添上“报错标志”，在表中用空白来表示。 这样构造出的LR(0)分析表为LR(0)分析表。,构造LR（0）分析表的步骤小结 (1)写出给定文法G的拓广文法G。 (2)写出文法G的基本LR（0）项目G的LR（0）项目集。 (3)利用CLOSURE和GOTO函数，求出相应的项目集规范族。 (4)构造识别该文法的全部活前缀的DFA。 (5)根据算法构造LR（0）分析表。,例如6.6已知文法，试构造该文法的LR(0)分析表. SBB BaB|b 【解】将该文法拓广为文法： (0)SS (1) SBB (2) BaB (3) B b 写出该文法的所有的项目集，构造出DFA,例如6.7 8086/8088汇编语言对操作数域的检查可用LR分析表的实现。设m代表存储器，r代表寄存器，i代表立即数；并且为了简单起间，省去了关于m、r 和i的产生式。设m、r 和i为终结符，则操作数域P的文法为： Pm,r|m,i|r,r|r,i|r,m 试构造能够正确识别操作数域的LR分析表。,【解】 （1）将文法拓广为： 0）SP 1）Pm,r 2）P m,i 3） Pr,r 4） Pr,i 5）.Pr,m (2)根据文法求得其项目集规范族和GOTO函数， DFA如图6-10所示。,LR(0)文法项目集规范族的冲突 前面我们介绍了LR(0)分析表的构造。项目集规范族中项目的类型，不外乎以下几种：移进项目、归约项目、待约项目和接受项目。一个项目集规范族可能包含以上4种不同的项目，但是一个项目集中不能有下列情况存在： （1）移进和归约同时存在。 形如： Aa, B 这时由于面临输入符号为a时不能确定是移进a 还是把归约为B,因为LR(0)分析是不向前看符号，所以对于归约的项目不管当前符号是什么都应该归约。对于同时存在移进和归约项目的称为移进归约冲突。 （,2）归约和归约项目同时存在。 设在文法的项目集规范族中含有以下形式的项目。 A , B 不管面临的是什么输入符号都不能确定归约为A，还是归约为B 。对于同时存在两个以上项目的状态称为归约归约冲突。 当一个文法的LR(0)项目集规范族不存在移进归约和归约归约冲突时，称这个文法为LR(0)文法。,6.3 SLR(1)分析表的构造,6.3.1问题的提出 给出文法： real real，i i 将该文法缩写并拓广如下： （0）SS （1）SrD （2）DD，i （3）Di 构造该文法的LR(0)项目集规范族如表6-9： 表6-9 LR(0)分析表族,在该文法中就会发现在状态I3中含有冲突的项目： SrD DD，i 设计出该文法的LR(0)分析表如表6-10所示：,6.3.2解决LR(0)分析方法中冲突问题的方法,1解决冲突的方法 假设在LR(0)的项目集规范族中有如下的项目集状态I ： I=Xb, A, B 也就是说在项目集中含有移进归约和归约归约冲突。其中，为文法的符号串，b为终结符。则要求满足如下的条件才能用SLR(1)分析方法进行分析。 FOLLOW（A）FOLLOW（B）= FOLLOW（A）b= FOLLOW（B）b=,那么当在状态I面临输入符号为a时，填写在分析表中的动有以下的规定决策。 1)面临输入符号为a=b时，则移进。 2)若aFOLLOW（A），则用产生式A进行归约。 3)若aFOLLOW（B），则用产生式B进行归约 如果是其它种情况就报错。 将上述的项目集规范族的情况广而推之，则假设某个文法的项目集中有如下的状态： I=A11b11, A22b22 ， Ammb m m， B11，B22 ，Bnn 要求满足的条件为：只要集合 b1，b2，b m和FOLLOW（B1），FOLLOW（B2），FOLLOW（Bn）两两不相交,解决的方法是： 1)面临输入符号为a b1，b2，b m时，则移进。 2)若aFOLLOW（Bi），则用产生式Bi 进行归约。 3)此外，报错。 2构造SLR（1）分析表的步骤 假设已构造出文法的LR（0）项目集和计算出所有的非终结符的FOLLOW集合。,设项目集规范族为： C=I0, I1, In，其中Ik为项目集的名字，k为状态号，SS所在的项目集的状态为初始状态。求出所有的非终结符的FOLLOW集合。则ACTION和GOTO表的构造步骤为： ）若项目Aa属于Ik，且转换函数GO(Ik，a)=Ij，当a为终结符时，则置ACTIONk,a为Sj。 2)若项目A属于Ik，则对a为任何终结符或“#”，且满足aFOLLOW(A)时，置ACTIONk,a= rj,j为产生式A在文法中的编号。 3)若GO(Ik，A)= Ij，则置GOTOk,A=j，其中A为非终结符，j为某一个状态号。 4）若项目SS属于Ik，则置ACTIONk,#= acc，表示接受。 5)凡不能用上述方法填入的分析表的的元素，均应添上“报错标志”，在表中用空白来表示。,例如6.8给出文法 EE EE+T|T TT*F|F F（E）|id 采用SLR(1)的分析方法，给出符号串i+i*i#进行分析时栈的变化过程。 （1）写出该文法的项目集规范族。,（2）找出该项目集规范族中的冲突,。 【解】不难看出，存在三个项目集规范族的冲突。 在 I1中有：EE，EE+T，两个项目就是一个移进归约的冲突，该表达式的文法不是LR(0)文法，因此不能构造LR(0)分析表。考察该冲突是否可以用SLR(1)来进行分析。 FOLLOW(S)=#+=，因此I1中的冲突可以解决。 在I2中的冲突为：E T和TT*F，该项目集有移进归约冲突。 FOLLOW(E)=+，），# +，），#*= 所以该文法能够解决冲突。 在I9中的冲突为：EE+T和TT*F，该冲突为移进归约冲突 FOLLOW(E)=+，），# +，），#*= 所以该文法能够解决冲突。 （3）画出识别活前缀的DFA。识别活前缀的DFA如图6-12所示,4）写出SLR(1)分析表 根据文法的DFA 写出该文法的分析表如表6-13所示,7.4LR（1）分析,一、LR（1）分析的提出 SLR（1）分析中，解决移进和归约冲突的条件是：假设在LR(0)的项目集规范族中有如下的项目集状态I如下: I=Xb, A, B 也就是说在项目集中含有移进-归约和归约 归约冲突。其中，为文法的符号串，b为终结符。则要求满足如下的条件才能用SLR（1）分析方法进行分析。 FOLLOW（A）FOLLOW（B）= FOLLOW（A）b= FOLLOW（B）b= 那么当在状态I时面临输入符号为a时，填写在分析表中的动有以下的规定决策。 面临输入符号为a=b时，则移进。 若aFOLLOW（A），则用产生式A进行归约。 若aFOLLOW（B），则用产生式B进行归约 如果是其它种情况就报错 ，也就是说当交集不为空时，无法解决,例：给定文法，构造识别活前缀的DFA,文法： （0）SS （1）SaAd （2）SbAc （3）Saec （4）Sbed （5）Ae 用SS作为初态集的项目，然后用闭包和转换函数构造文法的DFA,在项目集中就有两个冲突： I5：Saec Ae 该项目集很显然是移进和归约冲突。则FOLLOW（A）=c,d 在I5中，FOLLOW（A）c=c,dc 在I7中，FOLLOW（A）d=c,dc 因此根本不能用SLR（1）进行分析。所以采用新的分析方法即LR（1）的方法。,二、LR（1）分析的基本思想,LR(1)分析方法就是在SLR(1)分析方法的基础上进行改进。 其项目集规范族的构造原则有： 若AB项目集时，则B也属于I（B为一产生式）。由此不防考虑把FIRST（）作为产生式B归约的搜索符，称为向前搜索符，作为归约时查看的符号集合用以代替SLR（1）分析中的FOLLOW集。把此搜索符号的集合也放在相应项目的后面，这种处理方法即LR（1）方法。,1、LR（1）项目集规范族的构造,以SS，#属于初始项目集中，把“#”号作为向前搜索符，表示活前缀为（设是有关S产生式的某一部分）要归约成S时，必须面临输入符为“#”才行。 我们对初始项目SS，#求闭包后再用转换函数逐步求出整个文法的LR（1）项目集规范族。,构造LR（1）项目集的闭包函数,假定I是一个项目集，I的任何项目都属于CLOSURE（I）。 若有项目AB，a属于CLOSURE（I），B是文法的产生式。V*，b属于FIRST(a),则B，b也属于CLOSURE（I）中。 重复直到CLOSURE（I）不再增大为止。,（2）构造转换函数,LR（1）转换函数的构造与LR（0）的相似，GO（I，X）=CLOSURE（J），其中I是LR（1）的项目集，X是文法符号： J=任何形如AX， a的项目| AX， aI 对任何G 的LR（1）项目集族的构造仍以SS，#为初态集的初始项目，然后对其求出闭包和转换函数，直到项目集不再增大为止。 根据上述的步骤解决前面例中SLR（1）解决不了的问题。,（3）前例中的项目集规范族为：,I0： SS，# I4: SaAd,# SaAd,# I5: Saec,# SbAc,# Ae,d Saec,# I6: SbAc,# Sbed，# I7: Sbed，# I1： SS，# Ae，c I2： SaAd,# I8: SaAd , # Saec,# I9: Saec,# Ae，d I10: SbAc,# I3： SbAc,# I11: Sbed，# Sbed，# Ae，c,这样LR（1）方法构造的项目集规范族在项目集I5和I7中的移进归约冲突便可以解决。由于归约项目的搜索符集合和移进项目的待移进符号不相交，所以在I5中，当面临输入符号为d时归约，为c时移进，而在I7中则当面临输入符为c时归约，为d时移进，冲突就可以解决，该文法就是一个LR（1）文法。,2.LR(1)分析表的构造,由于一个LR（1）项目可以看成两个部分组成，一部分和LR（0）项目相同，这一部分称为心，另一部分为向前搜索符集合。因此LR（1）分析表的构造和LR（0）分析表的构造形式上相同，只是归约项目的归约动作取决于该归约项目的向前搜索符号。只有当面临的输入符号属于向前搜索符号的集合时，才做归约动作，其它的情况均出错,(1)构造的基本的过程如下：,设项目集规范族为： C=I0, I1, In，其中Ik为项目集的名字，k为状态号，SS所在的项目集的状态为初始状态。则ACTION和GOTO表的构造步骤为： 若项目Aa属于Ik，且转换函数GO（Ik，a）=Ij，当a为终结符时，则置ACTIONk,a为Sj。 若项目A，a属于Ik，置ACTIONk,a= rj,j为产生式A在文法中的编号。 若项目SS，#属于Ik，则置ACTIONk,#= acc，表示“接受”。 若GO（Ik，A）= Ij，则置GOTOk,A=j,其中A为非终结符，j为某一个状态号。 凡不能用上述方法添入的分析表的的元素，均应添上“报错标志”，在表中用空白来表示。,如果一个文法的LR（1）分析表不含多重入口，即任何一个LR（1）项目集中即无移进归约冲突或者归约归约冲突，则称该文法为LR（1）文法，所构造的相应的分析表为LR（1）分析表，使用LR（1）分析表的分析器称为LR（1）分析器或者LR（1）分析器。 一个文法是LR（0）文法一定也是SLR（1）文法，也是LR（1）文法，但是，反过来就不一定成立。 LR(1)项目集规范族使某些同心集进行了分裂,项目集的个数增加了.,3LR（1）文法的应用示例,给出文法:若文法为 （0）SS （1）SBB （2）BaB （3）Bb 写出它的LR（1）项目集规范族和LR（1）分析表 ,并根据LR(1)分析表判断字符串：aabb是否为文法合法的句子.,6.5 LALR分析方法,LR(1)分析表的构造对搜索符的计算方法比较确切，对文法放松了要求，但是它的状态的数目比SLR(1)的状态的数目增加了很多，主要是因为LR(1)项目集规范族中出现了许多同心的集合，这些状态占据了内存的空间。 为了克服LR(1)算法的缺点，就对LR(1)中的项目集规范族进行合并，若合并后的同心集族不产生新的冲突，则为LALR(1)项目集。合并了同心集后的项目集的数目和该文法的LR(0)、SLR(1)的相同。,6.5.1同心集的合并,在前面已经讲过，由于一个LR(1)项目可以看成由两个部分组成，一部分和LR(0)项目相同，这一部分称为心，另一部分为向前搜索符集合。对于LR(1)项目集规范族来讲，心相同的集合称为同心集。 在例题6-10的项目集可以发现同心集如下： I3：BaB，a/b I6: BaB，# BaB，a/b BaB，# Bb，a/b Bb，# I4：B b，a/b I7: B b,# I8：BaB，a/b I9: B aB,#,将同心集I3和I6，I4和I7，I8和I9合并后得到新的集合： I3，6： BaB，a/b /# BaB，a/b/# Bb，a/b/# I4，7： Bb，a/b/# I8，9 ： BaB，a/b/#,同心集合并后的状态集并不包含冲突，说明该文法是LALR(1)文法，如果有项目的冲突，就不是LALR(1)分析方法。 关于同心集的合并有如下几个问题需要说明： （1）同心集合并是心相同的项目集合并在一起，因此同心集合并后心不变，向前搜索符的集合发生变化。 （2）对于合并同心集后的项目集经转换函数后所达到的仍为同心集。 （3）若文法是LR(1)文法，合并同心集后若有冲突也只能是归约归约冲突，而不可能是移进和归约冲突。因为在合并前就不存在移进归约冲突，移进后更不可能出现移进和归约冲突。 （4）合并同心集后对语法错误的检查可能会出现推迟现象，但是错误的分析还是正确的。,6.5.2 LALR分析表的构造，LALR分析表的构造步骤如下,（1）构造文法的LR(1)项目集规范族，C=I0, I1, In。 （2）合并所有的同心集，使C变为C，C= J0, J1, Jn。 （3）构造文法的LALR(1)分析表. 1）若项目Aa属于Ik，且转换函数GO（Ik，a）=Ij，当a为终结符时，则置ACTIONk,a为Sj。 2）若项目A，a属于Ik，置ACTIONk,a= rj，j为产生式A在文法中的编号。 3）若项目SS，#属于Ik，则置ACTIONk,#= acc，表示“接受”。 4）若GO(Ik，A)= Ij，则置GOTOk,A=j，其中A为非终结符，j为某一个状态号。 5）凡不能用上述方法添入的分析表的的元素，均应添上“报错标志”，在表中用空白来表示。,例如6.12给定文法 （1）SBB （2）BaB （3）Bb 写出该文法的LR(1)项目集规范族，构造出该文法的LALR分析表，输入串 “aa#”，用LR(1)分析表和LALR(1)分析表来判断该输入串是否合法。 【解】将前面的LR（1）的项目集规范族合并之后，得到合并后的状态为： I3，6： BaB，a/b /# BaB，a/b/# Bb，a/b/# I4，7： Bb，a/b/# I8，9 ： BaB，a/b/# 由合并后的集合按照LALR(1)分析表的构造算法得到LALR分析表得到如下的表格为,例如6.13 给出文法，判断该文法是否是LR(1)文法，是否是LALR(1)文法。 文法的产生式为： （0）SS （1）SaAd （2）SbBd （3）S aBe （4）S bAe （5）A c （6）B c 【解】根据文法构造出该文法的项目集规范族。,检查每个项目集规范族，在任何项目集规范族中都不含移进归约或归约归约冲突。因此，该文法是LR(1)文法。进一步查看项目集规范族可以发现，I6和I9是同心集。 I6: A c，d B c，e I9: A c，e B c，d 若合并后变为： I6: A c,d/e B c,e/d 这样就出现了新的归约归约冲突，因为不管当前符号是d或e即可以用产生式A c归约也可以用产生式B c归约，因而可以判定该文法不是LALR(1)文法，当然也不是SLR(1)文法和LR(0)文法。,6.6 二义性文法的应用,例如6.14一程序语句的文法为： （1）Sif S else S （2）Sif S （3）SS；S （4）Sa 该二义文法终结符else 与最近的if 结合，试用LR分析器的基本思想为文法构造LR分析表。 【解】将文法拓广为： （0）SS （1）Si S e S （2）Si S （3）SS；S （4）Sa 由项目集规范族和转换函数构造出DFA 如图6-15所示。,分析上面的项目集规范族，我们可以看出，在项目I5中，有移进和归约的冲突。 Si S e S， SS；S两个项目需要移进，而Si S，项目需要归约。 FOLLOW(S)=#,e,; FOLLOW(S)e FOLLOW(S) ;,对于I5中，由于活前缀“iS”达到I5，遇到“e”，则和前面的活前缀“iS”结合形成iSeS句型，所以应该移进e；当遇到“；”时，则活前缀形成的“iS”为一个语句，所以应该归约。 对于I6和I8引起冲突的是“；”。 对于I6，当遇到后面的是“；”时，则应该将活前缀“S；S”归约为S。 对于I8，由于是由活前缀“iSeS”到达I8，因此遇到后面的“；”时，则应将活前缀“i S e S”归约。,例如6.15已知算术表达式文法，试构造该文法的LR分析表；并用来分析输入串i+i*i#的分析过程。 （1）EE+E （2）EE*E （3） E(E)|i 该文法是一个二义性文法，设计出该文法的LR分析表，输入i+i*i#判断该输入串是否合法。 【解】将文法拓广为： （0）EE （1）EE+E （2）EE*E （3） E(E)|i,在I1中，归约项目EE实际上为接受项目。由于FOLLOW（E）=#也就是只有遇到句子的结束标志“#”才能接受；因而与移进项目的移进符号“+
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号