《编译原理实用教程教学课件杨德芳第6章 LR分析技术》由会员分享，可在线阅读，更多相关《编译原理实用教程教学课件杨德芳第6章 LR分析技术（118页珍藏版）》请在金锄头文库上搜索。
1、第6章 LR分析技术,本章学习目标,LR(k)分析器是这样一种分析程序：它总是按从左到右的方式扫描输入串，并按照自底向上的方式进行归约。在这种分析过程中，它至多向前查看k个输入符号就能确定当前的动作是移进还是归约。本章要点： LR分析的基本原理 LR（0）分析表的构造 SLR（1）分析表的构造 LR（1）分析表的构造 LALR（1）分析表的构造,6.1 LR分析器的工作原理,自底向上分析方法是一种移进归约过程，当分析栈的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析方法的关键问题是在分析过程中如何确定句柄。LR分析方法根据当前分析栈中的符号串（通常用状态来表示）和向右顺序查看输入串的k（
2、k0）个符号就能惟一确定句柄。LR分析方法的归约过程正是规范推导的逆过程，所以LR分析过程是一种规范归约。 LR(k)分析方法是1965 年Knuth提出的。括号中的 k表示向右查看输入串符号的个数。这种方法比起自顶向下的LL（k）分析方法和自底向上的优先分析对文法的限制要少得多。也就是说对于大多数无二义性上下文无关文法描述的语言都可以用相应的LR分析器识别。而且这种方法还具有分析速度快，能准确、及时地指出出错位置等优点。它的主要缺点是对于一个实用语言文法分析器的构造工作量相当大，实现比较困难。,1LR分析的概述,一个LR分析器由三部分组成： （1）总控程序，也称为驱动程序。对所有的LR分析器
3、总控程序是相同的。 （2）分析表或分析函数。不同的文法其分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换表（GOTO）两部分,，们都用二维数组表示。 （3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定。,其中SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态栈的内容按关系GOTOSi，X= Sj。其中X为终结符或非终结符。,图6-1 LR分析器的工作过程,ACTIONSi,a规定了栈顶状态为Si时遇到输入符号a应该执行的动作。动作有4种可能： （1）移进：当Sj=GOTOSi,
4、a成立，则把Sj移入到状态栈，把a移到文法符号栈，其中i和j表示状态。 （2）归约：当在栈顶形成句柄为时，则用归约为相应的非终结符A，即当文法中有A的产生式，当的长度为（即|=）时，则从状态栈和文法符号栈中自栈顶向下去掉个符号，即栈指针SP减去；并把A移入文法符号栈，再把满足Sj=GOTOSi,A的状态移进状态栈，其中Si为修改后指针的栈顶状态。 （3）接受acc：当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则分析成功。 （4）报错：当遇到状态为某一个状态下出现不该遇到的文法符号栈时，则报错。说明输入串不是该文法能接受的句子。,2LR分析举例,表达式文法G
5、E如下所示，它对应的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.
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
7、）Ab2 （3）AAb3 （4）Bd4 根据这个文法对输入串abbcde 进行判断，形成如下的推导过程。 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 判断出该输入串是该文法的句子。 它的逆过程最左归约（规范归约）则为： 当输入串为abbcde时，根据它的推导过程可以写为： ab2b3cd4e1 用产生式（2）归约 aAb3cd4e1 用产生式（3）归约 aAbcd4e1 用产生式（4）归约 aAbcde1 用产生式（1）归约 S,其中“”表示归约。从这里可以看出对于一个合法的句子而言，每次归约后得到的都是已归约部分和输入剩余部分合起来构成文法的规范句型。而用哪个
8、产生式继续归约仅取决于当前句型的首部，例中每次归约前的句型的首部依次为： ab2 aAb3 aAbcd4 aAcBe1,这些符号正是在归约之前栈中的符号。当栈顶出现上述的符号串时，就采用相应的产生式进行归约，把句型的首部称为可归前缀。 我们再分析每个前部的前缀： ab2的前缀有,a,ab aAb3的前缀为,a,aA,aAb aAbcd4的前缀为,a,aA,aAb,aAbc,aAbcd aAcBe1的前缀为,a,aA,aAc, aAcB,aAcBe 我们把在规范句型中形成可归前缀之前包括可归前缀在内的所有的前缀称为活前缀。在规范归约的任何时刻，只要已分析过的部分即在符号栈内的符号串均为规范句型的
9、活前缀，则表明输入串的已分析过的部分是该文法某规范句型的正确部分。,3识别活前缀的有限自动机,定义6.1 若S A是文法G的拓广文法G中的一个规范推导。符号串是的前缀，则称是G的一个活前缀。也就是说是规范句型的前缀，但是它的右端不超过该句型句柄的末端。 根据定义，一旦出现在符号栈的栈顶，则形成句柄，就用产生式A进行归约。 在LR分析过程中，并不是直接分析文法符号栈中的符号是否形成句柄。我们把终结符和非终结符都看成一个有限自动机的输入符号，每有一个符号进栈，就认为自动机识别一个符号，而状态进行了转换。当识别到了可归约前缀时，相当在栈顶形成了句柄，则认为到达识别句柄的终态。,我们将上面的文法进行拓
10、广，文法表示成： （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，只有一个项
11、目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项目的分类,我们可以根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种。 移进项
12、目，形如Aa，其中和V*，aVT，即圆点后面为终结符的项目为移进项目，对应的状态为移进状态，分析时把a移进符号栈。 待约项目，形如AB，其中和V* ，BVN，即圆点后面为非终结符的项目为待约项目。它表明所对应的状态等待着分析完非终结符B所能推出的串归约成B，才能继续分析A的右部。 归约项目，形如A，其中V*，即圆点在最右端的项目称为归约项目。它表明一个产生式的右部已分析完成，句柄已形成，可以归约。 接受项目，形如S，其中V+，S为拓广文法，S为左部的产生式只有一个，因而它是归约项目的特殊情况，对应的状态为接受状态。我们规定S为初态。实际上接受项目中的为文法的开始符号。,3根据项目构造识别活前缀
13、的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）项目集规范族的
14、构造 （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的过程为： pr
15、ocedure 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 函数就能构造出一个
