第七章_LR分析(编译原理)

1、1盛威网：专业的计算机学习网站指导教师指导教师:杨建国杨建国二零零七年十一月二零零七年十一月2盛威网：专业的计算机学习网站1.1.重点掌握：重点掌握：LRLR分析方法与分析过程，分析方法与分析过程，LR(0)LR(0)项目、项目、项目集规范族及其构造、项目集规范族及其构造、LR(0)LR(0)文法及文法及LR(0)LR(0)分析分析表的构造、表的构造、SLRSLR（1 1）分析）分析2.2.理解：活前缀，可归前缀理解：活前缀，可归前缀3.3.了解：了解：LR(1)LR(1)、LALR(1)LALR(1)分析思想分析思想学习目标学习目标第7章LR分析3盛威网：专业的计算机学习网站v第一节第一节

2、LRLR分析概述分析概述v第二节第二节 LRLR（0 0）分析）分析v第三节第三节 SLRSLR（1 1）分析）分析v第八节第八节 典型例题及解答典型例题及解答教学内容教学内容v第四节第四节 LRLR（1 1）分析）分析v第五节第五节 LALRLALR（1 1）分析）分析v第六节第六节 二义性文法在二义性文法在LRLR分析中的应用分析中的应用v第七节第七节 语法分析程序的自动构造工具语法分析程序的自动构造工具YACCYACC4盛威网：专业的计算机学习网站知识结构知识结构5盛威网：专业的计算机学习网站7.1LR分析概述 根据当前分析栈中的符号串（通常以状态表示）根据当前分析栈中的符号串（通常以状

3、态表示）和向右顺序查看输入串的和向右顺序查看输入串的K K个（个（K=0K=0）符号就可唯一）符号就可唯一地确定句柄。地确定句柄。6盛威网：专业的计算机学习网站 L表示从左到右扫描输入串 R表示最左规约（即最右推导的逆过程） K表示向右查看输入串符号的个数 当K=1时，能满足当前绝大多数高级语言编译程序的需要。【注】【注】一般地说，大多数用无二义性上下文无关文法一般地说，大多数用无二义性上下文无关文法描述的程序设计语言均可用描述的程序设计语言均可用LRLR分析器分析器予以识别。予以识别。 1.LR1.LR（K K）的含义）的含义7盛威网：专业的计算机学习网站http:/www-cs-facul

4、/knuth/计算机程序设计艺术计算机程序设计艺术 第第1卷卷 基本算法基本算法 计算机程序设计艺术计算机程序设计艺术 第第2卷卷 半数值算法半数值算法计算机程序设计艺术计算机程序设计艺术 第第3卷卷 排序与查找排序与查找 LR(k) LR(k)分析技术分析技术KnuthKnuth于于19651965年首先提出年首先提出8盛威网：专业的计算机学习网站2.LR2.LR分析的特点分析的特点q适用范围广适用范围广，适用于多数无二义性的，适用于多数无二义性的上下文无关文法上下文无关文法q分析分析效率高效率高，报错及时报错及时q可以可以自动生成自动生成q手工实现手工实现工作

5、量大，必须使用自动生成工作量大，必须使用自动生成器器优点优点缺点缺点9盛威网：专业的计算机学习网站SLR(1)分析表(简单LR分析表) LR(0)分析表 构造简单构造简单, ,最易实现最易实现, ,大多数上下文无关文法都大多数上下文无关文法都可以构造出可以构造出SLRSLR分析表分析表, ,所以具有较高的实用价值。所以具有较高的实用价值。使用使用SLRSLR分析表进行语法分析的分析器叫分析表进行语法分析的分析器叫SLRSLR分析器。分析器。 对文法的限制较大，无实用价值，是构造其它对文法的限制较大，无实用价值，是构造其它LRLR分析表的基础分析表的基础（重点掌握）（重点掌握）（重点掌握）（重点

6、掌握）10盛威网：专业的计算机学习网站LR(1)LR(1)分析表分析表( (规范规范LRLR分析表分析表) ) 适用文法类最大适用文法类最大, ,几乎所有上下文无关文几乎所有上下文无关文法都能构造出法都能构造出LR(1)LR(1)分析表分析表, ,但其分析表体积太但其分析表体积太大，实用价值不大。大，实用价值不大。LALRLALR分析表分析表( (超前超前LRLR分析表分析表) ) 这种表适用的文法类及其实现上难易在这种表适用的文法类及其实现上难易在LR(1)LR(1)和和SLR(1)SLR(1)两种之间两种之间, ,比较实用。使用比较实用。使用LALRLALR分析表分析表进行语法分析的分析器

7、叫进行语法分析的分析器叫LALRLALR分析器。分析器。说明：四种分析表对应四类文法说明：四种分析表对应四类文法（了解）（了解）（了解）（了解）11盛威网：专业的计算机学习网站v四种四种LRLR类型：类型：LR(0)LR(0)、SLR(1)SLR(1)、LALR(1)LALR(1)、LR(1)LR(1)功能逐个增强功能逐个增强四种四种LRLR类型的文法是真包含关系类型的文法是真包含关系一个文法是一个文法是LR(0)LR(0)文法一定是文法一定是LR(1)LR(1)文法吗？文法吗？12盛威网：专业的计算机学习网站u回顾回顾 自底向上分析实现的自底向上分析实现的基本思想基本思想“移进归约移进归约”

8、方法方法文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d符号串符号串abbcdeabbcde是否是是否是GSGS的句子的句子7.2LR（0）分析13盛威网：专业的计算机学习网站归约（SaAcBe）#aAcBe10）接受#S11）移进ee#aAcB9）归约（Bd）e#aAcd8）移进dde#aAc7）归约（AAb）cde#aAb5）移进ccde#aA6）移进bbcde#aA4）归约（Ab）bcde#ab3）移进bbbcde#a2）移进aabbcde#1）动作动作输入符号串输入符号串符号栈符号栈步骤步骤对输入串对输入串abbcde#的移进的移进-规约分析过程规约分析

9、过程14盛威网：专业的计算机学习网站p在步骤在步骤3 3中，用中，用AbAb归约归约p在步骤在步骤5 5中，用中，用AAbAAb归约归约p问题：何时移进？何时归约？用哪个产生式问题：何时移进？何时归约？用哪个产生式归约（如何找当前句柄归约）？归约（如何找当前句柄归约）？15盛威网：专业的计算机学习网站 3 3） #a#ab b bcde# bcde# 归约归约( (AbAb) ) 5 5） #aA#aAb b cde# cde# 归约归约( (AAbAAb) ) 4 4） #aA bcde# #aA bcde# 移进移进 6 6） #aA cde# #aA cde# 移进移进分析：已分析过的部

10、分在栈中的分析：已分析过的部分在栈中的前缀前缀不同，而且不同，而且移进和归约后栈中的状态会发生变化移进和归约后栈中的状态会发生变化我们引入一个新的我们引入一个新的状态栈状态栈来表示符号栈中的符号来表示符号栈中的符号目前状态目前状态用用LRLR分析表分析表来表示不同状态下对于各输入符号应来表示不同状态下对于各输入符号应采取的动作采取的动作16盛威网：专业的计算机学习网站问题： 对于一个文法，状态集是如何确定的？LR分析表是如何得到的？答案答案：需要构造识别：需要构造识别可归前缀可归前缀的的有穷自动机有穷自动机 LRLR方法也是通过求方法也是通过求句柄句柄逐步归约进行语法分析。逐步归约进行语法分析

11、。 句柄句柄在简单优先分析法中是通过符号的优先关在简单优先分析法中是通过符号的优先关系而求得的；在系而求得的；在LRLR方法中，则是通过求方法中，则是通过求可归前缀可归前缀而而求得的。求得的。17盛威网：专业的计算机学习网站7.2.1 7.2.1 可归前缀和活前缀可归前缀和活前缀字的前缀是指该字的任意首部。 例如：字ABC的前缀有,A,AB,ABC。 如果Z=xy是一符号串，则x是Z的前缀，其中x,y为任意符号串（包括空串） 规范句型中句柄之前包括句柄在内的串称为可归前缀。 指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。 18盛威网：专业的计算机学习网站例例2.2.根据下面的文法识别输

12、入串abbcde。 1) SaAcBe 2) Ab 3) AAb 4) Bd 为每条产生式的尾部加上用i表示的产生式序号1)SaAcBe1 2)Ab2 3)AAb3 4)Bd419盛威网：专业的计算机学习网站用最右推导方式来识别,推导时把序号也带上。 SaAcBeaAcBe1aAcdaAcd4e1aAbaAb3cd4e1 abab2b3cd4e1若用最左归约的方式进行识别，则完全是上面的逆过程。 p规范句型abbcde的前缀有：，a,ab p规范句型aAbcde的前缀有：，a,aA,aAb p规范句型aAcde的前缀有： ，a,aA,aAc,aAcdp规范句型aAcBe的前缀有： ，a,aA,

13、aAc,aAcB,aAcBe20盛威网：专业的计算机学习网站u由例子我们得知：将栈内符号与未扫描的输入串拼接起来,可得一规范句型规范句型.即栈内符号串总是规范句型规范句型的前缀的前缀,且不含句柄右侧的符号不含句柄右侧的符号。:句柄一旦在栈顶形成,就不再移进新符号,而是要进行归约了.有两个要点: (1)它是规范句型的前缀它是规范句型的前缀 (2)它不含句柄右侧符号它不含句柄右侧符号21盛威网：专业的计算机学习网站【注】【注】在活前缀之后增添一些终结符号后，就可以使之成为规范句型。形式定义形式定义，则称为活前缀活前缀。*,tSV 即：对于文法G，若 活前缀就是当前规范句型中从第一个字符到句柄句柄最

14、后一个符号所形成的子串的前缀，若该子串的长度为n，活前缀就有n+1个。在这n+1个活前缀中，包含完整句柄的活前缀就是可归前缀可归前缀。 22盛威网：专业的计算机学习网站 可归前缀和活前缀在可归前缀和活前缀在LRLR分析中的作用分析中的作用 在LR分析过程中，实际上是把活前缀活前缀列出放在符号栈中，一旦在栈中出现可归前缀可归前缀，即句柄句柄已经形成，就用相应的产生式进行归约。 在分析的过程中，只要符号栈中的符号串是一个活前缀活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。 23盛威网：专业的计算机学习网站7.2.2 7.2.2 识别活前缀的有限自动机识别活前缀的有限自动机 0X131

15、0 4 Y1 5 1识别识别1(0|1)1(0|1)* *101101的的NFANFAn有限自动机有限自动机 一种识别装置一种识别装置分分DFADFA和和NFANFA如何确定规范如何确定规范句型的活前缀句型的活前缀 24盛威网：专业的计算机学习网站p用有限自动机来识别活前缀活前缀和可归前缀可归前缀p有限自动机如何构造？一个特例：已经有了可归约前缀如何构造识别活前缀和可归前缀的有限自动机由文法的产生式构造识别活前缀和可归前缀的有限自动机的方法25盛威网：专业的计算机学习网站有穷自动机的有穷自动机的输入字符输入字符：终结符和非终结符终结符和非终结符状态转换状态转换：每次让一个：每次让一个符号进栈符

16、号进栈，就看成识别过，就看成识别过了该符号，同时状态进行转换。了该符号，同时状态进行转换。当识别到当识别到可归前可归前缀缀（栈中形成句柄）时，认为达到了识别句柄的（栈中形成句柄）时，认为达到了识别句柄的终态。终态。因为因为LRLR分析时栈中始终保持是活前缀，所分析时栈中始终保持是活前缀，所以有限自动机识别过的符号串也是活前缀。以有限自动机识别过的符号串也是活前缀。终态终态：当识别到：当识别到可归约前缀可归约前缀（表明在栈中形成句（表明在栈中形成句柄），认为到达了识别句柄的终态，执行柄），认为到达了识别句柄的终态，执行归约归约。26盛威网：专业的计算机学习网站 拓广文法 在原文法在原文法G G中

17、增加产生式中增加产生式SSSS，S S为原文法为原文法G G的开始符号，所得的新文法称为的开始符号，所得的新文法称为G G的的拓广文法拓广文法，以，以GG表示，表示，SS为拓广后文法为拓广后文法GG的开始符号。的开始符号。目的目的 有时候文法中某些产生式右部含有开始符号，有时候文法中某些产生式右部含有开始符号，在归约过程中为了能分清是否已归约到文法的最初在归约过程中为了能分清是否已归约到文法的最初开始符，我们增加了一个新的开始符号开始符，我们增加了一个新的开始符号SS，使它，使它只在产生式左部，这样确保了不会混淆。只在产生式左部，这样确保了不会混淆。27盛威网：专业的计算机学习网站n构造识别活

18、前缀和可归约前缀的有限自动机的一个例子：特例：由句子规范推导的逆过程直观地看出它的活前缀和可归前缀按活前缀和可归前缀构造识别它们的有限自动机v定义定义7.17.1若若SS aAwaAw a aw w（w w只含终结符只含终结符）是文法是文法G G的拓广文法的拓广文法GG中的一个规范推导，符号串中的一个规范推导，符号串是是aa的前缀，则称的前缀，则称是是G G的一个的一个活前缀活前缀。也就是说。也就是说是规范句型是规范句型a aww的前缀，但它的右端不超过该句型句的前缀，但它的右端不超过该句型句柄的末端。柄的末端。RR* *28盛威网：专业的计算机学习网站例例3.3.根据下面的文法识别输入串根据

19、下面的文法识别输入串abbcdeabbcde。 1) S1) SaAcBe aAcBe 2) A 2) Ab b 3) A 3) AAb Ab 4) B 4) Bd d 文法文法GSGS：0 0）S S0S S01 1）S aAcBe1S aAcBe12 2）A b2A b23 3）A Ab3A Ab34 4）B d4B d4第一步：拓广文法第一步：拓广文法第二步：列出给定句子可归前缀第二步：列出给定句子可归前缀输入串输入串abbcde abbcde 的最右推导过程：的最右推导过程：SS=S S0=0=aAcaAcB Be e1 =a1 =aA Ac cd d4e14e1=a=aA Ab b3

20、cd4e1= a3cd4e1= ab b2b3cd4e12b3cd4e1S0 S0 ab2ab2aAb3aAb3aAcd4aAcd4aAcBe1aAcBe129盛威网：专业的计算机学习网站第三步：构造识别其活前缀及可归前缀的有限自动机第三步：构造识别其活前缀及可归前缀的有限自动机104387131210182591461715161110SabaAbaAcdaAcBe*1句子识别态i句柄识别态所有的状态都是活前缀的识别状态所有的状态都是活前缀的识别状态终态是句柄的识别态终态是句柄的识别态带带“* *”号的状态既是句柄识别态又是句子识别号的状态既是句柄识别态又是句子识别态，句子识别态仅有一个态，

21、句子识别态仅有一个30盛威网：专业的计算机学习网站第四步：构造第四步：构造识别活前缀的识别活前缀的NFANFA104387131210182591461715161110SabaAbaAcdaAcBeX *31盛威网：专业的计算机学习网站第五步：把第五步：把NFA确定化，重新编号确定化，重新编号X246879531AbaSbcBed*识别活前缀和可归前缀的识别活前缀和可归前缀的DFADFA32盛威网：专业的计算机学习网站X2a1*SA45b3b6c7dB89e理解识别活前缀和可归前缀的理解识别活前缀和可归前缀的DFADFA和分析过程的对应和分析过程的对应符号栈符号栈输入串输入串动作动作# #a

22、bbcde#abbcde#移进移进a a#a#abbcde#bbcde#移进移进b b#ab#abbcde#bcde#归约归约(A-b)(A-b)#aA#aAbcde#bcde#移进移进b b#aAb#aAbcde#cde#归约归约(A-Ab)(A-Ab)#aA#aAcde#cde#移进移进c c#aAc#aAcde#de#移进移进d d#aAcd#aAcde#e#归约归约(B-d)(B-d)#aAcB#aAcBe#e#移进移进e e#aAcBe#aAcBe# #归约归约(S-aAcBe)(S-aAcBe)#S#S# #接受接受33盛威网：专业的计算机学习网站ACTIONGOTOacebd#S

23、ABXS211acc2S343r2r2r2r2r2r24S6S55r3r3r3r3r3r36S787r4r4r4r4r4r48S99r1r1r1r1r1r1 对任何一个上下文无关文法只要构造出它的识别对任何一个上下文无关文法只要构造出它的识别活前缀和可归前缀的有穷自动机，就可以构造其相应的活前缀和可归前缀的有穷自动机，就可以构造其相应的分析表（分析表（ACTIONACTION表表和和GOTOGOTO表），进行表），进行LRLR分析分析X2a1*SA45b3b6c7dB89eS0S0，ab2ab2，aAb3aAb3，aAcd4aAcd4，aAcBe1aAcBe134盛威网：专业的计算机学习网站

24、以上示例中构造DFA的方法是通过一个句子的归约过程确定可归前缀，但是：对于一个复杂的文法，其可归前缀不是如此简单就能计算出来示例中用一个句子归约过程的所有活前缀和可归前缀构造出的DFA，恰好也是识别整个文法的活前缀和可归前缀的DFA，这仅是一个特殊情况特殊情况。对一个上下文无关文法需要求出它的所有活前缀和可归前缀后才能构造其识别该文法活前缀的DFA35盛威网：专业的计算机学习网站7.2.3 7.2.3 活前缀及其可归前缀的一般计算方法活前缀及其可归前缀的一般计算方法v定义定义7.27.2（非终结符的左文）（非终结符的左文）p对一个任意的上下文无关文法需用确定的办法来求出它的所有活前缀和可归前缀

25、才能构造其识别该文法活前缀的有限自动机。LC（A）= | S A, V*, V t*36盛威网：专业的计算机学习网站推论：推论：若文法若文法G G中有产生式中有产生式B BA A 则有：则有： LC(A)LC(A) LC(B)LC(B) 【证明】【证明】因为对任一形为因为对任一形为 B B 的句型必有规范推导的句型必有规范推导： SSB B A A即对任一个即对任一个 LC(B)LC(B)定有定有LC(A)LC(A)，所以，所以 LC(A)LC(A) LC(B)LC(B) *RR37盛威网：专业的计算机学习网站求求LCLC（A A）的方法）的方法 首先寻找文法中A在右部的产生式，假设该产生式左

26、部为Q，则 LC（A）=LC（Q）产生式右部A之前的符号串例例4.4.文法文法GSGS：SS0SS0SaAcBe1SaAcBe1Ab2Ab2AAb3AAb3Bd4Bd4由前面的定义与推论我们知：LC(S)= LC(S)=LC(S) = LC(A)=LC(S)aLC(A) =a LC(B)=LC(S)aAc=aAc38盛威网：专业的计算机学习网站LC(S)= LC(S)= LC(A)=a LC(B)=aAc化简用正规式表示： 这样我们求出了每个这样我们求出了每个非终非终结符结符在规范推导中用该非终结在规范推导中用该非终结符的右部替换该非终结符之前，符的右部替换该非终结符之前，它的左部可能出现的它

27、的左部可能出现的所有前缀所有前缀，也就是在规范归约过程中用句也就是在规范归约过程中用句柄归约成该非终结符之前柄归约成该非终结符之前不包不包括句柄的活前缀括句柄的活前缀。输入串输入串abbcdeabbcde的最右推导过程：的最右推导过程：SS=S S=aAcaAcB Be e=a=aA Ac cd de=ae=aA Ab bcde=acde=ab bbcdebcde解释：在上面的推导过程中，非终结符B依据产生式Bd被替换为d之前，它的左部是aAc，这个就是活前缀。或者说我们把从右看，把d归约成B之前不包含d这个句柄的活前缀是aAc。39盛威网：专业的计算机学习网站不包括句柄的活前缀不包括句柄的活

28、前缀+ +句柄句柄= =？ 可归前缀可归前缀令令 LR(0)C(ALR(0)C(A )= )= LC(A)LC(A) 文法文法GG的可归前缀有：的可归前缀有：LR(0)C(SLR(0)C(SS)=LC(S)S)=LC(S)S=SS=SLR(0)C(SLR(0)C(SaAcBe)=LC(S)aAcBe)=LC(S)aAcBe=aAcBaAcBe=aAcBe eLR(0)C(ALR(0)C(Ab)=LC(A)b)=LC(A)b=abb=abLR(0)C(ALR(0)C(AAb)=LC(A)Ab)=LC(A)Ab=aAb Ab=aAb LR(0)C(BLR(0)C(Bd)= LC(B)d)= LC(

29、B)d=aAcdd=aAcd对对LRLR方法，规定方法，规定LR(0)CONTEXTLR(0)CONTEXT(A(A)=LC(A)=LC(A) LR(0)CONTEXTLR(0)CONTEXT(A(A) )可简写为可简写为R(0)C(AR(0)C(A) )40盛威网：专业的计算机学习网站总结：如何构造识别文法活前缀的有限自动机？总结：如何构造识别文法活前缀的有限自动机？ 1 1、根据文法算出其可归前缀、根据文法算出其可归前缀(1)(1)求出非终结符的左文求出非终结符的左文(2)(2)求出产生式的左文，就可求出可归前缀求出产生式的左文，就可求出可归前缀2 2、根据可归前缀，构造识别文法活前缀的不

30、确定有限自动机、根据可归前缀，构造识别文法活前缀的不确定有限自动机3 3、确定化，从而构造出识别文法活前缀的确定的有限自动机、确定化，从而构造出识别文法活前缀的确定的有限自动机4. 4. 化简上面的确定有限自动机，合并其中的活前缀化简上面的确定有限自动机，合并其中的活前缀41盛威网：专业的计算机学习网站例例4.4.如文法如文法GG为：为：(0)S(0)SE E(1)E (1)E aA aA (2)E (2)E bBbB(3)A (3)A cAcA(4)A (4)A d d(5)B (5)B cBcB(6)B (6)B d d第一步：求非终结符的左文第一步：求非终结符的左文LC(S)=LC(S)

31、=LC(E)=LC(S)=LC(E)=LC(S)=LC(A)=LC(E)aLC(A)=LC(E)aLC(A)cLC(A)cacac* *LC(B)=LC(E)bLC(B)=LC(E)bLC(B)cLC(B)cbcbc* *第二步：求产生式的左文第二步：求产生式的左文LC(0)CLC(0)C（SESE）=E=ELC(0)CLC(0)C（EaAEaA）=aA=aALC(0)CLC(0)C（EbBEbB）=bB=bBLC(0)CLC(0)C（AcAAcA）=ac=ac* *cAcALC(0)CLC(0)C（AdAd）=ac=ac* *d dLC(0)CLC(0)C（BcBBcB）=bc=bc* *c

32、BcBLC(0)CLC(0)C（BdBd）=bc=bc* *d d42盛威网：专业的计算机学习网站第三步：构造识别文法活前缀的第三步：构造识别文法活前缀的NFA43盛威网：专业的计算机学习网站第三步：构造识别文法活前缀的第三步：构造识别文法活前缀的DFA并简化并简化44盛威网：专业的计算机学习网站p对任何一个上下文无关文法只要能够构造出它的识别可归前缀的有限自动机，就可以构造其相应的分析表分析表。p用这种方法构造识别可归前缀的有限自动机 从理论的角度从理论的角度讲是比较严格的，但实现起来却很复杂。是否存在一种比较实用的方法？是否存在一种比较实用的方法？存在存在45盛威网：专业的计算机学习网站7

33、.2.4 LR(0)7.2.4 LR(0)项目集规范族的构造项目集规范族的构造活前缀与句柄的关系活前缀与句柄的关系A A 的右部的右部 已出现在栈顶，可以已出现在栈顶，可以归约归约活前缀已含有句柄的活前缀已含有句柄的全部全部符号符号活前缀只含有句柄的活前缀只含有句柄的部分部分符号符号活前缀活前缀不含有不含有句柄的任何符号句柄的任何符号AA 1 1 2 2的右部子串的右部子串 1 1已出现在栈顶，正期已出现在栈顶，正期待从剩余输入串中能看到由待从剩余输入串中能看到由 2 2推出的符号串推出的符号串期望从剩余输入串中能看到由某产生式期望从剩余输入串中能看到由某产生式AA 的右部的右部 所推出的符号

34、串所推出的符号串 A A 1 1 2 2 A 为刻划产生式右部符号已有多大一部为刻划产生式右部符号已有多大一部分被识别，用项目来指示位置分被识别，用项目来指示位置46盛威网：专业的计算机学习网站1.1.项目的定义项目的定义 在文法的每个产生式右部添加一个圆点，就成为G的一个LR(0)项目（简称项目）。 n注：圆点在产生式中的位置不同则是不同项目。 例如：产生式SaAcBe对应有6个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 47盛威网：专业的计算机学习网站说明p产生式右部符号串的长度为n，则可以分解为n+

35、1个项目p产生式AA只有一个项目只有一个项目AA 48盛威网：专业的计算机学习网站2.2.项目的含义项目的含义如：产生式如：产生式UXYZUXYZ对应有对应有4 4个项目个项目 0 UXYZ0 UXYZ 1 UXYZ 1 UXYZ 2 UXYZ 2 UXYZ 3 UXYZ 3 UXYZ UXYZ 预期要归约的句柄是XYZ，但都未进栈UXYZ 预期要归约的句柄是XYZ，仅X进栈UXYZ 预期要归约的句柄是XYZ，仅XY进栈UXYZ XYZ全部进栈，XYZ可进行归约49盛威网：专业的计算机学习网站项目的直观意义项目的直观意义: : 在分析过程中的某一时刻已经归约的部分和在分析过程中的某一时刻已经归

36、约的部分和等待归约部分，圆点是栈内外的分界线。等待归约部分，圆点是栈内外的分界线。项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分句柄已识别的部分，圆点右部表示待待识别的部分识别的部分。50盛威网：专业的计算机学习网站3.3.项目的分类项目的分类 由于不同的LR(0)项目反映了在分析过程中栈顶的不同情况，因此，我们可以根据圆点位置和圆点后是终结符还是非终结符或为空，将一个文法的全部LR(0)项目进行分类。 移进项目移进项目 待约项目待约项目 归约项目归约项目 接受项目接受项目 51盛威网：专业的计算机学习网站圆点后面是圆点后面是终结符终结符的项目，表示栈内是句柄的一部的项目

37、，表示栈内是句柄的一部分，期待从输入串中移进一个符号，以形成句柄。分，期待从输入串中移进一个符号，以形成句柄。（1 1）移进项目：）移进项目：AaAa（2 2）待约项目：）待约项目：ABAB圆点后面是圆点后面是非终结符非终结符的项目，表示栈内是句柄的的项目，表示栈内是句柄的一部分，为了形成句柄，期待从剩余的输入串中一部分，为了形成句柄，期待从剩余的输入串中进行归约而得到，然后才能继续分析进行归约而得到，然后才能继续分析A A的右部。的右部。52盛威网：专业的计算机学习网站圆点在最右端圆点在最右端的项目，表示栈顶的部分内容已构成的项目，表示栈顶的部分内容已构成所期望的句柄，应使用产生式所期望的句

38、柄，应使用产生式AA进行归约。进行归约。（3 3）归约项目：）归约项目：AA （4 4）接受项目：）接受项目：SS特殊的归约项目特殊的归约项目，它是对文法开始符号的归约，它是对文法开始符号的归约项目，使用产生式项目，使用产生式SS进行归约，这时，输进行归约，这时，输入串归约为文法的开始符号，表示整个句子已入串归约为文法的开始符号，表示整个句子已经分析完毕，分析成功，也即输入串为该文法经分析完毕，分析成功，也即输入串为该文法的句子。的句子。规定规定AA53盛威网：专业的计算机学习网站开始项目开始项目形如形如SSSS的项目，其中的项目，其中SS是文法开始符号。是文法开始符号。即拓广文法开始符的产生

39、式圆点在最左边的项目。即拓广文法开始符的产生式圆点在最左边的项目。p由文法的产生式直接构造识别活前由文法的产生式直接构造识别活前缀和可归前缀的有限自动机缀和可归前缀的有限自动机54盛威网：专业的计算机学习网站1.1.构造方法构造方法（1）将文法进行拓广，保证文法开始符号不出现在任何产生式右部，即增加产生式SSS S，构成新的文法G（2）列出文法的所有产生式的项目，每个项目都为NFA的一个状态（3）确定初态初态、句柄识别态句柄识别态、句子识别态句子识别态 初态：开始项目SS句柄识别态：圆点在最后的项目，也是终态句子识别态：项目SS55盛威网：专业的计算机学习网站（4）确定状态之间的转换关系状态之

40、间的转换关系，并构造相应的NFAu若有项目i i：AXAX，项目j j：AXAX，则从状态i到状态j连一条标记为X X的箭弧。u若XVN，对于X的所有产生式圆点在最左边的状态k:Xrk:Xr，都从状态i到状态k连一条标记为的箭弧。（5）用子集法把NFA确定化为DFA，并简化56盛威网：专业的计算机学习网站2.2.实例实例例例5.5.为下面的文法构造识别活前缀的为下面的文法构造识别活前缀的DFADFA EaA|bBEaA|bBAcA|dAcA|dBcB|dBcB|d第一步：拓广文法第一步：拓广文法SESEEaA|bBEaA|bBAcA|dAcA|dBcB|dBcB|d57盛威网：专业的计算机学习

41、网站第二步：列出拓广文法第二步：列出拓广文法G的项目的项目1 1SESE2 2SE SE 3 3EaAEaA4 4EaA EaA 5 5EaAEaA6 6AcAAcA7 7AcAAcA8 8AcAAcA9 9AdAd10. Ad10. Ad11.EbB11.EbB 12. EbB 12. EbB 13. EbB13. EbB14.BcB14.BcB 15. BcB 15. BcB16. BcB16. BcB17.Bd17.Bd 18. Bd 18. Bd 第三步：确定第三步：确定初态初态、句柄识别态句柄识别态、句子识别态句子识别态 初态：开始项目SE句柄识别态：SE，EaA，EbB，AcA，

42、Ad，BcB，Bd句子识别态：项目SE58盛威网：专业的计算机学习网站第四步：确定第四步：确定状态之间的转换关系状态之间的转换关系，并构造相应的，并构造相应的NFA12E34a5A67c8A910d*1112b13B1415c16B1718d59盛威网：专业的计算机学习网站第五步：用子集法把第五步：用子集法把NFANFA确定化为确定化为DFADFA，并简化，并简化I0:SE EaA EbBbBI1:SEEI2: EaA AcA AddaI6:EaAAI4: AcA AcA AddI8:AcAAI10:AddccdI3: EbB BcB BddbI7:EbBBI5: BcB BcB BddccI

43、11:BddI9:BcBBd60盛威网：专业的计算机学习网站1)构造出的NFA是包含有串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。 说明说明2)相应DFA的每个状态是一个项目集项目集，称作LR(0)项目集，整个状态集称为LR(0)LR(0)项目集规范簇项目集规范簇。 3)在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。 61盛威网：专业的计算机学习网站4)有一个唯一的初态和一个唯一的接受态，但有若干个归约态，表示有若干种活前缀的识别状态。6)手工构造文法的项目集规范簇很困难。5)状态反映了识别

44、句柄的情况，即句柄的多大部分已进栈，即知道了历史情况。62盛威网：专业的计算机学习网站构造以构造以LR(0)LR(0)项目集为状态的识别活前缀的项目集为状态的识别活前缀的DFADFA NFA NFA确定化为确定化为DFADFA的工作量较大，我们考虑直接构的工作量较大，我们考虑直接构造出项目集作为造出项目集作为DFADFA的状态，就可直接构造的状态，就可直接构造DFADFA。 分析分析DFADFA状态的项目集内的项目之间、项目集之状态的项目集内的项目之间、项目集之间的间的规律规律性，性，直接构造直接构造出出DFADFA。p识别活前缀的识别活前缀的DFADFA的构造的构造如何构造如何构造DFADF

45、A的一个状态（项目集）的一个状态（项目集）如何由如何由DFADFA的一个状态求其他状态的一个状态求其他状态63盛威网：专业的计算机学习网站规律一规律一p若一个项目集中有项目若一个项目集中有项目AA BB ，则必有，则必有项目项目BB，其中，其中BB是产生式。是产生式。如如I I0 0、I I2 2、I I3 3、I I4 4、I I5 5。64盛威网：专业的计算机学习网站I0:SE EaA EbBbBI1:SEEI2: EaA AcA AddaI6:EaAAI4: AcA AcA AddI8:AcAAI10:AddccdI3: EbB BcB BddbI7:EbBBI5: BcB BcB Bd

46、dccI11:BddI9:BcBBd65盛威网：专业的计算机学习网站为实现这一步，给出下面定义：为实现这一步，给出下面定义：A.A.项目集闭包函数项目集闭包函数closureclosure步骤：步骤：（1 1）每一个）每一个I I中的项目都加进中的项目都加进closure(I)closure(I)；（2 2）若）若ABclosure(I)ABclosure(I)，B B是非终结符，那是非终结符，那么，对于任何关于么，对于任何关于B B的产生式的产生式B B，将项目，将项目B B加加进进CLOSURE(I)CLOSURE(I)；（3 3）重复执行（）重复执行（2 2）直到）直到closure(I

47、)closure(I)不再增大为止。不再增大为止。说明：说明：圆点后为终结符或在一个产生式的最后，求闭包圆点后为终结符或在一个产生式的最后，求闭包时不会增加新的项目时不会增加新的项目66盛威网：专业的计算机学习网站例例6.6.（0 0）SSSS（1 1）SSSS（2 2）SaS SaS （3 3）SaS SaS （4 4）SaSSaS（5 5）SbSb（6 6）SbSb若若I= SS I= SS 则则closure(I)=closure(I)=？ SS , SaS , Sb SS , SaS , Sb 练习：练习：I= SaS I= SaS closure(I)=closure(I)=？ Sa

48、S , SaS , Sb SaS , SaS , Sb 67盛威网：专业的计算机学习网站 有了初态的项目集之后，如何求出对于文法符有了初态的项目集之后，如何求出对于文法符号号X X可能转移到的下一个状态的项目集？可能转移到的下一个状态的项目集？ 【解释】【解释】若当前处于AXYZAXYZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式Yu|w。那么YuYu和YwYw这两个项目便是刻划期望移进 First(Y)中的某些符号的情况。 AXYZ，Yu和Yw这三个项目对应移进归约分析的同一个状态，我们可以把它们放在DFA的同一个项目集里。68盛威网：专业的计算机学习网站p若项目集中有若

49、项目集中有AA BB ，另一项目集中有，另一项目集中有AA BB ，则这两个项目集之间必有一条，则这两个项目集之间必有一条B B弧。弧。如：如：I I0 0 和和I I1 1、I I2 2、I I3 3等。等。规律二规律二69盛威网：专业的计算机学习网站I0:SE EaA EbBbBI1:SEEI2: EaA AcA AddaI6:EaAAI4: AcA AcA AddI8:AcAAI10:AddccdI3: EbB BcB BddbI7:EbBBI5: BcB BcB BddccI11:BddI9:BcBBd70盛威网：专业的计算机学习网站为实现这一步，给出下面定义：为实现这一步，给出下面定

50、义：B.B.状态转移函数状态转移函数GOGOX X是文法符号，是文法符号，I I项目：项目： AX AX J J项目：项目： AXAX则：则：GO(I,X)=closure(J)GO(I,X)=closure(J)【解释】【解释】GO函数实际就是检查I中的每一个后随符号为X的项目，将这个圆点向后移动一个位置，得到项目集J，再对项目集J求闭包。GO(I,X) GO(I,X) 的直观意义是的直观意义是: : 从状态从状态I(I(项目集项目集) )出发出发, ,经过经过X X弧所应该到达弧所应该到达的状态的状态( (项目集项目集) ) 71盛威网：专业的计算机学习网站例例7.7.（0 0）SSSS（

51、1 1）SSSS（2 2）SaS SaS （3 3）SaS SaS （4 4）SaSSaS（5 5）SbSb（6 6）SbSb求求GO(I,b)=?GO(I,b)=?GO(I,b)=closure(Sb)=SbGO(I,b)=closure(Sb)=Sb求求GO(I,a)=?GO(I,a)=?GO(I,a)=closure(SaS)=SaS,SaS,SbGO(I,a)=closure(SaS)=SaS,SaS,Sb例：例：I=SS,SaS ,Sb I=SS,SaS ,Sb 72盛威网：专业的计算机学习网站例例8.8.已知文法已知文法GG：SE SE EaA|bBEaA|bB AcA|dAcA|

52、dBcB|d BcB|d 有有I=SEI=SE，EaAEaA，EbBEbB求求GO(I,E)GO(I,E)，GO(I,a)GO(I,a)和和GO(I,b)GO(I,b)。GO(I,E)=CLOSURE(SE)=SEGO(I,E)=CLOSURE(SE)=SEGO(I,a)=CLOSURE(EaA)=EaA,AcA,AGO(I,a)=CLOSURE(EaA)=EaA,AcA,AddGO(I,b)=CLOSURE(EbB)=EbB,BcB,BGO(I,b)=CLOSURE(EbB)=EbB,BcB,Bdd 在在LRLR分析中，若分析中，若I I中有圆点位于中有圆点位于X X左边的项目左边的项目AX

53、AX，则当分析器从输入符号串中识别，则当分析器从输入符号串中识别出文法符号后，分析器要进入后续状态。出文法符号后，分析器要进入后续状态。73盛威网：专业的计算机学习网站核圆点右移后的项目圆点右移后的项目引申的含义：圆点引申的含义：圆点不在不在产生式右部产生式右部最左边最左边的项目是核。但是，开始项目的项目是核。但是，开始项目SSSS除除外。外。74盛威网：专业的计算机学习网站构造构造LR(0)LR(0)项目集规范族项目集规范族使用闭包函数（使用闭包函数（CLOSURECLOSURE）和转向函数）和转向函数(GO(I,X)(GO(I,X)构构造文法造文法GG的的LR(0)LR(0)的项目集规范族

54、的项目集规范族，步骤如下：，步骤如下：c)c)重复重复b)b)直到不出现新的项目集为止直到不出现新的项目集为止b)b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数GO (IGO (I，X)=X)= CLOSURE(J) CLOSURE(J)求出求出新状态新状态J J的项目集的项目集a)a)置项目置项目S SS S为初态集的核，然后对核求闭为初态集的核，然后对核求闭包包CLOSURECLOSURE（S SS S）得到）得到初态的项目集初态的项目集75盛威网：专业的计算机学习网站直接构造直接构造DFADFA的思想的思想 q从从SSSS开始，得到开始，得到DFAD

55、FA的的初态项目集初态项目集q然后通过状态转换函数然后通过状态转换函数GOGO求其所有的求其所有的后继项目集后继项目集C=C=closure(SS)closure(SS); ; dodo for(C for(C中的每个项目集中的每个项目集I I和每个符号和每个符号X X） if(GO(I,X)if(GO(I,X)非空非空, ,且不在且不在C C中）中） 把把GO(I,X)GO(I,X)加入加入C C中中; while(C while(C增大增大) ) return C;return C;算法算法 注：注：C C是集合，是集合，用于存放全部的用于存放全部的项目集项目集 76盛威网：专业的计算机学

56、习网站说明：1）此算法是迭代算法，置了C的初态（初态仅包含第一个项目集）后，每经过一次FOR语句，就扩大一次C中的项目集数，直到项目集数不再增加为止。 2）此算法是从I0开始，按该项目集内的项目顺序依次求出所有后继项目集后继项目集。由这样一层一层向下生成的所有项目集的方法避免了项目集的遗漏。 3）若在项目集中存在A项目，不应再做GO函数转向其他项目集，因为A和A是同一项目，都是A项目，它本身是归约项目，不存在后继项目。 4）由这个项目集规范族C中各个状态及状态转换函数GO，可构造一张识别活前缀的DFA图。 77盛威网：专业的计算机学习网站例例8.8.已知文法已知文法G G：EaA|bBEaA|

57、bB AcA|dAcA|dBcB|d BcB|d 直接构造能识别活前缀和可归前缀的直接构造能识别活前缀和可归前缀的DFADFA第一步：拓广文法第一步：拓广文法SESEEaA|bBEaA|bBAcA|dAcA|dBcB|dBcB|d78盛威网：专业的计算机学习网站第二步：构造第二步：构造DFADFA的状态的状态1.1.从从SSSS开始，得到开始，得到DFADFA的的初态项目集初态项目集I I0 0 = = Closure(S.E)Closure(S.E)I I0 0：S.E S.E ， E .a E .a ， E.bBE.bBGoIGoI0 0 ,E=SE. ,E=SE. II1 1=Closu

58、re(SE.)=Closure(SE.)I I1 1:SE:SE2.2.通过状态转换函数通过状态转换函数GOGO求其所有的求其所有的后继项目集后继项目集GoIGoI0 0 ,a=Sa.A ,a=Sa.AII2 2=Closure(Sa.A)=Closure(Sa.A)I I2 2: Ea.A: Ea.A，A.cAA.cA，A.dA.d79盛威网：专业的计算机学习网站GoIGoI0 0,b=Sb.B ,b=Sb.B II3 3=Closure(Sb.B)=Closure(Sb.B)I I3 3:Eb.B:Eb.B，B.cBB.cB，B.dB.dGoIGoI2 2,A=SaA.,A=SaA.II4

59、 4=Closure(SaA.)=Closure(SaA.)I I4 4:EaA:EaAGoIGoI2 2,c=Ac.A ,c=Ac.A II5 5=Closure(Ac.A)=Closure(Ac.A)I I5 5 : Ac.A : Ac.A，A.cAA.cA，A.dA.dGoIGoI2 2,d=Ad. ,d=Ad. II6 6=Closure(Ad.)=Closure(Ad.)I I6 6: Ad.: Ad.80盛威网：专业的计算机学习网站GoIGoI3 3 ,B=EbB. ,B=EbB.II7 7=Closure(EbB.)=Closure(EbB.)I I7 7:EbB:EbBGoIG

60、oI3 3 ,c=Ec.B ,c=Ec.B I I8 8=Closure(Ec.B)=Closure(Ec.B)I I8 8:Ec.B:Ec.B，B.cBB.cB，B.dB.d GoIGoI3 3 ,d=Bd. ,d=Bd. I I9 9=Closure(Bd.)=Closure(Bd.)I I9 9:Bd.:Bd.GoIGoI5 5 ,A=AcA. ,A=AcA. I I1010=Closure(AcA.)=Closure(AcA.)I I1010:AcA.:AcA.GoIGoI8 8 ,B=BcB. ,B=BcB. I I1111=Closure(BcB.)=Closure(BcB.)I