编译原理第七章ppt课件.ppt

《编译原理第七章ppt课件.ppt》由会员分享，可在线阅读，更多相关《编译原理第七章ppt课件.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第七章第七章 LRLR分析法分析法经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第七章第七章LR分析法分析法7.1 LR分析概述7.2 LR（0）分析7.3 SLR（1）分析7.4 LR（1）分析7.5 LALR（1）分析7.6 二义性文法在LR分析中的应用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费

2、用复习：复习：自底向上分析自底向上分析n思想思想n从输入串出发，反复利用产生式进行归约，如从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误否则输入串有语法错误n核心核心n寻找句型中的当前归约对象寻找句型中的当前归约对象“句柄句柄”进行进行归约归约,用不同的方法寻找句柄，就可获得不同的用不同的方法寻找句柄，就可获得不同的分析方法分析方法3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1.优先法优先法-ch6算符优先

3、分析算符优先分析根据归约的先后次序为句型中根据归约的先后次序为句型中相邻相邻的文法符的文法符号规定优先关系号规定优先关系句柄内相邻符号同时归约，是同优先级的句柄内相邻符号同时归约，是同优先级的句柄两个端点符号的优先级要高于句柄外与之句柄两个端点符号的优先级要高于句柄外与之相邻的符号的优先级，句柄内相邻符号具有相相邻的符号的优先级，句柄内相邻符号具有相同的优先级同的优先级a1ai-1aj+1an4经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2.状态法状态法-ch7 LR分析法分析法根据句柄的形成过程建立状态根据

4、句柄的形成过程建立状态用状态来描述不同时刻句柄是否形成用状态来描述不同时刻句柄是否形成因为句柄是产生式的右部，可用产生式来表示因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态句柄的不同识别状态例如：例如：SbBB可分解为如下识别状态可分解为如下识别状态S.bBB 移进移进b bSb.BB 等待归约出等待归约出B BSbB.B 等待归约出等待归约出B BSbBB.归约归约5经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR分析法是分析法是1965年由年由Knuth提出的一种提出的一种自自底向上底向上分析

5、方法，它的适用范围很广，很受分析方法，它的适用范围很广，很受计算机理论界的重视。计算机理论界的重视。自底向上分析法的关键问题是在分析过程自底向上分析法的关键问题是在分析过程中中如何确定句柄如何确定句柄。LR分析法能根据当前分析栈分析法能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查中的符号串（通常以状态表示）和向右顺序查看输入串的看输入串的k个（个（k0）符号可唯一确定分析器）符号可唯一确定分析器的动作是移进还是归约和用哪个产生式归约，的动作是移进还是归约和用哪个产生式归约，能唯一地确定句柄。能唯一地确定句柄。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失

6、，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR（K）表示）表示“从左至右，每步向前从左至右，每步向前（右）查看（右）查看K个输入符号个输入符号”。K=0表示表示不需要向右查看输入符号不需要向右查看输入符号LR分析法严格执行最左归约，分析法严格执行最左归约，是一是一种规范归约种规范归约，这一点与算符优先分析法，这一点与算符优先分析法不同。不同。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR分析法的分析法的优点优点：对文法限制少，适用范围广。对文法限制少，适用范围广。分析速度快分析速度快能准确及时地

7、报错能准确及时地报错缺点缺点：构造分析器的工作量较大构造分析器的工作量较大K值愈大，实现愈困难值愈大，实现愈困难经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用本章主要介绍本章主要介绍LR分析的基本思想，及分析的基本思想，及当当K1时，时，LR分析器的基本构造原理和分析器的基本构造原理和方法。着重介绍方法。着重介绍LR（0）、）、SLR（1）、）、LALR（1）、LR（1）四种分析器的构造）四种分析器的构造方法。方法。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消

8、费者购买商品的价款或接受服务的费用7.1LR分析概述分析概述一一LR分析器的组成分析器的组成一个一个LRLR分析器由分析器由3 3个部分组成：个部分组成：(1)总控程序总控程序：也称驱动程序，所有：也称驱动程序，所有LR分析器的总分析器的总控程序都是相同的。控程序都是相同的。(2)分析表或分析函数分析表或分析函数:不同的文法分析表不同；同一不同的文法分析表不同；同一个文法采用的个文法采用的LR分析器不同时，分析表也不同。分析器不同时，分析表也不同。分析表可分为分析表可分为动作表（动作表（ACTION）和和状态转换状态转换表表（GOTO）两部分，它们都可用二维数组表示。两部分，它们都可用二维数组

9、表示。(3)分析栈分析栈：包括文法符号栈和状态栈：包括文法符号栈和状态栈经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二 LR分析器工作过程分析器工作过程LR分析器的动作由栈顶状态和当前输入分析器的动作由栈顶状态和当前输入符号决定。符号决定。SP输出输出输入串输入串#总控程序总控程序ACTION表表GOTO表表SnXn S1X1S0X0经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 SP：栈指针：栈指针Si：状态栈：状态栈Xi：

10、文法符号栈：文法符号栈ACTION表和表和GOTO表分别为动作表和状态转换表。表分别为动作表和状态转换表。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用GOTOSi，X=Sj表示栈顶状态为表示栈顶状态为Si遇到当遇到当前前文法符号为文法符号为X时应转向状态时应转向状态Sj。ACTIONSi，a规定了栈顶状态为规定了栈顶状态为Si时遇时遇到到输入符号输入符号a应执行的动作。动作有应执行的动作。动作有4种种：(1)移进移进：把：把a移入文法符号栈，把移入文法符号栈，把Sj=GOTOSi，a移入到状态栈。其移入到状态

11、栈。其中中i，j表示状态号。表示状态号。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(2)归约归约：当栈顶形成句柄为：当栈顶形成句柄为时，把时，把归约为归约为相应的非终结符相应的非终结符A（A为文法中的为文法中的产生式）。设产生式）。设的长度为的长度为r（即（即|=r），则从状态栈和文法符号栈中自），则从状态栈和文法符号栈中自顶向下顶向下去掉去掉r个符号（即栈指针个符号（即栈指针SP-r），把），把A移入文法符号栈，移入文法符号栈，Sj=GOTOSi，A移进状态栈，移进状态栈，Si为为修改指针后的栈顶状态。修

12、改指针后的栈顶状态。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(3)接受接受acc：文法符号栈中只有开始符：文法符号栈中只有开始符S，输，输入串只入串只有有#，则为分析成功。，则为分析成功。(4)报错报错：当遇到状态栈顶为某一状态下出：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句说明输入串不是该文法能接受的句子。子。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或

13、接受服务的费用LR分析器的分析器的关键部分是分析表的构造关键部分是分析表的构造，下面，下面将针对每种不同的将针对每种不同的LR分析器详细介绍其构造分析器详细介绍其构造思想及方法。思想及方法。7.2LR（0）分析）分析LR（0）分析表构造的思想和方法是构造）分析表构造的思想和方法是构造其它其它LR分析表的基础。分析表的基础。先引进一些概念和术语：先引进一些概念和术语：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用拓广文法拓广文法：对原文法：对原文法GS增加一产生式增加一产生式SS，S只在左部出现。只在左部出现。对

14、文法进行拓广的目的：为了对某些右对文法进行拓广的目的：为了对某些右部含有开始符的文法，在归约过程中能分清部含有开始符的文法，在归约过程中能分清是否已归约到文法的最初开始符，还是在文是否已归约到文法的最初开始符，还是在文法右部出现的开始符。拓广文法的开始符法右部出现的开始符。拓广文法的开始符S只在左部出现，这样确保不会混淆。只在左部出现，这样确保不会混淆。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 可归前缀可归前缀：如果有：如果有S=，为终结符串为终结符串（或空），（或空），含有句柄，且句柄在含有句柄，且句柄

15、在 的后端，称的后端，称 为可归前缀。为可归前缀。*R活前缀活前缀：把形成可归前缀之前包括可归前缀：把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。在内的所有规范句型的前缀都称为活前缀。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用定义定义7.1若若S=A =是文法是文法G中的一个规范推导（中的一个规范推导（为句柄），如果符为句柄），如果符号串号串是是的前缀，则称的前缀，则称是是G G的一个的一个活活前缀前缀，的右端不超过句柄的末端。的右端不超过句柄的末端。*RR经营者提供商品或者服务有欺诈

16、行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例如：例如：GS：（：（1）SaAcBe（2）Ab（3）AAb（4）BdaAbcde是规范句型。是规范句型。因为因为:S=aAcBe=aAcde=aAbcde 从左至右，从左至右，规范句型规范句型aAbcde的活前缀有的活前缀有、a、aA、aAb，而，而aAbc不是活前缀，因为它不是活前缀，因为它包含句柄后面的符号包含句柄后面的符号c。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用由以上分析我们很容易理解，在由

17、以上分析我们很容易理解，在LR分析过分析过程中，实际上是把程中，实际上是把的前缀列出放在符号的前缀列出放在符号栈中，一旦在栈中出现栈中，一旦在栈中出现（可归前缀），（可归前缀），即句柄已经形成，则用产生式即句柄已经形成，则用产生式A进行归进行归约。（约。（参考参考P125-表表7.2）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.2.2 7.2.2 识别活前缀的有限自动机识别活前缀的有限自动机（略）（略）7.2.3 7.2.3 活前缀及其可归前缀的一般计算方法活前缀及其可归前缀的一般计算方法（略）（略）7.

18、2.4 LR7.2.4 LR（0 0）项目集规范族的构造）项目集规范族的构造 （1）LR（0）项目）项目 在文法在文法G中每个产生式的右部适当位置添中每个产生式的右部适当位置添加一个圆点加一个圆点 构成项目。构成项目。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例如：例如：SaAc对应有对应有4个项目个项目:（右部长度（右部长度3加加1）0S aAc1Sa Ac2SaA c3SaAc 一个产生式可对应的项目数为它的右部符一个产生式可对应的项目数为它的右部符号串长度加号串长度加1 注意：注意：A仅有项目仅有项目

19、A 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用每个项目的含义与圆点的位置有关，概括每个项目的含义与圆点的位置有关，概括地说地说，圆点的左部圆点的左部表示分析过程的某时刻表示分析过程的某时刻用该产生式归约时句柄已识别的部分，用该产生式归约时句柄已识别的部分，圆圆点的右部点的右部表示待识别部分。表示待识别部分。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用项目项目S aAc：希望用希望用S的右部归约，当前输入串中符号应为的右部归

20、约，当前输入串中符号应为a项目项目Sa Ac：已与第一个符号已与第一个符号a匹配，需分析匹配，需分析A的右部的右部项目项目SaA c：A的右部已分析完归约成的右部已分析完归约成A，希望输入串中符号为，希望输入串中符号为c项目项目SaAc：S的右部分析完毕，句柄已形成，可以进行归约的右部分析完毕，句柄已形成，可以进行归约。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用根据圆点所在位置和圆点后是终结符还是非根据圆点所在位置和圆点后是终结符还是非终结符，把项目分为以下几种：终结符，把项目分为以下几种：1.移移进进项项

21、目目：圆圆点点后后为为终终结结符符的的项项目目，对对应应状状态为移进状态。态为移进状态。形如形如A a，aVT 2.2.待约项目待约项目：圆点后为非终结符的项目，如圆点后为非终结符的项目，如A B，BVN。表示所对应的状态等待表示所对应的状态等待着分析完非终结符着分析完非终结符B所能推出的串归约成所能推出的串归约成B，才能继续分析，才能继续分析A的右部。的右部。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.3.归约项目归约项目：圆点在最右部的项目，如：圆点在最右部的项目，如A，表明一个产生式的右部已分析完，

22、句柄已，表明一个产生式的右部已分析完，句柄已形成，可以归约。形成，可以归约。4.4.接受项目接受项目：形如：形如S，S为拓广文法，为拓广文法，S为左部的产生式只有一个，它是特殊的归为左部的产生式只有一个，它是特殊的归约项目，对应状态为接受状态。约项目，对应状态为接受状态。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（3）LR（0）项目集规范族的构造）项目集规范族的构造 n对于构成识别一个文法活前缀的对于构成识别一个文法活前缀的DFA项目集的项目集的全体称为这个文法的全体称为这个文法的LR（0）项目集规范族项目

23、集规范族。n按（按（2）中方法，列出拓广文法的所有项目，）中方法，列出拓广文法的所有项目，构造构造NFA再确定化，这样做确定化的工作量较再确定化，这样做确定化的工作量较大，可以大，可以用闭包函数求用闭包函数求DFA项目集项目集。（2 2）构造识别活前缀的构造识别活前缀的NFA（了解了解）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 定义和构造项目集定义和构造项目集 I的闭包函数的闭包函数 CLOSURE（I）a）I的项目均在的项目均在CLOSURE（I）中）中b）若若A B属属于于CLOSURE（I），则则每

24、每一一形如形如B 的项目也属于的项目也属于CLOSURE（I）c)重复重复b）直到）直到CLOSURE（I）不再扩大为止）不再扩大为止经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 定义转换函数定义转换函数GO（I，X）如下）如下：GO（I，X）=CLOSURE（J）其中：其中：I为包含某一项目的状态，为包含某一项目的状态，XVN VTJ=任何形如任何形如AX 的项目的项目|A X属于属于I经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服

25、务的费用圆圆点点不不在在产产生生式式右右部部最最左左边边的的项项目目称称为为核核（拓广文法（拓广文法S S除外）除外）GO（I，X）转换函数得到的）转换函数得到的J为转向后状态为转向后状态所含项目集的核。所含项目集的核。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用使用使用CLOSURE和和GO（I，X）构造文法）构造文法G的的LR（0）项目集规范族）项目集规范族：a）置置项项目目S S为为初初态态集集的的核核，求求CLOSURE（S S）得到初态的项目集）得到初态的项目集b）对初态集或其它的项目集应用转换函数

26、）对初态集或其它的项目集应用转换函数GO（I，X）=CLOSURE（J）求求出出新新状状态态J的项目集。的项目集。c)c)重复重复b）直到不出现新的项目集为止。直到不出现新的项目集为止。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例如：例如：GS：SSSaAcAAbbAb经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用cAbbbaSI7I6I5I4I3I1I2I0S SS aAcSS Sa AcA AbbA bAb SaA cA

27、A bbAAb bSaAc AAbb 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR（0）项目集规范族的项目分为四种：）项目集规范族的项目分为四种：移进项目、归约项目、待约项目和接受项移进项目、归约项目、待约项目和接受项目。目。一个项目集中可能包含以上四种不同的一个项目集中可能包含以上四种不同的项目，但是一个项目集中不能有下列情项目，但是一个项目集中不能有下列情况存在：况存在：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用a

28、)移进项目和归约项目同时存在移进项目和归约项目同时存在形如形如称称移进移进归约冲突归约冲突。A aB b)归归约约和和归归约约项项目目同同时时存存在在形如形如 称称归约归约归约冲突归约冲突。A B 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR（0）文法：）文法：一个文法的一个文法的LR（0）项目）项目集规范族不存在移进集规范族不存在移进归约或归约归约或归约归约归约冲突时，这个文法为冲突时，这个文法为LR（0）文法。）文法。(4)LR（0）分析表的构造）分析表的构造 是是LR（0）分析器的重要组成部分，是总

29、控）分析器的重要组成部分，是总控程序分析动作的依据。程序分析动作的依据。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR（0）分析表可用一个二维数组表示，行）分析表可用一个二维数组表示，行标为状态号，列标为文法符号和标为状态号，列标为文法符号和#。分析表。分析表由两部分组成：由两部分组成：动作表动作表ACTION：表示当前状态下面临输入符表示当前状态下面临输入符应做的动作。应做的动作。转换表转换表GOTO：表示当前状态下面临文法符号：表示当前状态下面临文法符号应转向的下一个状态。应转向的下一个状态。经营者提供

30、商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用构造一个文法的构造一个文法的LR（0）分析表，首先构造）分析表，首先构造其识别活前缀的自动机其识别活前缀的自动机DFA，利用，利用DFA的项的项目集和状态转换函数构造它的目集和状态转换函数构造它的LR（0）分析）分析表。表。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用LR（0）分析表的构造算法如下：）分析表的构造算法如下：假设已构造出假设已构造出LR（0）项目集规范族如下：）项目集规范族如下

31、：C=I0，I1，In，其中，其中Ik为项目集的名字，为项目集的名字，k为为状态名，令包含状态名，令包含S S项目的集合项目的集合Ik的下标为的下标为分析器的初始状态，那么分析表的分析器的初始状态，那么分析表的ACTION表表和和GOTO表构造步骤为：表构造步骤为：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用a)a)若项目若项目A a属于属于Ik且转换函数且转换函数GO（Ik，a）=Ij，当，当aVT时，则置时，则置ACTIONk，a为为Sj，其动作含义为将，其动作含义为将a移进符移进符号栈，号栈，j进入状态

32、栈。进入状态栈。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用b)b)若项目若项目A 属于属于Ik，则对，则对任意任意aVT和和#，置，置ACTIONk，a和和ACTIONk，#为为rj。j为为A产生式序号。产生式序号。rj动作的含义是把当动作的含义是把当前文法符号栈顶的符号串前文法符号栈顶的符号串归约为归约为A，栈顶，栈顶指针向下移动指针向下移动|的长度，非终结符的长度，非终结符A变为当变为当前面临的符号。前面临的符号。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金

33、额为消费者购买商品的价款或接受服务的费用c)c)若若GO（Ik，A）=Ij，则置，则置GOTOk，A为为j，其中，其中AVN，表示当前状态为，表示当前状态为k时，时，遇文法符号遇文法符号A时应转向时应转向j，因此，因此A移入文法移入文法符号栈，符号栈，j移入状态栈。移入状态栈。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用d)d)若项目若项目SS 属于属于Ik，则置，则置ACTIONk，#为为acc，表示接受，表示接受e)e)凡不能用上述方法填入的分析表的元素，均凡不能用上述方法填入的分析表的元素，均应填上应填

34、上“报错标志报错标志”。为清晰起见，表中用。为清晰起见，表中用空白表示出错。空白表示出错。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例：例：SvI:T1拓广文法拓广文法SS0II,i2Ii3Tr4构造构造LR（0）分析表）分析表先构造识别活前缀的先构造识别活前缀的DFA（即（即LR（0）项目集规范族）项目集规范族）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用IITi,I:riSI7I6I5I3II I2 2I I0 0S

35、SS vI:TSS Sv I:TI I,iI iIi SvI:TII,iSvI:TT rII,iTr II,i SvI:T I I1 1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用然后构造然后构造LR（0）分析表）分析表，如下所示：，如下所示：状态状态ACTIONGOTOvi，：r#SIT0S211acc2S433S6S54r3r3r3r3r3r35S986S77r2r2r2r2r2r28r1r1r1r1r1r19r4r4r4r4r4r4经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的

36、损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用练习练习：构造下列文法的构造下列文法的LR（0）分析表）分析表SaAcAbB|baBdB|e 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(5)LR（0）分析器的工作过程）分析器的工作过程1)1)若若ACTIONS，a=Sj，aVT，则，则 a移入符移入符号栈，号栈，j移入状态栈。移入状态栈。2)2)若若ACTIONS，a=rj，aVT或或#，则用第，则用第 j个产生式归约，并将两个栈的指针减去个产生式归约，并将两个栈的指针减去 k，其中其中k为第为第

37、 j个产生式右部的符号串的长度，个产生式右部的符号串的长度，这时当前面临符号为第这时当前面临符号为第 j个产生式左部的非个产生式左部的非终结符。终结符。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3)3)若若ACTIONS，a=acc，a=#，则为接受，则为接受，表示分析成功。表示分析成功。4)4)若若GOTOS，A=j，AVN，表明前一动作，表明前一动作是用关于是用关于A的产生式归约，当前面临非终结的产生式归约，当前面临非终结符符A应移入符号栈，应移入符号栈，j移入状态栈。移入状态栈。5)5)若若ACTIO

38、NS，a=空白，则转向出错处理空白，则转向出错处理经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用对于前例文法，句子对于前例文法，句子vi，i：r的的LR（0）分析）分析过程。过程。步骤步骤状态栈状态栈符号栈符号栈输入串输入串ACTIONGOTO 10#vi，i：r#S2 202#vi，i：r#S4 3024#vi，i：r#r33 4023#vI，i：r#S6 50236#vI，i：r#S7 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服

39、务的费用602367#vI，i：r#r23 7023#vI：r#S5 80235#vI：r#S9 902359#vI：r#r481002358#vI：T#r111101#S#acc 步骤步骤状态栈状态栈符号栈符号栈输入串输入串ACTIONGOTO 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用练习练习：SaAcAbB|baBdB|e句子句子 abdec#的的LR（0）分析过程。）分析过程。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务

40、的费用7 73 SLR3 SLR（1 1）分析）分析 大多数实用的程序设计语言的文法不能满大多数实用的程序设计语言的文法不能满足足LR（0）文法的条件，本节将介绍对于）文法的条件，本节将介绍对于LR（0）规范族中有冲突的项目集用）规范族中有冲突的项目集用向前查看向前查看一个符号一个符号的办法进行处理，以解决冲突。的办法进行处理，以解决冲突。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用简单简单的的LR（1）分析法，用）分析法，用SLR（1）表示：对冲突的状态向前查看一个符表示：对冲突的状态向前查看一个符号，确定

41、动作（是移进还是归约，按号，确定动作（是移进还是归约，按哪一个产生式归约）哪一个产生式归约）经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用假定文法假定文法G的一个项目集的一个项目集 I含有含有m个移进项目：个移进项目：A A1 11a a11A A2 22 a a22 A Amm a amm和n个归约项目个归约项目：B11 Bnn 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用如果集合如果集合a1，a2，am和集合和集合FOLL

42、OW（B1）FOLLOW（Bn）两两不相交两两不相交，则项目集，则项目集I中的冲突可按以下原则中的冲突可按以下原则解决，设解决，设a是下一输入符号是下一输入符号1）若若aa1，a2，am，则移进，则移进a2）若若aFOLLOW（Bi），i=1，2n；则则用用Bii 归约。归约。3)3)此外，报错。此外，报错。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用SLRSLR（1 1）文法：）文法：如果一个文法的如果一个文法的LRLR（0 0）项目表中所含冲突都能用上述方法解决，项目表中所含冲突都能用上述方法解决，则这个

43、文法是则这个文法是SLRSLR（1 1）文法，所构造的）文法，所构造的分析表为分析表为SLRSLR（1 1）分析表，使用）分析表，使用SLRSLR（1 1）分析表的分析器称为）分析表的分析器称为SLRSLR（1 1）分析器分析器经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用SLRSLR（1 1）分析表的构造方法）分析表的构造方法（改进改进）：基基本本和和LR（0）分分析析表表的的构构造造算算法法相相同同，只只需需将将b）改为：）改为：若若A 属于属于I IK，则，则任何任何aFOLLOW（A）或）或“#”，置，

44、置ACTIONk，a=rj，j为产生式为产生式A在文法在文法GG中的文法编号。中的文法编号。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例如：拓广文法例如：拓广文法GSS0SrD1DD，i2 D i 3 D i 3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1)1)其识别活前缀的其识别活前缀的DFA为：为：，DiirSI6I5I4I3I1I2I0SSSrDSSSrDDD,iDiDiSrD DD,iDD,iDD,i经营者提供商

45、品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用在在I3中存在移进中存在移进归约冲突：归约冲突：移进项目移进项目DD,i，归约项目归约项目SrD 求各非终结符的求各非终结符的FOLLOW集集FOLLOW（S）=#FOLLOW（S）=#FOLLOW（D）=，#因为因为FOLLOW（S）=#，=所以所以 可以用可以用SLRSLR（1 1）方法解决。）方法解决。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2)2)构造改进的构造改进的SLRSLR（

46、1 1）分析表）分析表 状态状态ACTIONGOTOr，i#SD0S211acc2S433S5r14r3r35S66r2r2经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3)3)句子句子riri，i i的的SLRSLR（1 1）分析过程）分析过程步骤步骤状态栈状态栈符号栈符号栈输入串输入串ACTIONGOTO10#ri，i#S2202#ri，i#S43024#ri，i#r334023#rD，i#S550235#rD，i#S6602356#rD，i#r237023#rD#r118 08 01 1#S#acc#S#

47、acc 经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.4 LR7.4 LR（1 1）分析）分析SLRSLR（1 1）方法虽然相对）方法虽然相对LRLR（0 0）有所改进，）有所改进，但仍然存在着多余归约，说明但仍然存在着多余归约，说明SLRSLR（1 1）方）方法向前查看一个符号的方法不够确切，法向前查看一个符号的方法不够确切，LRLR（1 1）方法恰好是要解决）方法恰好是要解决SLRSLR（1 1）方法在）方法在某些情况下存在的无效归约问题。某些情况下存在的无效归约问题。经营者提供商品或者服务有欺诈行为的

48、，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.4.1 LR7.4.1 LR（1 1）项目集族的构造）项目集族的构造 S S，#属于初始项目集，属于初始项目集，#为为向前向前搜索符搜索符。针对初始项目。针对初始项目S S，#，求闭包，求闭包后再用转换函数逐步求出整个文法的后再用转换函数逐步求出整个文法的LR（1）项目集族，具体构造步骤如下：）项目集族，具体构造步骤如下：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（1）构造构造LR（1）项目集的闭包函数）项目

49、集的闭包函数a）I的任何项目都属于的任何项目都属于CLOSURE（I）b）若若有有项项目目A B，aCLOSURE（I），B是产生式，是产生式，V*，bFIRST（a），则则 B，b也也 属属 于于CLOSURE（I）c)重复重复b），直到），直到CLOSURE（I）不再增大为止。）不再增大为止。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用（2）转换函数的构造）转换函数的构造 LR（1）转换函数的构造与）转换函数的构造与LR（0）的相似，）的相似，GO（I，X）=CLOSURE（J）其中其中I是是LR（1）的

50、项目集，）的项目集，X是文法符号。是文法符号。J=任何形如任何形如AX，a的项目的项目|A X，aI经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例如：例如：SS0SaAd1SbAc2Saec3Sbed4Ae5构造它的构造它的LR（1）项目集规范族：）项目集规范族：经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用I0：SS，#I1：SS，#I3：SbAc，#SaAd，#I2：SaAd，#Sbed，#SbAc，#Saec，#Ae，c