文法例 1
文法 Gz,Z ? D
Z ? Z D
D ? 0 |1 |… |9
句子 12的推导：
Z ? ZD ?DD ?1D ?12
Z ? ZD ?DD ?D2 ?12
Z
Z D
D
1
2
文法例 2
?文法 G=({+,*,i,(,)},{E},E,P),其中 P为：
? E ? i
? E ? E + E
? E ? E * E
? E ? ( E )
? 句型 i * i + i,
推导 1,E ? E + E ? E * E + E ? i * E + E
? i * i + E ? i * i + i
E + E
E
E * E
i i
推导 1的语法树
i
E
E * E
E + E
i i
推导 2的语法树
i
推导 2,E ? E * E ? i * E
? i * E + E ? i * i + E ? i * i + i
<Stm> →if <Exp> then <Stm> else <Stm>
<Stm> →if <Exp> then <Stm>
<Stm> →,.....
假设有条件语句
if e1 then if e2 then s1 else s2
则可有下图所示的两棵不同的语法分析树：
if语句的二义性
if
if
then
<Stm>
<Stm><Stm>
<Stm>
elsethen<Exp>
<Exp>e1
e2 s1
s2
<Stm>
<Stm><Stm>
<Stm>
elsethenif
thenif
<Exp>
<Exp>
e1
e2 s1 s1
文法二义性的消除
?二义性文法的判定是递归不可解的
?消除二义性的方法：
? 1.设置一规则，该规则可在产生二义
性的情况下，指出哪一个分析树是正确的
? 2.将文法改变成一个强制正确分析树
的构造格式
表达式的无二义性文法
?E ? T
?E ? E + T
?T ? F
?T ? T * F
?F ? ( E )
?F ? i
?E ? T | E + T
?T ? F | T * F
?F ? ( E ) | i
If语句的无二义性文法定义
Stmt ? Matched_stmt
| Unmatched_stmt
Matched_stmt ?if E then Matched_stmt else
Matched_stmt
| other
Unmatched_stmt ?if E then Stmt
| if E then Matched_stmt
else Unmatched_stmt
有关文法实用中的一些说明
? 有关文法的实用限制
? 有害规则 U ? U
? 多余规则 { 不可到达的，不可终止的 }
? 上下文无关文法中的 ?规则 A ? ?
文法 G[s]:
1) S?? B e
2) B ? C e
3) B ? A f
4) A ? A e
5) A ? e
6) C ? C f
7) C ? C
8) D ? f
求能推出 ?的非终极符
? S_Lambda = {Aj | Aj ? ? ? PSet};
? 对 p?PSet,Ap ? X1… Xn,
如果 Xi?S_Lambda,0?i?n,则
S_Lambda = S_Lambda ? {Ap}
? 重复第二步，直至 S_Lambda收敛为止
消除空产生式算法
?S_Lambda = {Aj | Aj ?+ ?};
? 删除所有的空产生式和只能导出空串的非终
极符。
? 对剩余的每个产生式 P,A?C1C2… Cp
如果有 Ci?S_Lambda,因为删除了所有的空
产生式，需要扩充一些产生式,
A?C1… Ci-1Ci+1… Cp
? 重复上述过程直至不出现新的产生式为止。
语法分析方法
? 自顶向下分析方法
递归子程序法
LL分析方法
? 自底向上分析方法
优先关系法
LR分析方法
自顶向下分析概述
? 从文法开始符出发试图推导出所给的终极符串。
? 例 G[z], [1] Z ?aBd [2] B ?d
[3] B ?c [4] B ?bB
对给定的终极符串 abcd,推导过程：
Z ?[1] aBd ?[4] abBd ?[3] abcd
aBd # abcd # Match
Bd # bcd # Derivation
bBd # bcd # Match
Bd # cd # Derivation
cd # cd # Match
d # d # Match
# # Success
自顶向下的语法分析过程【 Sf,Rest,Action(D/M/S/E)】
Z # abcd # Derivation
Z
a B d
b B
c
自底向上分析概述
? 从终极符串出发归约（ reduce） 出文法的开始符。
? 例 G[z], [1] Z ?aBd [2] B ?d
[3] B ?c [4] B ?bB
对给定的终极符串 abcd,归约过程：
abcd ?[3] abBd?[4] aBd ?[3] Z
#a bcd # Shift
#ab cd # Shift
#abc d # Reduce[3]
#abB d # Reduce[4]
#aB d # Shift
#aBd # Reduce[1]
#Z # Success
自底向上的语法分析过程【 Analysis ST,Input,Action(S/R/E/S)】
# abcd # Shift
a b c d
B
B
Z
文法 G1[S],S ? pA | qB
A ? cAd | a
输入串 W= pccadd。 自顶向下的推导过程为,
S
? pA
? pcAd
? pccAdd
? pccadd
相应的语法树为：
p A
c A d
c A d
a
S
文法 G2[s],S ?Ap |Bq
A ?a |cA
B ?b |dB
输入串 W=ccap。 自顶向下的推导过程为,
S
? Ap
? cAp
? ccAp
? ccap
相应的语法树为：
S
A p
c A
c A
a
First集的定义
设 G=(VT,VN,S,P)是上下文无关文法,
??(VT ? VN )*
First(?)={ a ?VT | ??* a...}
?(if ??*? then {?})
? 可以根据当前的输入符号是属于哪个产生式右
部的首符集而决定选择相应产生式进行推导 。
文法 G3[S],S ? aA | d
A ? bAS | ?
输入串 W=abd。 自顶向下的推导过程为,
S
? aA
? abAS
? abS
? abd
相应的语法树为：
S
a A
b A S
? d
Follow集的定义
设 G=(VT,VN,S,P)是上下文无关文法,A?VN，
S是开始符号
?Follow(A)={ a ?VT | S?+,..Aa..,}
? (if S?*......A then {#} )
? 当文法中存在 产生式 形如,A??时，如果当
前的字符属于 Follow(A)，则用空取代 A的出
现。
三个集合的定义
?First(?) ={ a ?VT | ??* a......}
? ( if ??*? then {?} )
?Follow(A) = { a ?VT | S?+,...Aa....,}
? ( if S?*......A then {#} )
? Predict(A→ ?)
= First(?), 当 ??First(?)
= First(?)-{?}?Follow(A), 当 ??First(?)
计算 First(X)集
对每一文法符号 X计算 First(X)
? 若 X?VT,First(X)={X}
? 若 X?VN则
First(X)={a| X?a… ?PSet,a ?VT}
? 若 X?VN,且有产生式 X??,则 ?? First(X)
? 若 X?VN,有产生式 X?Y1Y2… Yn,且 Y1,Y2,…,Yi ?VN
当 Y1,Y2,…,Yi-1?* ?，
则 First(Y1)-{?},First(Y2)-{?},…
First(Yi-1)-{?},First(Yi)都包含在 First(X)中。
当 Yi ?* ?(i=1,2,… n),将 {?}并入 First(X) 中。
计算 First(?)集
若符号串 ?=X1X2… Xn，
? 当 X1,X2,… Xi-1?*?,Xi不能 ?* ?，则
?First(?)=?1i-1(First(Xj)-{?}) ? First(Xi)
? 若所有 Xi都能 ?*?，则
?First(?)= ?1nFirst(Xj)
计算 Follow集
1:对所有 A?VN,令 Follow(A):={ }； 对开始符 S,
令 Follow(S):={# }；
2:若有产生式 A→xBy,
如果 ??First(y) 则：
Follow(B):= First(y)
否则
Follow(B):=(First(y)－ {?}) ? Follow(A)
3:重复 2和 3,直至对所有 A?VN,Follow(A)收
敛为止 。
计算 Predict集
? Predict(A→ ?)
= First(?), 当 First(?)不含 ?
= First(?)-{ ?} ? Follow(A),
当 First(?)含 ?
? E? ? T E’
? E’ ? + T E’ | ?
? T ? F T’
? T’ ? * F T’ | ?
? F ? id | ( E )
Predict( E?TE’ ) = first(TE’) = { id,( }
Predict( E’ ?+TE’ ) = first(+TE’) = { + }
Predict( E’ ? ? ) = follow(E’) = { ),# }
Predict( T ? FT’ ) = first(FT’) = { id,( }
Predict( T’ ?*FT’ ) = first(*FT’) = { * }
Predict( T’ ? ? ) = follow(T’) = { +,),# }
Predict( F ?id ) = first(id) = { id }
Predict( F ?(E) ) = first((E)) = { ( }
3型（正则）文法与自动机
?3型文法与产生式的形式为：
A ? ?B 或 A ? ?
的文法等价。其中 ??VT＋ 。
? 定理,3型文法与自动机等价
3型文法到自动机的转换
? 设给定 3型文法 G=(VN,VT,P,Z),构造一
个自动机 A=(S,?,?,s0,F),使得 L(A)=L(G)。
? 构造过程：
(1)令 S = VN?{K},?=VT,s0= Z,F={K}.
(2)对 G中产生式形如：
X ? aY 则定义 ?(X,a)= Y?P
X ? a 则定义 ?(X,a)= K?P
其中 K是新符号。
则 L(A)= L(G)
自动机到 3型文法的转换
? 给定自动机 A=(S,?,?,s0,F),构造等价的
3型文法 G=(VN,VT,P,Z),使得 L(A)=L(G)
(只有一个初始状态 )
? 构造过程：
设 F’= {Y| Y?F且 Y有输出边 }
(1) 令 VN= S\F’,VT= ?,Z= s0
(2) 如有 ?(X,a)=Y,
如果 Y?F,则定义 X?a
如果 Y?F’,则定义 X?aY
则 L(A)= L(G)
? 文法 G[N]:
N ? D |N D
D ? 0 |1 | 2| … | 9
（ 1)写出 5678和 021的最左推导和最右推导，并给出
它们的语法树形式
（ 2）举出三个无最右推导的句型
? 文法 G[S]:
S ? uBDz B ? Br | w D ? EF
E ? y | ? F ? x | ?
计算非终极符的 First,Follow集，产生式的
Predict集
文法 Gz,Z ? D
Z ? Z D
D ? 0 |1 |… |9
句子 12的推导：
Z ? ZD ?DD ?1D ?12
Z ? ZD ?DD ?D2 ?12
Z
Z D
D
1
2
文法例 2
?文法 G=({+,*,i,(,)},{E},E,P),其中 P为：
? E ? i
? E ? E + E
? E ? E * E
? E ? ( E )
? 句型 i * i + i,
推导 1,E ? E + E ? E * E + E ? i * E + E
? i * i + E ? i * i + i
E + E
E
E * E
i i
推导 1的语法树
i
E
E * E
E + E
i i
推导 2的语法树
i
推导 2,E ? E * E ? i * E
? i * E + E ? i * i + E ? i * i + i
<Stm> →if <Exp> then <Stm> else <Stm>
<Stm> →if <Exp> then <Stm>
<Stm> →,.....
假设有条件语句
if e1 then if e2 then s1 else s2
则可有下图所示的两棵不同的语法分析树：
if语句的二义性
if
if
then
<Stm>
<Stm><Stm>
<Stm>
elsethen<Exp>
<Exp>e1
e2 s1
s2
<Stm>
<Stm><Stm>
<Stm>
elsethenif
thenif
<Exp>
<Exp>
e1
e2 s1 s1
文法二义性的消除
?二义性文法的判定是递归不可解的
?消除二义性的方法：
? 1.设置一规则，该规则可在产生二义
性的情况下，指出哪一个分析树是正确的
? 2.将文法改变成一个强制正确分析树
的构造格式
表达式的无二义性文法
?E ? T
?E ? E + T
?T ? F
?T ? T * F
?F ? ( E )
?F ? i
?E ? T | E + T
?T ? F | T * F
?F ? ( E ) | i
If语句的无二义性文法定义
Stmt ? Matched_stmt
| Unmatched_stmt
Matched_stmt ?if E then Matched_stmt else
Matched_stmt
| other
Unmatched_stmt ?if E then Stmt
| if E then Matched_stmt
else Unmatched_stmt
有关文法实用中的一些说明
? 有关文法的实用限制
? 有害规则 U ? U
? 多余规则 { 不可到达的，不可终止的 }
? 上下文无关文法中的 ?规则 A ? ?
文法 G[s]:
1) S?? B e
2) B ? C e
3) B ? A f
4) A ? A e
5) A ? e
6) C ? C f
7) C ? C
8) D ? f
求能推出 ?的非终极符
? S_Lambda = {Aj | Aj ? ? ? PSet};
? 对 p?PSet,Ap ? X1… Xn,
如果 Xi?S_Lambda,0?i?n,则
S_Lambda = S_Lambda ? {Ap}
? 重复第二步，直至 S_Lambda收敛为止
消除空产生式算法
?S_Lambda = {Aj | Aj ?+ ?};
? 删除所有的空产生式和只能导出空串的非终
极符。
? 对剩余的每个产生式 P,A?C1C2… Cp
如果有 Ci?S_Lambda,因为删除了所有的空
产生式，需要扩充一些产生式,
A?C1… Ci-1Ci+1… Cp
? 重复上述过程直至不出现新的产生式为止。
语法分析方法
? 自顶向下分析方法
递归子程序法
LL分析方法
? 自底向上分析方法
优先关系法
LR分析方法
自顶向下分析概述
? 从文法开始符出发试图推导出所给的终极符串。
? 例 G[z], [1] Z ?aBd [2] B ?d
[3] B ?c [4] B ?bB
对给定的终极符串 abcd,推导过程：
Z ?[1] aBd ?[4] abBd ?[3] abcd
aBd # abcd # Match
Bd # bcd # Derivation
bBd # bcd # Match
Bd # cd # Derivation
cd # cd # Match
d # d # Match
# # Success
自顶向下的语法分析过程【 Sf,Rest,Action(D/M/S/E)】
Z # abcd # Derivation
Z
a B d
b B
c
自底向上分析概述
? 从终极符串出发归约（ reduce） 出文法的开始符。
? 例 G[z], [1] Z ?aBd [2] B ?d
[3] B ?c [4] B ?bB
对给定的终极符串 abcd,归约过程：
abcd ?[3] abBd?[4] aBd ?[3] Z
#a bcd # Shift
#ab cd # Shift
#abc d # Reduce[3]
#abB d # Reduce[4]
#aB d # Shift
#aBd # Reduce[1]
#Z # Success
自底向上的语法分析过程【 Analysis ST,Input,Action(S/R/E/S)】
# abcd # Shift
a b c d
B
B
Z
文法 G1[S],S ? pA | qB
A ? cAd | a
输入串 W= pccadd。 自顶向下的推导过程为,
S
? pA
? pcAd
? pccAdd
? pccadd
相应的语法树为：
p A
c A d
c A d
a
S
文法 G2[s],S ?Ap |Bq
A ?a |cA
B ?b |dB
输入串 W=ccap。 自顶向下的推导过程为,
S
? Ap
? cAp
? ccAp
? ccap
相应的语法树为：
S
A p
c A
c A
a
First集的定义
设 G=(VT,VN,S,P)是上下文无关文法,
??(VT ? VN )*
First(?)={ a ?VT | ??* a...}
?(if ??*? then {?})
? 可以根据当前的输入符号是属于哪个产生式右
部的首符集而决定选择相应产生式进行推导 。
文法 G3[S],S ? aA | d
A ? bAS | ?
输入串 W=abd。 自顶向下的推导过程为,
S
? aA
? abAS
? abS
? abd
相应的语法树为：
S
a A
b A S
? d
Follow集的定义
设 G=(VT,VN,S,P)是上下文无关文法,A?VN，
S是开始符号
?Follow(A)={ a ?VT | S?+,..Aa..,}
? (if S?*......A then {#} )
? 当文法中存在 产生式 形如,A??时，如果当
前的字符属于 Follow(A)，则用空取代 A的出
现。
三个集合的定义
?First(?) ={ a ?VT | ??* a......}
? ( if ??*? then {?} )
?Follow(A) = { a ?VT | S?+,...Aa....,}
? ( if S?*......A then {#} )
? Predict(A→ ?)
= First(?), 当 ??First(?)
= First(?)-{?}?Follow(A), 当 ??First(?)
计算 First(X)集
对每一文法符号 X计算 First(X)
? 若 X?VT,First(X)={X}
? 若 X?VN则
First(X)={a| X?a… ?PSet,a ?VT}
? 若 X?VN,且有产生式 X??,则 ?? First(X)
? 若 X?VN,有产生式 X?Y1Y2… Yn,且 Y1,Y2,…,Yi ?VN
当 Y1,Y2,…,Yi-1?* ?，
则 First(Y1)-{?},First(Y2)-{?},…
First(Yi-1)-{?},First(Yi)都包含在 First(X)中。
当 Yi ?* ?(i=1,2,… n),将 {?}并入 First(X) 中。
计算 First(?)集
若符号串 ?=X1X2… Xn，
? 当 X1,X2,… Xi-1?*?,Xi不能 ?* ?，则
?First(?)=?1i-1(First(Xj)-{?}) ? First(Xi)
? 若所有 Xi都能 ?*?，则
?First(?)= ?1nFirst(Xj)
计算 Follow集
1:对所有 A?VN,令 Follow(A):={ }； 对开始符 S,
令 Follow(S):={# }；
2:若有产生式 A→xBy,
如果 ??First(y) 则：
Follow(B):= First(y)
否则
Follow(B):=(First(y)－ {?}) ? Follow(A)
3:重复 2和 3,直至对所有 A?VN,Follow(A)收
敛为止 。
计算 Predict集
? Predict(A→ ?)
= First(?), 当 First(?)不含 ?
= First(?)-{ ?} ? Follow(A),
当 First(?)含 ?
? E? ? T E’
? E’ ? + T E’ | ?
? T ? F T’
? T’ ? * F T’ | ?
? F ? id | ( E )
Predict( E?TE’ ) = first(TE’) = { id,( }
Predict( E’ ?+TE’ ) = first(+TE’) = { + }
Predict( E’ ? ? ) = follow(E’) = { ),# }
Predict( T ? FT’ ) = first(FT’) = { id,( }
Predict( T’ ?*FT’ ) = first(*FT’) = { * }
Predict( T’ ? ? ) = follow(T’) = { +,),# }
Predict( F ?id ) = first(id) = { id }
Predict( F ?(E) ) = first((E)) = { ( }
3型（正则）文法与自动机
?3型文法与产生式的形式为：
A ? ?B 或 A ? ?
的文法等价。其中 ??VT＋ 。
? 定理,3型文法与自动机等价
3型文法到自动机的转换
? 设给定 3型文法 G=(VN,VT,P,Z),构造一
个自动机 A=(S,?,?,s0,F),使得 L(A)=L(G)。
? 构造过程：
(1)令 S = VN?{K},?=VT,s0= Z,F={K}.
(2)对 G中产生式形如：
X ? aY 则定义 ?(X,a)= Y?P
X ? a 则定义 ?(X,a)= K?P
其中 K是新符号。
则 L(A)= L(G)
自动机到 3型文法的转换
? 给定自动机 A=(S,?,?,s0,F),构造等价的
3型文法 G=(VN,VT,P,Z),使得 L(A)=L(G)
(只有一个初始状态 )
? 构造过程：
设 F’= {Y| Y?F且 Y有输出边 }
(1) 令 VN= S\F’,VT= ?,Z= s0
(2) 如有 ?(X,a)=Y,
如果 Y?F,则定义 X?a
如果 Y?F’,则定义 X?aY
则 L(A)= L(G)
? 文法 G[N]:
N ? D |N D
D ? 0 |1 | 2| … | 9
（ 1)写出 5678和 021的最左推导和最右推导，并给出
它们的语法树形式
（ 2）举出三个无最右推导的句型
? 文法 G[S]:
S ? uBDz B ? Br | w D ? EF
E ? y | ? F ? x | ?
计算非终极符的 First,Follow集，产生式的
Predict集
