1
2.3 句型的分析
? 句型的分析,构造一算法，用以判断所给的符号串是
否为某文法的句型
? 常见分析方法有 自顶向下分析 和 自底向上分析 两类；
? 自顶向下 从开始符出发，试图推导出给定的符号串；
? 自底向上 从已给的符号串出发，试图将其 归约 为开始
符。归约：是推导的逆过程,即将某一符号子串替换成
相应产生式的左部变量。
.,,,][4.2
**
的一个句型是则称若是文法设定义 GSVSG
G
??? ??
2
2.3.1 规范推导和规范归约
问题, 根据文法 G2[E],从 E推导出 i+i*i,
(1)E? E+T? E+T*F? T+T*F? T+T*i
? F+T*i? i+T*i? i+F*i?i+i*i
(2)E? E+T? T+T? F+T? i+T? i+T*F
? i+F*F? i+i*F? i+i*i
(3)E? E+T? E+T*F? E+T*i? E+F*i
? E+i*i ? T+i*i? F+i*i? i+i*i
(4) … …
? 对于一文法而言，从开始符到某句型的 推导过程可能
不唯一 。
最左推导
最右推导
G2[E],
E?E+T|T
T?T*F|F
F?(E)|i
3
规范推导
? 为了让计算机实现推导的自动进行，引入推导时非终
结符的替换顺序。
? 最左（右）推导, 在推导序列的每一步直接推导中，
被替换的总是当前句型中最左（右）的非终结符。
? 形式定义,设有从符号串 ?到符号串 ?的推导序列
其中,xUy ? xuy表示该推导序列中的任一直接推导，
如果总有 x?VT*，则该推导序列为 最左推导 ；如果总
有 y?VT*,则该推导序列为 最右推导，最右推导 也称
为 规范推导。
,??
??
??? x u yx Uy
4
规范句型
? 由 最左推导 推出的句型称为 左句型 ；由 最右推导 或 规
范推导 推出的句型称为 右句型 或 规范句型 。
? 每个 句子 都有相应的最左和最右（规范）推导，因此，
句子即是 左句型 也是 右句型 （规范句型）
? 但并不是每个 句型 都有最左和最右推导。 例如，句型
T*i+T有唯一推导,
E ? E+T ? T+T ?T*F+T ?T*i+T
上述推导既不是最左推导，也不是最右推导，因此
T*i+T既不是左句型，也不是右句型。
5
自顶向下的语法分析
? 对于给定的符号串 w，采用 自顶向下 的分析来判断 w是
否为 L(G[S])的句子的方法是,建立从开始符 S到 w的
最左推导, S?* w
? 每步推导时，对应于最左非终结符相应的产生式可能
会有多个，如,此时就面临一个
如何选择候选式的问题。除非有办法预先知道哪个候
选式有用，否则 只能一个一个地试探。因此，推导过
程可能是 带回溯 的。
? 带回溯的语法分析效率大大降低，为提高效率，就应
尽量避免回溯（不带回溯的 LL分析方法） 。
nU ??? ||| 21 ??
6
自底向上的语法分析 —— 归约
? 归约 是 推导的逆过程，是把当前的符号串 ???中构成
文法某个产生式 A??右部的子串 ?替换成产生式的左
部符号 A，得到一个新的符号串 ?A? 。这样的一步动作，
称为进行了一步 归约 。
? 例如，符号串 F+i*i中的 F可按产生式 T?F归约为 T，
从而得到新的符号串 T+i*i。
? 若归约的每一步都归约的是当前符号串中最左边的某
产生式的右部，则称该归约是 最左归约。
? 最左归约 是 最右推导（规范推导） 的逆过程，因此 最
左归约 也称为 规范归约 。
7
自底向上的语法分析过程
? 自底向上的语法分析,从已给的符号串 w出发，试图以
相反的方向为 w建立一个规范推导，最终得到文法的
开始符。
? 若从给定的符号串 w出发，一步步地将其归约，最终
得到文法的开始符号，则归约成功，说明 w是该文法
定义的一个句子；否则,w不是该文法定义的句子。
8
符号串 i+i*i的归约过程
步序 当前符号串 w i 所用的产生式
0 i + i * i
F → i
1 F + i * i
T → F
2 T + i * i
E → T
3 E + i * i F → i
4 E + F * i T → F
5 E + T * i
F → i
6 E + T * F
T → T*F
7 E + T
E → E+T
8 E
由上表可以看出，该归约过程是 最左 归约，其逆过程
就是 规范推导 （式 2.5）。
G2[E],
E?E+T|T
T?T*F|F
F?(E)|i
9
关于归约的一点说明
? 对于前面例子中归约的第五步，当前的符号串为 E+T*i,
有，可以有以下几种规约,
E+T*i 归约为符号串 E*i,继续归约得 E*E,
无法继续进行归约
E+T*i 归约为符号串 E+E*i,继续归约得 E+ E*E,
无法继续进行归约
E+T*i 归约为符号串 E+T*F,这是唯一正确的归约，
也就是说,i是唯一可被归约的最左子串。
? 那么，对于规范归约的每一步，如何确定符号串中的当
前应被归约的最左子串呢？这个问题将在 2.3.3小节进行
讨论。
10
2.3.2 语法树和二义性
? 语法树是一有向树,
1）有且仅有一个结点无父结点，称为根（ S）；
2）除根外，每个结点恰有一个父结点； 无回路性
3）对于任一结点 m,从根到 m可达 ; 连通性
4）每个结点的子孙结点是有序的（从左到右）。
子树：某一结点及其全部子孙结点所构成的树。
直接子树：根结点只有孩子结点，没有更远的子孙结点
的子树。
11
语法树的定义
设 G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语
法树,
1）每个结点有一标记 X,X?V；
2）根的标记为 S（文法的开始符号）；
3）若结点 X有孩子结点，则 X?VN；
4）如果 A有 k个孩子结点，自左至右为 X1,X2,…,X k，则
A? X1X2…X k ?P
12
语法树的构造
? 例如，文法 G2[E]的句子 i+i*i
相应的语法树见右图 。
E?E+T|T
T?T*F|F
F?(E)|i
? 从树的根结点出发，按句型或
句子的推导顺序，逐步向下构
造语法树。
? 从末端结点出发，按归约的顺
序逐步向上构造各个子树，最
后形成整棵语法树。
E
E + T
T
F
i
T * F
F i
i
13
语法树的性质
? 对于文法 G的任一句型，总能构造一棵语法树，并且
该语法树的所有叶结点自左至右排列就构成了该句型。
? 给定一棵语法树，就知道了其中的 非终结符、终结符、
使用的产生式以及表征的句型或句子 。
? 但并不能完全确定 产生式使用的顺序 。一方面，语法
树既可以自顶向下构造，也可以自底向上构造；即使
确定了构造方式，也不能确定分支上产生式的使用顺
序。
? 语法树构造过程中使用产生式的顺序不同，就对应了
不同的推导或归约过程。因此，一棵语法树可以对应
多个推导或者归约序列。
14
二义性文法
? 但一个句型或句子的语法树与其最左推导和最右推导
一一对应（如果其最左推导和最右推导存在）。
? 如果一个文法产生的每一个句子的最左和最右推导都
对应唯一的一棵语法树，则称此文法为 无二义性文法 。
? 也存在一些文法 G，其某个句子 w?L(G),对应结构不同
的语法树，即 w对应了多个不同的最左（右）推导，
这类文法称为 二义性文法 。
15
文法的二义性举例
? 例如，文法 G3[E]：
E?E+E|E*E|(E)|i
是二义性文法，其
句子 i+i*i有两棵不
同的语法推导树。
E
E E
E E
+
* i
i i
E
E E
E E +
*
i i
i
16
if B1 then C else C
C
if B2 then C
S1 S2
C
if B1 then C
S1 S2
if B1 then C else C
文法的二义性举例
PASCAL中的 if语句（ G[C]）,
C?if B then C； C? if B then C else C； C?S
B表示布尔表达式,S表示语句。 G[C]是二义性文法，
因为句型 if B1 then if B2 then S1 else S2
有两棵不同的语法推导树。
17
关于二义性文法
? 二义性 对编译程序而言是 有害 的。因为语法分析的不
确定性会导致语义分析的不确定性，进而导致目标代
码生成时的不确定性。
? 消除文法的二义性,
– 改写文法,例如，文法 G3[E]可用本章定义的文法 G2[E]
取代，而 G2[E]不是二义性的。
– 利用附加条件 。例如,i+i*i的归约过程中，若规定 *
比 +优先级高，则系统先按 E*E进行归约，再按 E+E进行
归约；若 规定 else只能和距其最近的尚未被匹配的 then
进行匹配，就可解决 else悬空的问题。
18
二义性文法的判定性
? 对于任意的 前后文无关文法,其是否具有 二义性是不
可判定的 。
? 对于某个 具体的文法 而言，其 二义性是可判定的 。
– 第四章中的 LL(1),LR(0),LR(1)等都是无二义性文法，
并且存在判定任一前后文无关文法是否为 LL(1),
LR(0)或 LR(1)的算法。 无二义性文法的充分条件
– 若一文法 G含有 既是左递归又是右递归 的文法符号，
即有
A AvA v?V* 或 A A 或 A A?及 A ?A
则 G必定是二义性文法。 二义性文法的充分条件
?? ???? ??
19
消除文法的二义性
? 可以利用文法的等价性对二义性文法进行改造。
? 但并非所有的二义性文法都可消除其二义性 。即存在
这样的前后文无关语言，定义它的一切文法都是二义
性的。这样的语言称为 先天二义性语言 。例如，可以
证明
为一先天二义性语言。
? 前后文无关语言的 先天二义性 也是不可判定的 。
}1,|{}1,|{ ???? mndcbamndcbaL nmmnmmnn
20
2.3.3 短语和句柄
? 问题, 在自底向上的语法分析中,对于每一步直接归约,
应如何确定当前句型中应被归约的 最左子串?
句柄 的概念
? 短语和直接短语,对于某个句型 ?的语法树，如它的一
棵子树的根结点为 A，且该子树的叶子结点自左至右排
列起来所形成的符号串为 ?，则 ?是句型 ?相对于 A的一
个短语（产生句型 ?时使用了从 A到 ?的推导）；若此子
树为直接子树，则 ?是句型 ?相对于产生式 A??的直接
短语（产生句型 ?时使用了产生式 A??）。
21
句型 ?= E+T*F+i的短语和直接短语
? 句型 ?= E+T*F+i的语法树见右图
? 考查以 E为根的子树，对应的叶结点
为 E+T*F,所以,E+T*F 称为句型 ?相
对于非终结符 E 的 短语。 同理,i是 句
型 ?相对于 T 的 短语。
? 考查以 T为根的子树，对应的叶结点
为 T*F,并且 是一直接子树,因此
T*F是句型 ?相对于产生式 T?T*F的 直
接短语 。同理,i是句型 ?相对于产生
式 F?i的 直接短语 。
E
E + T
E + T
T * F
F
i
22
短语、直接短语的定义
? 例如，对句型 ?= E+T*F+i,由定义，有,
(1)E?* E+T+i(?=E+,A=T,?=+i)及 T?T*F(=?),故 T*F是 ? 相对
于产生式 T?T*F的 直接短语 ;
(2)E?* E+T*F+F F?i,i是 ? 相对于产生式 F?i的 直接短语 ;
(3)E?* E+i与 E ?+ E+T*F,E+T*F 是 ?相对于非终结符 E的 短语 ;
(4)E?* E及 E?* E+T*F+i(= ?),?是 ?相对于开始符号 E的 短语
)()(
),(
,,,][8.2
*
*
直接短语的短语产生式相对于非终结符
是句型则称及有对于
若的一个句型其中是文法设定义
?
? ? ??????
???? ? ?
?
????
??
?
?
AA
AAASVA
VVSG
N
23
短语和直接短语的判据
? 从句型 ?=E+T*F+i的语法树可知,E+T不是它的一个 直接
短语,因为虽然 E?E+T是 G2的一个产生式,但不存在从 E
到 E*F+i的推导,所以,当判断一符串是否为某一句型的
短语时,须检查定义 2.8的两个条件是否同时满足,
? 一个简单判据：短语或者直接短语必须是某棵子树的
所有叶子结点排列起来的符号串。
? 采用自底向上分析时,每步 归约 就是将一个产生式 右部
替换成 其 左部,也就是把该句型的语法树中的 一棵直接
子树的叶子结点剪去,即每次归约的符号串必是当前句
型的一个直接短语,
24
句柄：最左直接短语
? 为使句型分析可以自动地进行，每次对 最左直接短语
进行归约。
? 定义 2.9 一个句型的最左直接短语称为此句型的 句柄 。
? 句柄和归约示例
? 在规范句型中，句柄右边的符号（如果有的话）必然
是终结符号。因为 规范归约是 规范 推导的逆过程。
? 对于无二义性文法，它的任何规范句型都有唯一的语
法树，也有唯一的句柄。
25
句柄和归约示例
? 以 L(G2)的句子 i+i*i+i为例,给出
其最右推导如下。
? E?E+T ?E+F ?E+i ?E+T +i ?
E+T*F+i ?E+T*i+i ? E+F*i+i ?
E+i*i+i ?T+i*i+i ?F+i*i+i
?i+i*i+i
? 上面推导的逆过程就是规范归约
的过程。可以看出，每步归约的
均是 当前句型 的 最左直接短语
（句柄），也是最左直接子树的
叶结点。
E
E + T
E + T
T * F T
F
i
F
F
i
i
i
1
2
3
4
5 6
7
8
9
10
11
G2[E],
E?E+T|T
T?T*F|F
F?(E)|i
2.3 句型的分析
? 句型的分析,构造一算法，用以判断所给的符号串是
否为某文法的句型
? 常见分析方法有 自顶向下分析 和 自底向上分析 两类；
? 自顶向下 从开始符出发，试图推导出给定的符号串；
? 自底向上 从已给的符号串出发，试图将其 归约 为开始
符。归约：是推导的逆过程,即将某一符号子串替换成
相应产生式的左部变量。
.,,,][4.2
**
的一个句型是则称若是文法设定义 GSVSG
G
??? ??
2
2.3.1 规范推导和规范归约
问题, 根据文法 G2[E],从 E推导出 i+i*i,
(1)E? E+T? E+T*F? T+T*F? T+T*i
? F+T*i? i+T*i? i+F*i?i+i*i
(2)E? E+T? T+T? F+T? i+T? i+T*F
? i+F*F? i+i*F? i+i*i
(3)E? E+T? E+T*F? E+T*i? E+F*i
? E+i*i ? T+i*i? F+i*i? i+i*i
(4) … …
? 对于一文法而言，从开始符到某句型的 推导过程可能
不唯一 。
最左推导
最右推导
G2[E],
E?E+T|T
T?T*F|F
F?(E)|i
3
规范推导
? 为了让计算机实现推导的自动进行，引入推导时非终
结符的替换顺序。
? 最左（右）推导, 在推导序列的每一步直接推导中，
被替换的总是当前句型中最左（右）的非终结符。
? 形式定义,设有从符号串 ?到符号串 ?的推导序列
其中,xUy ? xuy表示该推导序列中的任一直接推导，
如果总有 x?VT*，则该推导序列为 最左推导 ；如果总
有 y?VT*,则该推导序列为 最右推导，最右推导 也称
为 规范推导。
,??
??
??? x u yx Uy
4
规范句型
? 由 最左推导 推出的句型称为 左句型 ；由 最右推导 或 规
范推导 推出的句型称为 右句型 或 规范句型 。
? 每个 句子 都有相应的最左和最右（规范）推导，因此，
句子即是 左句型 也是 右句型 （规范句型）
? 但并不是每个 句型 都有最左和最右推导。 例如，句型
T*i+T有唯一推导,
E ? E+T ? T+T ?T*F+T ?T*i+T
上述推导既不是最左推导，也不是最右推导，因此
T*i+T既不是左句型，也不是右句型。
5
自顶向下的语法分析
? 对于给定的符号串 w，采用 自顶向下 的分析来判断 w是
否为 L(G[S])的句子的方法是,建立从开始符 S到 w的
最左推导, S?* w
? 每步推导时，对应于最左非终结符相应的产生式可能
会有多个，如,此时就面临一个
如何选择候选式的问题。除非有办法预先知道哪个候
选式有用，否则 只能一个一个地试探。因此，推导过
程可能是 带回溯 的。
? 带回溯的语法分析效率大大降低，为提高效率，就应
尽量避免回溯（不带回溯的 LL分析方法） 。
nU ??? ||| 21 ??
6
自底向上的语法分析 —— 归约
? 归约 是 推导的逆过程，是把当前的符号串 ???中构成
文法某个产生式 A??右部的子串 ?替换成产生式的左
部符号 A，得到一个新的符号串 ?A? 。这样的一步动作，
称为进行了一步 归约 。
? 例如，符号串 F+i*i中的 F可按产生式 T?F归约为 T，
从而得到新的符号串 T+i*i。
? 若归约的每一步都归约的是当前符号串中最左边的某
产生式的右部，则称该归约是 最左归约。
? 最左归约 是 最右推导（规范推导） 的逆过程，因此 最
左归约 也称为 规范归约 。
7
自底向上的语法分析过程
? 自底向上的语法分析,从已给的符号串 w出发，试图以
相反的方向为 w建立一个规范推导，最终得到文法的
开始符。
? 若从给定的符号串 w出发，一步步地将其归约，最终
得到文法的开始符号，则归约成功，说明 w是该文法
定义的一个句子；否则,w不是该文法定义的句子。
8
符号串 i+i*i的归约过程
步序 当前符号串 w i 所用的产生式
0 i + i * i
F → i
1 F + i * i
T → F
2 T + i * i
E → T
3 E + i * i F → i
4 E + F * i T → F
5 E + T * i
F → i
6 E + T * F
T → T*F
7 E + T
E → E+T
8 E
由上表可以看出，该归约过程是 最左 归约，其逆过程
就是 规范推导 （式 2.5）。
G2[E],
E?E+T|T
T?T*F|F
F?(E)|i
9
关于归约的一点说明
? 对于前面例子中归约的第五步，当前的符号串为 E+T*i,
有，可以有以下几种规约,
E+T*i 归约为符号串 E*i,继续归约得 E*E,
无法继续进行归约
E+T*i 归约为符号串 E+E*i,继续归约得 E+ E*E,
无法继续进行归约
E+T*i 归约为符号串 E+T*F,这是唯一正确的归约，
也就是说,i是唯一可被归约的最左子串。
? 那么，对于规范归约的每一步，如何确定符号串中的当
前应被归约的最左子串呢？这个问题将在 2.3.3小节进行
讨论。
10
2.3.2 语法树和二义性
? 语法树是一有向树,
1）有且仅有一个结点无父结点，称为根（ S）；
2）除根外，每个结点恰有一个父结点； 无回路性
3）对于任一结点 m,从根到 m可达 ; 连通性
4）每个结点的子孙结点是有序的（从左到右）。
子树：某一结点及其全部子孙结点所构成的树。
直接子树：根结点只有孩子结点，没有更远的子孙结点
的子树。
11
语法树的定义
设 G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语
法树,
1）每个结点有一标记 X,X?V；
2）根的标记为 S（文法的开始符号）；
3）若结点 X有孩子结点，则 X?VN；
4）如果 A有 k个孩子结点，自左至右为 X1,X2,…,X k，则
A? X1X2…X k ?P
12
语法树的构造
? 例如，文法 G2[E]的句子 i+i*i
相应的语法树见右图 。
E?E+T|T
T?T*F|F
F?(E)|i
? 从树的根结点出发，按句型或
句子的推导顺序，逐步向下构
造语法树。
? 从末端结点出发，按归约的顺
序逐步向上构造各个子树，最
后形成整棵语法树。
E
E + T
T
F
i
T * F
F i
i
13
语法树的性质
? 对于文法 G的任一句型，总能构造一棵语法树，并且
该语法树的所有叶结点自左至右排列就构成了该句型。
? 给定一棵语法树，就知道了其中的 非终结符、终结符、
使用的产生式以及表征的句型或句子 。
? 但并不能完全确定 产生式使用的顺序 。一方面，语法
树既可以自顶向下构造，也可以自底向上构造；即使
确定了构造方式，也不能确定分支上产生式的使用顺
序。
? 语法树构造过程中使用产生式的顺序不同，就对应了
不同的推导或归约过程。因此，一棵语法树可以对应
多个推导或者归约序列。
14
二义性文法
? 但一个句型或句子的语法树与其最左推导和最右推导
一一对应（如果其最左推导和最右推导存在）。
? 如果一个文法产生的每一个句子的最左和最右推导都
对应唯一的一棵语法树，则称此文法为 无二义性文法 。
? 也存在一些文法 G，其某个句子 w?L(G),对应结构不同
的语法树，即 w对应了多个不同的最左（右）推导，
这类文法称为 二义性文法 。
15
文法的二义性举例
? 例如，文法 G3[E]：
E?E+E|E*E|(E)|i
是二义性文法，其
句子 i+i*i有两棵不
同的语法推导树。
E
E E
E E
+
* i
i i
E
E E
E E +
*
i i
i
16
if B1 then C else C
C
if B2 then C
S1 S2
C
if B1 then C
S1 S2
if B1 then C else C
文法的二义性举例
PASCAL中的 if语句（ G[C]）,
C?if B then C； C? if B then C else C； C?S
B表示布尔表达式,S表示语句。 G[C]是二义性文法，
因为句型 if B1 then if B2 then S1 else S2
有两棵不同的语法推导树。
17
关于二义性文法
? 二义性 对编译程序而言是 有害 的。因为语法分析的不
确定性会导致语义分析的不确定性，进而导致目标代
码生成时的不确定性。
? 消除文法的二义性,
– 改写文法,例如，文法 G3[E]可用本章定义的文法 G2[E]
取代，而 G2[E]不是二义性的。
– 利用附加条件 。例如,i+i*i的归约过程中，若规定 *
比 +优先级高，则系统先按 E*E进行归约，再按 E+E进行
归约；若 规定 else只能和距其最近的尚未被匹配的 then
进行匹配，就可解决 else悬空的问题。
18
二义性文法的判定性
? 对于任意的 前后文无关文法,其是否具有 二义性是不
可判定的 。
? 对于某个 具体的文法 而言，其 二义性是可判定的 。
– 第四章中的 LL(1),LR(0),LR(1)等都是无二义性文法，
并且存在判定任一前后文无关文法是否为 LL(1),
LR(0)或 LR(1)的算法。 无二义性文法的充分条件
– 若一文法 G含有 既是左递归又是右递归 的文法符号，
即有
A AvA v?V* 或 A A 或 A A?及 A ?A
则 G必定是二义性文法。 二义性文法的充分条件
?? ???? ??
19
消除文法的二义性
? 可以利用文法的等价性对二义性文法进行改造。
? 但并非所有的二义性文法都可消除其二义性 。即存在
这样的前后文无关语言，定义它的一切文法都是二义
性的。这样的语言称为 先天二义性语言 。例如，可以
证明
为一先天二义性语言。
? 前后文无关语言的 先天二义性 也是不可判定的 。
}1,|{}1,|{ ???? mndcbamndcbaL nmmnmmnn
20
2.3.3 短语和句柄
? 问题, 在自底向上的语法分析中,对于每一步直接归约,
应如何确定当前句型中应被归约的 最左子串?
句柄 的概念
? 短语和直接短语,对于某个句型 ?的语法树，如它的一
棵子树的根结点为 A，且该子树的叶子结点自左至右排
列起来所形成的符号串为 ?，则 ?是句型 ?相对于 A的一
个短语（产生句型 ?时使用了从 A到 ?的推导）；若此子
树为直接子树，则 ?是句型 ?相对于产生式 A??的直接
短语（产生句型 ?时使用了产生式 A??）。
21
句型 ?= E+T*F+i的短语和直接短语
? 句型 ?= E+T*F+i的语法树见右图
? 考查以 E为根的子树，对应的叶结点
为 E+T*F,所以,E+T*F 称为句型 ?相
对于非终结符 E 的 短语。 同理,i是 句
型 ?相对于 T 的 短语。
? 考查以 T为根的子树，对应的叶结点
为 T*F,并且 是一直接子树,因此
T*F是句型 ?相对于产生式 T?T*F的 直
接短语 。同理,i是句型 ?相对于产生
式 F?i的 直接短语 。
E
E + T
E + T
T * F
F
i
22
短语、直接短语的定义
? 例如，对句型 ?= E+T*F+i,由定义，有,
(1)E?* E+T+i(?=E+,A=T,?=+i)及 T?T*F(=?),故 T*F是 ? 相对
于产生式 T?T*F的 直接短语 ;
(2)E?* E+T*F+F F?i,i是 ? 相对于产生式 F?i的 直接短语 ;
(3)E?* E+i与 E ?+ E+T*F,E+T*F 是 ?相对于非终结符 E的 短语 ;
(4)E?* E及 E?* E+T*F+i(= ?),?是 ?相对于开始符号 E的 短语
)()(
),(
,,,][8.2
*
*
直接短语的短语产生式相对于非终结符
是句型则称及有对于
若的一个句型其中是文法设定义
?
? ? ??????
???? ? ?
?
????
??
?
?
AA
AAASVA
VVSG
N
23
短语和直接短语的判据
? 从句型 ?=E+T*F+i的语法树可知,E+T不是它的一个 直接
短语,因为虽然 E?E+T是 G2的一个产生式,但不存在从 E
到 E*F+i的推导,所以,当判断一符串是否为某一句型的
短语时,须检查定义 2.8的两个条件是否同时满足,
? 一个简单判据：短语或者直接短语必须是某棵子树的
所有叶子结点排列起来的符号串。
? 采用自底向上分析时,每步 归约 就是将一个产生式 右部
替换成 其 左部,也就是把该句型的语法树中的 一棵直接
子树的叶子结点剪去,即每次归约的符号串必是当前句
型的一个直接短语,
24
句柄：最左直接短语
? 为使句型分析可以自动地进行，每次对 最左直接短语
进行归约。
? 定义 2.9 一个句型的最左直接短语称为此句型的 句柄 。
? 句柄和归约示例
? 在规范句型中，句柄右边的符号（如果有的话）必然
是终结符号。因为 规范归约是 规范 推导的逆过程。
? 对于无二义性文法，它的任何规范句型都有唯一的语
法树，也有唯一的句柄。
25
句柄和归约示例
? 以 L(G2)的句子 i+i*i+i为例,给出
其最右推导如下。
? E?E+T ?E+F ?E+i ?E+T +i ?
E+T*F+i ?E+T*i+i ? E+F*i+i ?
E+i*i+i ?T+i*i+i ?F+i*i+i
?i+i*i+i
? 上面推导的逆过程就是规范归约
的过程。可以看出，每步归约的
均是 当前句型 的 最左直接短语
（句柄），也是最左直接子树的
叶结点。
E
E + T
E + T
T * F T
F
i
F
F
i
i
i
1
2
3
4
5 6
7
8
9
10
11
G2[E],
E?E+T|T
T?T*F|F
F?(E)|i
