《编译第六章》PPT课件.ppt

第六章 LR分析法及 分析程序自动构造 第六章 LR分析法及分析程序自动构造（ 1） 第一节 概述 本章介绍上下文无关文法的 LR分析方法及分 析程序的自动构造 LR：自左至右扫描 ,最右推导的逆过程 一、 LR方法 1.基本思想 在规范归约过程中，一方面记住已移进 和归约的整个符号串，另一方面根据当前所 用的产生式推测未来可能碰到的输入符号 . 第六章 LR分析法及分析程序自动构造（ 2） 第一节 概述 一、 LR方法 2.优缺点 优点：与其它技术相比，适应文法范围更广。能力 更强，识别效率相当，尤其在自左向右扫描输入串 时就能发现其中错误，并能准确指出出错位置。 缺点：若用手工构造分析程序，工作量太大，且容 易出错，所以必须使用自动产生这种分析程序的产 生器。 3.产生器的作用 应用产生器产生一大类上下文无关文法的 LR分析程 序 对二义性文法或难分析的特殊文法，施加一些限制， 使之能用 LR分析。 第六章 LR分析法及分析程序自动构造（ 3） LR分析法通过 LR分析器来实现 总控程序 分析表 输出带 第一节 概述 二、 LR分析器 输入带 下 推 栈 第六章 LR分析法及分析程序自动构造（ 4） 1、从逻辑上说， LR分析器包括两部分： 总控程序，或称为语法分析程序； 分析表 注：后面要学习的所有 LR分析器的总控程序都相同。 仅仅是它们的分析表不同 2、总控程序作用： 查分析表，根据分析表的内容做若干简单动作，如 读头后移，入栈出栈等。 注：由于总控程序很简单，所以产生器的任务就是 产生分析表 第一节 概述 二、 LR分析器 第六章 LR分析法及分析程序自动构造（ 5） 一个文法的 LR分析器常常对应着若干不同分析表， 所有分析表都恰好识别文法所产生的所有语句 本章将讨论四种不同分析表构造方法 1.LR(0)分析表： 分析能力有限，但这是建立其它 LR分析法的基础。 2.SLR分析表： 简单 LR分析表构造法，是一种容易实现又有实用价 值的方法，但存在一些文法构造不出 SLR分析表 第一节 概述 三、分析表 第六章 LR分析法及分析程序自动构造（ 6） 3、规范 LR分析表 它能力最强，但实现代价过高，分析表尺寸太大 4、 LALR分析表 向前看 LR分析表构造文法，也是一种常用方法 注：实际上， SLR和 LALR分别是对 LR(0)和规范 LR的 改进 最后，将讨论如何使用二义文法构造 LR分析器并产 生高效的分析技术 第一节 概述 三、分析表 第六章 LR分析法及分析程序自动构造（ 7） 6.1 LR分析器 一、 LR分析法的基本思想 在规范归约时，当一串貌似句柄的符号串呈现于栈 顶时， LR分析法根据三方面的信息找句柄： 历史：记录在栈内的符号串移进，归约的历史情况 展望：预测句柄之后可能出现的信息； 现实：读头下的符号 注： LR分析法的基本思想是符号人的思维习惯的， 但实现有困难，因为基于 “ 历史 ” 对未来的 “ 展望 ” 可能存在多种可能。当把 “ 历史 ” 和 “ 展望 ” 材 料综合在一起时复杂性就大大增加。如果简化对 “ 展望 ” 的要求，就可获得实际可行的分析算法。 第六章 LR分析法及分析程序自动构造（ 8） 6.1 LR分析器 总控程序 分析表 输出带 输入带 下 推 栈 二、 LR分析器 一个 LR分析器实际上是带有下推栈的确定的有限状 态自动机。可将一个 “ 历史 ” 与这个 “ 历史 ” 下的展 望信息综合为抽象的一个状态 第六章 LR分析法及分析程序自动构造（ 9） 1、下推栈： 下推栈用于存放分析输入串过程中的所有和 “ 历史 ” 及相应 “ 展望 ” 信息形成的抽象状 态 由于每个状态都概括了从分析开始到归约阶 段的全部 “ 历史 ” 和 “ 展望 ” 信息，所以 LR 分析器的每步动作可由栈顶状态和读头下符 号唯一确定 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自动构造（ 10） 1、下推栈： 6.1 LR分析器 二、 LR分析器 sm s0 xm # 状态栈 符号栈 下 推 栈 栈顶指针 把一个 “ 历史 ” 和这个 “ 历史 ” 下的 “ 展望 ” 信 息综合为抽象的一个状态，下推栈用于存放在对输 入串进行分析的过程中这些状态，由于每个状态都 概括了从分析开始到归约阶段的全部 “ 历史 ” 和 “ 展望 ” 信息，所以栈顶的状态就可用于决定当前 的动作 第六章 LR分析法及分析程序自动构造（ 11） 1、下推栈 ： 6.1 LR分析器 二、 LR分析器 sm s0 xm # 状态栈 符号栈 下 推 栈 栈顶指针 为了便于了解栈顶状态对正规分析过程的作用，我们 把栈分为两栏：状态栏和符号栏。符号栈仅用于记录迄 今移进 -归约所得到的文法符号，由于它们已经被概 括在 “ 状态 ” 里了，所以对语法分析不起作用。 初始时，状态栈放 S0（初态），符号栈放 “ #” （栈 底符）；栈顶 Sm代表符号栈内的符号串 XmXm-1 X1及其展 望信息 第六章 LR分析法及分析程序自动构造（ 12） 6.1 LR分析器 二、 LR分析器 2 .分析表 LR分析器的核心是分析表 a1 a2 a n a1 a2 a n A1 A2 A n S0 . . Sk 这张分析表包含两部分：动作表（ Action)和转向表 (GoTo)， 它们都是二维数组 Si表示状态， ai表示终结符， Ai表示非终结符 Action goto 第六章 LR分析法及分析程序自动构造（ 13） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 15） 2 .分析表 2）动作表 ACTION ACTIONS,a表示在当前状态 S下，面临读头下的符号 a所应 采取的动作， 注：该动作有四种可能：移进，归约，出错，接受 3）转向表 (GOTO) GOTOS,X表示：若 XV T，表示在当前状态下，读入 X应转 向什么状态；若 XV N，表示当前栈顶句柄归约成 X后，应转 向什么状态 注：对终结符的移进动作和转向动作可以合并在一起填在动 作表中，这样，转向表可以只保留非终结符转向部分 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自动构造（ 14） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 15） 3.总控程序的动作 1）移进 把 (Sm,ai)的下一个状态 S=GOTO(Sm,ai)连同读头下 符号推进栈内 ,栈顶成为 (S,ai),读头前进一格 2）归约 指用某产生式 A b进行归约。若 b的长度为 g，则 弹出栈顶的 g个元素，使得栈顶的状态变成 Sm-g,然后把 （ Sm-g,A)的下一个状态 S=GOTO(Sm-g,A)连同非终结符 A一起推进 栈，栈顶变成（ S,A)，读头不动。 3）接受 分析成功，退出总控程序 4）报错 输入串出错，调出相应出错程序 注：不管哪一类分析程序，总控程序的动作都一样。程序本 身很简单，按动作表中填的内容具体实施而已。 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自动构造（ 17） 6.1 LR分析器 例：根据表达式文法的 LR分析表分析输入串 i*i+i的 LR动作过程 E E+T E T T T*F T F F (E) F i 第六章 LR分析法及分析程序自动构造（ 18） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 注：表中符号的含义： Sj shift j,指将读入符号 a移进栈内并转到 j状 态，栈顶变成（ j,a); rj reduce j ,按第 j号产生式进行归约； acc accept,分析成功； 空白格 出错标志，若填入相应出错处理程序的 编号，便转相应程序处理。 分析过程 LR分析器的动作情况也可以描述成机器内部的格 局间转换，其格局用三元式表示为（状态栈，已归 约的符号栈，待继续分析的输入串） 6.1 LR分析器 第六章 LR分析法及分析程序自动构造（ 16） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 i*i+i # E E+T E T T T*F T F F (E) F i 第六章 LR分析法及分析程序自动构造（ 20） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 *i+i # E E+T E T T T*F T F F (E) F i 5 i 5 i 第六章 LR分析法及分析程序自动构造（ 21） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 *i+i # E E+T E T T T*F T F F (E) F i 3 F 第六章 LR分析法及分析程序自动构造（ 22） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 *i+i # E E+T E T T T*F T F F (E) F i 3 F 第六章 LR分析法及分析程序自动构造（ 23） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 *i+i # E E+T E T T T*F T F F (E) F i 2 T 第六章 LR分析法及分析程序自动构造（ 24） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 i+i # E E+T E T T T*F T F F (E) F i 2 T 7 * 第六章 LR分析法及分析程序自动构造（ 25） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 +i # E E+T E T T T*F T F F (E) F i 2 T 5 i 第六章 LR分析法及分析程序自动构造（ 26） 7 * 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 +i # E E+T E T T T*F T F F (E) F i 2 T 7 * 5 i 第六章 LR分析法及分析程序自动构造（ 27） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 +i # E E+T E T T T*F T F F (E) F i 2 T 7 * 10 F 第六章 LR分析法及分析程序自动构造（ 28） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 +i # E E+T E T T T*F T F F (E) F i 10 F 7 * 2 T 第六章 LR分析法及分析程序自动构造（ 29） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自动构造（ 19） 0 # 状态、符号栈 +i# E E+T E T T T*F T F F (E) F i 2 T 第六章 LR分析法及分析程序自动构造（ 30） 状态栈 符号栈 输入串 动作 0 # i*i+i# 05 #i *i+i# 移进 03 #F *i+i# R6归约 02 #T *i+i# R4归约 027 #T* i+i# 移进 0275 #T*i +i# 移进 02710 #T*F +i# R6归约 02 #T +i# R3归约 01 #E +i# R2归约 016 #E+ i# 移进 0165 #E+i # 移进 0163 #E+F # R6归约 0169 #E+T # R4归约 01 #E # acc 分析成功 第六章 LR分析法及分析程序自动构造（ 31） 4、 LR文法 定义：如果某一文法能够构造一张分析表， 使得表中每一元素至多只有一种明确动作， 则该文法称为 LR文法 注： 1）并非所有 CFG都是 LR文法，但对于多 数程序设计语言来说，一般都可以用 LR文法 描述 2）和 LL(1)分析法相比， LR分析法适应 的文法范围要广一些 6.1 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自动构造（ 32） 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造基本思想 构造 LR(0)分析表基本思想： 只根据历史信息识别呈现于栈顶的句柄 注： LR(0)分析表构造的思想和方法是构造 其它 LR分析法的基础 构造 LR(0)分析表基本策略 构造文法 G的一个有限自动机，它能识别文 法中的所有活前缀 第六章 LR分析法及分析程序自动构造（ 33） 1.活前缀 字的前缀是指该字的任意首部 例如：字 ABC的前缀有 e,A,AB,ABC 活前缀的概念： 指规范句型的一个前缀，这种前缀不含句柄 之后的任何符号 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 34） 例如：根据下面的文法识别输入串 abbcde 1) S aAcBe 2) A b 3) A Ab 4) B d 为每条产生式的尾部加上用 I表示的产生式序号 1) S aAcBe1 2) A b2 3) A Ab3 4) B d4 第六章 LR分析法及分析程序自动构造（ 35） 用最右推导方式来识别，推导时把序号也带上 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 若用最左归约的方式进行识别，则完全是上面的逆过 程 规范句型 abbcde的前缀有： e,a ab 规范句型 aAbcde的前缀有 : e,a,aA,aAb 规范句型 aAbcde的前缀有 : e,a,aA,aAc,aAcd 规范句型 aAbcde的前缀有 : e,a,aA,aAc,aAcB,aAcBe 第六章 LR分析法及分析程序自动构造（ 36） 1.活前缀 活前缀有两种类型： 1）归态活前缀 :活前缀的尾部正好是句柄之 尾，这时可以进行归约，归约之后又成为另 一句型的活前缀 2）非归态活前缀 :句柄尚未形成，需要继续 移进若干符号之后才能形成句柄 6.2 LR(0)项目 集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 37） 2.构造自动机识别活前缀 对于一个文法。可以构造有限自动机，它能识别 G 的所有活前缀 由于产生式右部的符号串就是句柄。若某些符号串 都已进栈，则表示它已处于 归态活前缀 。若只有部 分进栈，则表示它处于 非归态活前缀 。要想知道活 前缀有多大部分进栈了，可以为每个产生式构造一 个自动机，由它的状态来记住当前情况，此 “ 状态 ” 称为 “ 项目 ” ，这些自动机的全体就是能识别所有 活前缀的有限自动机。 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 38） 2.构造自动机识别活前缀 1）项目： 在文法的每个产生式右部添加一个圆点，就成为 G 的一个 LR(0)项目（简称项目） 注：圆点在产生式中的位置不同则是不同项目 注： （ 1）可以把圆点理解为栈内外的分界线 （ 2）产生式右部符号串的长度为 n，则可以分解 为 n+1个项目 （ 3）产生式 A e只有一个项目 A 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 39） 2.构造自动机识别活前缀 1）项目： 例如，产生式 A XYZ对应四个项目 A XYZ, 预期要归约的句柄是 XYZ，但都未进栈 A XYZ,预期要归约的句柄是 XYZ，但 X进栈 A XYZ,预期要归约的句柄是 XYZ，仅 XY进栈 A XYZ,Z处于归态活前缀， XYZ可进行归约，这 个项目就是归约项目 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 41） 2.构造自动机识别活前缀 2）由项目构造 NFA的构造方法 （ 1）将文法进行拓广，保证文法开始符号 S不出 现在任何产生式右部，即增加产生式 S S, 并令 S S作为初态项目； （ 2）凡圆点右串的最右边的项目称终态项目或 称归约项目。而 S S称为接受项目； 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 40） 2.构造自动机识别活前缀 2）由项目构造 NFA的构造方法 （ 3）设项目 i为 X X1 .Xi-1Xi Xn,项目 j为 X X1 .XiXi+1 Xn,则从项目画一弧线射向 j， 标记为 Xi;若 Xi是终结符，则项目 i称为移进项目， Xi是非终结符则称项目 i为待约项目； （ 4）若项目 i为 X aAb,其中 A是非终结符，则从 i 项目画 e弧射向所有 A g的项目， gV * 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 42） 2.构造自动机识别活前缀 2）由项目构造 NFA的构造方法 注： 1）构造出的 NFA是包含有 e串的 NFA，可以使用子 集法使之确定化，使之成为一个以项目集为状态的 DFA，这个 DFA就是建立 LR分析算法的基础 2）相应 DFA的每个状态是一个项目集，称作 LR(0) 项目集，整个状态集称为 LR(0)项目集规范簇 3）在 DFA的一个状态对应的项目集内，每个项目 是 “ 等价 ” 的，即从期待归约的角度看相同 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 43） 2.构造自动机识别活前缀 2）由项目构造 NFA的构造方法 注： 4）有一个唯一的初态和一个唯一的接受 态，但有若干个归约态，表示有若干种活前 缀的识别状态 5）状态反映了识别句柄的情况，既句柄 的大多部分已进栈，即知道了历史情况 6）手工构造文法的项目集规范簇很困难 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)分析表构造 第六章 LR分析法及分析程序自动构造（ 44） 例如：有一拓广的文法 G6.1构造识别活前缀的 NFA S E E aA|bB A cA|d B cB|d 解： 1、这个文法的项目有： 1.S E 2.S E 3.E aA 4.E aA 5.E aA 6.A cA 7.A cA 8.A cA 9.A d 10.A d 11.E bB 12.E bB 13.E bB 14.B cB 15.B cB 16.B cB 17.B d 18.B d 第六章 LR分析法及分析程序自动构造（ 45） 2.构造识别活前缀的 NFA 3 8 6 7 4 9 10 1 5 2 11 15 14 12 1 6 13 1 8 17 e a E e c e A b e d B e c B d e e e e A e 第六章 LR分析法及分析程序自动构造（ 46） 确定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A d 第六章 LR分析法及分析程序自动构造（ 47） 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)项目集规范族的构造 3. LR(0)项目集规范族的机器构造 1）拓广文法： 增加 S S产生式 ,使文法的开始符 号不出现在任何产生式右部，从而保证有唯一的接受 项目 注：即使原开始符号 S不出现在任何产生式右部， 为了统一起见也要增加该产生式 第六章 LR分析法及分析程序自动构造（ 48） 3. LR(0)项目集规范族的机器构造 2）定义和构造项目集的闭包 设 I是拓广文法 G的一个项目集，定义和构造 I的闭 包 CLOSURE(I) 构造文法： A.I的任何项目都属于 CLOSURE(I); B.若 A aBb属于 CLOSURE(I),B是非终结符 ,那 么，对于任何关于 B的产生式 B g,项目 B g也属于 CLOSURE(I); C.重复执行步骤 B,直到 CLOSURE(I)不再扩大为止 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)项目集规范族的构造 第六章 LR分析法及分析程序自动构造（ 49） 3. LR(0)项目集规范族的机器构造 3）状态转换函数 GO GO(I,X)定义为 CLOSURE(J),其中 I,J都是项目 集， X(V NV T), J=任何形如 A aXb的项目 |A aXbI 注：其含义是对于任意项目集 I,由于 I中有 A aXb项目， J中有 A aXb项目，表 示识别活前缀又移进一个符号 X 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)项目集规范族的构造 第六章 LR分析法及分析程序自动构造（ 50） 3. LR(0)项目集规范族的机器构造 4)构造 LR(0)项目集规范族的算法 过程如下： C=CLOSURE(S S) /*初态项目集 */ DO for (对 C中每个项目集 I和 G中每个文法符号 X) IF ( GO(I,X)非空且不属于 C) 把 GO(I,X)加入 C中 WHILE C 仍然在扩大 注：其中 C是集合，用于存放全部项目集 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)项目集规范族的构造 第六章 LR分析法及分析程序自动构造（ 51） 6.2 LR(0)项目集族和 LR(0)分析表的构造 注： 1）此算法是迭代算法。置了 C的初态（初态仅 包含第一个项目集）后，每经过一次 FOR语句。就 扩大一次 C中的项目集数，直到项目集数不再增加 为止。 2）此算法是从 I0开始，按该项目集内的项目顺序依 次求出所有后继项目集，由这样一层一层向下生成 的所有项目集的方法避免了项目集的遗漏。 3）若在项目集中存在 A e，不应再做 GO函数转 向其它项目集，因为 A e和 A e是同一项 目，都是 A 项目，它本身是归约项目，不存在 后继项目。 4）由这个项目集规范族 C中各个状态及状态函数 GO 可构造一张识别活前缀的 DFA图。 第六章 LR分析法及分析程序自动构造（ 52） 例如：有一拓广的文法 G6.1构造识别活前缀的 NFA S E E aA|bB A cA|d B cB|d 解： 1、这个文法的项目有： 1.S E 2.S E 3.E aA 4.E aA 5.E aA 6.A cA 7.A cA 8.A cA 9.A d 10.A d 11.E bB 12.E bB 13.E bB 14.B cB 15.B cB 16.B cB 17.B d 18.B d 第六章 LR分析法及分析程序自动构造（ 45） 3. LR(0)项目集规范族的机器构造 2）定义和构造项目集的闭包 设 I是拓广文法 G的一个项目集，定义和构造 I的闭 包 CLOSURE(I) 构造文法： A.I的任何项目都属于 CLOSURE(I); B.若 A aBb属于 CLOSURE(I),B是非终结符 ,那 么，对于任何关于 B的产生式 B g,项目 B g也属于 CLOSURE(I); C.重复执行步骤 B,直到 CLOSURE(I)不再扩大为止 6.2 LR(0)项目集族和 LR(0)分析表的构造 一、 LR(0)项目集规范族的构造 第六章 LR分析法及分析程序自动构造（ 49） 0:S E E aA E bB 第六章 LR分析法及分析程序自动构造（ 67） 0:S E E aA E bB 2: E aA A cA A dc 1:S E 3:E bB B cB B d a E b 第六章 LR分析法及分析程序自动构造（ 68） 0:S E E aA E bB 2: E aA A cA A d 1:S E 3:E bB B cB B d a E b 4:A cA A cA A d 10:A d 6:E aA c d A 第六章 LR分析法及分析程序 自动构造（ 69） 1:S E 0:S E E aA E bB 4:A cA A cA E d 2: E aA A cA E dc 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 7:E bB 11:B d c b E c a d B A d 第六章 LR分析法及分析程序自动构造（ 70） 确定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 7:E bB 11:B d 9:B cB c c b E c a B d d B A d 第六章 LR分析法及分析程序自动构造（ 71） 确定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A 第六章 LR分析法及分析程序自动构造（ 72） 3 8 6 7 4 9 10 1 5 2 11 15 14 12 1 6 13 1 8 17 e a E e c e A b e d B e c B d e e e e A e 第六章 LR分析法及分析程序自动构造（ 46） 1、 构造 LR(0)分析表 设 C=I0,I1 .In,以各项目集 Ik（ k=0, .n) 的 k作为状态 符号，并以包含 S S的项目集作为初始状态，同时将 G 文法的产生式进行编号，然后按下列步骤填写 ACTION表和 GOTO表； 1）若项目 A aab 属于 Ik的状态且 GO(Ik,a)=Ij;a为终结符， 则置 ACTIONk,a=sj;即移进 a，并转向 Ij状态。 2）若项目 A aI k,则对任何终结符 a（包括语句结 束符 #），置 ACTIONk,a=rj;即根据 j号产生式进行 归约。 6.2 LR(0)项目集族和 LR(0)分析表的构造 二、 LR(0)分析表的构造算法 第六章 LR分析法及分析程序自动构造（ 54） 确定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A d 第六章 LR分析法及分析程序自动构造（ 47） 1、 构造 LR(0)分析表 3）若项目 S S属于 Ik，则置 ACTIONk,#=accept,简写 acc； 4）若 GO(Ik,A)=Ij,A是非终结符，则置 GOTOk,A=j； 5）分析表中凡不能用步骤 1至 4填入信息的空白项， 均置上出错标志。 6.2 LR(0)项目集族和 LR(0)分析表的构造 二、 LR(0)分析表的构造算法 第六章 LR分析法及分析程序自动构造（ 55） 2.LR(0)文法 定义：若文法 G按上面算法构造出来的分析表 不包含多重定义项，则该文法 G是 LR(0)文法。 注： 1）这说明 LR(0)文法的每个项目集中不 包含有任何冲突项目 2） LR(0)文法的能力很弱，没有使用价 值，但可以利用它的构造算法来构造出其它 LR分析表。 6.2 LR(0)项目集族和 LR(0)分析表的构造 二、 LR(0)分析表的构造算法 第六章 LR分析法及分析程序自动构造（ 56） 例如：下面的文法是 LR(0)文法，但对这个文法的 各个产生式给予编号并写成： 0.S E 1.E aA 2.E bB 3.A cA 4.A d 5.B cB 6.B d 第六章 LR分析法及分析程序自动构造（ 57） 确定化后 1:S E 0:S E E aA E bB 4:A cA A cA A d 2: E aA A cA A d 3:E bB B cB B d 5:B cB B cB B d 6:E aA 10:A d 8:A cA 7:E bB 11:B d 9:B cB c c b E c c a B d d B A d A d 第六章 LR分析法及分析程序自动构造（ 47） 例如：下面文法 G的 LR(0)项目集规范族中含有如下一个项 目集（状态） I : I=X d bb /*移进项目 */ A a /*归约项目 */ B a /*归约项目 */ 这三个项目告诉我们应做的动作各不相同，出现了移 进 归约冲突和归约 归约冲突。这个文法一定不是 LR(0)文法 第六章 LR分析法及分析程序自动构造（ 59） 6.3 SLR分析表的构造 SLR是的一种改进，它在归约时除了考虑历史情况 之外还考虑了一点现实。 一、消除冲突 1、一个有冲突的项目集。可以根据读头下符号的 不同来消除冲突。 一般而言，对于任何形如 I=X d bb, A a, B a 的 LR(0)项目集，若 Follow(A) Follow(B)= 且 b Follow(A)， b Follow(B),则可以根据当前读头下符号 a来消除 冲突，即在构造分析表的算法中做一些改变 第六章 LR分析法及分析程序自动构造（ 60） 6.3 SLR分析表的构造 一、消除冲突 1)若当前输入符 a=b,做移进 ; 2)若当前输入符 aFollow(A), 按 A a产 生式归约； 3)若当前输入符 aFollow(B), 按 B a产 生式归约； 4)其他，报错。 二、构造 SLR分析表的算法 设 C=I0,I1, .In以各项目集 Ik(k=0, .n)作的 k为状态序号，并以 S S包含的项目集作为初始 状态，同时将产生式进行编号，然后按下列步骤填 写 ACTION表和 GOTO表： 1）若项目 A aab属于 Ik状态且 Go(Ik,a)=Ij， a为 终结符，则置 ACTIONk,a=Sj；即：移进 a，并转向 Ij状态。 2）若项目 A a IK。则对任何终结符 a Follow(A) ，置 ACTIONk,a=rj；其中 j为产生 式 A a的编号，即根据 j号产生式 A a进行归 约 第六章 LR分析法及分析程序自动构造（ 84） 6.3 SLR分析表的构造 6.3 SLR分析表的构造 二、构造 SLR分析表的算法 3）若项目 S S属于 Ik，则 ACTIONk,#=acc； 4）若 GO(Ik,A)=Ij， A是非终结符，则 GoTok,A=j； 5）分析表中凡不能用步骤 1至 4填入信息的空白项， 均置上 “ 出错标志 ” 。 注： 1）若文法按上面算法构造出来的分析表不包含 多重定义项，则该文法 G是 SLR文法。 2）二义文法决不是 LR文法 3） SLR分析法包含的展望信息是体现在利用了 Follow(A)信息，可以解决 “ 归约 归约 ” 冲突。 4） SLR分析法没有包含足够的展望信息，不能完 全解决 “ 移进 归约 ” 冲突，需要改进。 第六章 LR分析法及分析程序自动构造（ 85） 例如：试构造表达式文法 G(E)的 SLR分析表 0.S E 1.E E+T 2.E T 3.T T*F 4.T F 5. F (E) 6.F i 解 :按照求 LR(0)项目集规范族的算法 ,求得 G(E)文法 得项目集族如下图 : 6.3 SLR分析表的构造 二、构造 SLR分析表的算法 第六章 LR分析法及分析程序自动构造（ 86） I5:F i I0:S E E E+T E T T T*F T F F (E) F i I2:E T T T*F I1:S E E E+T I4:F (E) E E+T E T T T*F T F F (E) F i I3:T F I6:E E+T T T*F T F F (E) F i I10:T TF I7:T T*F F (E) F i I9:E E+T T T*F I8:F (E) E E+T I11:F (E) i i ( F T I2 ( I4 T T E ) E F * F i ( I5 I3 I5 i + ( 第六章 LR分析法及分析程序自动构造（ 87） F * 6.3 SLR分析表的构造 二、构造 SLR分析表的算法 构造 SLR分析表时要注意项目集族中 I1,I2,I9 三个项目集 ,其中含有冲突 : I1:S E I2:E T I9:E E+T E E+T T T*F T T*F 根据原来的文法分别求 S ,E的 Follow集 ,按 SLR方法进行分析 ,得 第六章 LR分析法及分析程序自动构造（ 88） 状态 ACTION GOTO i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 S7 r1 r1 10 r3 r3 r3 r3 第六章 LR分析法及分析程序自动构造（ 89） 例：一个非 SLR文法的例子 ,有如下文法 : 1.S S 1.S L=R 3.S R 4.L *R 5.L i 6. R L 按照求 LR(0)项目集规范族的算法 ,求得 G(S)文法得 项目集族如下图 : 6.3 SLR分析表的构造 二、构造 SLR分析表的算法 第六章 LR分析法及分析程序自动构造（ 90） 5:L i 0:S S S L=R S R L *R L I R L 3:S R 4: L *R R L L i L i 6:S L=R R L L *R L i 8:R L 7:L *R 2:S L=R R L 1:S S 9:S L=R = i S * * i R i * L L R R 第六章 LR分析法及分析程序自动构造（ 91） L 状态 ACTION GOTO = i * # S L R 0 S5 S4 1 2 3 1 acc 2 S6/ r6 r6 3 r3 4 S5 S4 8 7 5 r5 r5 6 S5 S4 8 9 7 r4 r4 8 r6 r6 9 r2 第六章 LR分析法及分析程序自动构造（ 69） 一 在构造 SLR分析表的方法中 ,若项目集 Ik中含有 A a,那么在状态 K时 ,只要面临输入符号 aFOLLOW(A), 就确定采用 A a产生式进行归约 .但 是在某种情况下 ,当状态 k呈现于栈顶时 ,栈里的符号 串所构成的活前缀 ba未必允许把 a规约成 A.因为可能 没有一个规范句型含有前缀 bA.因此此时用 A a产 生式进行归约未必有效 . -我们可以从上例中看到这个问题 6.4 规范 LR分析表的构造 对 SLR分析的思考 第六章 LR分析法及分析程序自动构造（ 93） 5:L i 0:S S S L=R S R L *R L I R L 3:S R 4: L *R R L L i L i 6:S L=R R L L *R L i 8:R L 7:L *R 2:S L=R R L 1:S S 9:S L=R = i S * * i R i * L L R R 第六章 LR分析法及分析程序自动构造（ 91） L 6.4 规范 LR分析表的构造 结论 : 一由此看出 ,并非随符都出现在规范句型中 . 对策 : 一给每个 LR(0)项目添加展望信息 ,即添加句柄之后可 能跟的终结符 ,因为这些终结符确实是规范句型中 跟在句炳之后的 .这就是 LR(1)的方法 . 可能引起的问题 一故 ,LR(1)项目是对 LR(0)项目的分裂 ,若文法中终结 符的数目为 n,则每个 LR(0)项目都可以分裂成 n个 LR(1)项目 .这可能会引起分析表的膨胀 . 第六章 LR分析法及分析程序自动构造（ 95） 6.4 规范 LR分析表的构造 一、相关定义 1、 LR(1)项目：形如（ A ab,a)的二元式称为 LR(1)项目，其中， A ab是文法的一个产生式， a是终结符，称为搜索符。 1） LR(1)项目是对 LR(0)项目的分裂，若文法中终结 符的数目为 n，则每个 LR(0)项目可以分裂成 n个 LR(1)项目。 2）（ A ab,a)的含义：预期当栈顶句柄 ab形成 后，在读头下读到 a，此时 a在栈内， b还未入栈， 那它展望了句柄后的一个符号。 第六章 LR分析法及分析程序自动构造（ 72） 6.4 规范 LR分析表的构造 一、相关定义 2、有效项目： 一若存在规范推导 S dAw dabw,其中 da 称规范句型 dabw的活前缀（记作 g),aFirst( w), 则 LR(1)项目（ A ab,a)对于活前缀 g是有效的， 如果 aFirst （ w),即使 aFollow(A), 项目（ A ab,a)也是无效的。 注： 1）规范 LR分析法仅考虑有效的 LR(1)项目，在 LR(1)项目中有效的项目并不多。 2）对于多数程序设计语言，向前展望一个符 号就是足以决定归约与否，所以只研究 LR(1). 第六章 LR分析法及分析程序自动构造（ 97） 例：对非 SLR文法的例子。有如下文法： -1.S S 2.S aAd -3.S bAc 4.S aec -5.S bed 6.A e 按照求 LR(0)项目集规范族的算法，求得 G(S)文法 得项目集族，其中某状态中发生移进 -归约冲突： Ix:S aec A e 由于规范推导为： S S aAd aed S S aec 第六章 LR分析法及分析程序自动构造（ 98） 这两个最右推导中已包含了活前缀为 ae的所 有句型，可见 “ aAc”决不会是规范句型，即： 归约成非终结符 “ A”之后。其后决不会跟 “ c”. 故：虽然 Follow(A)=c,d,但是（ A e,c) 对活前缀 ae是无效的，仅（ A e,d)是有 效的。 第六章 LR分析法及分析程序自动构造（ 99） 6.4 规范 LR分析表的构造 二、构造 LR(1)项目集规范族的算法 1、函数 CLOSURE(I)I的项目集 (1)I的任何项目都属于 CLOSURE(I); (2)若项目 (A aBb,a)属于 CLOSURE(I),B g是 一个产生式，那么对于 FIRST(ba)中的每个终结符 b， 如果 (B g,b)原来不在 CLOSURE(I)中，则把它 加进去； (3)重复步骤 (2)直到 CLOSURE(I)不再扩大为止。 注：因为 (A aBb,a)属于 CLOSURE(I),那么 (B g,b)当然也属于 CLOSURE(I),其中 b必定是跟在 B后面的终结符，即 bFirst( ba).若 b=e,则 b=a 第六章 LR分析法及分析程序自动构造（ 100） 6.4 规范 LR分析表的构造 二、构造 LR(1)的项目集规范族的算法 2、 GO函数 令 I是一个项目集， X是文法符号，函数 GO(I,X)定义为 GO(I,X)=CLOSURE(J) -其中 J=任何形如（ A aXb,a)的项目 (A aXb,a) I 注：在执行转换函数 GO时，搜索符并不改变。 第六章 LR分析法及分析程序自动构造（ 101） 6.4 规范 LR分析表的构造 3、构造拓广文法的 LR(1)项目集族 C的算法 PROC ITEMSETLR1 C=CLOSURE (S S,#); DO FOR C中的每个项目集 I和 G的每个文法符号 X IF GO(I,X)非空且不属于 C 把 GO(I,X)加入 C中； WHILE C 依然扩大； 第六章 LR分析法及分析程序自动构造（ 102） 例：有如下文法： 1.S S 2.S L=R 3.S R 4.L *R 5.L i 6.R L 按照求 LR(1)项目集规范族的算法 ,求 G(S)文法的项 目集族 解 :1、求初态项目集 I0:从（ S S ,#)项目开始 求闭包 得： 第六章 LR分析法及分析程序自动构造（ 103） I0初态 S S,# S L=R,# S R,# L *R,= L i,= R L,# L *R,# L i,# I0初态 S S,# S L=R,# S R,# L *R,=|# L i,=|# R L,# 缩写为 2、接着利用 GO函数，对该项目集内得各项目求后继项目集， 然后再对新求的项目集重复上面的过程，直到项目集不再 增加为止。 第六章 LR分析法及分析程序自动构造（ 104） 5:L i,=|# 0 S S, S L=R,# S R,# L *R,=|# L i,=|# R L,# 3:S R,# 4: L *R,=|# R L,# L i, =|# L i, =|# 6:S L=R,# R L,# L *R,=|# L i, =|# 8:R L,# 7:L *R, =|# 2:S L=R,# R L,# 1:S S ,# 9:S L=R,# = i S * * i R i * L L R R 第六章 LR分析法及分析程序自动构造（ 91） L I10 I12 6.4 规范 LR分析表的构造 三、构造 LR(1)分析表的算法 设 C=I0,I1, .In,以各项目集 Ik(k=0,1, .n)的下标 k为分 析表中的状态，并以包含（ S S,#)的项目的状态为分析 表初态。按下列步骤填写 ACTION表和 GOTO表： 1）若项目（ A aab,b)属于 Ik，且 GO(Ik,a)=Ij,a为终结符， 则置 ACTIONk,a=Sj;即：移进 a,并转向 Ij状态。 2）若项目（ A a,a) I k,则置 ACTIONk,a=rj;其中 j为 产生式 A a的编号，即根据 j号产生式 A a进行归约 第六