第七章_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 盛威网：专业的计

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

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

4、的含义 7 盛威网：专业的计算机学习网站 /knuth/ 计算机程序设计艺术计算机程序设计艺术 第第1卷卷 基本算法基本算法 计算机程序设计艺术计算机程序设计艺术 第第2卷卷 半数值算法半数值算法 计算机程序设计艺术计算机程序设计艺术 第第3卷卷 排序与查找排序与查找 LR(k) LR(k)分析技术分析技术KnuthKnuth于于19651965年首先提出年首先提出 8 盛威网：专业的计算机学习网站 2.LR2.LR分析的特点分析的特点 q适用范围广适用范围广，适用于多数无二义性的，适用于多数无二义性的 上下文无关文法上下文无关

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

6、对文法的限制较大，无实用价值，是构造其它LRLR 分析表的基础分析表的基础 （重点掌握）（重点掌握） （重点掌握）（重点掌握） 10 盛威网：专业的计算机学习网站 LR(1)LR(1)分析表分析表( (规范规范LRLR分析表分析表) ) 适用文法类最大适用文法类最大, ,几乎所有上下文无关文几乎所有上下文无关文 法都能构造出法都能构造出LR(1)LR(1)分析表分析表, ,但其分析表体积太但其分析表体积太 大，实用价值不大。大，实用价值不大。 LALRLALR分析表分析表( (超前超前LRLR分析表分析表) ) 这种表适用的文法类及其实现上难易在这种表适用的文法类及其实现上难易在LR(1)LR

7、(1) 和和SLR(1)SLR(1)两种之间两种之间, ,比较实用。使用比较实用。使用LALRLALR分析表分析表 进行语法分析的分析器叫进行语法分析的分析器叫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)文法一定是文法一定

8、是LR(1)LR(1)文法吗？文法吗？ 12 盛威网：专业的计算机学习网站 u回顾回顾 自底向上分析实现的自底向上分析实现的基本思想基本思想“移进归约移进归约”方法方法 文法文法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#a

9、A4） 归约（Ab）bcde#ab3） 移进bbbcde#a2） 移进aabbcde#1） 动作动作输入符号串输入符号串符号栈符号栈步骤步骤 对输入串对输入串abbcde#的移进的移进-规约分析过程规约分析过程 14 盛威网：专业的计算机学习网站 p在步骤在步骤3 3中，用中，用AbAb归约归约 p在步骤在步骤5 5中，用中，用AAbAAb归约归约 p问题：何时移进？何时归约？用哪个产生式问题：何时移进？何时归约？用哪个产生式 归约（如何找当前句柄归约）？归约（如何找当前句柄归约）？ 15 盛威网：专业的计算机学习网站 3 3） #a#ab b bcde# bcde# 归约归约( (AbAb)

10、 ) 5 5） #aA#aAb b cde# cde# 归约归约( (AAbAAb) ) 4 4） #aA bcde# #aA bcde# 移进移进 6 6） #aA cde# #aA cde# 移进移进 分析：已分析过的部分在栈中的分析：已分析过的部分在栈中的前缀前缀不同，而且不同，而且 移进和归约后栈中的状态会发生变化移进和归约后栈中的状态会发生变化 我们引入一个新的我们引入一个新的状态栈状态栈来表示符号栈中的符号来表示符号栈中的符号 目前状态目前状态 用用LRLR分析表分析表来表示不同状态下对于各输入符号应来表示不同状态下对于各输入符号应 采取的动作采取的动作 16 盛威网：专业的计算机

11、学习网站 问题： 对于一个文法，状态集是如何确定的？ LR分析表是如何得到的？ 答案答案：需要构造识别：需要构造识别可归前缀可归前缀的的有穷自动机有穷自动机 LRLR方法也是通过求方法也是通过求句柄句柄逐步归约进行语法分析。逐步归约进行语法分析。 句柄句柄在简单优先分析法中是通过符号的优先关在简单优先分析法中是通过符号的优先关 系而求得的；在系而求得的；在LRLR方法中，则是通过求方法中，则是通过求可归前缀可归前缀而而 求得的。求得的。 17 盛威网：专业的计算机学习网站 7.2.1 7.2.1 可归前缀和活前缀可归前缀和活前缀 字的前缀是指该字的任意首部。 例如：字ABC的前缀有,A,AB,

12、ABC。 如果Z=xy是一符号串，则x是Z的前缀，其中x,y为 任意符号串（包括空串） 规范句型中句柄之前包括句柄在内的串称为可归前缀。 指规范句型的一个前缀，这种前缀不含句柄之后 的任何符号。 18 盛威网：专业的计算机学习网站 例例2.2.根据下面的文法识别输入串abbcde。 1) SaAcBe 2) Ab 3) AAb 4) Bd 为每条产生式的尾部加上用i表示的产生式序号 1)SaAcBe1 2)Ab2 3)AAb3 4)Bd4 19 盛威网：专业的计算机学习网站 用最右推导方式来识别,推导时把序号也带上。 SaAcBeaAcBe1aAcdaAcd4e1aAbaAb3cd4e1 ab

13、ab2b3cd4e1 若用最左归约的方式进行识别，则完全是上面的逆过程。 p规范句型abbcde的前缀有：，a,ab p规范句型aAbcde的前缀有：，a,aA,aAb p规范句型aAcde的前缀有： ，a,aA,aAc,aAcd p规范句型aAcBe的前缀有： ，a,aA,aAc,aAcB,aAcBe 20 盛威网：专业的计算机学习网站 u由例子我们得知：将栈内符号与未扫描的输入串拼 接起来,可得一规范句型规范句型.即栈内符号串总是规范句型规范句型 的前缀的前缀,且不含句柄右侧的符号不含句柄右侧的符号。 :句柄一旦在栈顶形成,就不再移进新符号,而是 要进行归约了. 有两个要点: (1)它是规

14、范句型的前缀它是规范句型的前缀 (2)它不含句柄右侧符号它不含句柄右侧符号 21 盛威网：专业的计算机学习网站 【注】【注】在活前缀之后增添一些终结符号后，就可以使之成 为规范句型。 形式定义形式定义 ，则称为活前缀活前缀。 * , t SV 即：对于文法G，若 活前缀就是当前规范句型中从第一个字符到句柄句柄 最后一个符号所形成的子串的前缀，若该子串的长度 为n，活前缀就有n+1个。在这n+1个活前缀中，包含 完整句柄的活前缀就是可归前缀可归前缀。 22 盛威网：专业的计算机学习网站 可归前缀和活前缀在可归前缀和活前缀在LRLR分析中的作用分析中的作用 在LR分析过程中，实际上是把活前缀活前缀

15、列 出放在符号栈中，一旦在栈中出现可归前缀可归前缀， 即句柄句柄已经形成，就用相应的产生式进行归 约。 在分析的过程中，只要符号栈中的符 号串是一个活前缀活前缀，就可保证已被分析过的 部分是该文法规范句型的正确部分。 23 盛威网：专业的计算机学习网站 7.2.2 7.2.2 识别活前缀的有限自动机识别活前缀的有限自动机 0 X 1 3 10 4 Y 1 5 1 识别识别1(0|1)1(0|1)* *101101的的NFANFA n有限自动机有限自动机 一种识别装置一种识别装置 分分DFADFA和和NFANFA 如何确定规范如何确定规范 句型的活前缀句型的活前缀 24 盛威网：专业的计算机学习

16、网站 p用有限自动机来识别活前缀活前缀和可归前缀可归前缀 p有限自动机如何构造？ 一个特例：已经有了可归约前缀如何构造识 别活前缀和可归前缀的有限自动机 由文法的产生式构造识别活前缀和可归前缀 的有限自动机的方法 25 盛威网：专业的计算机学习网站 有穷自动机的有穷自动机的输入字符输入字符：终结符和非终结符终结符和非终结符 状态转换状态转换：每次让一个：每次让一个符号进栈符号进栈，就看成识别过，就看成识别过 了该符号，同时状态进行转换。了该符号，同时状态进行转换。当识别到当识别到可归前可归前 缀缀（栈中形成句柄）时，认为达到了识别句柄的（栈中形成句柄）时，认为达到了识别句柄的 终态。终态。因为

17、因为LRLR分析时栈中始终保持是活前缀，所分析时栈中始终保持是活前缀，所 以有限自动机识别过的符号串也是活前缀。以有限自动机识别过的符号串也是活前缀。 终态终态：当识别到：当识别到可归约前缀可归约前缀（表明在栈中形成句（表明在栈中形成句 柄），认为到达了识别句柄的终态，执行柄），认为到达了识别句柄的终态，执行归约归约。 26 盛威网：专业的计算机学习网站 拓广文法 在原文法在原文法G G中增加产生式中增加产生式SSSS，S S为原文法为原文法G G 的开始符号，所得的新文法称为的开始符号，所得的新文法称为G G的的拓广文法拓广文法，以，以GG 表示，表示，SS为拓广后文法为拓广后文法GG的开始

18、符号。的开始符号。 目的目的 有时候文法中某些产生式右部含有开始符号，有时候文法中某些产生式右部含有开始符号， 在归约过程中为了能分清是否已归约到文法的最初在归约过程中为了能分清是否已归约到文法的最初 开始符，我们增加了一个新的开始符号开始符，我们增加了一个新的开始符号SS，使它，使它 只在产生式左部，这样确保了不会混淆。只在产生式左部，这样确保了不会混淆。 27 盛威网：专业的计算机学习网站 n构造识别活前缀和可归约前缀的有限自动机的一 个例子： 特例：由句子规范推导的逆过程直观地看出它的活前缀 和可归前缀 按活前缀和可归前缀构造识别它们的有限自动机 v定义定义7.17.1若若SS aAwa

19、Aw a aw w（w w只含终结符只含终结符） 是文法是文法G G的拓广文法的拓广文法GG中的一个规范推导，符号串中的一个规范推导，符号串 是是aa的前缀，则称的前缀，则称是是G G的一个的一个活前缀活前缀。也就是说。也就是说 是规范句型是规范句型a aww的前缀，但它的右端不超过该句型句的前缀，但它的右端不超过该句型句 柄的末端。柄的末端。 RR * * 28 盛威网：专业的计算机学习网站 例例3.3.根据下面的文法识别输入串根据下面的文法识别输入串abbcdeabbcde。 1) S1) SaAcBe aAcBe 2) A 2) Ab b 3) A 3) AAb Ab 4) B 4) B

20、d d 文法文法GSGS： 0 0）S S0S S0 1 1）S aAcBe1S aAcBe1 2 2）A b2A b2 3 3）A Ab3A Ab3 4 4）B d4B d4 第一步：拓广文法第一步：拓广文法第二步：列出给定句子可归前缀第二步：列出给定句子可归前缀 输入串输入串abbcde abbcde 的最右推导过程：的最右推导过程： SS=S S0=0=aAcaAcB Be e1 =a1 =aA Ac cd d4e14e1 =a=aA Ab b3cd4e1= a3cd4e1= ab b2b3cd4e12b3cd4e1 S0 S0 ab2ab2 aAb3aAb3 aAcd4aAcd4 aA

21、cBe1aAcBe1 29 盛威网：专业的计算机学习网站 第三步：构造识别其活前缀及可归前缀的有限自动机第三步：构造识别其活前缀及可归前缀的有限自动机 10 43 87 1312 1018 2 5 9 14 6 17 1516 11 10 S ab aAb aAcd a AcBe * * 1句子识别态 i句柄识别态 所有的状态都是活前缀的识别状态所有的状态都是活前缀的识别状态 终态是句柄的识别态终态是句柄的识别态 带带“* *”号的状态既是句柄识别态又是句子识别号的状态既是句柄识别态又是句子识别 态，句子识别态仅有一个态，句子识别态仅有一个 30 盛威网：专业的计算机学习网站 第四步：构造第四

22、步：构造识别活前缀的识别活前缀的NFANFA 10 43 87 1312 1018 2 5 9 14 6 17 1516 11 10 S ab aAb aAcd a AcBe X * 31 盛威网：专业的计算机学习网站 第五步：把第五步：把NFA确定化，重新编号确定化，重新编号 X24 68 7 9 5 3 1 A ba Sbc Be d * 识别活前缀和可归前缀的识别活前缀和可归前缀的DFADFA 32 盛威网：专业的计算机学习网站 X 2 a 1 * S A 45 b 3 b 6 c 7 d B 89 e 理解识别活前缀和可归前缀的理解识别活前缀和可归前缀的 DFADFA和分析过程的对应和

23、分析过程的对应 符号栈符号栈输入串输入串动作动作 # #abbcde#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#

24、 #接受接受 33 盛威网：专业的计算机学习网站 ACTIONGOTO acebd#SAB XS21 1acc 2S34 3r2r2r2r2r2r2 4S6S5 5r3r3r3r3r3r3 6S78 7r4r4r4r4r4r4 8S9 9r1r1r1r1r1r1 对任何一个上下文无关文法只要构造出它的识别对任何一个上下文无关文法只要构造出它的识别 活前缀和可归前缀的有穷自动机，就可以构造其相应的活前缀和可归前缀的有穷自动机，就可以构造其相应的 分析表（分析表（ACTIONACTION表表和和GOTOGOTO表），进行表），进行LRLR分析分析 X 2 a 1 * S A 45 b 3 b 6

25、c 7 d B 89 e S0S0，ab2ab2，aAb3aAb3， aAcd4aAcd4，aAcBe1aAcBe1 34 盛威网：专业的计算机学习网站 以上示例中构造DFA的方法是通过一个句子的归约过 程确定可归前缀，但是： 对于一个复杂的文法，其可归前缀不是如此简单就 能计算出来 示例中用一个句子归约过程的所有活前缀和可归前 缀构造出的DFA，恰好也是识别整个文法的活前缀和 可归前缀的DFA，这仅是一个特殊情况特殊情况。 对一个上下文无关文法需要求出它的所有活前缀和 可归前缀后才能构造其识别该文法活前缀的DFA 35 盛威网：专业的计算机学习网站 7.2.3 7.2.3 活前缀及其可归前缀

26、的一般计算方法活前缀及其可归前缀的一般计算方法 v定义定义7.27.2（非终结符的左文）（非终结符的左文） p对一个任意的上下文无关文法需用确定的办法来求出 它的所有活前缀和可归前缀才能构造其识别该文法活前 缀的有限自动机。 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(

27、A)LC(A)，所以，所以 LC(A)LC(A) LC(B)LC(B) * RR 37 盛威网：专业的计算机学习网站 求求LCLC（A A）的方法）的方法 首先寻找文法中A在右部的产生式，假设该产生 式左部为Q，则 LC（A）=LC（Q）产生式右部A之前的符号串 例例4.4.文法文法GSGS： SS0SS0 SaAcBe1SaAcBe1 Ab2Ab2 AAb3AAb3 Bd4Bd4 由前面的定义与推论我们知： LC(S)= LC(S)=LC(S) = LC(A)=LC(S)aLC(A) = a LC(B)=LC(S)aAc=aAc 38 盛威网：专业的计算机学习网站 LC(S)= LC(S)=

28、 LC(A)=a LC(B)=aAc 化简用正规式表示： 这样我们求出了每个这样我们求出了每个非终非终 结符结符在规范推导中用该非终结在规范推导中用该非终结 符的右部替换该非终结符之前，符的右部替换该非终结符之前， 它的左部可能出现的它的左部可能出现的所有前缀所有前缀， 也就是在规范归约过程中用句也就是在规范归约过程中用句 柄归约成该非终结符之前柄归约成该非终结符之前不包不包 括句柄的活前缀括句柄的活前缀。 输入串输入串abbcdeabbcde的最右推导过程：的最右推导过程： SS=S S=aAcaAcB Be e=a=aA Ac cd de=ae=aA Ab bcde=acde=ab bbc

29、debcde 解释：在上面的推导过程中，非终结符B依据产生式 Bd被替换为d之前，它的左部是aAc，这个就是活前 缀。或者说我们把从右看，把d归约成B之前不包含d 这个句柄的活前缀是aAc。 39 盛威网：专业的计算机学习网站 不包括句柄的活前缀不包括句柄的活前缀+ +句柄句柄= =？ 可归前缀可归前缀 令令 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=S LR(0)C(SLR(0)C(SaAcBe)=LC(S)aAcBe)=LC(S)aAcBe=aAcB

30、aAcBe=aAcB e e LR(0)C(ALR(0)C(Ab)=LC(A)b)=LC(A)b=abb=ab LR(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(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 盛威网：专业的计算机学习网站 总结：如何构造识别文法活

31、前缀的有限自动机？总结：如何构造识别文法活前缀的有限自动机？ 1 1、根据文法算出其可归前缀、根据文法算出其可归前缀 (1)(1)求出非终结符的左文求出非终结符的左文 (2)(2)求出产生式的左文，就可求出可归前缀求出产生式的左文，就可求出可归前缀 2 2、根据可归前缀，构造识别文法活前缀的不确定有限自动机、根据可归前缀，构造识别文法活前缀的不确定有限自动机 3 3、确定化，从而构造出识别文法活前缀的确定的有限自动机、确定化，从而构造出识别文法活前缀的确定的有限自动机 4. 4. 化简上面的确定有限自动机，合并其中的活前缀化简上面的确定有限自动机，合并其中的活前缀 41 盛威网：专业的计算机学

32、习网站 例例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)= LC(E)=LC(S)=LC(E)=LC(S)= LC(A)=LC(E)aLC(A)=LC(E)aLC(A)cLC(A)c acac* * LC(B)=LC(E)bLC(B)=LC(E)bLC(B)cLC(B)c bcbc* * 第二步：求产生式的左文第二步：求产生式的左文

33、LC(0)CLC(0)C（SESE）=E=E LC(0)CLC(0)C（EaAEaA）=aA=aA LC(0)CLC(0)C（EbBEbB）=bB=bB LC(0)CLC(0)C（AcAAcA）=ac=ac* *cAcA LC(0)CLC(0)C（AdAd）=ac=ac* *d d LC(0)CLC(0)C（BcBBcB）=bc=bc* *cBcB LC(0)CLC(0)C（BdBd）=bc=bc* *d d 42 盛威网：专业的计算机学习网站 第三步：构造识别文法活前缀的第三步：构造识别文法活前缀的NFA 43 盛威网：专业的计算机学习网站 第三步：构造识别文法活前缀的第三步：构造识别文法活

34、前缀的DFA并简化并简化 44 盛威网：专业的计算机学习网站 p对任何一个上下文无关文法只要能够构造出 它的识别可归前缀的有限自动机，就可以构 造其相应的分析表分析表。 p用这种方法构造识别可归前缀的有限自动机 从理论的角度从理论的角度讲是比较严格的，但实现起来却 很复杂。 是否存在一种比较实用的方法？是否存在一种比较实用的方法？ 存在存在 45 盛威网：专业的计算机学习网站 7.2.4 LR(0)7.2.4 LR(0)项目集规范族的构造项目集规范族的构造 活前缀与句柄的关系活前缀与句柄的关系 A A 的右部的右部 已出现在栈顶，可以已出现在栈顶，可以归约归约 活前缀已含有句柄的活前缀已含有句

35、柄的全部全部符号符号 活前缀只含有句柄的活前缀只含有句柄的部分部分符号符号 活前缀活前缀不含有不含有句柄的任何符号句柄的任何符号 AA 1 1 2 2的右部子串的右部子串 1 1已出现在栈顶，正期已出现在栈顶，正期 待从剩余输入串中能看到由待从剩余输入串中能看到由 2 2推出的符号串推出的符号串 期望从剩余输入串中能看到由某产生式期望从剩余输入串中能看到由某产生式AA 的右部的右部 所推出的符号串所推出的符号串 A A 1 1 2 2 A 为刻划产生式右部符号已有多大一部为刻划产生式右部符号已有多大一部 分被识别，用项目来指示位置分被识别，用项目来指示位置 46 盛威网：专业的计算机学习网站

36、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+1个项目 p产生式AA只有一个项目只有一个项目AA 48 盛威网：专业的计算机学习网站 2.2.项目的含义项目的含义 如：产生式如：产生式UXYZUXYZ对应有对应有4 4个项目个项目

37、 0 U0 UXYZXYZ 1 UX 1 UXYZ YZ 2 UXY 2 UXYZ Z 3 UXYZ 3 UXYZ UXYZ 预期要归约的句柄是XYZ，但都未进栈 UXYZ 预期要归约的句柄是XYZ，仅X进栈 UXYZ 预期要归约的句柄是XYZ，仅XY进栈 UXYZ XYZ全部进栈，XYZ可进行归约 49 盛威网：专业的计算机学习网站 项目的直观意义项目的直观意义: : 在分析过程中的某一时刻已经归约的部分和在分析过程中的某一时刻已经归约的部分和 等待归约部分，圆点是栈内外的分界线。等待归约部分，圆点是栈内外的分界线。 项目圆点的左部表示分析过程的某个时刻用该产 生式归约时句柄已识别的部分句柄

38、已识别的部分，圆点右部表示待待 识别的部分识别的部分。 50 盛威网：专业的计算机学习网站 3.3.项目的分类项目的分类 由于不同的LR(0)项目反映了在分析过程中栈顶的不 同情况，因此，我们可以根据圆点位置和圆点后是终结符 还是非终结符或为空，将一个文法的全部LR(0)项目进行 分类。 移进项目移进项目 待约项目待约项目 归约项目归约项目 接受项目接受项目 51 盛威网：专业的计算机学习网站 圆点后面是圆点后面是终结符终结符的项目，表示栈内是句柄的一部的项目，表示栈内是句柄的一部 分，期待从输入串中移进一个符号，以形成句柄。分，期待从输入串中移进一个符号，以形成句柄。 （1 1）移进项目：）

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

40、 特殊的归约项目特殊的归约项目，它是对文法开始符号的归约，它是对文法开始符号的归约 项目，使用产生式项目，使用产生式SS进行归约，这时，输进行归约，这时，输 入串归约为文法的开始符号，表示整个句子已入串归约为文法的开始符号，表示整个句子已 经分析完毕，分析成功，也即输入串为该文法经分析完毕，分析成功，也即输入串为该文法 的句子。的句子。 规定规定AA 53 盛威网：专业的计算机学习网站 开始项目开始项目 形如形如SSS S的项目，其中的项目，其中SS是文法开始符号。是文法开始符号。 即拓广文法开始符的产生式圆点在最左边的项目。即拓广文法开始符的产生式圆点在最左边的项目。 p由文法的产生式直接构

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

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

43、广文法第二步：列出拓广文法G的项目的项目 1 1SSE E2 2SESE 3 3EEaAaA 4 4EaEaA A 5 5EaAEaA6 6AAcAcA 7 7AcAcA A8 8AcAAcA9 9AAd d 10. Ad10. Ad11.E11.EbBbB 12. Eb 12. EbB B 13. EbB13. EbB14.B14.BcBcB 15. Bc 15. BcB B 16. BcB16. BcB17.B17.Bd d 18. Bd 18. Bd 第三步：确定第三步：确定初态初态、句柄识别态句柄识别态、句子识别态句子识别态 初态：开始项目SE 句柄识别态：SE，EaA，EbB，AcA

44、， Ad，BcB，Bd 句子识别态：项目SE 58 盛威网：专业的计算机学习网站 第四步：确定第四步：确定状态之间的转换关系状态之间的转换关系，并构造相应的，并构造相应的NFA 12 E 3 4 a 5 A 6 7 c 8 A 9 10 d * 11 12 b 13 B 14 15 c 16 B 17 18 d 59 盛威网：专业的计算机学习网站 第五步：用子集法把第五步：用子集法把NFANFA确定化为确定化为DFADFA，并简化，并简化 I0:SE EaA EbBbB I1:SE E I2: EaA AcA Add aI6:EaA A I4: AcA AcA Add I8:AcA A I10

45、:Ad d c c d I3: EbB BcB Bdd b I7:EbB B I5: BcB BcB Bdd c c I11:Bd d I9:BcB B d 60 盛威网：专业的计算机学习网站 1)构造出的NFA是包含有串的NFA，可以使用子集法使之 确定化，使之成为一个以项目集为状态的DFA，这个DFA 就是建立LR分析算法的基础。 说明说明 2)相应DFA的每个状态是一个项目集项目集，称作LR(0)项目集， 整个状态集称为LR(0)LR(0)项目集规范簇项目集规范簇。 3)在DFA的一个状态对应的项目集内，每个项目是“等价” 的，即从期待归约的角度看相同。 61 盛威网：专业的计算机学习网

46、站 4)有一个唯一的初态和一个唯一的接受态，但有若干个 归约态，表示有若干种活前缀的识别状态。 6)手工构造文法的项目集规范簇很困难。 5)状态反映了识别句柄的情况，即句柄的多大部分 已进栈，即知道了历史情况。 62 盛威网：专业的计算机学习网站 构造以构造以LR(0)LR(0)项目集为状态的识别活前缀的项目集为状态的识别活前缀的 DFADFA NFA NFA确定化为确定化为DFADFA的工作量较大，我们考虑直接构的工作量较大，我们考虑直接构 造出项目集作为造出项目集作为DFADFA的状态，就可直接构造的状态，就可直接构造DFADFA。 分析分析DFADFA状态的项目集内的项目之间、项目集之状

47、态的项目集内的项目之间、项目集之 间的间的规律规律性，性，直接构造直接构造出出DFADFA。 p识别活前缀的识别活前缀的DFADFA的构造的构造 如何构造如何构造DFADFA的一个状态（项目集）的一个状态（项目集） 如何由如何由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 EbBbB I

48、1:SE E I2: EaA AcA Add aI6:EaA A I4: AcA AcA Add I8:AcA A I10:Ad d c c d I3: EbB BcB Bdd b I7:EbB B I5: BcB BcB Bdd c c I11:Bd d I9:BcB B d 65 盛威网：专业的计算机学习网站 为实现这一步，给出下面定义：为实现这一步，给出下面定义： A.A.项目集闭包函数项目集闭包函数closureclosure 步骤：步骤： （1 1）每一个）每一个I I中的项目都加进中的项目都加进closure(I)closure(I)； （2 2）若）若ABclosure(I)AB

49、closure(I)，B B是非终结符，那是非终结符，那 么，对于任何关于么，对于任何关于B B的产生式的产生式B B，将项目，将项目B B加加 进进CLOSURE(I)CLOSURE(I)； （3 3）重复执行（）重复执行（2 2）直到）直到closure(I)closure(I)不再增大为止。不再增大为止。 说明：说明：圆点后为终结符或在一个产生式的最后，求闭包圆点后为终结符或在一个产生式的最后，求闭包 时不会增加新的项目时不会增加新的项目 66 盛威网：专业的计算机学习网站 例例6.6. （0 0） SSSS （1 1） SSSS （2 2） SaS SaS （3 3） SaS SaS

50、（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)=？ SaS , SaS , Sb SaS , SaS , Sb 67 盛威网：专业的计算机学习网站 有了初态的项目集之后，如何求出对于文法符有了初态的项目集之后，如何求出对于文法符 号号X X可能转移到的下一个状态的项目集？可能转移到的下一个状态的项目集？ 【解释】【解释】若当前处于A AXXYZYZ刻划的情况，

51、期望移进 First(Y)中的某些符号，假如有产生式Yu|w。 那么Y Y u u和Y Y w w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况。 AXYZ，Yu和Yw这三个项目对应移进 归约分析的同一个状态，我们可以把它们放在 DFA的同一个项目集里。 68 盛威网：专业的计算机学习网站 p若项目集中有若项目集中有AA BB ，另一项目集中有，另一项目集中有 AA BB ，则这两个项目集之间必有一条，则这两个项目集之间必有一条B B弧。弧。 如：如：I I0 0 和和I I1 1、I I2 2、I I3 3等。等。 规律二规律二 69 盛威网：专业的计算机学习网站 I0:SE

52、 EaA EbBbB I1:SE E I2: EaA AcA Add aI6:EaA A I4: AcA AcA Add I8:AcA A I10:Ad d c c d I3: EbB BcB Bdd b I7:EbB B I5: BcB BcB Bdd c c I11:Bd d I9:BcB B d 70 盛威网：专业的计算机学习网站 为实现这一步，给出下面定义：为实现这一步，给出下面定义： B.B.状态转移函数状态转移函数GOGO X X是文法符号，是文法符号，I I项目：项目： AX AX J J项目：项目： AXAX 则：则：GO(I,X)=closure(J)GO(I,X)=clos

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

54、 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|d BcB|d BcB|d 有有I=SI=SE E，EEaAaA，EEbBbB 求求GO(I,E)GO(I,E)，GO(I,a)GO(I,a)和和GO(

55、I,b)GO(I,b)。 GO(I,E)=CLOSURE(SEGO(I,E)=CLOSURE(SE)=SE)=SE GO(I,a)=CLOSURE(EaGO(I,a)=CLOSURE(EaA)=EaA)=EaA,AA,AcA,AcA,Add GO(I,b)=CLOSURE(EbGO(I,b)=CLOSURE(EbB)=EbB)=EbB,BB,BcB,BcB,Bdd 在在LRLR分析中，若分析中，若I I中有圆点位于中有圆点位于X X左边的项目左边的项目 AXAX，则当分析器从输入符号串中识别，则当分析器从输入符号串中识别 出文法符号后，分析器要进入后续状态。出文法符号后，分析器要进入后续状态。

56、 73 盛威网：专业的计算机学习网站 核 圆点右移后的项目圆点右移后的项目 引申的含义：圆点引申的含义：圆点不在不在产生式右部产生式右部最左边最左边 的项目是核。但是，开始项目的项目是核。但是，开始项目SSSS除除 外。外。 74 盛威网：专业的计算机学习网站 构造构造LR(0)LR(0)项目集规范族项目集规范族 使用闭包函数（使用闭包函数（CLOSURECLOSURE）和转向函数）和转向函数(GO(I,X)(GO(I,X)构构 造文法造文法GG的的LR(0)LR(0)的项目集规范族的项目集规范族，步骤如下：，步骤如下： c)c)重复重复b)b)直到不出现新的项目集为止直到不出现新的项目集为止

57、 b)b)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数 GO (IGO (I，X)=X)= CLOSURE(J) CLOSURE(J)求出求出新状态新状态J J的项目集的项目集 a)a)置项目置项目S S S S为初态集的核，然后对核求闭为初态集的核，然后对核求闭 包包CLOSURECLOSURE（S S S S）得到）得到初态的项目集初态的项目集 75 盛威网：专业的计算机学习网站 直接构造直接构造DFADFA的思想的思想 q从从SSSS开始，得到开始，得到DFADFA的的初态项目集初态项目集 q然后通过状态转换函数然后通过状态转换函数GOGO求其所有的求

58、其所有的后继项目集后继项目集 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 盛威网：专业的计算机学习网站 说明： 1）此算法是迭代算法，置了C的初态（初态仅包含第 一个项目集）后

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

60、构造能识别活前缀和可归前缀的直接构造能识别活前缀和可归前缀的DFADFA 第一步：拓广文法第一步：拓广文法 SESE EaA|bBEaA|bB AcA|dAcA|d BcB|dBcB|d 78 盛威网：专业的计算机学习网站 第二步：构造第二步：构造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.bB GoIGoI0 0 ,E=SE. ,E=SE. II1 1=Closure(SE.)=Clos