首页 结束
LR(0)项目集规范族的构造
定义：构成识别一个文法活前缀的DFA项目集 （状态）的全体，称为这个文法的LR(0)项目集 规范族。
编 译 原 理
LR
(一) LR（0）项目
在每个产生式的右部适当位置添加一个圆点构成 项目（item）。每个项目的含义和圆点的位置有 关。项目圆点的左部表示分析过程的某个时刻用 该产生式归约时句柄已识别的部分，圆点右部表 示待识别的部分。
分 析
【例】演示
首页 结束
每一项ACTION[S，aJ所规定的动作是下述4种可能之--： (1)移进：把(S，a)的下一状态S’ =ACTION[S，a]和输 入符号a推进栈（对终结符，GOTO[S，a]的值已放入 ACTION[S，a]中)，下一个· 输入符号变成现行输入符号。
编 译 原 理
LR
首页 结束
分 析
编 译 原 理
LR
对于--个文法，如果能构造一张分析表，使得它的每个 入口均是唯一确定的，则把这个文法称为LR文法。对于 一个LR文法，当分析器对输入串进行自左至右扫描时， 一旦句柄呈现于栈顶，就能及时对它实行归约。 一个LR分析器有时需要“展望”和实际检查未来 的k个输入符号才能决定应采取什么样的“移进一归约” 决策。一般而言， 一个文法如果能用一个每步顶多向前 检查K个输入符号的LR分析器进行分析，则这个文法就 称为LR(k)文法。 对于一个文法，如果它的任何"移进一归约"分析器都 存在尽管栈的内容和符号都已了解，但无法确定是“移 进”还是“归约”；或者，无法从几种可能的规约中确 定其一的情形，那么这个文法就是非LR(1)的。
【例】
分 析
A->a.Xb
X
A->aX.b
构造文法G的LR(0) 项目集规范族的方法 :
把文法的所有产生式的项目都引出，每个项目都 为NFA的一个状态。其中文法的第一个产生式的 第一个项目S’→ . S为文法的初态集的核心项。 a)置项目S’→ . S为初态集的核心项后，对核心 编 项求闭包CLOSURE（{S’→ . S}）得到初态的项目 译 集 原 b)对初态集或其它所构造的项目集应用转换函 理 数GOTO(I，X)= CLOSURE(J)求出新状态J的项 LR 目集 c)重复b)直到不出现新的项目集为止 分
编 译 原 理
LR
分 析
（2）闭包函数CLOSURE(I) 如果I是文法G’的一个项目集，定义和构造I 的闭包CLOSURE(I)如下： a)I的项目都在CLOSURE(I)中 b)若A→a . Bb属于CLOSURE(I)，则每一 形如B→. g的项目也属于CLOSURE(I) c)重复b)直到CLOSURE(I)不再扩大。 【说明】求闭包函数的过程实际上就是求 所有等价状态的过程。
分 析
是符号串的任意首部。活前缀就是可归前缀 的任意首部。
首页 结束
编 译 原 理
LR
【例如】 可归前缀ab的活前缀为ε,a,ab 可归前缀aAb的活前缀为ε,a,aA,aAb 可归前缀aAcd的活前缀为ε,a,aA,aAc,aAcd 可归前缀aAcBe的活前缀为ε,a,aA,aAc,aAcB,aAcBe
分 析
一、LR(k)分析法
L ：从左到右扫描输入符号，
R ：最右推导对应的最左归约,
k ：超前读入k个符号，用以确定归约所用的规则。
编
LR分析法在自左至右扫描输入串时就能发现其中 译 的任何错误．并能准确地指出出错地点。 原 大多数用上下文无关文法描述的程序语言都可用 理 LR分析器予以识别。 LR 主要缺点是，用手工构造分析程序则工作量相当 分 大。因此，必须求助于自动产生这种分析程序的产 析 生器。 首页 结束
第七章
LR分析法
教学目的：让学生了解LR分析方法的基
编 译 原 理
LR
本思想，掌握LR(0) 、SLR(1) 、LR(1)、 LALR(1) 分析法。 教学重点： LR（0）分析、LR（l）分 析、SLR（1）分析和LALR（1）分析； 构造LR分析的分析表。
课时分配：8学时
分 析
本章知识点(内容)
首页 结束
分 析
编 译 原 理
LR
由于最右推导就是规范推导，因此句型 aAcBe、aAcde、aAbcde、abbcde为规范句型。 规范句型的这种前部分符号串称为可归前缀。 【例如】 符号串aAcBe是规范句型aAcBe的可归前缀， aAcd是规范句型aAcd[4]e[1]的可归前缀， aAb是规范句型aAb[3]cd[4]e[1]的可归前缀， ab是规范句型ab[2]b[3]cd[4]e[1]的可归前缀。 我们把形成可归前缀之前包括可归前缀在内的 所有规范句型的前缀都称为活前缀。所谓前缀就
分 析
首页 结束
如何识别文法符号栈中的内容就是活前缀
由于活前缀实际上就是满足一定要求的符号 串，因此识别活前缀的工作和识别单词的工作非 常类似，所以我们可以采用有穷自动机这种数 据模型来实现活前缀的识别。
编 译 原 理
LR
分 析
识别活前缀的有穷自动机的构造
编 译 原 理
LR
基本思想是我们可以把文法的终结符和非 终结符都看成有穷自动机的输入符号，每次把一 个符号进栈看成已识别过了该符号，同时状态进 行转换，当识别到可归前缀时，相当于在栈中形 成句柄，达到了识别句柄的终态。
首页 结束
编 译 原 理
LR
分 析
规范句型活前缀
一、活前缀和可归前缀的形式定义
若S’ αAγ αβγ,则称αβ为可归前缀; 若有串W是 αβ的前缀，则称W是G的一个活前缀（S‘为文法拓广后的 开始符，它只出现在规则左部）。可归前缀是包含句柄的 活前缀。
编 译 原 理
LR二Biblioteka 说明：规范句型的活前缀有两个要点: (1)它是规范句型的前缀; (2)它不含句柄右侧符号
分 析
首页 结束
实现识别活前缀的有穷自动机的构造有两种 方法：
编 译 原 理
LR
分 析
方法1： 由文法的产生式直接构造识别活前缀和可归前 缀的有穷自动机 方法2： 通过构造文法G的LR(0)的项目集规范族来直 接构造识别活前缀的DFA 【说明】由于NFA确定化为DFA的工作量较大，我 们考虑直接构造出项目集规范族作为DFA的状态， 来构造DFA。
编 译 原 理
LR
LR分析法：
[1] 对文法限制少；[2] 适用范围广； [3] 分析速度快； [4]报错准确。 [5] 易于实现自动生成。由于构造分析器的工作量很大， 不大可能手工构造；如用软件工具Yacc-Yet Another Compiler Compiler,Bell，这些软件工具叫LR生成器。
LR分析概述
编 译 原 理
LR
LR（0）分析 SLR（1）分析 LR（1）分析 LALR（1）分析
分 析
二义文法在LR分析中的应用
7.1 LR(Left-Right)分析概述
算符优先分析法存在的问题
强调算符之间的优先关系的唯一性，这使得它的 适应面比较窄；算法在发现最左素短语的尾时，需要 返回来寻找对应的最左素短语头。
首页 结束
编 译 原 理
LR
分 析
输入缓冲区
a1 … ai … an #
状态栈 符号栈
编 译 原 理
LR Sm Sm-1 … … … S1 S0 Xm Xm-1 … … … X1 #
LR总控程序
输出规则 序列
分 析
动作表 action
转移表 goto
首页
分析表
结束
编 译 原 理
LR
分析表包括两部分： 一部分是（ACTION)表，另一部分是"状态转 换"(GOTO)表。它们都是二维数组。 ACTION[S，a]中规定了当状态S面临输入符号 a时应采取什么动作。 GOTO[S，X]规定了状态S面对文法符号X(终结 符或非终结符)时下一状态是什么。 显然，GOTO[S，X]定义了一个以文法符号为 字母表的DFA。
首页 结束
分 析
7.2
LR(0)分析法
【例】已知文法G[S]，分析符号串abbcde是否是
编 译 原 理
LR
G[S]的句子 。 (1) S → aAcBe[1] (2) A → b[2] (3) A → Ab[3] (4) B → d[4] 【解】这里每个产生式的右部字符串末尾的编号是为了
方便查看在最右推导中是选择哪个产生式推导的，并不是 产生式的一部分。 句子的最右推导过程为： S =>aAcBe[1] =>aAcd[4]e[1]=>aAb[3]cd[4]e[1]=>ab[2]b[3]cd[4]e[1]
首页 结束
分 析
编 译 原 理
LR
根据圆点所在的位置和圆点后是终结符还是非终 结符把项目分为以下几种： 1、移进项目，形如 A →a . ab 2、待约项目，形如 A →a . Bb 3、归约项目，形如 A →a . 4、接受项目，形如 S’→S .
分 析
首页 结束
编 译 原 理
LR
【例】产生式S→aAcBe对应的6个项目是： [0]S→.aAcBe [1]S→a.AcBe [2]S→aA.cBe [3]S→aAc.Be [4]S→aAcB.e [5]S→aAcBe.
分 析
首页 结束
一个产生式可对应的项目为它的右部符号长度加 1，对空产生式
A-> ε 仅有一个项目 A->.
编 译 原 理
LR
【例】产生式A->X YZ 对应4个项目
A->.XY Z
A->X· YZ
A->X Y· Z
A->X YZ·
首页 结束
分 析
（二）LR(0)项目集规范族的构造