自底向上分析－ LR分析概述
? 自底向上分析的思想和主要问题
? 几种 LR分析方法：
LR(0)
SLR(1)
LR(1)
LALR(1)
主要内容：
LR的几个基本概念
线性正则式的状态机 LRSM
? 短语,设 S是文法的开始符,???是句型 (即
有 S ?*???）,如果满足条件：
? S ?* ?A?
? A ?+ ?
? 则称 ?是句型 ???的一个短语。
? 直接短语（简单短语）,如果满足条件：
? S ?* ?A?
? A ? ?
? 则称 ?是句型 ???的一个简单短语。
? 句柄,一个句型可能有多个简单短语，其中
最左的简单短语称之为句柄。
一个有用的定理
? 定义,由某一结点及其所属分支组成的部分
树称为原树的一颗子树。只有单层分支的子
树称为简单子树。
? 定理：
? 1.每个句型都有一颗语法树，每个语法
树的叶组成一句型。
? 2.每棵子树的叶组成短语，每颗简单子
树的叶组成简单短语，最左简单子树的叶组
成句柄。
?句型, (T+i)*i+F
E
E + T
T
T * F
iF
( E )
E + T
T
i
F
F
?短语：
1.(T+i)*i+F
2.(T+i)*i
3.(T+i)
4.T+i
5.T
6.第一个 i
7.第二个 i
8.F
?简单短语：
T,第一个 i,第二个 i,F
?句柄,T
? 规范句型,用最右推导导出的句型 (也称右句
型）。
? 规范前缀,若存在规范句型 ??，且 ?是终极符
串或空串，则称 ?为规范前缀。
? 规范活前缀,若规范前缀 ?不含句柄或含一个
句柄并且具有形式 ?=???(?是句柄 )，则称规范
前缀 ?为规范活前缀 (简称活前缀）。
? 归约规范活前缀,若活前缀 ?是含句柄的活前
缀，即有 ?=???，且 ?是句柄，则称活前缀 ?为
归约规范活前缀（简称归约活前缀）。
例,S ? aAcBe [1]
A ? b [2]
A ? Ab [3]
B ? d [4]
输入流,abbcde。
规范推导过程为：
逆过程,(分析栈，输入流 )
( -,abbcde)
?(a,bbcde)
?(ab,bcde)
?(aA,bcde)
?(aAb,cde)
?(aA,cde)
?(aAc,de)
?(aAcd,e)
?(aAcB,e)
?(aAcBe,-)
?(S,-)
S ? aAcBe[1]
? aAcd[4]e[1]
? aAb[3]cd[4]e[1]
? ab[2]b[3]cd[4]e[1]
? 活前缀的描述性定义,形成可归前缀之
前，包括可归前缀在内所有规范句型的
前缀都称为活前缀。
? 活前缀 为一个或若干规范句型的前缀。
? 在规范归约过程中的任何时刻已分析过
的部分，即在分析栈（符号栈）中的符
号串均为 规范句型的活前缀,表明输入
串的已被分析过的部分是该文法某规范
句型的一个正确部分。
线性正则式状态机－ LRSM
? 线性正则式,不含 *符号的正则表达式
?LRSM,(Linear Regular States Machine)
(1)从 LRSM可构造出恰好接受给定所有正
则式的确定自动机 DA；
(2)从 LRSM的终止状态可判定接受的是哪
个正则式；
(3)从 LRSM的状态可判定一个正则式是不
是另一正则式的前缀。
? 项目,假设 ??[P]是一个正则式，则我们称形
如 ???[P]的表示为项目，其中 P是正则式编号。
其中黑点可出现于任何位置上。
? 项目集,用 IS表示
?IS(X),
SubItems(IS,X)=
{?X??[P]|??X?[P]?IS,X?SymbSet}
简记为 IS(X)
假设有线性正则项集,
IS = {?abd[1],?abc[2],?bc[3],de?[4],
de?c[5]},
则有,
IS(a) = { a?bd[1],a?bc[2] }
IS(b) = { b?c[3] }
IS(c) = { dec?[4] }
线性正则式到 LRSM的构造
给定正则式集 {?1,?2,… ?n}：
■ 构造初始项目集 IS0={??1[1],...,??n[n]},并给 IS0
标上 NO(表示未处理 ） 。
■ 从已构造的 LRSM部分图选择被标为 NO的任一项目集
ISi,并做下面动作：
[1] 对每个符号 X?SymbSet：
若 ISiX非空, 给 ISiX标上 NO,并在 ISi和 ISiX之间
画有向 X边,ISi → ISiX。
[2] 给 ISi标上 OK。
■ 重复上述步骤二，直至在 LRSM中没有被标记为 NO的
状态（项目集）结点为止。
a b
d
c
d
b
e
c
d
?abc[1]
?abd[2]
?ad[3]
?bec[4]
?bed[5]
S0
a?bc[1]
a?bd[2]
a?d[3]
S1=S0a
ab?c[1]
ab?d[2]
S3
b?ec[4]
b?ed[5]
S2
be?c[4]
be?d[5]
S5
abc?[1]
S6
abd?[2]S
7
ad?[3]
S4
bec?[4]
S8
bed?[5]
S9
正则式到 LRSM的转换例
LRSM的性质
? 展望符, Lookup(S)
? 有效前缀集 Prefix(S)
? 状态 Si中的项目 ???[P]表示 ?部分已被输
入，而且是 Si的前缀的后缀,?表示待输
入部分。
? 可构造接受给定正则式集合的 DA
? 严格前缀,某状态中既含有定位点在尾处
的项目又含有定位点不在尾处的项目，则
一个正则式是另一个正则式的严格前缀。
? 作业：
? 书 Page129 习题 7,8
? 文法 G[E]:
E ? T | E + T
T ? F | T * F
F ? ( E ) | i
i (1) *i (2) +i (3)是 G的一个句子，
（ 1） 画出该句子的语法分析树
（ 2）给出该句子的所有短语，简单短语，句柄
? 自底向上分析的思想和主要问题
? 几种 LR分析方法：
LR(0)
SLR(1)
LR(1)
LALR(1)
主要内容：
LR的几个基本概念
线性正则式的状态机 LRSM
? 短语,设 S是文法的开始符,???是句型 (即
有 S ?*???）,如果满足条件：
? S ?* ?A?
? A ?+ ?
? 则称 ?是句型 ???的一个短语。
? 直接短语（简单短语）,如果满足条件：
? S ?* ?A?
? A ? ?
? 则称 ?是句型 ???的一个简单短语。
? 句柄,一个句型可能有多个简单短语，其中
最左的简单短语称之为句柄。
一个有用的定理
? 定义,由某一结点及其所属分支组成的部分
树称为原树的一颗子树。只有单层分支的子
树称为简单子树。
? 定理：
? 1.每个句型都有一颗语法树，每个语法
树的叶组成一句型。
? 2.每棵子树的叶组成短语，每颗简单子
树的叶组成简单短语，最左简单子树的叶组
成句柄。
?句型, (T+i)*i+F
E
E + T
T
T * F
iF
( E )
E + T
T
i
F
F
?短语：
1.(T+i)*i+F
2.(T+i)*i
3.(T+i)
4.T+i
5.T
6.第一个 i
7.第二个 i
8.F
?简单短语：
T,第一个 i,第二个 i,F
?句柄,T
? 规范句型,用最右推导导出的句型 (也称右句
型）。
? 规范前缀,若存在规范句型 ??，且 ?是终极符
串或空串，则称 ?为规范前缀。
? 规范活前缀,若规范前缀 ?不含句柄或含一个
句柄并且具有形式 ?=???(?是句柄 )，则称规范
前缀 ?为规范活前缀 (简称活前缀）。
? 归约规范活前缀,若活前缀 ?是含句柄的活前
缀，即有 ?=???，且 ?是句柄，则称活前缀 ?为
归约规范活前缀（简称归约活前缀）。
例,S ? aAcBe [1]
A ? b [2]
A ? Ab [3]
B ? d [4]
输入流,abbcde。
规范推导过程为：
逆过程,(分析栈，输入流 )
( -,abbcde)
?(a,bbcde)
?(ab,bcde)
?(aA,bcde)
?(aAb,cde)
?(aA,cde)
?(aAc,de)
?(aAcd,e)
?(aAcB,e)
?(aAcBe,-)
?(S,-)
S ? aAcBe[1]
? aAcd[4]e[1]
? aAb[3]cd[4]e[1]
? ab[2]b[3]cd[4]e[1]
? 活前缀的描述性定义,形成可归前缀之
前，包括可归前缀在内所有规范句型的
前缀都称为活前缀。
? 活前缀 为一个或若干规范句型的前缀。
? 在规范归约过程中的任何时刻已分析过
的部分，即在分析栈（符号栈）中的符
号串均为 规范句型的活前缀,表明输入
串的已被分析过的部分是该文法某规范
句型的一个正确部分。
线性正则式状态机－ LRSM
? 线性正则式,不含 *符号的正则表达式
?LRSM,(Linear Regular States Machine)
(1)从 LRSM可构造出恰好接受给定所有正
则式的确定自动机 DA；
(2)从 LRSM的终止状态可判定接受的是哪
个正则式；
(3)从 LRSM的状态可判定一个正则式是不
是另一正则式的前缀。
? 项目,假设 ??[P]是一个正则式，则我们称形
如 ???[P]的表示为项目，其中 P是正则式编号。
其中黑点可出现于任何位置上。
? 项目集,用 IS表示
?IS(X),
SubItems(IS,X)=
{?X??[P]|??X?[P]?IS,X?SymbSet}
简记为 IS(X)
假设有线性正则项集,
IS = {?abd[1],?abc[2],?bc[3],de?[4],
de?c[5]},
则有,
IS(a) = { a?bd[1],a?bc[2] }
IS(b) = { b?c[3] }
IS(c) = { dec?[4] }
线性正则式到 LRSM的构造
给定正则式集 {?1,?2,… ?n}：
■ 构造初始项目集 IS0={??1[1],...,??n[n]},并给 IS0
标上 NO(表示未处理 ） 。
■ 从已构造的 LRSM部分图选择被标为 NO的任一项目集
ISi,并做下面动作：
[1] 对每个符号 X?SymbSet：
若 ISiX非空, 给 ISiX标上 NO,并在 ISi和 ISiX之间
画有向 X边,ISi → ISiX。
[2] 给 ISi标上 OK。
■ 重复上述步骤二，直至在 LRSM中没有被标记为 NO的
状态（项目集）结点为止。
a b
d
c
d
b
e
c
d
?abc[1]
?abd[2]
?ad[3]
?bec[4]
?bed[5]
S0
a?bc[1]
a?bd[2]
a?d[3]
S1=S0a
ab?c[1]
ab?d[2]
S3
b?ec[4]
b?ed[5]
S2
be?c[4]
be?d[5]
S5
abc?[1]
S6
abd?[2]S
7
ad?[3]
S4
bec?[4]
S8
bed?[5]
S9
正则式到 LRSM的转换例
LRSM的性质
? 展望符, Lookup(S)
? 有效前缀集 Prefix(S)
? 状态 Si中的项目 ???[P]表示 ?部分已被输
入，而且是 Si的前缀的后缀,?表示待输
入部分。
? 可构造接受给定正则式集合的 DA
? 严格前缀,某状态中既含有定位点在尾处
的项目又含有定位点不在尾处的项目，则
一个正则式是另一个正则式的严格前缀。
? 作业：
? 书 Page129 习题 7,8
? 文法 G[E]:
E ? T | E + T
T ? F | T * F
F ? ( E ) | i
i (1) *i (2) +i (3)是 G的一个句子，
（ 1） 画出该句子的语法分析树
（ 2）给出该句子的所有短语，简单短语，句柄
