编译原理课件.ppt

第七章第七章 LRLR分析法分析法教学目的：教学目的：让学生了解让学生了解LR分析方法的基分析方法的基本思想，掌握本思想，掌握LR(0)、SLR(1)、LR(1)、LALR(1)分析法。分析法。教学重点：教学重点：LR（0）分析、）分析、LR（l）分）分析、析、SLR（1）分析和）分析和LALR（1）分析；）分析；构造构造LR分析的分析表。分析的分析表。课时分配：课时分配：8学时学时本章知识点本章知识点(内容内容)LR分析概述分析概述LR（0）分析）分析SLR（1）分析）分析LR（1）分析）分析LALR（1）分析）分析二义文法在二义文法在LRLR分析中的应用分析中的应用7.1 LR(Left-Right)分析概述算符优先分析法存在的问题算符优先分析法存在的问题 强调算符之间的优先关系的唯一性，这使得它的强调算符之间的优先关系的唯一性，这使得它的适应面比较窄；算法在发现最左素短语的尾时，需要适应面比较窄；算法在发现最左素短语的尾时，需要返回来寻找对应的最左素短语头。返回来寻找对应的最左素短语头。LR分析法：分析法：1对文法限制少；对文法限制少；2适用范围广；适用范围广；3分析速度快；分析速度快；4报错准确。报错准确。5易于实现自动生成。由于构造分析器的工作量很大，易于实现自动生成。由于构造分析器的工作量很大，不大可能手工构造；如用软件工具不大可能手工构造；如用软件工具Yacc-YetAnotherCompilerCompiler,Bell，这些软件工具叫，这些软件工具叫LR生成器。生成器。一、一、LR(k)LR(k)分析法分析法 L L：从左到右：从左到右扫描描输入符号，入符号，R R：最右推：最右推导对应的最左的最左归约,k k：超前：超前读入入k k个符号，用以确定个符号，用以确定归约所用的所用的规则。lLR分析法在自左至右扫描输入串时就能发现其中的分析法在自左至右扫描输入串时就能发现其中的任何错误并能准确地指出出错地点。任何错误并能准确地指出出错地点。l大多数用上下文无关文法描述的程序语言都可用大多数用上下文无关文法描述的程序语言都可用LR分析器予以识别。分析器予以识别。l主要缺点是，用手工构造分析程序则工作量相当大。主要缺点是，用手工构造分析程序则工作量相当大。因此，必须求助于自动产生这种分析程序的产生器。因此，必须求助于自动产生这种分析程序的产生器。二、二、LRLR分析法分类：分析法分类：LR(0)表构造法。这种方法的局限性极大、但它是建立其表构造法。这种方法的局限性极大、但它是建立其它较一般的它较一般的LR分析法的基础。分析法的基础。SIR表构造法。虽然，有一些文法构造不出表构造法。虽然，有一些文法构造不出SLR分析表，分析表，但是，这是一种比较容易实现又极有使用价值的方法。但是，这是一种比较容易实现又极有使用价值的方法。规范规范LR表构造法。这种分析表能力最强，能够适用一大表构造法。这种分析表能力最强，能够适用一大类文法，但实现代价过高，或者说，分析表的体积非常大。类文法，但实现代价过高，或者说，分析表的体积非常大。向前向前LR表构造法（简称表构造法（简称LAIR）。这种分析表的能力介于）。这种分析表的能力介于SIR和规范和规范LR之间，稍加努力，就可以高效地实现。之间，稍加努力，就可以高效地实现。规范归约（最左归约一最右推导的逆过程）的关键规范归约（最左归约一最右推导的逆过程）的关键问题是寻找句柄。问题是寻找句柄。LR方法的基本思想是方法的基本思想是:在规范归约的过程中，一方在规范归约的过程中，一方面要记住已移进和归约出的整个字符串，也就是说面要记住已移进和归约出的整个字符串，也就是说要记住历史；一方面能够根据所用的产生式的推测要记住历史；一方面能够根据所用的产生式的推测未来可能碰到的输入符号，也就是说能够对未来进未来可能碰到的输入符号，也就是说能够对未来进行展望。这样，当一串貌似句柄的字符串出现在分行展望。这样，当一串貌似句柄的字符串出现在分析栈的顶部时，我们希望能够根据历史和展望以及析栈的顶部时，我们希望能够根据历史和展望以及现实的输入符号这三部分的材料，决定出现在栈顶现实的输入符号这三部分的材料，决定出现在栈顶的这一串符号是否就是我们要找的的这一串符号是否就是我们要找的句柄。句柄。三、三、LR分析器的逻辑结构分析器的逻辑结构一个一个LR分析器包括两部分：一个总控分析器包括两部分：一个总控(驱动驱动)程序和一张分析表。注意：所有程序和一张分析表。注意：所有LR分析器的总分析器的总控程序都是一样的，只是分析表各有不同。因此控程序都是一样的，只是分析表各有不同。因此产生器的主要任务就是产生分析表。产生器的主要任务就是产生分析表。LRLR分析器的分析器的核心部分是一张分析表。核心部分是一张分析表。采用下推自动机这种数据模型。包括以下几个部采用下推自动机这种数据模型。包括以下几个部分：分：1.输入带。输入带。2.分析栈：包括状态栈和文法符号栈两部分。分析栈：包括状态栈和文法符号栈两部分。3.LR分析表：包括动作表和状态转移表两张表。分析表：包括动作表和状态转移表两张表。LRLR总控程序总控程序总控程序总控程序 输出规则输出规则输出规则输出规则 序列序列序列序列状态栈状态栈符号栈符号栈输入缓冲区输入缓冲区分析表分析表分析表包括两部分：分析表包括两部分：一部分是（一部分是（ACTION)表，另一部分是表，另一部分是状态转状态转换换(GOTO)表。它们都是二维数组。表。它们都是二维数组。ACTIONS，a中规定了当状态中规定了当状态S面临输入符号面临输入符号a时应采取什么动作。时应采取什么动作。GOTOS，X规定了状态规定了状态S面对文法符号面对文法符号X(终结终结符或非终结符符或非终结符)时下一状态是什么。时下一状态是什么。显然，显然，GOTOS，X定义了一个以文法符号为定义了一个以文法符号为字母表的字母表的DFA。【例】演示【例】演示每一项每一项ACTIONSACTIONS，aJaJ所规定的动作是下述所规定的动作是下述4 4种可能之种可能之-：(1)(1)移进：把移进：把(S(S，a)a)的下一状态的下一状态S S=ACTIONS=ACTIONS，aa和输和输入符号入符号a a推进栈（对终结符，推进栈（对终结符，GOTOSGOTOS，aa的值已放入的值已放入ACTIONACTIONSS，aa中中)，下一个，下一个输入符号变成现行输入符号。输入符号变成现行输入符号。(2)(2)归约：指用某一产生式归约：指用某一产生式A A 进行归约。假若进行归约。假若 的长的长度为度为 ，归约的动作是去掉栈顶的，归约的动作是去掉栈顶的 个项，然后把个项，然后把(Sm(Sm-，A)A)的下一状态和文法符号的下一状态和文法符号A A推进栈。归约动作不改变现推进栈。归约动作不改变现行输入符号。执行归约的动作意味着呈现于栈顶的符号串行输入符号。执行归约的动作意味着呈现于栈顶的符号串是一个相对于是一个相对于A A的句柄。的句柄。(3)(3)接受：宣布分析成功，停止分析器的工作。接受：宣布分析成功，停止分析器的工作。(4)(4)报错：报告发现源程序含有错误，调用出错处理程报错：报告发现源程序含有错误，调用出错处理程序。序。对于对于-个文法，如果能构造一张分析表，使得它的每个个文法，如果能构造一张分析表，使得它的每个入口均是唯一确定的，则把这个文法称为入口均是唯一确定的，则把这个文法称为LR文法。对于文法。对于一个一个LR文法，当分析器对输入串进行自左至右扫描时，文法，当分析器对输入串进行自左至右扫描时，一旦句柄呈现于栈顶，就能及时对它实行归约。一旦句柄呈现于栈顶，就能及时对它实行归约。一个一个LR分析器有时需要分析器有时需要“展望展望”和实际检查未来的和实际检查未来的k个输入符号才能决定应采取什么样的个输入符号才能决定应采取什么样的“移进一归约移进一归约”决决策。一般而言，策。一般而言，一个文法如果能用一个每步顶多向前检一个文法如果能用一个每步顶多向前检查查K个输入符号的个输入符号的LR分析器进行分析，则这个文法就称分析器进行分析，则这个文法就称为为LR(k)文法。文法。对于一个文法，如果它的任何对于一个文法，如果它的任何移进一归约移进一归约分析器都分析器都存在尽管栈的内容和符号都已了解，但无法确定是存在尽管栈的内容和符号都已了解，但无法确定是“移移进进”还是还是“归约归约”；或者，无法从几种可能的规约中确；或者，无法从几种可能的规约中确定其一的情形，那么这个文法就是非定其一的情形，那么这个文法就是非LR(1)的。的。7.2 LR(0)7.2 LR(0)分析法分析法【例【例】已知文法已知文法GS，分析符号串，分析符号串abbcde是否是是否是GS的句子的句子。(1)SaAcBe1(2)Ab2(3)AAb3(4)Bd4【解【解】这里每个产生式的右部字符串末尾的编号是为了这里每个产生式的右部字符串末尾的编号是为了方便查看在最右推导中是选择哪个产生式推导的，并不是方便查看在最右推导中是选择哪个产生式推导的，并不是产生式的一部分。产生式的一部分。句子的最右推导过程为：句子的最右推导过程为：S=aAcBe1=aAcd4e1=aAb3cd4e1=ab2b3cd4e1由于最右推导就是规范推导，因此句型由于最右推导就是规范推导，因此句型aAcBe、aAcde、aAbcde、abbcde为规范句型。为规范句型。规范句型的这种前部分符号串称为可归前缀。规范句型的这种前部分符号串称为可归前缀。【例如【例如】符号串符号串aAcBe是规范句型是规范句型aAcBe的可归前缀，的可归前缀，aAcd是规范句型是规范句型aAcd4e1的可归前缀，的可归前缀，aAb是规范句型是规范句型aAb3cd4e1的可归前缀，的可归前缀，ab是规范句型是规范句型ab2b3cd4e1的可归前缀。的可归前缀。我们把形成可归前缀之前包括可归前缀在内的我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。所有规范句型的前缀都称为活前缀。所谓前缀就所谓前缀就是符号串的任意首部。活前缀就是可归前缀是符号串的任意首部。活前缀就是可归前缀的任意首部的任意首部。【例如【例如】可归前缀可归前缀ab的活前缀为的活前缀为,a,ab可归前缀可归前缀aAb的活前缀为的活前缀为,a,aA,aAb可归前缀可归前缀aAcd的活前缀为的活前缀为,a,aA,aAc,aAcd可归前缀可归前缀aAcBe的活前缀为的活前缀为,a,aA,aAc,aAcB,aAcBe因为规范归约实际上就是规范推导的逆过程。因为规范归约实际上就是规范推导的逆过程。可归前缀就是存放在文法符号栈中的内容，它和可归前缀就是存放在文法符号栈中的内容，它和输入缓冲器的剩余内容合在一起如果刚好就是规输入缓冲器的剩余内容合在一起如果刚好就是规范句型，就能够保证我们的归约是一个规范归约范句型，就能够保证我们的归约是一个规范归约的过程。即栈内符号串总是规范句型的前缀的过程。即栈内符号串总是规范句型的前缀,且不且不含句柄右侧的符号。原因含句柄右侧的符号。原因:句柄一旦在栈顶形成句柄一旦在栈顶形成,就不再移进新符号就不再移进新符号,而是要进行归约了。而是要进行归约了。我们把具有上述性质的符号串称为规范句型的活我们把具有上述性质的符号串称为规范句型的活前缀。前缀。为什么要引进活前缀的概念？为什么要引进活前缀的概念？规范句型活前缀一、活前缀和可归前缀的形式定义一、活前缀和可归前缀的形式定义若若SA,则称则称为可归前缀为可归前缀;若有串若有串W是是的前缀，则称的前缀，则称W是是G的一个活前缀（的一个活前缀（S为文法拓广后的为文法拓广后的开始符，它只出现在规则左部）。可归前缀是包含句柄的开始符，它只出现在规则左部）。可归前缀是包含句柄的活前缀。活前缀。二、说明：二、说明：规范句型的活前缀有两个要点规范句型的活前缀有两个要点:(1)它是规范句型的前缀它是规范句型的前缀;(2)它不含句柄右侧符号它不含句柄右侧符号由于活前缀实际上就是满足一定要求的符号由于活前缀实际上就是满足一定要求的符号串，因此识别活前缀的工作和识别单词的工作非串，因此识别活前缀的工作和识别单词的工作非常类似，所以我们可以采用常类似，所以我们可以采用有穷自动机有穷自动机这种数据这种数据模型来实现活前缀的识别。模型来实现活前缀的识别。如何识别文法符号栈中的内容就是活前缀如何识别文法符号栈中的内容就是活前缀基本思想是我们可以把文法的终结符和非基本思想是我们可以把文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形行转换，当识别到可归前缀时，相当于在栈中形成句柄，达到了识别句柄的终态。成句柄，达到了识别句柄的终态。识别活前缀的有穷自动机的构造实现识别活前缀的有穷自动机的构造有两种实现识别活前缀的有穷自动机的构造有两种方法：方法：方法方法1：由文法的产生式直接构造识别活前缀和可归前由文法的产生式直接构造识别活前缀和可归前缀的有穷自动机缀的有穷自动机方法方法2：通过构造文法通过构造文法G的的LR(0)的项目集规范族来直的项目集规范族来直接构造识别活前缀的接构造识别活前缀的DFA【说明】由于【说明】由于NFA确定化为确定化为DFA的工作量较大，我的工作量较大，我们考虑直接构造出项目集规范族作为们考虑直接构造出项目集规范族作为DFA的状态，的状态，来构造来构造DFA。LR(0)项目集规范族的构造项目集规范族的构造定义：构成识别一个文法活前缀的定义：构成识别一个文法活前缀的DFA项目集项目集（状态）的全体，称为这个文法的（状态）的全体，称为这个文法的LR(0)项目集规项目集规范族。范族。(一一)LR)LR（0 0）项目）项目在每个产生式的右部适当位置添加一个圆点构成在每个产生式的右部适当位置添加一个圆点构成项目（项目（item）。每个项目的含义和圆点的位置有）。每个项目的含义和圆点的位置有关。项目圆点的左部表示分析过程的某个时刻用关。项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。示待识别的部分。根据圆点所在的位置和圆点后是终结符还是非终根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：结符把项目分为以下几种：1、移进项目，形如、移进项目，形如Aa.ab2、待约项目，形如、待约项目，形如Aa.Bb3、归约项目，形如、归约项目，形如Aa.4、接受项目，形如、接受项目，形如SS.【例】产生式【例】产生式S SaAcBe对应的对应的6个项目是：个项目是：0S S.aAcBe1S Sa.AcBe2S SaA.cBe3S SaAc.Be4S SaAcB.e5S SaAcBe.一个产生式可对应的项目为它的右部符号长度加一个产生式可对应的项目为它的右部符号长度加1，对空产生式，对空产生式A-仅有一个项目仅有一个项目A-.【例】产生式【例】产生式A-XYZ对应对应4个项目个项目A-.XYZA-XYZA-XYZA-XYZ（二）（二）LR(0)LR(0)项目集规范族的构造项目集规范族的构造对于构成识别一个文法活前缀的对于构成识别一个文法活前缀的DFA项目集的全体项目集的全体称为这个文法的称为这个文法的LR（0）项目集规范族）项目集规范族（1）首先，为了使）首先，为了使接受接受状态易于识别，总是状态易于识别，总是将文法将文法G进行拓广。假定文法进行拓广。假定文法G是一个以是一个以S为开始符为开始符号的文法，我们构造一个号的文法，我们构造一个G，它包含了整个，它包含了整个G并引并引进了一个不出现在进了一个不出现在G中的非终结符中的非终结符S；同时加进了；同时加进了一个新产生式一个新产生式S一一S，而这个，而这个S是是G的开始符号，的开始符号，称称G是是G的拓广文法。会有一个仅含项目的拓广文法。会有一个仅含项目S-S的的状态，这就是唯一状态，这就是唯一的的接受接受态。态。如果如果I是文法是文法G的一个项目集，定义和构造的一个项目集，定义和构造I的闭包的闭包CLOSURE(I)如下：如下：a)I的项目都在的项目都在CLOSURE(I)中中b)若若Aa.Bb属于属于CLOSURE(I)，则每一，则每一形如形如B.g的项目也属于的项目也属于CLOSURE(I)c)重复重复b)直到直到CLOSURE(I)不再扩大。不再扩大。【说明【说明】求闭包函数的过程实际上就是求所求闭包函数的过程实际上就是求所有等价状态的过程。有等价状态的过程。（2）闭包函数）闭包函数CLOSURE(I)（3）转换函数）转换函数GOTO（I，X)定义转换函数如下：定义转换函数如下：GOTO（I，X）=CLOSURE（J）其中：其中：I为包含某一项目集的状态，为包含某一项目集的状态，X为一文法符为一文法符号号J=任何形如任何形如AaX.b的项目的项目|Aa.Xb属于属于I定义两个函数后，就可以通过闭包函数定义两个函数后，就可以通过闭包函数CLOSURE求求DFA一个状态的项目集，通过转换函一个状态的项目集，通过转换函数求数求DFA一个状态的项目集一个状态的项目集【例【例】A-a.XbA-aX.bX构造文法构造文法G的的LR(0)项目集规范族的方法项目集规范族的方法:把文法的所有产生式的项目都引出，每个项目都把文法的所有产生式的项目都引出，每个项目都为为NFA的一个状态。其中文法的第一个产生式的的一个状态。其中文法的第一个产生式的第一个项目第一个项目S.S为文法的初态集的核心项。为文法的初态集的核心项。a)置项目置项目S.S为初态集的核心项后，对核心为初态集的核心项后，对核心项求闭包项求闭包CLOSURE（S.S）得到初态的项目）得到初态的项目集集b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数GOTO(I，X)=CLOSURE(J)求出新状态求出新状态J的项目集的项目集c)重复重复b)直到不出现新的项目集为止直到不出现新的项目集为止【例】文法【例】文法GS:0SEE1EaA1EaA2EbB2EbB3AcA3AcA4Ad4Ad5BcB5BcB6Bd 6Bd 其其规范范项目集族构造如目集族构造如下：下：假定假定C=I。，。，I1，In)。由于我们已。由于我们已经习惯用数字表示状态，因此令每个项目经习惯用数字表示状态，因此令每个项目集集Ik的下标的下标k作为分析器的状态。特别是作为分析器的状态。特别是令包含项目令包含项目SS(表示整个句子还未输表示整个句子还未输入入)的集合的集合Ik的下标的下标k为分析器的初态。为分析器的初态。LR(0)分析表的构造分析表的构造分析表的分析表的ACTION子表和子表和GOTO子表可按如下方子表可按如下方法构造：法构造：(1)若项目若项目A-a属于属于Ik且且GO(Ik,a)=Ij，a为终结符，置为终结符，置ACTIONk,a为将为将(j，a)移进栈移进栈”，简记为，简记为“Sj(2)若项目若项目A-.属于属于Ik，则对任何终结符，则对任何终结符a(或或结束符结束符#)，置，置ACTIONk,a为用产生式为用产生式A-a进行进行归约，简记为归约，简记为“rj”(注意：注意：j是产生式的编号而是产生式的编号而不是项目集的状态号，即不是项目集的状态号，即A-a是文法是文法G的第的第j个产个产生式生式)。（3）若项目）若项目S-S属于属于Ik(S表示整个句子已表示整个句子已输入并归约结束输入并归约结束)，则置，则置ACTIONK，#为可为可“接接受受”，简记为，简记为“acc”。(4)若若GO(Ik,A)=Ij,A为非终结符，则置为非终结符，则置GOTOk，A=j。(5)分析表中凡不能用规则分析表中凡不能用规则(1)一一(4)填入的空白填入的空白格均置上格均置上“报错标志报错标志”。LR(0)LR(0)分析算法分析算法 1 1、置、置输入指入指针 ipip 指向指向输入串的第一个符号；令入串的第一个符号；令 s s 是是栈顶状态，顶状态，a a 是是 ipip 所指向的符号所指向的符号;将将#压入压入符号栈，将开始状态符号栈，将开始状态0 0压入状态栈；压入状态栈；2 2、重复、重复执行如下行如下过程：程：ifif（actions,a=sjactions,a=sj）把符号把符号a a入符号入符号栈，把状，把状态j j入状入状态栈；使使 ipip 指向下一个指向下一个输入符号。入符号。else if else if（actions,a=rjactions,a=rj）从栈顶弹出第从栈顶弹出第j j条规则右部串长条规则右部串长|个符个符号；号；把把归约得到的非得到的非终结符符A A压入符号入符号栈；将将gotos,Agotos,A 的的值j j压入状入状态栈；并并输出出规则 AA。else if else if（actions,a=accactions,a=acc）returnreturn；else else error()error()；【例】文法【例】文法GS:0SE1EaA2EbB3AcA4Ad5BcB6Bd,对输入串对输入串bccdbccd#分析如下：分析如下：步骤步骤状态栈状态栈符号栈符号栈输入串输入串actionGoto1 0#bccd#S32 03#bccd#S53 035#bccd#S54 0355#bccd#S115 0355(11)#bccd#r696 03559#bccB#r597 0359#bcB#r578 037#bB#r219 01#E#accLR（0）文法）文法1、如果、如果I中至少含两个归约项目，则称中至少含两个归约项目，则称I有有归约归约归约冲突（归约冲突（Reduce/ReduceConflict）2、如果、如果I中既含归约项目，又含移进项目，则称中既含归约项目，又含移进项目，则称I有移进有移进归约冲突（归约冲突（Shift/ReduceConflict）3、如果、如果I既没有归约既没有归约归约冲突，又没有移进归约冲突，又没有移进归约冲突，则称归约冲突，则称I是相容的是相容的(Consistent)，否则，否则称称I是不相容的。是不相容的。4、对文法、对文法G，如果，如果 IC,都是相容的，则称都是相容的，则称G为为LR(0)文法。文法。【例】有产生式如下【例】有产生式如下SBBBaB|b构造该文法的构造该文法的LR(0)分析表分析表将文法将文法G拓广为文法拓广为文法G0)S一一S1)SBB2)BaB3)Bb列出列出LR(0)的所有项目的所有项目1、SS5、SBB9、B-.b2、S一一S.6、BaB10、B-b.3、S一一.BB7、BaB4、SBB8、BaB.用用e_CLOSURE办法构造文法办法构造文法G的的LR(0)项目集规范族项目集规范族I0:S-.SS-.BBB-.aBB-.bI1:S-S.I2：SBBB一一.aBB.bI3:B-a.BB-.aBB-.bI4:B-b.I5:S-BB.I6:B-aB.状态状态 ACTlONACTlON GOTO GOTO a b#S B a b#S B 0 s3 S4 1 2 0 s3 S4 1 2 1 aCC 1 aCC 2 s3 S4 5 2 s3 S4 5 3 S3 s4 6 3 S3 s4 6 4 r3 r3 r3 4 r3 r3 r3 5 r1 r1 rl 5 r1 r1 rl 6 r2 r2 r2 6 r2 r2 r2 LR(0)分析表分析表【练习】设有文法【练习】设有文法GS：S-EE-Aa|bBA-cA|dB-cB|d构造构造LR(0)分析表，并利用此分析表判断符号串分析表，并利用此分析表判断符号串acccd是否是文法是否是文法GS的句子。的句子。LR(0)文法是一类非常简单的文法，没有文法是一类非常简单的文法，没有查看下一符号查看下一符号(Token),决定分析动作仅仅根据决定分析动作仅仅根据到目前已经看到的东西，分析能力弱。即使到目前已经看到的东西，分析能力弱。即使是定义算术表达式这样的简单文法也不是是定义算术表达式这样的简单文法也不是LR(0)。改进办法改进办法:向前查看下一符号向前查看下一符号-SLR(1),LR(1),LALR(1)7.3 SLR(1)7.3 SLR(1)分析分析7.3 SLR(1)分析法一、一、LR(0)LR(0)分析存在的问题分析存在的问题 【例】已知文法【例】已知文法G,开始符号为开始符号为S,判断该文法是判断该文法是否为否为LR(0)文法。文法。(0)SS(1)SrD(2)DD,i(3)Di单击演示单击演示这里仅仅凭这里仅仅凭LR(0)LR(0)项目本身的信息已经无法项目本身的信息已经无法解决项目之间的冲突，需要向前查看一个解决项目之间的冲突，需要向前查看一个符号，再来决定到底是采取移进动作还是符号，再来决定到底是采取移进动作还是归约动作。归约动作。二、解决方法二、解决方法对含有移进对含有移进-归约和归约归约和归约-归约冲突的项目集归约冲突的项目集I=Xa.bb,Ag.,Bd.若有：若有：FOLLOW(A)FOLLOW(B)=FOLLOW(A)b=FOLLOW(B)b=状态状态I面临某输入符号面临某输入符号a1)若若a=b，则移进，则移进2)若若aFOLLOW(A),则用产生式则用产生式Ag进行归约进行归约3)若若aFOLLOW(B),则用产生式则用产生式Bd进行归约进行归约4)此外，报错此外，报错若一个文法的若一个文法的LR(0)LR(0)分析表中所含有的分析表中所含有的动作冲突都能用上述方法解决，则称动作冲突都能用上述方法解决，则称这个文法是这个文法是SLR(1)SLR(1)文法。文法。SLR(1)SLR(1)文法是文法是无二义的。无二义的。对任给的一个文法对任给的一个文法G，我们可用如下的，我们可用如下的办法构造它的办法构造它的SLR(1)分析表：分析表：首先把首先把G拓广为拓广为G，对，对G构造构造LR(0)项目集项目集规范族和活前缀识别自动机的状态转换函数规范族和活前缀识别自动机的状态转换函数GO，使用闭包函数和函，使用闭包函数和函数，然后再按下面的算法构造数，然后再按下面的算法构造G的的SLR分析分析表。表。SLR(1)SLR(1)分析表构造方法分析表构造方法(1)若项目若项目A-a属于属于Ik且且GO(Ik,a)=Ij，a为终结符，为终结符，置置ACTIONk,a为将为将(j，a)移进栈移进栈”，简记为，简记为“Sj。(2)若项目若项目A-.属于属于Ik，则对任何终结符，则对任何终结符a(或结束符或结束符#)，且，且aFOLLOW（A)，置，置ACTIONk,a为用产生式为用产生式A-a进行归进行归约，简记为约，简记为“rj”。(3)若项目若项目S-S属于属于Ik(S表示整个句子已输入并归约结束表示整个句子已输入并归约结束)，则置，则置ACTIONK，#为可为可“接受接受”，简记为，简记为“acc”。(4)若若GO(Ik,A)=Ij,A为非终结符，则置为非终结符，则置GOTOk，A=j；。；。(5)分析表中凡不能用规则分析表中凡不能用规则(1)一一(4)填入的空白格均置上填入的空白格均置上“报错报错标志标志”。分析表的分析表的ACTION子表和子表和GOTO子表构造方法：子表构造方法：【练习】判断下列文法是否是【练习】判断下列文法是否是LRLR（0 0），如），如不是说明理由，判断是否是不是说明理由，判断是否是SLRSLR（1 1）文法。）文法。文法文法GSS-iSeSS-iSS-a【练习】文法个【练习】文法个GE为：为：EE+T|TT-T*F|FF-(E)|i分析它是分析它是LR（0）文法还是）文法还是SLR（1）文法。）文法。SLRSLR（1 1）的局限性：）的局限性：在在SLR方法中，若项目集方法中，若项目集Ik含有含有A-.，那么在状态，那么在状态k时，只要所面临的输入时，只要所面临的输入符号符号aFOLLOW(A)，就确定采取，就确定采取“用用A-归约归约”的动作。但是在某种情况下，当状的动作。但是在某种情况下，当状态态k呈现于栈顶时，栈里的符号串所构成的活呈现于栈顶时，栈里的符号串所构成的活前缀前缀未必允许把未必允许把归约为归约为A，因为可能没有，因为可能没有一个规范句型含有前缀一个规范句型含有前缀Aa。因此，在这种。因此，在这种情况下，用情况下，用A-进行归约未必有效。进行归约未必有效。即在即在SLR方法中存在无效归约。方法中存在无效归约。7.4LR（1）分析）分析【例】下列文法【例】下列文法G为为0)S-S1)S一一aAd2)S-bAc3)Saec4)S一一bed5)A-elo：S-SS一一aAdS-.bAcSaecS一一bedaI2：SaAdSa.ecA一一eeI5：S-aecA-eAI4：SaA.dcI9:S-aec.I1:S-S.SI3：SbAcSbedA-ebI8:S-aAd.dI6：S-bA.cAI7：S-bedA-eeI10:SbAc.cI11:S-bed.dLR(0)识别识别G的活前缀的的活前缀的DFA项目项目I5、I7中的移进中的移进-归约冲突，不能用归约冲突，不能用SLR(1)解决。解决。I5：S-aecA-e因因S=S=aAd=aedRRS=S=aec对活前缀对活前缀ae，面临输入符号，面临输入符号c时应移进，面临时应移进，面临d时时应用应用A-e归约归约FOLLOW(A)=c,d,其中面临其中面临c时时存在无效归约。存在无效归约。LRLR（1 1）项目的一般形式）项目的一般形式重新定义项目，使得每个项目都附带有重新定义项目，使得每个项目都附带有K个终结符。每个项目的个终结符。每个项目的一般形式是一般形式是:A-，ala2akA-是一个是一个LR(0)项目，每一个项目，每一个a都是终结符。这样的一个项目都是终结符。这样的一个项目称为一个称为一个LRIk项目。项目中的项目。项目中的ala2ak称为它的向前搜索符串称为它的向前搜索符串(或展或展望串望串)。向前搜索符串仅对归约项目。向前搜索符串仅对归约项目A-，ala2ak有意义。有意义。对于任何移进或待约项目对于任何移进或待约项目A-，ala2ak，搜索搜索符串符串ala2ak不起作用。归约项目不起作用。归约项目A-，ala2ak，意味着当它所属的状态呈现在栈顶且，意味着当它所属的状态呈现在栈顶且后续的后续的k个输入符号为个输入符号为ala2ak，才可以把栈顶的，才可以把栈顶的归约为归约为A。这。这里只对里只对k1的情形感兴趣，因为对多数程序语言的语法来说，向前搜的情形感兴趣，因为对多数程序语言的语法来说，向前搜索索(展望一个符号就基本可以确定展望一个符号就基本可以确定“移进移进”或或“归约归约”。构造有效的构造有效的LR(1)项目集族的办法本质上和构造项目集族的办法本质上和构造LR(0)项目集项目集规范族的办法是规范族的办法是样的。即也需要两个函数样的。即也需要两个函数CLOSURE和和GO。假定假定I是一个项目集，它的闭包是一个项目集，它的闭包CLOSURE()可按如下方可按如下方式构造：式构造：(1)I的任何项目都属于的任何项目都属于CLOSURE()。(2)若项目若项目A-，a属于属于CLOSURE()，B是一个产生式，对于是一个产生式，对于FIRST(a)中的每个终结符中的每个终结符b(即即a所有可能推导出的开头终结符所有可能推导出的开头终结符b，仅当，仅当时时b=a)如果如果B.，b原来不在原来不在CLOSURE(I)中，则把它加进去。中，则把它加进去。(3)重复执行步骤重复执行步骤(2)，直到，直到CLOSURE(I)不再增大为止不再增大为止lo：S-S，#S一一aAd，#S-.bAc，#Saec，#S一一bed，#eI5：S-aec,#A-e,dAI4：SaA.d,#cI9:S-aec.,#aI2：SaAd,#Sa.ec,#A一一e,dI1:S-S.，#SI3：SbAc,#Sbed,#A-e,cbI8:S-aAd.,#dI6：S-bA.c,#AI7：S-bed,#A-e,ceI10:SbAc.,#cI11:S-bed.,#dLR（1）项目集和转换函数【例】下列文法【例】下列文法G为为0)S-S1)S一一aAd2)S-bAc3)Saec4)S一一bed5)A-e假定假定C=I。，。，Il，In。，令每个，令每个Ik的下标的下标k为分析表的状态，令那个含有为分析表的状态，令那个含有S-S，#的的Ik的的k为分析器的初态。动作为分析器的初态。动作ACTION和状态转换和状态转换GOTO可按如下方法构造：可按如下方法构造：(1)若项目若项目A一一a，b属于属于Ik且且GO(Ik,a)=Ij，a为终结符，则置为终结符，则置ACTIONk，a为为将状态将状态i和符和符号号a移进栈移进栈，简记为，简记为Si。(2)若项目若项目A一一，a属于属于Ik，则置，则置ACTIONk，a为为“用产生式用产生式A-归约归约”，简记为，简记为rj,其中，其中，j是产生式的编号，即是产生式的编号，即A-是文法是文法G的第的第j个产生式。个产生式。文法的文法的LR(1)项目集族构造分析表的算法是：项目集族构造分析表的算法是：(3)若项目若项目S-S，#属于属于Ik，则置，则置ACTIONk，#为为接受接受，简记为，简记为acc。(4)若若GO(Ik，A)=Ij，A为非终结符，则置为非终结符，则置GOTO(Ik，A)=j。(5)分析表中凡不能用规则分析表中凡不能用规则(1)(4)填入信息的空填入信息的空白栏均填上白栏均填上出错标志出错标志。文法的文法的LR(1)项目集族构造分析表的算法是：项目集族构造分析表的算法是：按上述算法构造的分析表，若不存在多重定按上述算法构造的分析表，若不存在多重定义入口义入口(即动作冲突即动作冲突)的情形，则称它是文法的情形，则称它是文法G的一张规范的的一张规范的LR(1)分析表。使用这种分析分析表。使用这种分析表的分析器叫做一个规范的表的分析器叫做一个规范的LR分析器。具有分析器。具有规范的规范的LR(1)分析表的文法称为一个分析表的文法称为一个LR(1)文文法。法。【例【例】(0)SS(1)SL=RL=R (2)SR(2)SR (3)L*R (3)L*R (4)Li (4)Li (5)RL (5)RLLR(1)比比SLR（1）能力强）能力强I0:SS,#SL=R,#SR,#L*R,=/#Li,=/#RL,#I1:SS,#sI9:SL=R,#RI6:SL=R,#RL,#L*R,#Li,#=I2:SL=R,#RL,#LI3:SR,#RI5:Li,=/#iiI12:Li,#iiI13:L*R,#RLI10:RL,#LI7:L*R,=/#RI8:RL,=/#LI4:L*R,=/#RL,=/#Li,=/#L*R,=/#*I11:L*R,#RL,#L*R,#Li,#*LR(1)LR(1)项目集及转换函数项目集及转换函数例：给定文法例：给定文法GA：A-(A)|a1)画出画出LR（1）项目识别所有活前缀的）项目识别所有活前缀的DFA2)构造构造LR（1）分析表）分析表I0:A-.A,#A-.(A),#A-.a,#AI1:A-A.,#(I2:A-(.A),#A-.(A),)A-.a,)aI3:A-a.,#AI4:A-(A.),#aI6:A-a.,)AI8:A-(A.),)(I5:A-(.A),)A-.(A),)A-.a,)(a)I9:A-(A).,)I7:A-(A).,#)LR（1）项目集和转换函数）项目集和转换函数每个每个SLR(1)SLR(1)文法都是文法都是LR(1)LR(1)的，一个的，一个SLR(1)SLR(1)文法的规范文法的规范LRLR分析器比其分析器比其SLR(1)SLR(1)分析器的分析器的状态要多。状态要多。【例】【例】GSGS：(1)S(1)S BB BB (2)B(2)BaB aB (3)B(3)B b b I0:S S,#S BB,#B aB,a/bB b,a/b I1:S S,#sI2:S BB,#B aB,#