编译原理 第七章 LR分析法

第7章LR分析第七章LR分析法课前索引【课前思考】◇复习自顶向下和自底向上语法分析思想的区别◇自底向上分析方法是一种移进-归约过程◇算符优先分析法是如何确定可归约串的？◇什么是规范推导和规范归约？它们之间有什么关系？◇什么是规范句型？◇什么是规范句型的句柄？◇移进-归约过程是当分析的栈顶符号串形成句柄时就采取归约动作◇自底向上分析法的关键问题是在分析过程中如何确定句柄。◇如何确定一个输入符号串是否是所给文法的句子？【学习目标】本章将介绍自底向上分析的另一种方法，即LR分析法。◇理解LR分析法的基本思想◇理解可归前缀和子前缀概念◇理解识别活前缀的有限自动机概念◇掌握LR分析器的构造思想和方法◇对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器，并能判断所给文法是四种分析器的哪几类。◇对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子◇了解某些二义性文法在LR分析中的应用。【学习指南】LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它LR类分析器的基础。因此，首先应学好LR(0)项目集规范族构造的基本原理和方法。当K=1时，已能满足当前绝大多数高级语言编译程序实现的需要。SLR(1)分析是为学习LR(1)分析做准备，LR(1)项目集族的构造是LALR(1)分析器的构造原理和基础。LALR(1)分析器是当前大多数高级程序设计语言编译程序所采用的语法分析技术，也是编译程序语法分析器自动构造工具YACC(将在第13章介绍）的实现基本原理。由此，LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法都必须深入理解和掌握。【难重点】◇可归前缀和子前缀概念◇识别活前缀的有限自动机概念◇对可归前缀为规范归约的句柄的理解◇构造LR(1)项目集族时搜索符的计算◇LR分析器的关键部分是分析表的构造◇对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器第7章LR分析◇当一个文法能构造出不含移进-归约或归约-归约冲突时的LR(0)/SLR(1)/LALR(1)/LR(1)分析表时，称这个文法为LR(0)/SLR(1)/LALR(1)/LR(1)文法。◇对给定的文法能判断是四种LR类文法的哪几类◇了解某些二义性文法在LR分析中的应用【知识结构】第7章LR分析在第6章中已经讨论过，自底向上分析方法是一种移进-归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR(K)分析方法是1965年Knuth提出的，括号中的K表示向右查看输入串符号的个数。这种方法比起自顶向下的LL(K)分析方法和算符优先分析方法对文法的限制要少得多，也就是说对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置。它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。目前对于真正实用的编译程序，所采用的LR分析器都是借助于美国Bell实验室1974年推出的一个编译器的编译器-YACC来实现的。它能接受一个用BNF描述的满足LALR(1)的上下文无关文法并将自动构造LALR(1)语法分析器。本章将主要介绍LR分析的基本思想和当K≤1时LR分析器的基本构造原理和方法。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，对绝大多数高级语言的语法分析器是不能适用的，然而，它是构造其它LR类分析器的基础。当K=1时，已能满足当前绝大多数高级语言编译程序的需要。因此，我们将着重介绍LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器的构造方法。其中SLR(1)和LALR(1)分别是LR(0)和LR(1)的一种改进。7.1LR分析概述一个LR分析器由3个部分组成：(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定(LR(0)分析器不需向前查看输入符号)。LR分析器工作过程示意图如图7.1所示。图7.1LR分析器工作过程示意图f7-1-1.swf其中SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[Si,X]＝Sj表示，规定当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符，状态的含义将在后面介绍。ACTION[Si,a]规定了栈顶状态为Si时遇到输入符号a应执行的动作。动作有4种可能：①移进②归约③接受acc④报错①移进：把Sj=GOTO[Si，a]移入到状态栈，把a移入到文法符号栈。其中i，j表示状态号。第7章LR分析②归约：当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即文法中有A→β的产生式，若β的长度为r(即|β|=r)，则从状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈指针SP减去r。并把A移入文法符号栈内，Sj=GOTO[Si，A]移进状态栈，其中Si为修改指针后的栈顶状态。③接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。④报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。LR分析器的关键部分是分析表的构造，后边将针对每种不同的LR分析器详细介绍其构造思想及方法。回顾在第6章中曾给出的例6.1文法，现以此为例复习自底向上分析方法移进-归约过程。f7-1-2.swf在步骤3中，用A→b归约在步骤5中，用A→Ab归约问题：何时移进？何时归约？用哪个产生式归约？是LR分析要解决的重要问题。第7章LR分析7.2LR(0)分析LR(0)分析表构造的思想和方法是构造其它LR分析表的基础。我们回顾在第6章中曾给出例6.1文法G[S]为：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d对输入串abbcde#用自底向上归约的方法进行分析，当归约到第5步时栈中符号串为#aAb，我们采用了产生式(3)进行归约而不是用产生式(2)归约，而在第3步归约时栈中符号串为#ab时却用产生式(2)归约，虽然在第2步和第5步归约前栈顶符号都为b，但归约所用产生式却不同，其原因在于已分析过的部分在栈中的前缀不同，也就是我们在LR分析中引进的状态栈的栈顶状态不同，为了说明这个问题我们先在表7.1中给出例6.1文法G[S]的LR(0)分析表，在表7.2给出对输入串abbcde#的分析过程，并引进一些概念和术语。对表7.1的构造原理和表7.2分析过程的实现思想将在下面详细介绍。表7.1例6.1文法的LR(0)分析表ACTIONGOTOacebd#SAB0123456789S2...r2.r3.r4r1...S5r2.r3.r4r1....r2.r3S9r4r1..S4S6r2.r3.r4r1....r2S8r3.r4r1.acc..r2.r3.r4r11..3.....7表7.1符号说明：Si：移进，将状态i和输入符进栈ri：归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。表7.2对输入串abbcde#的分析过程f7-2-2.swf总结上面LR分析算法为：置ip指向输入串w的第一个符号令Si为栈顶状态a是ip指向的符号（当前输入符号）begin(重复开始)ifACTION[Si,a]=SjthenbeginPUSHj,a(进栈)ip前进(指向下一输入符号)第7章LR分析endelseifACTION[Si,a]=rj(若第j条产生式为A→β)thenbeginpop|β|项若当前栈顶状态为SkpushGOTO[Sk,A]和A(进栈)endelseifACTION[Si,a]=accthenreturn(成功）elseerrorend.(重复结束)对于上面的分析过程我们可以知道LR分析器的关键部分是分析表的构造,那么可提出以下问题：一个文法的LR分析表是如何得到的？对于一个文法，状态集是如何确定的？为了解决这些问题引入可归前缀与活前缀概念7.2.1可归前缀和子前缀为了在以后的LR分析中不致引起混淆，现对原文法进行拓广。若原文法G的开始符号为S，在G中加产生式S′→S后得新的文法G′，则称G′为原文法G的拓广文法，而S′为拓广后文法G′的开始符号。对文法进行拓广的目的是为了对某些右部含有开始符号的文法，在归约过程中能分清是否已归约到文法的最初开始符，还是在文法右部出现的开始符号，拓广文法的开始符号S′只在左部出现，这样确保了不会混淆。我们可以形式地定义活前缀如下：定义7.1若S′αAωRRαβω是文法G′中的一个规范推导，G′是G的拓广文法，符号串γ是αβ的前缀，则称γ是G的，也是G′的一个活前缀。实际上γ是规范句型αβω的前缀，但它的右端不超过该句型句柄的末端（其中A→β是一产生式，ω∈VT*；α、β、γ∈V*）。由以上分析我们很容易理解，在LR分析过程中，实际上是把αβ的前缀列出放在符号栈中，一旦在栈中出现αβ，即句柄已经形成，则用产生式A→β进行归约。若对例6.1文法G[S]的每条产生式编上序号用[i]表示加在产生式的尾部，使产生式变为：S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]但[i]不属产生式的文法符号，对输入串abbcde进行推导时把序号也带入，则最右推导过程为：SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]所以输入串abbcde为该文法的句子。第7章LR分析它的逆过程,即最左归约(规范归约)则为：ab[2]b[3]cd[4]e[1]用产生式(2)归约aAb[3]cd[4]e[1]用产生式(3)归约aAcd[4]e[1]用产生式(4)归约aAcBe[1]用产生式(1)归约S其中表示归约，从这里可以看到每次归约时，归约前和归约后的已归约部分和剩余部分合起来只是构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前部分，例中每次归约前句型的前部分依次为：ab[2]aAb[3]aAcd[4]aAcBe[1]这正是我们在表7.2的分析过程中每次采取归约动作前符号栈中的内容，即分别对应步骤3、5、8、10时符号栈中的符号串，我们把规范句型的这种前部分串称可归前缀。我们再来分析下列规范句型的前缀：ε,a,abε,a,aA,aAbε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe不难发现前缀a,aA,aAc都不只是某一个规范句型的前缀，因此我们把形成可归前缀之前包括可归前缀在内所有规范句型的前缀都称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串已被分析过的部分是该文法某规范句型的一个正确部分。7.2.2识别活前缀的有限自动机在LR方法实际分析过程中并不是去直接分析文法符号栈中的符号