1
编译原理第四章 语法分析上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 3月
2
本章目的描述程序语言的语法结构,需借助于上下文无关文法 。 文法是描述程序语言的依据,也是编译的依据 。 识别上下文无关文法所生成的语言的方法是语法分析的关键 。 本章的目的是研究这些方法 。
3
第四章 语法分析
§ 4.1 语法分析概述词法分析器按词法规则将输入字符串识别为单词符号流,这些单词符号便是上下文无关文法中的终结符 。
语法分析器的任务,是把由这些终结符组成的有限列序,作为语法分析器的输入串,按文法规则,识别它是否构成了合法的句子 (程序 ),并对语法分析中发现的错误,作出必要的处理 。
4
语法分析器与词法分析器和语义分析器的关系如果语法分析器作为单独一遍,通常以分析树的形式作为其输出,供语法分析的后续阶段继续分析 。 如果语法分析与语义分析,中间代码生成构成一遍,则每当识别一个文法结构时,
就调用相应分析程序,并生成中间代码,因此输出为中间代码形式 。
5
语法分析的方法通常有两类,即自上而下分析方法和自下而上分析方法,或称为自顶向下 (top-down)和自底向上 (bottom-up)分析方法 。 它们都要判断一输入串是否为一合法句子 。
6
对自上而下分析来说，能否找到从文法开始符开始的推导序列，使得推导出的句子恰为输入串。或者说，能否从根结点出发，向下生长出一棵语法分析树，其叶结点组成的句子恰为输入串。显然语法分析树的每一步生长 (每一步推导 )都以能否与输入串匹配为准。
对自下而上分析来说，能否从输入串出发找到一个归约序列，能最终地归约为文法开始符。
或者说，能否从叶结点出发，向上归结出以文法开始符为根结点的语法分析树，每一步的归约，都以待处理的字符串是否已形成句柄 (或最左素短语 )为准。
7
§ 4.2 递归下降分析方法递归下降分析法是一种自顶向下的分析方法,文法的每个非终结符,对应于一个递归过程 。 分析就是从方法开始符出发执行一组递归过程,向下推导,直到推导出句子 。 或者说从根结点出发,自上而下为输入串寻找一个最左匹配序列,建立一棵语法分析树 。
8
一、试探分析法
[例 4.1] 文法
S->xAy
A->ab |a
若输入串为 xay时,分析过程为：
(1) 首先建立根结点 S。
(2) 文法关于 S的产生式只有一个,所以从 S生长分析树如图 4.1(a)。 它的第一个终结符 x与输入串待分析字符 x匹配,于是下一待分析字符为 a,期待与分析树中 x右的叶结点 A匹配 。
9
(3) 非终结符 A有两个候选式,先选用第一个候选式 。 生长分析树如图 4.1(b),这时分析树第二叶结点 a恰与待分析字符 a匹配 。
(4) 输入串中下一待分析字符为 y,期待与第三叶结点 b匹配 。 此时发觉这两个字符是不同的,
即匹配失败 。 问题在于在生成 A的子树时选用的是第一个候选式 。
(5) 于是将 A的这棵子树注销,把匹配指针退回到输入串的第二字符,也即恢复与 A匹配时的现场,即 (3)之前 。
10
(6) A选用第二候选式,生长分析树如图
4.1(c),这时第二叶结点 a与输入串第二字符匹配 。
(7) 输入串下一待分析字符指向 y,分析树指向 a右叶结点 y。 两者恰匹配,所以,分析树 4.1(c)即为输入串 xay语法分析树 。
11
S
x A y
S
x A y
S
x A y
a b a
(a) (b) (c)
图 4.1 试探分析法
12
递归下降分析法的两个障碍
公共的左因子,α
P→ α β 1 | α β 2 | … | α β n
导致必须回溯到上次试探的现场 。
左递归文法,P→ P α | β
导致无限的最左推导，使匹配陷入困境。
13
二,提取左因子产生式
P→ αβ 1 | αβ 2 | … | αβ n (4.1)
有公共的左因子 α。 引进新的非终符 P’，
令：
P→ α P’|?
P’→ β 1 | β 2 | … | β n (4.2)
则它与 (4.1)是等价的,而 β 1,β 2,…,β n没有公共左因子 。 其中?是不以 α为前缀的候选式 。 当然所花的代价是增加了一个非终结符,增加了一个产生式 。
14
[例 4.2] 例 4.1的文法提取左因子后为：
S->xAy
A->aA’
A’->b |?
15
三,消除左递归产生式其中 b不以 A为前缀 。 这是直接左递归形式,它产生的符号串为 ba*
结构 。 引进非终结符 A’,令它同样产生 ba*形符号串,所以与 (4.3)等价,但是它不是左递归的 。
更一般些对的等价文法为
ba |AA?
a
b
|AA
AA
nmAAAA bbbaaa ||||||| 2121
aaa
bbb
||||
|||
21
21
AAAA
AAAA
m
n
16
消除左递归后，为
iEF
FFTT
TTEE
|)(
|*
|
iEF
TFT
TFT
ETE
ETE
|)(
|*
|'
||
|
SdAcA
bAaS
间接左递归的例
17
消除间接左递归的算法
(1) 将文法 G的所有非终结符按一给定的顺序排序；
(2) for(i＝ 1； i<=n； i++)
for(j＝ 1； j<=i-1； j++)
{ 把一个 形如的产生式改写为,
其中 是的所有产生式；
消除 A1产生式的直接左递归；
}
(3) 化简 。 去除从开始符号出发无法到达的非终结符的产生式,即去除多余产生式 。
算法不允许文法中有?产生式 。 因此如果文法中有?的产生式,需将文法改写 。
vAA ji?
vvvA ki ||| 21
kjA ||| 21
18
四,预测分析器消除了左递归,提取了公共左因子之后,就可以构造一个不带回溯的递归下降分析器了 。 即为每个非终结符写一个递归过程,以实现关于这个非终结符的分析 。
[例 4.6] (4.5)为消除左递归后的无公共左因子的表达式文法,它的预测分析器,
void match(token t)
{if(lookahead==t){ lookahead=nexttoken;}
else{ error();}
}
19
void E()
{ T(); E’();}
void T()
{ F(); T’();}
voidT’()
{ if(lookahead==’*’){ match(‘*’);F();T’();}
}
20
void E’()
{if(lookahead==’+’){match(‘+’);T();E’();}}
void F()
{if(lookahead==’i’){match(‘i’);}
else if(lookahead==’(‘)
{match(‘(‘);E();if(lookahead==‘)’)
{match(‘)’);}
else {error();}}
else{error();}
}
用分析器作语法分析有个前提条件,即描述语法分析器的语言必须允许递归调用 。
21
§ 4.3 非递归的预测分析方法一,表驱动的预测分析器它由一张分析表,一个分析栈和一个控制程序组成 。
分析表是一个二维数组 M[A,a],其中 A是非终结符,a为终结符或 $。 图 4.4为相应于 (4.5)
表达式文法的分析表,M[A,a]中若为产生式时,表明 A可用该产生式推导,以求与输入字符 a匹配 。 M[A,a]中若为空,表明 A不可能推导出与 a匹配的字符串,故为出错 。 其实其中应存放 error标志,这留待以后介绍 。
22
i + * ( ) $
E
E?
T
T?
F
E? TE?
T? FT?
F? i
E +TE?
T T *FT?
E? TE?
T? FT?
F? (E)
E
T
E
T
23
分析栈中存放分析时的文法符号,开始时栈底放结束标志 $,输入串也以 $作为结束标志 。 当分析栈中只有 $,输入指针也指向 $时,分析成功 。
控制程序根据分析栈栈顶符号 x和当前输入符号 a来决定分析器的动作：
(1)若 x=a=$,则分析成功,停止分析器的工作 。 输入串是文法的合法句子 。
(2) 若 x=a$,栈顶符号与输入符匹配 。 x从栈顶弹出,
输入指针指向下一输入符,准备对下一个字符的分析 。
(3) 若 x为一非终结符，查 M[A,a]：
若 M[A,a]中为一 A－产生式,将 A自栈顶弹出,将产生式右部符号串按逆序逐一推入栈中；特别当产生式为,则只是将 A自栈顶弹出 。
若 M[A,a]=error,则调用出错处理程序 。
24
ak $
X
$
控制程序分析表栈输入串输出图 4.6 表驱动预测分析器模型
25
预测分析控制程序将 $和文法开始符依次推入栈中；
使 ip指向第一个输入符；
do { 令栈顶符号为 x,ip指向符号为 a;
if(x∈ VT||x==$)
{if(x==a) {将 x从栈中弹出并指向下一 ip;}
else {error();}
}
else {if(M[x,a]=x?y1y2… yk)
{将 x从栈中弹出 ;
把 yk,yk-1,… y1依次推入栈中 ;
输出产生式 x?y1y2… yk;}
else {error();}
}
} while (x!=$)
26
[例 4.7] 如果输入串为 i+i*i，按图 4.4的分析表，分析过程如图 4.7所列。
分析栈 输入串 输出
$E
$E?T?
$E?T?F
$E?T?i
$E?T?
$E?
$E?T+
$E?T
$E?T?F
i+i?i$
i+i?i$
i+i?i$
i+i?i$
+i?i$
+i?i$
+i?i$
i?i$
i?i$
E?TE?
T?FT?
F?i
T
E+TE?
T?FT?
分析栈 输入串 输出
$E?T?i
$E?T?
$E?T?F?
$E?T?F
$E?T?i
$E?T?
$E?
$
i?i$
i$
i$
i$
i$
$
$
$
F?i
TFT?
F?i
T
E
图 4.7 i+i*i的预测分析过程
27
二,FIRST集和 FOLLW集表驱动的预测分析器,除了分析表将因文法而异外,分析栈,控制程序是相同的 。 因此构造一个文法的表驱动预测分析器,其实就是构造该文法的分析表 。
为了构造分析表,引进 FIRST集和 FOLLOW
集 。
28
定义 4.1 设 α ∈ (Vt∪Vn) *,则由 α 的所有可能推导出的开头终结符或可能的?为的 FIRST集,即：
*
FIRST(α)={a |α => a?,a ∈ Vt},
特别,若 *
α =>?,则?∈ FIRST(α) 。
29
FIRST集求法：
对每一文法符号,构造 FIRST(x)时,只要连续使用下列规则,直至每个 FIRST集不再增大为止 。
(1) 若 x ∈ Vt,则 FIRST(x)={x}
(2) 若 x ∈ Vn,且有 x-> α ∈ P,则将 a加入到 FIRST(x)
中；特别若 x->?∈ P,则将?加入到 FIRST(x)中 。
(3) 若 x-> Y… ∈ P 且 Y∈ Vn,则将 FIRST(Y)-{?}加入到 FIRST(x)中；
若 x->Y1Y2… Yk ∈ P,而 Y1Y2… Yi-1 ∈ Vn且
*
Y1Y2… Yi-1 =>?,则将所有 FIRST(Yi)-{?}加入到
FIRST(x)中 （ 1≤j≤i） 。 特别当
*
Y1Y2… Yk =>?时,则将?加入到 FIRST(x)中 。
30
定义 4.2 对任一 A∈ Vn,文法的所有句型中跟随在 A 后的终结符及 $ 的集合,为 A 的
FOLLOW集 。 即,*
FOLLOW(A)={a|S =>… Aa…,a∈ Vt}
特别 $∈ FOLLOW(S)。 其中 S为文法开始符,
$为输入结束标志 。
31
FOLLOW(A)的求法对文法的每个,构造 FOLLOW(A)时,只要连续使用下列规则,直至每个 FOLLOW集不再增大为止 。
(1) $∈ FOLLOW(S) ；
(2) 若 A-> αBβ ∈ P,FIRST(β) 加至
FOLLOW(B)中； *
(3) 若 A->αB ∈ P,或 A->αBβ ∈ P且 β =>?，
则将 FOLLOW(A)加至 FOLLOW(B)中。
32
[例 4.8] (4.5)文法
E → TE’
E’ →+TE’ |?
T→FT’
T→*FT’ |?
F→(E) | i
先构造 FIRST集：
根据规则 (2)，
FIRST(F)={(,i)}
FIRST(T’)={*,?}
FIRST(E’)={+,?}
根据规则 (3)，
FIRST(E)= FIRST(T)= FIRST(F)= {(,i)}
33
然后再构造 FOLLOW集：
根据规则 (1)，
$∈ FOLLOW(E),故 FOLLOW(E)= {$}。
根据规则 (2)，
)∈ FOLLOW(E),故 FOLLOW(E)= {),$}；
FIRST(T’)－ {?}?FOLLOW(F)，
故 FOLLOW(F)={*}；
FIRST(E’)－ {?}?FOLLOW(T)，
故 FOLLOW(T)={+}。
34
根据规则 (3)，
FOLLOW(E)?FOLLOW(E’),
故 FOLLOW(E’)={),$}；
FOLLOW(E)?FOLLOW(T)，
故 FOLLOW(T) ={+,),$ }；
FOLLOW(T)?FOLLOW(T’),
故 FOLLOW(T’)={+,),$ }；
FOLLOW(T)?FOLLOW(F)，
故 FOLLOW(F)= {+,*,),$ }。
35
最后的结果为：
FIRST(E)=FIRST(T)=FIRST(F)={(,i}
FIRST(E’)={+,?}
FIRST(T’)={*,?}
FOLLOW(E)= FOLLOW(E )={),$}
FOLLOW(T)= FOLLOW(T )={+,),$ }
FOLLOW(F)= {+,*,),$ }
36
注意到有限集可用成员表来表示的事实，如全集 E={a,b,c,d}，集合
A={a,c,d}，集合 B={b,c}，则可用下表来表示集合 A,B：
如果例 4.8的 FIRST集和 FOLLOW集也用成员表来表示（当然,FIRST集的全集为 VT∪{ ε },FOLLOW集的全集为 VT∪{$},其中 VT为终结符集），则按算法求取相应集合的过程，可分别用图 4.8之 (a),(b)
表来表示：
a b c d
A √ √ √
B √ √
产生式 + * ( ) i ε
E→TE ’ 3 3
E’→+TE ’|ε 2 2
T→FT ’ 3 3
T’→*FT ’|ε 2 2
F→(E)|i 2 2
产生式 + * ( ) i $
E→ TE’ 2 1
E’→+TE ’|ε 3
T→FT ’ 2 3 3
T’→*FT ’|ε 3 3 3
F→(E)|i 3 2 3 3
(a) (b)
37
其中,数字 x分别表示引用相应求取 FIRST集,FOLLOW集算法的第
x规则 。 鉴于求 FOLLOW集的规则 2依赖于 FIRST集,因此将二张表用一张表表示,可能会更方便些 。 这时,表中用 √ 表示 FIRST
集的成员,○ 表示 FOLLOW集的成员,于是有图 4.9,当然它忽略了过程,只表示了结果 。
产生式 + * （ ） i $ ε
E→ TE’ √ ○ √ ○
E’→+TE ’|ε √ ○ ○ √
T→FT ’ ○ √ ○ √ ○
T’→*FT ’|ε ○ √ ○ ○ √
F→(E)|i ○ ○ √ ○ √ ○
图 4.9 文法（ 4.5）的 FIRST集和 FOLLOW集
38
三,LL(1)文法上下文无关文法 G，任一非终结符 A的产生式设为
(1),当 时,i,j=1,2,…,n ；
(2) 若,则,j=1,…n,
且 。 则称 G是 LL(1)文法。
四,预测分析表的构造对文法的每个产生式
(1) 对每个,将 记入 M[A,a]中；
(2) 若,则对任何,把记入 M[A,b]
(3) 凡无定义的 M[A,a]均标上错误标志 。
nA aaa ||| 21
aa )()( ji FI RS TFI RS T ji?
a *?i
a )()( AFO L L O WFI RS T j
ij?
a?A
)(aF IR S Ta? a?A
)(a? F IR S T? )( AF O L L O Wb?
a?A
39
很明显 LL(1)文法的二个条件保证了分析表的每个 M[A,a]中登记的内容是唯一的，即不含多重定义项。
实际上，实用的分析器有如下变通：
·并不是将整个产生式 A→ α记入 M[A,a]中。因为 M[A,a]中的产生式左部一定是 A，故只需将产生式右部记入表中即可；
·如 α=x1x2…xn,则记入表中的 α，其实是按其逆序
xn…x2x1 记入表中的，这样控制程序中将匹配产生式推入分析栈时，只要按表中文法符号序列顺序入栈即可。提高了控制程序运行的效率；
·与此同时，若 xi为终结符，则它必为与输入符匹配的 a，若匹配，则无须入栈，而输入指针即移向下一输入字符，这样就减少了一个分析步骤。
上述变通节省了分析表的空间，提高了分析的效率。
40
i + * ( ) $
E
E?
T
T?
F
E?TE?
T?FT?
F?i
E +TE?
e
T
e
T *FT?
e
E?TE?
T?FT?
F?(E)
e
E
e
T
e
e
E
e
T
e
§ 4.4 算符优先分析法一,算符优先关系表上下文无关文法 G，如果它不含 产生式，并且产生式右部均不含相连的非终结符，即没有,或 形式的产生式，则
G是一个算符文法。
P QRP?
i|(E) F
F|F*T T
T|TE E
41
定义 4.5 算符文法 G,对任何,定义 a与 b之间的优先关系如下：
(1) a? b,G中有 或 形式的产生式 。
(2) a? b,G中有 的产生式,且 或 。
(3) a? b,G中有 的产生式,且 或 。
对,
由 得 + i
由 得 + *
由 得 + (
又由 得 i +
由 得 ) +
由 得 + +
TVba,?
abP a QbP?
bQRbQ
aQ aRQ
aQP?
QbP?
iT
TEE
FTT *
)(ET
iE
)(EE
TEE
+ * i ( ) $
+
*
i
(
)
$
42
二,算符优先分析方法这也是一种表驱动的分析方法,除了优先关系表作为分析表外,还需要一个分析栈和一个分析控制程序,协同地进行语法分析 。
分析控制程序的算法,如图 4.13所示 。 分析栈为 S,下标 K为分析栈使用的深度 。 第 (27)
行是个形式归约,归约时非终结符名并不重要 。
43
(1) K=1；
(2) S[K]= $ ； /*栈底置终止状态 */
(3) 使 ip指向第一个输入符；
(4) while(1)
(5) {
(6) if (S[K]=$ && ip指向 $)
(7) {
(8) return；
(9) }
(10) else
(11) {
(12) 令 ip所指向的符号为 a；
(13) if(S[K]∈ VT)
44
(14) {
(15) j=K；
(16) }
(17) else
(18) {
(19) j==K-1； /*S[j]为栈顶终结符 */
(20) }
(21) if(S[j]? a||S[j]? a)
(22) {
(23) K=K+1；
(24) S[K]=a；
45
(25) ip指向下一输入符；
(26) }
(27) else if (S[j]? a) /*归约 */
(28) {
(29) do
(30) {
(31) b=S[j]；
(32) if(S[j-1]∈ VT )
46
(33) {
(34) j=j-1；
(35) }
(36) else
(37) {
(38) j=j-2；
(39) }
(40) }while(S[j]? b)
(41) 把 S[j+1]… S[K]归约为某个 N；
(42) K=j+1；
47
(43) S[K]=N；
(44) }
(45) else
(46) {
(47) error();
(48) }
(49) }
(50) }
图 4.13 算符优先控制程序
48
[例 4.12]文法 (4.4)i+i*i的算法优先分析过程如图 4.14所示 。
分析栈 输入串 动作
$ i+i*i$ $ i
$i +i*i$ i + 归约
$F +i*i$ $ +
$F+ i*i$ + i
$F+i *i$ i * 归约
$F+F *i$ + *
$F+F* i$ * i
$F+F*i $ i $ 归约
$F+F*F $ * $ 归约
$F+T $ + $ 归约
$E $ 结束
49
三、优先关系表的构造
},,|{)(
},,|{)(
NT
NT
VQVaaQPaPaPLA S TV T
VQVaQaPaPaPF I R S TV T
或或
E
E T+
i
T * F
F iF
T
i
图 4.15 相应的句柄规约
50
问题在于如何求出每个非终结符的 FIRSTVT集和 LASTVT集 。
构造 FIRSTVT(P)可遵照下列两条规则：
·若有产生式 或 P →Qa …,则 ；
·若有产生式 则 。
构造 LASTVT(P)有类似的两条规则：
·若有产生式 或,则 ；
·若有产生式 则 。
[例 4.13]文法 (4.4)的 FIRTVST集和 LASTVT集,是这样得到的：
由 F?(E)|i,FIRSTVT(F)={(,I},LASTVT(F)={）,i}
由 T?T*F|F,FIRSTVT(T)={*,(,I},LASTVT(F)={*,）,i}
由 E?E+T|T,FIRSTVT(E)={+,*,(,I},LASTVT(F)={+,*,),i}
参照前节 FIRST集的成员表表示法,本例的 FIRST集,LASTVT集也可用成员表表示,其中用 √ 表示 FIRST集的成员,○ 表示 LASTVT集的成员,则有图 4.16
aP? )( PF IR S T V Ta?
QP? )()( PF I R S T V TQF I R S T V T?
aP aQP
)( PL A S T VTa?
QP )()( PL A S T V TQL A S T V T?
51
+ * i ( ) $
+
*
i
(
)
$
+ * （ ） i
E?E+T|T √ ○ √ ○ √ ○ √ ○
T?T*F|F √ ○ √ ○ √ ○
F?(E)|i √ ○ √ ○
于是,由,有 + +,* +,) +,i +,+ *,+ (,+ i
由,有 * *,) *,i *,* (,* i
由,有 ( ),( +,( *,( (,( i,+ ),* ),) ),i )
TEE
FTT *?
)(EF?
52
四,优先函数用优先关系表来表示每对终结符之间的优先关系,存储量大,查讯费时 。 如果对每个终结符赋以一个值 (这就定义了终结符的一个函数 f)，
值的大小恰反映了优先关系,则终结符 a,b间的优先关系便转换成终结符的优先函数值 f(a),f(b)的比较 。 这样优先表可以省了,比较也方便了 。
·一个终结符在栈中 (左 )在输入串中 (右 )的优先值是不同的,如有 +? )
且有 )? +。 因此对一个终结符而言它应有一个左优先数和一个右优先数 。 这就定义了终结符的一对函数 f,g,要求满足：
如 a b,则应有 f(a)=g(b)；
如 a b,则应有 f(a)<g(b)；
如 a b,则应有 f(a)>g(b)。
这对优先函数中的 f通常称为入栈函数,g称为比较函数 。
53
·优先函数并不唯一,若 (f,g)是优先函数,显然 (f+m,g+m)也是优先函数 。
·算符优先文法 (即有确定的优先关系表 )不一定有优先函数,如对图
4.17给出的优先关系表就不存在优先函数,因为若存在优先函数 (f,
g),则
f(a)=g(a) f(a)>g(b) 图 4.17优先表
f(b)=g(a) f(b)=g(b)
于是有 f(a)>g(b)=f(b)=g(a)=f(a),得到 f(a)>g(a)的矛盾关系 。
a b
a
b
54
§ 4.5 LR分析器一,LR分析法
a1 ai $
Xm-1
$
…
控制程序分析表输出图 4.23 LR分析器模型
Sm-1
0
…
XmSm
gotoaction
55
状态
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
11 r5 r5 r5 r5
图 4.21 文法 (4.4)的 LR分析表
56
分析程序对任何 LR分析器都适用 。 它从输入串中读入当前输入符
a,然后由栈顶状态 si与当前输入字符 a查 action表,决定应取何种动作 。
·若为 sj,则将状态 j(连同相应的输入符 a)移入栈顶 。
·若为 rj,则按第 j个产生式 归约,设右部符号 的长度为 t,将分析栈顶 t个状态 (连同它们的文法符号 )上托出栈,设呈现栈顶的状态为,归约后的非终结符为 A,查 goto表的 项,
得到状态 j,将状态 j(连同文法符 A)移入栈顶 。
·若为 acc,则结束分析,输入串被接受 。
·其他转错误处理程序 。
AS,?
b?A b
S?
57图 4.24 i+i*i的 LR分析过程分析栈 输入串 动作
1 0$ i+i?i$ s5
2 0$ 5i +i?i$ r5,F?i goto(0,F)=3
3 0$ 3F +i?i$ r4,T?F goto(0,T)=2
4 0$ 2T +i?i$ r2,E?T goto(0,E)=1
5 0$ 1E +i?i$ s6
6 0$ 1E 6+ i?i$ s5
7 0$ 1E 6+5i?i$ r6,F?i goto(6,F)=3
8 0$ 1E 6+3F?i$ r4,T?F goto(6,F)=9
9 0$ 1E 6+9T?i$ s7
10 0$ 1E 6+9T 7* i$ s5
11 0$ 1E 6+9T 7*5i $ r6,F?i goto(7,F)=10
12 0$ 1E 6+9T 7*10F $ r3,T?T*F goto(6,T)=9
13 0$ 1E 6+9T $ r1,E?E+T goto(0,E)=1
14 0$ 1E $ acc
58
二,识别活前缀的 DFA
定义 4.8 规范句型的一个前缀,如果它不含句柄后任何符号,则称它是该规范句型的一个活前缀 。 也即若 是文法的一个产生式,S是文法开始符,并有：
则 的任何前缀都是规范句型 的活前缀 。
在上述定义中,是句型 关于 A的直接短语，并且是一次最右推导 (规范推导 )，所以 是最左直接短语，是一句柄，因此的任何前缀不含句柄后的任何符号，特别，句柄 是 的后缀，是分析栈栈顶的符号串。
a b RR AS*
ab
ab?
ab?A
ab
ab?
ab?ab
ab?ab
59
作为规范句型的活前缀不含句柄后的任何符号,这就决定了活前缀与句柄之间只可能有三种关系：
(1) 活前缀不含句柄的任何符号,此时期待从剩余输入串中识别由的 所能推导出的符号串 。
(2) 活前缀只含句柄的真前缀,也即产生式 中 已识别于分析栈顶之上,期待从剩余输入串中识别由 所能推导出的符号串 。
(3) 活前缀已含句柄的全部符号,这表明 的右部符号串已在分析栈顶,分析动作应为按此产生式将 归约为 A。
由此可见句柄是一类活前缀的后缀,如果能识别一个文法的所有活前缀,自然也就能识别这个文法的所有句柄了,所以我们将讨论如何识别文法的活前缀 。
首先我们采用下列形式分别表示上述三种情况,即：
abab?A
a
b
.,.,,abbaab AAA
ab?A
ab?A
ab
ab
60
一个产生式如,根据圆点的位置不同可以有通常我们称 为归约项目称 及 为待约项目,
称 为移进项目
T.EE
.TEE
TE.E
T.EE
TEE
T.EE
TE.E T.E?
TE.E
61
对于像 (4.4)这样的文法,文法开始符的产生式不唯一：
这样就会有两个归约项目 和 。 同时,E又在产生式右部出现,这两个归约项目并不意味着分析的结束 。 为此,对任何文法 G,我们总是将 G拓广为等价的 G’,它以 S’为文法开始符,增加了一个产生式,其中 S为 G的文法开始符,这样接受项目 便可唯一了 。
可以利用文法的所有项目作为状态来构造一个识别所有活前缀的 NFA，
其中 为唯一的初态,任何状态均认为是 NFA的终态,它作为活前缀识别态,如果状态 i为：
而状态 j为：
则由状态 i画一标记为 的有向边至状态 j，如果状态 i中 为一非终结符，
则从状态 i画 有向边至所有 xi→,a的状态。这样就构成一个识别活前缀的 NFA。
TTEE |
T.EE
T.E?
SS,SS
nii xxxxX,11
nii xxxxX 11,
SS,
ix
ix
62
定义 4.9 对于项目,如果有：
则称 对活前缀 有效 。
如果项目 对活前缀 有效,也即有：
设,关于 B的产生式为,则有：
因 也是对活前缀 有效的项目,这说明,对活前缀有效的项目可能还不止一个 。 于是对活前缀 有效的项目的集合称为的有效项目集 。 文法 G的所有对活前缀有效的项目集组成的集合称为文法 G的 LR(0)项目集规范族 C。
a b RR AS*ba.?A
a
ba BA,?
b*RB
aaba RRRR BBAxS **
.?B
ba.?A
a?a b RR AS*
a?a
a
63
I0,SE
EE+T
ET
TT*F
TF
F(E)
Fi
SE?I1,
E?E?+T
I2,E?T?
T?T?*F
F?i?
I3,
I4,
T?F?
F?(.E)
EE+T
ET
TT*F
TF
F(E)
Fi
I5,
I6,
I7,
I8,
E?E+?T F?i?
F?i?
F?i?
F?i?
T?T*?F
F(E)
Fi
F?(E?)
E?E?+T
TT*F
TF
F(E)
Fi
I9,
I10,
I11,
图 4.26 文法 (4.9)的 LR(0)项目集规范族
64
三,SLR分析表的构造
LR分析表，其实就是识别活前缀的带下推栈的 DFA，
DFA的状态便是对活前缀有效的项目集，
项目集中的各个项目指出了在识别活前缀后应执行的动作，这便是 action
表中的内容，
这里存在着：
移进 —— 归约的冲突。
归约 —— 归约的冲突。
解决上述冲突的一种简单办法是考察 FOLLOW(A)和 FOLLOW(B)，
如果 {b}与 FOLLOW(A),FOLLOW(B)两两不交，则移进或归约的动作便可唯一确定。
输入字符为 a时
(1) a＝ b,则移进；
(2),则用 归约；
(3),则用 归约；
(4) 此外出错 。
.},,,.{ aaba BAbXI
F O L L O W ( A ) a? a?A
F O L L O W ( B )a? a?B
65
SE
EE
+T
ET
TT
*F
TF
F(
E)
Fi
SE?
E?E?+T
E?T?
T?T?*F
T?F?
F?(.
E)
EE
+T
ET
TT
*F
TF
F(
E)
Fi
F?i?
E?E
+?T
TT
*F
TF
F(
E)
Fi
T?T*?F
F(E)
Fi
F?(E?)
E?E?+T
E?
E+T?
T?
T?*F
T?T*F?
F?(E)?
I1
:
I2
:
I3:
I4:
I5
:
I6:
I7
:
I8
:
I9:
I10:
I11:
I0,状态
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
11 r5 r5 r5 r5
FOLLOW(E)＝ {+,),$}
FOLLOW(T)＝ FOLLOW(F)＝ {+,*,},$}
66
四,LR(1)分析表的构造
LR
i|*RL
R|RLS
设文法 G为：
FOLLOW(S)＝ {$}
FOLLOW(L)＝ FOLLOW(R)＝ {＝,$}
67
I0＝ {SS,SL＝ R,SR,L*R,Li,RL}
I1＝ go(I0,S)＝ {SS?},故 goto[0,S]＝ 1
I2＝ {S?L?＝ R,R?L?},故 goto[0,L]＝ 2
I3＝ {S?R?},故 goto[0,R]＝ 3
I4＝ {L?*?R,RL,L*R,Li},故 action[0,*]＝ S4
I5＝ {L?i?},故 action[0,i]＝ S5
由 I1,故 action[1,$]=acc
对 I2：
由 S?L?＝ R,记 go(I2,＝ )＝ I6,则 action[2,＝ ]＝ S6
由 R?L?,由于 FOLLOW(R)＝ {＝,$}
action[2,＝ ]＝ s6
action[2,=]＝ r5
action[2,＝ ] 处 发 生 了 移 进 与 归 约 的 冲 突,这 是 因 为,
{＝ }∩FOLLOW(R) ＝ {＝ }。
68
重新定义项目为一二元组形式：
{A?a?b,a1…ak}
只讨论 k＝ 1的情况：对于 LR(1)的项目 [A?a?b,a]，如果有：
,而则称该项目对活前缀?a有效 。
如果项目 [A?a?Bb,a]对活前缀?a有效,并且有 B
则对任何 b?FOLLOW(),[B,b]也对活前缀?a有效,这里,
FOLLOW()＝ FOLLOW(b?)＝ FOLLOW(ba)。
},|{)( * TVaAaSaAF OL L OW
AS R*?
),(
$,
F I R S Ta
aaba RRRR BBAS **
b*R
a b RR AS*
69
I0＝ closure({[SS,$]})＝ {[SS,$]},[SL＝ R,$],[SR,$]，
[L*R,＝ |S],[Li,＝ |$],[RL,$]}
I1＝ go(I0,S)＝ {[SS?,$]}
I2＝ go(I0,L)＝ {[S?L?＝ R,$],[R?L?,$]}
I3＝ go(I0,R)＝ {[S?R?,$]}
I4＝ go(I0,*)＝ {[L?*?R,＝ |$],[RL,＝ |$],[L*R,＝ |$],[Li,＝ |$]}
I5＝ go(I0,i)＝ {[L?i?,＝ |$]}
I6＝ go(I2,＝ )＝ {[S?L＝?R,$],[RL,$],[L*R,$],[Li,$]}
I7＝ go(I4,R)＝ {[L?*R?,＝ |$]}
I8＝ go(I4,L)＝ {[R?L?,＝ |$]}
I9＝ go(I6,R)＝ {[S?L＝ R?,$]}
I10＝ go(I6,L)＝ {[R?L?,$]}
I11＝ go(I6,*)＝ {[L?*?R,$],[RL,$],[L*R,$],[L→,i,$] }
I12＝ go(I6,i)＝ {[L?i?,$]}
I13＝ go(I11,R)＝ {[L?*R?,$]}
70
图 4.28 文法 (4.11)的 LR(1)分析表状态 Action goto
＝ * i $ S L R
0 s4 s5 1 2 3
1 acc
2 s6 r5
3 r2
4 s4 s5 8 7
5 r4 r4
6 s11 s12 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 s11 s12 10 13
12 r4
13 r3
71
五,LALR分析表的构造两个 LR(1)的项目集,如果除了搜索符,它们是两两相同的,则称这两个项目集为同心集 。
除去初态项目外,一个项目集的核是由此项目集中那些圆点不在最左端的项目组成,而初态项目集的核仅为 {[SS,$]}。
例如,例 4.20中,I8与 I10,I4与 I11,I5与 I12,I7与 I13是两两同心的,而
I2的核为 I2本身,I4的核为 {[L?*?R,＝ |$]},I6的核为 {[S?L＝?R,$]}。
如果将同心的 LR(1)的项目集合并,显然项目集的个数 (即状态数 )与 SLR
相同；如果用核代替项目集,则可以压缩项目集的大小 。 这两种方法都能起压缩空间的作用,这就是 LALR分析法的基本思想,现分别进行讨论 。
例如,在例 4.20中将
I10与 I8合并为 I8?＝ {[R?L?,＝ |$]}
I11与 I4合并为 I4?＝ {[L?*?R,＝ |$],[RL,＝ |$]，
[L*R,＝ |$],[Li,＝ |$]}
I12与 I5合并为 I5?＝ {[L?i?,＝ |$]}
I13与 I7合并为 I7?＝ {[L?*R?,＝ |$]}
于是状态数由原来 14个减少为 10,不难发现它恰为 LR(0)项目集的个数 。
72
图 4.29 文法 (4.11)的 LALR分析表状态 Action goto
＝ * i $ S L R
0 s1 s5 1 2 3
1 Acc
2 S6 r5
3 r2
4 s4 s5 8 7
5 R4 r4
6 s4 s5 8 9
7 R3 r3
8 R5 r5
9 r1
73
(1) 不可能引起移进? 归约冲突。如果合并后的项目集 I含有移进? 归约冲突：即 [A?a?,a]?I，
它表明当前输入符为 a时，按 A?a归约；并且
[B?a?ab,b]?I，它要求将 a移进。注意到在合并同心集的过程中，合并前的项目集应有相同的
,心,,即 LR(0)项目集，只是搜索符可能不同，
但搜索符也必须在合并前的某个项目集中出现。
则合并前的项目集中至少有一个项目集，它含有
[A?a?,a]和 [B?a?ab,c]这就表明合并前已经有移进? 归约冲突，与假设不符。因此无冲突的
LR(1)项目集在合并同心集时不会引起移进? 归约冲突。
(2) 有可能引起归约? 归约冲突。
74
§ 4.6 二义文法的应用
G1文法,E?E+E|E*E|(E)|i
G2文法,E?E+T|T
T?T*F|F
F?(E)|i
他们的比较：
二义 VT VN P
G1 Y 5 1 4
G2 N 5 3 6
75
I0,S.E
E?.E+E
E?.E*E
E?.(E)
E?.i
I1,SE.
E?E.+E
E?E.*E
I2,E?(.E)
E?.E+E
E?.E*E
E?.(E)
E?.i
I3,E?i.
I4,E?E+.E
E?.E+E
E?.E*E
E?.(E)
E?.i
I5,E?E*.E
E?.E+E
E?.E*E
E?.(E)
E?.i
I6,E?(E.)
E?E.+E
E?E.*E
I7,E?E+E.
E?E.+E
E?E.*E
I8,E?E*E.
E?E.+E
E?E.*E
I9,E?(E).
76
空间大小为 10× 7与 12× 9之比状态
action goto
i + * ( ) $ E
0 s3 s2 1
1 s4 s5 acc
2 s2 s2 6
3 r4 r4 r4 r4
4 s3 s2 7
5 s3 s2 8
6 s4 s5 s9
7 r1 s5 r1 r1
8 r2 r2 r2 r2
9 r3 r3 r3 r3
编译原理第四章 语法分析上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 3月
2
本章目的描述程序语言的语法结构,需借助于上下文无关文法 。 文法是描述程序语言的依据,也是编译的依据 。 识别上下文无关文法所生成的语言的方法是语法分析的关键 。 本章的目的是研究这些方法 。
3
第四章 语法分析
§ 4.1 语法分析概述词法分析器按词法规则将输入字符串识别为单词符号流,这些单词符号便是上下文无关文法中的终结符 。
语法分析器的任务,是把由这些终结符组成的有限列序,作为语法分析器的输入串,按文法规则,识别它是否构成了合法的句子 (程序 ),并对语法分析中发现的错误,作出必要的处理 。
4
语法分析器与词法分析器和语义分析器的关系如果语法分析器作为单独一遍,通常以分析树的形式作为其输出,供语法分析的后续阶段继续分析 。 如果语法分析与语义分析,中间代码生成构成一遍,则每当识别一个文法结构时,
就调用相应分析程序,并生成中间代码,因此输出为中间代码形式 。
5
语法分析的方法通常有两类,即自上而下分析方法和自下而上分析方法,或称为自顶向下 (top-down)和自底向上 (bottom-up)分析方法 。 它们都要判断一输入串是否为一合法句子 。
6
对自上而下分析来说，能否找到从文法开始符开始的推导序列，使得推导出的句子恰为输入串。或者说，能否从根结点出发，向下生长出一棵语法分析树，其叶结点组成的句子恰为输入串。显然语法分析树的每一步生长 (每一步推导 )都以能否与输入串匹配为准。
对自下而上分析来说，能否从输入串出发找到一个归约序列，能最终地归约为文法开始符。
或者说，能否从叶结点出发，向上归结出以文法开始符为根结点的语法分析树，每一步的归约，都以待处理的字符串是否已形成句柄 (或最左素短语 )为准。
7
§ 4.2 递归下降分析方法递归下降分析法是一种自顶向下的分析方法,文法的每个非终结符,对应于一个递归过程 。 分析就是从方法开始符出发执行一组递归过程,向下推导,直到推导出句子 。 或者说从根结点出发,自上而下为输入串寻找一个最左匹配序列,建立一棵语法分析树 。
8
一、试探分析法
[例 4.1] 文法
S->xAy
A->ab |a
若输入串为 xay时,分析过程为：
(1) 首先建立根结点 S。
(2) 文法关于 S的产生式只有一个,所以从 S生长分析树如图 4.1(a)。 它的第一个终结符 x与输入串待分析字符 x匹配,于是下一待分析字符为 a,期待与分析树中 x右的叶结点 A匹配 。
9
(3) 非终结符 A有两个候选式,先选用第一个候选式 。 生长分析树如图 4.1(b),这时分析树第二叶结点 a恰与待分析字符 a匹配 。
(4) 输入串中下一待分析字符为 y,期待与第三叶结点 b匹配 。 此时发觉这两个字符是不同的,
即匹配失败 。 问题在于在生成 A的子树时选用的是第一个候选式 。
(5) 于是将 A的这棵子树注销,把匹配指针退回到输入串的第二字符,也即恢复与 A匹配时的现场,即 (3)之前 。
10
(6) A选用第二候选式,生长分析树如图
4.1(c),这时第二叶结点 a与输入串第二字符匹配 。
(7) 输入串下一待分析字符指向 y,分析树指向 a右叶结点 y。 两者恰匹配,所以,分析树 4.1(c)即为输入串 xay语法分析树 。
11
S
x A y
S
x A y
S
x A y
a b a
(a) (b) (c)
图 4.1 试探分析法
12
递归下降分析法的两个障碍
公共的左因子,α
P→ α β 1 | α β 2 | … | α β n
导致必须回溯到上次试探的现场 。
左递归文法,P→ P α | β
导致无限的最左推导，使匹配陷入困境。
13
二,提取左因子产生式
P→ αβ 1 | αβ 2 | … | αβ n (4.1)
有公共的左因子 α。 引进新的非终符 P’，
令：
P→ α P’|?
P’→ β 1 | β 2 | … | β n (4.2)
则它与 (4.1)是等价的,而 β 1,β 2,…,β n没有公共左因子 。 其中?是不以 α为前缀的候选式 。 当然所花的代价是增加了一个非终结符,增加了一个产生式 。
14
[例 4.2] 例 4.1的文法提取左因子后为：
S->xAy
A->aA’
A’->b |?
15
三,消除左递归产生式其中 b不以 A为前缀 。 这是直接左递归形式,它产生的符号串为 ba*
结构 。 引进非终结符 A’,令它同样产生 ba*形符号串,所以与 (4.3)等价,但是它不是左递归的 。
更一般些对的等价文法为
ba |AA?
a
b
|AA
AA
nmAAAA bbbaaa ||||||| 2121
aaa
bbb
||||
|||
21
21
AAAA
AAAA
m
n
16
消除左递归后，为
iEF
FFTT
TTEE
|)(
|*
|
iEF
TFT
TFT
ETE
ETE
|)(
|*
|'
||
|
SdAcA
bAaS
间接左递归的例
17
消除间接左递归的算法
(1) 将文法 G的所有非终结符按一给定的顺序排序；
(2) for(i＝ 1； i<=n； i++)
for(j＝ 1； j<=i-1； j++)
{ 把一个 形如的产生式改写为,
其中 是的所有产生式；
消除 A1产生式的直接左递归；
}
(3) 化简 。 去除从开始符号出发无法到达的非终结符的产生式,即去除多余产生式 。
算法不允许文法中有?产生式 。 因此如果文法中有?的产生式,需将文法改写 。
vAA ji?
vvvA ki ||| 21
kjA ||| 21
18
四,预测分析器消除了左递归,提取了公共左因子之后,就可以构造一个不带回溯的递归下降分析器了 。 即为每个非终结符写一个递归过程,以实现关于这个非终结符的分析 。
[例 4.6] (4.5)为消除左递归后的无公共左因子的表达式文法,它的预测分析器,
void match(token t)
{if(lookahead==t){ lookahead=nexttoken;}
else{ error();}
}
19
void E()
{ T(); E’();}
void T()
{ F(); T’();}
voidT’()
{ if(lookahead==’*’){ match(‘*’);F();T’();}
}
20
void E’()
{if(lookahead==’+’){match(‘+’);T();E’();}}
void F()
{if(lookahead==’i’){match(‘i’);}
else if(lookahead==’(‘)
{match(‘(‘);E();if(lookahead==‘)’)
{match(‘)’);}
else {error();}}
else{error();}
}
用分析器作语法分析有个前提条件,即描述语法分析器的语言必须允许递归调用 。
21
§ 4.3 非递归的预测分析方法一,表驱动的预测分析器它由一张分析表,一个分析栈和一个控制程序组成 。
分析表是一个二维数组 M[A,a],其中 A是非终结符,a为终结符或 $。 图 4.4为相应于 (4.5)
表达式文法的分析表,M[A,a]中若为产生式时,表明 A可用该产生式推导,以求与输入字符 a匹配 。 M[A,a]中若为空,表明 A不可能推导出与 a匹配的字符串,故为出错 。 其实其中应存放 error标志,这留待以后介绍 。
22
i + * ( ) $
E
E?
T
T?
F
E? TE?
T? FT?
F? i
E +TE?
T T *FT?
E? TE?
T? FT?
F? (E)
E
T
E
T
23
分析栈中存放分析时的文法符号,开始时栈底放结束标志 $,输入串也以 $作为结束标志 。 当分析栈中只有 $,输入指针也指向 $时,分析成功 。
控制程序根据分析栈栈顶符号 x和当前输入符号 a来决定分析器的动作：
(1)若 x=a=$,则分析成功,停止分析器的工作 。 输入串是文法的合法句子 。
(2) 若 x=a$,栈顶符号与输入符匹配 。 x从栈顶弹出,
输入指针指向下一输入符,准备对下一个字符的分析 。
(3) 若 x为一非终结符，查 M[A,a]：
若 M[A,a]中为一 A－产生式,将 A自栈顶弹出,将产生式右部符号串按逆序逐一推入栈中；特别当产生式为,则只是将 A自栈顶弹出 。
若 M[A,a]=error,则调用出错处理程序 。
24
ak $
X
$
控制程序分析表栈输入串输出图 4.6 表驱动预测分析器模型
25
预测分析控制程序将 $和文法开始符依次推入栈中；
使 ip指向第一个输入符；
do { 令栈顶符号为 x,ip指向符号为 a;
if(x∈ VT||x==$)
{if(x==a) {将 x从栈中弹出并指向下一 ip;}
else {error();}
}
else {if(M[x,a]=x?y1y2… yk)
{将 x从栈中弹出 ;
把 yk,yk-1,… y1依次推入栈中 ;
输出产生式 x?y1y2… yk;}
else {error();}
}
} while (x!=$)
26
[例 4.7] 如果输入串为 i+i*i，按图 4.4的分析表，分析过程如图 4.7所列。
分析栈 输入串 输出
$E
$E?T?
$E?T?F
$E?T?i
$E?T?
$E?
$E?T+
$E?T
$E?T?F
i+i?i$
i+i?i$
i+i?i$
i+i?i$
+i?i$
+i?i$
+i?i$
i?i$
i?i$
E?TE?
T?FT?
F?i
T
E+TE?
T?FT?
分析栈 输入串 输出
$E?T?i
$E?T?
$E?T?F?
$E?T?F
$E?T?i
$E?T?
$E?
$
i?i$
i$
i$
i$
i$
$
$
$
F?i
TFT?
F?i
T
E
图 4.7 i+i*i的预测分析过程
27
二,FIRST集和 FOLLW集表驱动的预测分析器,除了分析表将因文法而异外,分析栈,控制程序是相同的 。 因此构造一个文法的表驱动预测分析器,其实就是构造该文法的分析表 。
为了构造分析表,引进 FIRST集和 FOLLOW
集 。
28
定义 4.1 设 α ∈ (Vt∪Vn) *,则由 α 的所有可能推导出的开头终结符或可能的?为的 FIRST集,即：
*
FIRST(α)={a |α => a?,a ∈ Vt},
特别,若 *
α =>?,则?∈ FIRST(α) 。
29
FIRST集求法：
对每一文法符号,构造 FIRST(x)时,只要连续使用下列规则,直至每个 FIRST集不再增大为止 。
(1) 若 x ∈ Vt,则 FIRST(x)={x}
(2) 若 x ∈ Vn,且有 x-> α ∈ P,则将 a加入到 FIRST(x)
中；特别若 x->?∈ P,则将?加入到 FIRST(x)中 。
(3) 若 x-> Y… ∈ P 且 Y∈ Vn,则将 FIRST(Y)-{?}加入到 FIRST(x)中；
若 x->Y1Y2… Yk ∈ P,而 Y1Y2… Yi-1 ∈ Vn且
*
Y1Y2… Yi-1 =>?,则将所有 FIRST(Yi)-{?}加入到
FIRST(x)中 （ 1≤j≤i） 。 特别当
*
Y1Y2… Yk =>?时,则将?加入到 FIRST(x)中 。
30
定义 4.2 对任一 A∈ Vn,文法的所有句型中跟随在 A 后的终结符及 $ 的集合,为 A 的
FOLLOW集 。 即,*
FOLLOW(A)={a|S =>… Aa…,a∈ Vt}
特别 $∈ FOLLOW(S)。 其中 S为文法开始符,
$为输入结束标志 。
31
FOLLOW(A)的求法对文法的每个,构造 FOLLOW(A)时,只要连续使用下列规则,直至每个 FOLLOW集不再增大为止 。
(1) $∈ FOLLOW(S) ；
(2) 若 A-> αBβ ∈ P,FIRST(β) 加至
FOLLOW(B)中； *
(3) 若 A->αB ∈ P,或 A->αBβ ∈ P且 β =>?，
则将 FOLLOW(A)加至 FOLLOW(B)中。
32
[例 4.8] (4.5)文法
E → TE’
E’ →+TE’ |?
T→FT’
T→*FT’ |?
F→(E) | i
先构造 FIRST集：
根据规则 (2)，
FIRST(F)={(,i)}
FIRST(T’)={*,?}
FIRST(E’)={+,?}
根据规则 (3)，
FIRST(E)= FIRST(T)= FIRST(F)= {(,i)}
33
然后再构造 FOLLOW集：
根据规则 (1)，
$∈ FOLLOW(E),故 FOLLOW(E)= {$}。
根据规则 (2)，
)∈ FOLLOW(E),故 FOLLOW(E)= {),$}；
FIRST(T’)－ {?}?FOLLOW(F)，
故 FOLLOW(F)={*}；
FIRST(E’)－ {?}?FOLLOW(T)，
故 FOLLOW(T)={+}。
34
根据规则 (3)，
FOLLOW(E)?FOLLOW(E’),
故 FOLLOW(E’)={),$}；
FOLLOW(E)?FOLLOW(T)，
故 FOLLOW(T) ={+,),$ }；
FOLLOW(T)?FOLLOW(T’),
故 FOLLOW(T’)={+,),$ }；
FOLLOW(T)?FOLLOW(F)，
故 FOLLOW(F)= {+,*,),$ }。
35
最后的结果为：
FIRST(E)=FIRST(T)=FIRST(F)={(,i}
FIRST(E’)={+,?}
FIRST(T’)={*,?}
FOLLOW(E)= FOLLOW(E )={),$}
FOLLOW(T)= FOLLOW(T )={+,),$ }
FOLLOW(F)= {+,*,),$ }
36
注意到有限集可用成员表来表示的事实，如全集 E={a,b,c,d}，集合
A={a,c,d}，集合 B={b,c}，则可用下表来表示集合 A,B：
如果例 4.8的 FIRST集和 FOLLOW集也用成员表来表示（当然,FIRST集的全集为 VT∪{ ε },FOLLOW集的全集为 VT∪{$},其中 VT为终结符集），则按算法求取相应集合的过程，可分别用图 4.8之 (a),(b)
表来表示：
a b c d
A √ √ √
B √ √
产生式 + * ( ) i ε
E→TE ’ 3 3
E’→+TE ’|ε 2 2
T→FT ’ 3 3
T’→*FT ’|ε 2 2
F→(E)|i 2 2
产生式 + * ( ) i $
E→ TE’ 2 1
E’→+TE ’|ε 3
T→FT ’ 2 3 3
T’→*FT ’|ε 3 3 3
F→(E)|i 3 2 3 3
(a) (b)
37
其中,数字 x分别表示引用相应求取 FIRST集,FOLLOW集算法的第
x规则 。 鉴于求 FOLLOW集的规则 2依赖于 FIRST集,因此将二张表用一张表表示,可能会更方便些 。 这时,表中用 √ 表示 FIRST
集的成员,○ 表示 FOLLOW集的成员,于是有图 4.9,当然它忽略了过程,只表示了结果 。
产生式 + * （ ） i $ ε
E→ TE’ √ ○ √ ○
E’→+TE ’|ε √ ○ ○ √
T→FT ’ ○ √ ○ √ ○
T’→*FT ’|ε ○ √ ○ ○ √
F→(E)|i ○ ○ √ ○ √ ○
图 4.9 文法（ 4.5）的 FIRST集和 FOLLOW集
38
三,LL(1)文法上下文无关文法 G，任一非终结符 A的产生式设为
(1),当 时,i,j=1,2,…,n ；
(2) 若,则,j=1,…n,
且 。 则称 G是 LL(1)文法。
四,预测分析表的构造对文法的每个产生式
(1) 对每个,将 记入 M[A,a]中；
(2) 若,则对任何,把记入 M[A,b]
(3) 凡无定义的 M[A,a]均标上错误标志 。
nA aaa ||| 21
aa )()( ji FI RS TFI RS T ji?
a *?i
a )()( AFO L L O WFI RS T j
ij?
a?A
)(aF IR S Ta? a?A
)(a? F IR S T? )( AF O L L O Wb?
a?A
39
很明显 LL(1)文法的二个条件保证了分析表的每个 M[A,a]中登记的内容是唯一的，即不含多重定义项。
实际上，实用的分析器有如下变通：
·并不是将整个产生式 A→ α记入 M[A,a]中。因为 M[A,a]中的产生式左部一定是 A，故只需将产生式右部记入表中即可；
·如 α=x1x2…xn,则记入表中的 α，其实是按其逆序
xn…x2x1 记入表中的，这样控制程序中将匹配产生式推入分析栈时，只要按表中文法符号序列顺序入栈即可。提高了控制程序运行的效率；
·与此同时，若 xi为终结符，则它必为与输入符匹配的 a，若匹配，则无须入栈，而输入指针即移向下一输入字符，这样就减少了一个分析步骤。
上述变通节省了分析表的空间，提高了分析的效率。
40
i + * ( ) $
E
E?
T
T?
F
E?TE?
T?FT?
F?i
E +TE?
e
T
e
T *FT?
e
E?TE?
T?FT?
F?(E)
e
E
e
T
e
e
E
e
T
e
§ 4.4 算符优先分析法一,算符优先关系表上下文无关文法 G，如果它不含 产生式，并且产生式右部均不含相连的非终结符，即没有,或 形式的产生式，则
G是一个算符文法。
P QRP?
i|(E) F
F|F*T T
T|TE E
41
定义 4.5 算符文法 G,对任何,定义 a与 b之间的优先关系如下：
(1) a? b,G中有 或 形式的产生式 。
(2) a? b,G中有 的产生式,且 或 。
(3) a? b,G中有 的产生式,且 或 。
对,
由 得 + i
由 得 + *
由 得 + (
又由 得 i +
由 得 ) +
由 得 + +
TVba,?
abP a QbP?
bQRbQ
aQ aRQ
aQP?
QbP?
iT
TEE
FTT *
)(ET
iE
)(EE
TEE
+ * i ( ) $
+
*
i
(
)
$
42
二,算符优先分析方法这也是一种表驱动的分析方法,除了优先关系表作为分析表外,还需要一个分析栈和一个分析控制程序,协同地进行语法分析 。
分析控制程序的算法,如图 4.13所示 。 分析栈为 S,下标 K为分析栈使用的深度 。 第 (27)
行是个形式归约,归约时非终结符名并不重要 。
43
(1) K=1；
(2) S[K]= $ ； /*栈底置终止状态 */
(3) 使 ip指向第一个输入符；
(4) while(1)
(5) {
(6) if (S[K]=$ && ip指向 $)
(7) {
(8) return；
(9) }
(10) else
(11) {
(12) 令 ip所指向的符号为 a；
(13) if(S[K]∈ VT)
44
(14) {
(15) j=K；
(16) }
(17) else
(18) {
(19) j==K-1； /*S[j]为栈顶终结符 */
(20) }
(21) if(S[j]? a||S[j]? a)
(22) {
(23) K=K+1；
(24) S[K]=a；
45
(25) ip指向下一输入符；
(26) }
(27) else if (S[j]? a) /*归约 */
(28) {
(29) do
(30) {
(31) b=S[j]；
(32) if(S[j-1]∈ VT )
46
(33) {
(34) j=j-1；
(35) }
(36) else
(37) {
(38) j=j-2；
(39) }
(40) }while(S[j]? b)
(41) 把 S[j+1]… S[K]归约为某个 N；
(42) K=j+1；
47
(43) S[K]=N；
(44) }
(45) else
(46) {
(47) error();
(48) }
(49) }
(50) }
图 4.13 算符优先控制程序
48
[例 4.12]文法 (4.4)i+i*i的算法优先分析过程如图 4.14所示 。
分析栈 输入串 动作
$ i+i*i$ $ i
$i +i*i$ i + 归约
$F +i*i$ $ +
$F+ i*i$ + i
$F+i *i$ i * 归约
$F+F *i$ + *
$F+F* i$ * i
$F+F*i $ i $ 归约
$F+F*F $ * $ 归约
$F+T $ + $ 归约
$E $ 结束
49
三、优先关系表的构造
},,|{)(
},,|{)(
NT
NT
VQVaaQPaPaPLA S TV T
VQVaQaPaPaPF I R S TV T
或或
E
E T+
i
T * F
F iF
T
i
图 4.15 相应的句柄规约
50
问题在于如何求出每个非终结符的 FIRSTVT集和 LASTVT集 。
构造 FIRSTVT(P)可遵照下列两条规则：
·若有产生式 或 P →Qa …,则 ；
·若有产生式 则 。
构造 LASTVT(P)有类似的两条规则：
·若有产生式 或,则 ；
·若有产生式 则 。
[例 4.13]文法 (4.4)的 FIRTVST集和 LASTVT集,是这样得到的：
由 F?(E)|i,FIRSTVT(F)={(,I},LASTVT(F)={）,i}
由 T?T*F|F,FIRSTVT(T)={*,(,I},LASTVT(F)={*,）,i}
由 E?E+T|T,FIRSTVT(E)={+,*,(,I},LASTVT(F)={+,*,),i}
参照前节 FIRST集的成员表表示法,本例的 FIRST集,LASTVT集也可用成员表表示,其中用 √ 表示 FIRST集的成员,○ 表示 LASTVT集的成员,则有图 4.16
aP? )( PF IR S T V Ta?
QP? )()( PF I R S T V TQF I R S T V T?
aP aQP
)( PL A S T VTa?
QP )()( PL A S T V TQL A S T V T?
51
+ * i ( ) $
+
*
i
(
)
$
+ * （ ） i
E?E+T|T √ ○ √ ○ √ ○ √ ○
T?T*F|F √ ○ √ ○ √ ○
F?(E)|i √ ○ √ ○
于是,由,有 + +,* +,) +,i +,+ *,+ (,+ i
由,有 * *,) *,i *,* (,* i
由,有 ( ),( +,( *,( (,( i,+ ),* ),) ),i )
TEE
FTT *?
)(EF?
52
四,优先函数用优先关系表来表示每对终结符之间的优先关系,存储量大,查讯费时 。 如果对每个终结符赋以一个值 (这就定义了终结符的一个函数 f)，
值的大小恰反映了优先关系,则终结符 a,b间的优先关系便转换成终结符的优先函数值 f(a),f(b)的比较 。 这样优先表可以省了,比较也方便了 。
·一个终结符在栈中 (左 )在输入串中 (右 )的优先值是不同的,如有 +? )
且有 )? +。 因此对一个终结符而言它应有一个左优先数和一个右优先数 。 这就定义了终结符的一对函数 f,g,要求满足：
如 a b,则应有 f(a)=g(b)；
如 a b,则应有 f(a)<g(b)；
如 a b,则应有 f(a)>g(b)。
这对优先函数中的 f通常称为入栈函数,g称为比较函数 。
53
·优先函数并不唯一,若 (f,g)是优先函数,显然 (f+m,g+m)也是优先函数 。
·算符优先文法 (即有确定的优先关系表 )不一定有优先函数,如对图
4.17给出的优先关系表就不存在优先函数,因为若存在优先函数 (f,
g),则
f(a)=g(a) f(a)>g(b) 图 4.17优先表
f(b)=g(a) f(b)=g(b)
于是有 f(a)>g(b)=f(b)=g(a)=f(a),得到 f(a)>g(a)的矛盾关系 。
a b
a
b
54
§ 4.5 LR分析器一,LR分析法
a1 ai $
Xm-1
$
…
控制程序分析表输出图 4.23 LR分析器模型
Sm-1
0
…
XmSm
gotoaction
55
状态
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
11 r5 r5 r5 r5
图 4.21 文法 (4.4)的 LR分析表
56
分析程序对任何 LR分析器都适用 。 它从输入串中读入当前输入符
a,然后由栈顶状态 si与当前输入字符 a查 action表,决定应取何种动作 。
·若为 sj,则将状态 j(连同相应的输入符 a)移入栈顶 。
·若为 rj,则按第 j个产生式 归约,设右部符号 的长度为 t,将分析栈顶 t个状态 (连同它们的文法符号 )上托出栈,设呈现栈顶的状态为,归约后的非终结符为 A,查 goto表的 项,
得到状态 j,将状态 j(连同文法符 A)移入栈顶 。
·若为 acc,则结束分析,输入串被接受 。
·其他转错误处理程序 。
AS,?
b?A b
S?
57图 4.24 i+i*i的 LR分析过程分析栈 输入串 动作
1 0$ i+i?i$ s5
2 0$ 5i +i?i$ r5,F?i goto(0,F)=3
3 0$ 3F +i?i$ r4,T?F goto(0,T)=2
4 0$ 2T +i?i$ r2,E?T goto(0,E)=1
5 0$ 1E +i?i$ s6
6 0$ 1E 6+ i?i$ s5
7 0$ 1E 6+5i?i$ r6,F?i goto(6,F)=3
8 0$ 1E 6+3F?i$ r4,T?F goto(6,F)=9
9 0$ 1E 6+9T?i$ s7
10 0$ 1E 6+9T 7* i$ s5
11 0$ 1E 6+9T 7*5i $ r6,F?i goto(7,F)=10
12 0$ 1E 6+9T 7*10F $ r3,T?T*F goto(6,T)=9
13 0$ 1E 6+9T $ r1,E?E+T goto(0,E)=1
14 0$ 1E $ acc
58
二,识别活前缀的 DFA
定义 4.8 规范句型的一个前缀,如果它不含句柄后任何符号,则称它是该规范句型的一个活前缀 。 也即若 是文法的一个产生式,S是文法开始符,并有：
则 的任何前缀都是规范句型 的活前缀 。
在上述定义中,是句型 关于 A的直接短语，并且是一次最右推导 (规范推导 )，所以 是最左直接短语，是一句柄，因此的任何前缀不含句柄后的任何符号，特别，句柄 是 的后缀，是分析栈栈顶的符号串。
a b RR AS*
ab
ab?
ab?A
ab
ab?
ab?ab
ab?ab
59
作为规范句型的活前缀不含句柄后的任何符号,这就决定了活前缀与句柄之间只可能有三种关系：
(1) 活前缀不含句柄的任何符号,此时期待从剩余输入串中识别由的 所能推导出的符号串 。
(2) 活前缀只含句柄的真前缀,也即产生式 中 已识别于分析栈顶之上,期待从剩余输入串中识别由 所能推导出的符号串 。
(3) 活前缀已含句柄的全部符号,这表明 的右部符号串已在分析栈顶,分析动作应为按此产生式将 归约为 A。
由此可见句柄是一类活前缀的后缀,如果能识别一个文法的所有活前缀,自然也就能识别这个文法的所有句柄了,所以我们将讨论如何识别文法的活前缀 。
首先我们采用下列形式分别表示上述三种情况,即：
abab?A
a
b
.,.,,abbaab AAA
ab?A
ab?A
ab
ab
60
一个产生式如,根据圆点的位置不同可以有通常我们称 为归约项目称 及 为待约项目,
称 为移进项目
T.EE
.TEE
TE.E
T.EE
TEE
T.EE
TE.E T.E?
TE.E
61
对于像 (4.4)这样的文法,文法开始符的产生式不唯一：
这样就会有两个归约项目 和 。 同时,E又在产生式右部出现,这两个归约项目并不意味着分析的结束 。 为此,对任何文法 G,我们总是将 G拓广为等价的 G’,它以 S’为文法开始符,增加了一个产生式,其中 S为 G的文法开始符,这样接受项目 便可唯一了 。
可以利用文法的所有项目作为状态来构造一个识别所有活前缀的 NFA，
其中 为唯一的初态,任何状态均认为是 NFA的终态,它作为活前缀识别态,如果状态 i为：
而状态 j为：
则由状态 i画一标记为 的有向边至状态 j，如果状态 i中 为一非终结符，
则从状态 i画 有向边至所有 xi→,a的状态。这样就构成一个识别活前缀的 NFA。
TTEE |
T.EE
T.E?
SS,SS
nii xxxxX,11
nii xxxxX 11,
SS,
ix
ix
62
定义 4.9 对于项目,如果有：
则称 对活前缀 有效 。
如果项目 对活前缀 有效,也即有：
设,关于 B的产生式为,则有：
因 也是对活前缀 有效的项目,这说明,对活前缀有效的项目可能还不止一个 。 于是对活前缀 有效的项目的集合称为的有效项目集 。 文法 G的所有对活前缀有效的项目集组成的集合称为文法 G的 LR(0)项目集规范族 C。
a b RR AS*ba.?A
a
ba BA,?
b*RB
aaba RRRR BBAxS **
.?B
ba.?A
a?a b RR AS*
a?a
a
63
I0,SE
EE+T
ET
TT*F
TF
F(E)
Fi
SE?I1,
E?E?+T
I2,E?T?
T?T?*F
F?i?
I3,
I4,
T?F?
F?(.E)
EE+T
ET
TT*F
TF
F(E)
Fi
I5,
I6,
I7,
I8,
E?E+?T F?i?
F?i?
F?i?
F?i?
T?T*?F
F(E)
Fi
F?(E?)
E?E?+T
TT*F
TF
F(E)
Fi
I9,
I10,
I11,
图 4.26 文法 (4.9)的 LR(0)项目集规范族
64
三,SLR分析表的构造
LR分析表，其实就是识别活前缀的带下推栈的 DFA，
DFA的状态便是对活前缀有效的项目集，
项目集中的各个项目指出了在识别活前缀后应执行的动作，这便是 action
表中的内容，
这里存在着：
移进 —— 归约的冲突。
归约 —— 归约的冲突。
解决上述冲突的一种简单办法是考察 FOLLOW(A)和 FOLLOW(B)，
如果 {b}与 FOLLOW(A),FOLLOW(B)两两不交，则移进或归约的动作便可唯一确定。
输入字符为 a时
(1) a＝ b,则移进；
(2),则用 归约；
(3),则用 归约；
(4) 此外出错 。
.},,,.{ aaba BAbXI
F O L L O W ( A ) a? a?A
F O L L O W ( B )a? a?B
65
SE
EE
+T
ET
TT
*F
TF
F(
E)
Fi
SE?
E?E?+T
E?T?
T?T?*F
T?F?
F?(.
E)
EE
+T
ET
TT
*F
TF
F(
E)
Fi
F?i?
E?E
+?T
TT
*F
TF
F(
E)
Fi
T?T*?F
F(E)
Fi
F?(E?)
E?E?+T
E?
E+T?
T?
T?*F
T?T*F?
F?(E)?
I1
:
I2
:
I3:
I4:
I5
:
I6:
I7
:
I8
:
I9:
I10:
I11:
I0,状态
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
11 r5 r5 r5 r5
FOLLOW(E)＝ {+,),$}
FOLLOW(T)＝ FOLLOW(F)＝ {+,*,},$}
66
四,LR(1)分析表的构造
LR
i|*RL
R|RLS
设文法 G为：
FOLLOW(S)＝ {$}
FOLLOW(L)＝ FOLLOW(R)＝ {＝,$}
67
I0＝ {SS,SL＝ R,SR,L*R,Li,RL}
I1＝ go(I0,S)＝ {SS?},故 goto[0,S]＝ 1
I2＝ {S?L?＝ R,R?L?},故 goto[0,L]＝ 2
I3＝ {S?R?},故 goto[0,R]＝ 3
I4＝ {L?*?R,RL,L*R,Li},故 action[0,*]＝ S4
I5＝ {L?i?},故 action[0,i]＝ S5
由 I1,故 action[1,$]=acc
对 I2：
由 S?L?＝ R,记 go(I2,＝ )＝ I6,则 action[2,＝ ]＝ S6
由 R?L?,由于 FOLLOW(R)＝ {＝,$}
action[2,＝ ]＝ s6
action[2,=]＝ r5
action[2,＝ ] 处 发 生 了 移 进 与 归 约 的 冲 突,这 是 因 为,
{＝ }∩FOLLOW(R) ＝ {＝ }。
68
重新定义项目为一二元组形式：
{A?a?b,a1…ak}
只讨论 k＝ 1的情况：对于 LR(1)的项目 [A?a?b,a]，如果有：
,而则称该项目对活前缀?a有效 。
如果项目 [A?a?Bb,a]对活前缀?a有效,并且有 B
则对任何 b?FOLLOW(),[B,b]也对活前缀?a有效,这里,
FOLLOW()＝ FOLLOW(b?)＝ FOLLOW(ba)。
},|{)( * TVaAaSaAF OL L OW
AS R*?
),(
$,
F I R S Ta
aaba RRRR BBAS **
b*R
a b RR AS*
69
I0＝ closure({[SS,$]})＝ {[SS,$]},[SL＝ R,$],[SR,$]，
[L*R,＝ |S],[Li,＝ |$],[RL,$]}
I1＝ go(I0,S)＝ {[SS?,$]}
I2＝ go(I0,L)＝ {[S?L?＝ R,$],[R?L?,$]}
I3＝ go(I0,R)＝ {[S?R?,$]}
I4＝ go(I0,*)＝ {[L?*?R,＝ |$],[RL,＝ |$],[L*R,＝ |$],[Li,＝ |$]}
I5＝ go(I0,i)＝ {[L?i?,＝ |$]}
I6＝ go(I2,＝ )＝ {[S?L＝?R,$],[RL,$],[L*R,$],[Li,$]}
I7＝ go(I4,R)＝ {[L?*R?,＝ |$]}
I8＝ go(I4,L)＝ {[R?L?,＝ |$]}
I9＝ go(I6,R)＝ {[S?L＝ R?,$]}
I10＝ go(I6,L)＝ {[R?L?,$]}
I11＝ go(I6,*)＝ {[L?*?R,$],[RL,$],[L*R,$],[L→,i,$] }
I12＝ go(I6,i)＝ {[L?i?,$]}
I13＝ go(I11,R)＝ {[L?*R?,$]}
70
图 4.28 文法 (4.11)的 LR(1)分析表状态 Action goto
＝ * i $ S L R
0 s4 s5 1 2 3
1 acc
2 s6 r5
3 r2
4 s4 s5 8 7
5 r4 r4
6 s11 s12 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 s11 s12 10 13
12 r4
13 r3
71
五,LALR分析表的构造两个 LR(1)的项目集,如果除了搜索符,它们是两两相同的,则称这两个项目集为同心集 。
除去初态项目外,一个项目集的核是由此项目集中那些圆点不在最左端的项目组成,而初态项目集的核仅为 {[SS,$]}。
例如,例 4.20中,I8与 I10,I4与 I11,I5与 I12,I7与 I13是两两同心的,而
I2的核为 I2本身,I4的核为 {[L?*?R,＝ |$]},I6的核为 {[S?L＝?R,$]}。
如果将同心的 LR(1)的项目集合并,显然项目集的个数 (即状态数 )与 SLR
相同；如果用核代替项目集,则可以压缩项目集的大小 。 这两种方法都能起压缩空间的作用,这就是 LALR分析法的基本思想,现分别进行讨论 。
例如,在例 4.20中将
I10与 I8合并为 I8?＝ {[R?L?,＝ |$]}
I11与 I4合并为 I4?＝ {[L?*?R,＝ |$],[RL,＝ |$]，
[L*R,＝ |$],[Li,＝ |$]}
I12与 I5合并为 I5?＝ {[L?i?,＝ |$]}
I13与 I7合并为 I7?＝ {[L?*R?,＝ |$]}
于是状态数由原来 14个减少为 10,不难发现它恰为 LR(0)项目集的个数 。
72
图 4.29 文法 (4.11)的 LALR分析表状态 Action goto
＝ * i $ S L R
0 s1 s5 1 2 3
1 Acc
2 S6 r5
3 r2
4 s4 s5 8 7
5 R4 r4
6 s4 s5 8 9
7 R3 r3
8 R5 r5
9 r1
73
(1) 不可能引起移进? 归约冲突。如果合并后的项目集 I含有移进? 归约冲突：即 [A?a?,a]?I，
它表明当前输入符为 a时，按 A?a归约；并且
[B?a?ab,b]?I，它要求将 a移进。注意到在合并同心集的过程中，合并前的项目集应有相同的
,心,,即 LR(0)项目集，只是搜索符可能不同，
但搜索符也必须在合并前的某个项目集中出现。
则合并前的项目集中至少有一个项目集，它含有
[A?a?,a]和 [B?a?ab,c]这就表明合并前已经有移进? 归约冲突，与假设不符。因此无冲突的
LR(1)项目集在合并同心集时不会引起移进? 归约冲突。
(2) 有可能引起归约? 归约冲突。
74
§ 4.6 二义文法的应用
G1文法,E?E+E|E*E|(E)|i
G2文法,E?E+T|T
T?T*F|F
F?(E)|i
他们的比较：
二义 VT VN P
G1 Y 5 1 4
G2 N 5 3 6
75
I0,S.E
E?.E+E
E?.E*E
E?.(E)
E?.i
I1,SE.
E?E.+E
E?E.*E
I2,E?(.E)
E?.E+E
E?.E*E
E?.(E)
E?.i
I3,E?i.
I4,E?E+.E
E?.E+E
E?.E*E
E?.(E)
E?.i
I5,E?E*.E
E?.E+E
E?.E*E
E?.(E)
E?.i
I6,E?(E.)
E?E.+E
E?E.*E
I7,E?E+E.
E?E.+E
E?E.*E
I8,E?E*E.
E?E.+E
E?E.*E
I9,E?(E).
76
空间大小为 10× 7与 12× 9之比状态
action goto
i + * ( ) $ E
0 s3 s2 1
1 s4 s5 acc
2 s2 s2 6
3 r4 r4 r4 r4
4 s3 s2 7
5 s3 s2 8
6 s4 s5 s9
7 r1 s5 r1 r1
8 r2 r2 r2 r2
9 r3 r3 r3 r3
