当前位置:首页 >> 小学教育 >>

山东理工大学-编译原理内部课件-第五章:自顶而下语法分析方法


第5章 自顶向下语法分析方法
?

?
? ?

?

?

?

5.1 确定的自顶向下语法分析思想 5.2 LL(1)文法的判别 5.4 不确定的自顶向下分析思想 5.3 某些非LL(1)文法到LL(1)文法的等价变换 ? 回溯——提取公共左因子 ? 无限循

环——消除左递归 5.5 确定的自顶向下分析方法 ? 5.5.1 递归子程序法 ? 5.5.2 预测分析方法 本章练习 作业
课程目录
1

内容回顾
?句型、句子和语言的定义: ?句型
?有文法G[S],若S ==*>α ,且α ∈V*, 是α 是文法G的一个句型。 则称

?句子
?有文法G[S],若S ==*>α ,且α ∈VT* ,则称 是α 是文法G的一个句子。

?语言
?由文法 G 产生的所有句子的集合 L(G)={α |S==+>α ,且α ∈VT*}
2

?最左(最右)推导 ?句型分析(句子分析)

内容回顾(续)

?在推导的任何一步α==*>β(其中α和β是句型), 都 对α中的最左(最右)非终结符进行替换。

?识别一个符号串是否为某文法的句型(句子)的过程。 ?也就是某文法的某个推导的构造过程。
?

设文法G为: E →E+T|T T →T*F|F F →(E)|i

E 自 顶 向 下
E + T

T
F

T
F

*

F
i

?

请问符号串i+i*i是 否为该文法的句子?

自 底 向 上

i

i
3

常用语法分析方法
?语法分析算法可分为两大类: ?自顶向下分析法
?从文法的开始符号出发,反复使用各种产生式向 下推导,寻找与输入符号串匹配的推导。

?自底向上分析法
?从输入串开始,逐步进行归约,直至归约到文法 的开始符号。

?两种方法反映了两种不同的语法树的构造过程
?自顶向下——从树根推导到树叶。 ?自底向上——从树叶归约到树根。
4

5.1 确定的自顶向下分析思想 p75
?基本方法
?对任何输入串,试图从文法的开始符号出发, 自上而下地为输入串建立一棵语法树,或者说 为输入串寻找一个最左推导。

?过程本质
?是一种试探过程,是反复使用不同产生式谋求 匹配输入串的过程如何选择哪个产生式进行推 导? ?某文法符号对应当前输入符号时,有唯一的产 生式进行替换并向下推导。

5

例5.1 p75
?若有文法G1[S]:
?S → pA|qB ?A → cAd|a ?B →dB|b

?若输入串W=pccadd,请问每一步推导 产 生式选择是不是唯一的? ?给出语法树 唯一的 ?文法的特点:
?每个产生式的右部都由终结符开始; ?若两个产生式左部相同,则右部由不同的终结 符开始。 6

例5.2 p76
?若有文法G2[S]:
?S → Ap|Bq A → cA|a B →dB|b

?若输入串W=ccap,请问每一步推导 产生 式选择是不是唯一的? ?给出语法树 唯一的 ?文法的特点:
?产生式右部不全是由终结符开始; ?若两个产生式左部相同,则右部由不同的终结 符或不同的非终结符开始。 ?无空产生式。

?如何选择唯一的产生式进行推导?First集合
7

FIRST(α)集合的定义 p76

α

? 设G=(VT,VN,S,P) α ∈V* ? FIRST(α )={a|α ==*> aβ ,a∈VT} a …… *>ε ,则ε ∈FIRST(α ) ?若α == ?FIRST(α )是α 的所有可能推导的首遇终结 符号或ε ,是选择产生式的依据。 ?FIRST(Ap) ={ a,c } S → Ap|Bq Ap==>ap Ap==>cAp A → cA|a ?FIRST(Bq) ={ b,d} B →dB|b Bq ==>bq Bq==>dBq ? 因为S的两个候选式FIRST(Ap)∩ FIRST(Bq)=φ ,所以 当S与面临的输入符号i匹配时,可能出现几种选择? (1)i∈FIRST(Ap),选择S → Ap匹配 8 (2)i∈FIRST(Bq),选择S → Bq匹配 (3)出错

例5.3 p77
?若有文法G2[S]:
?S → aA|d A → bAS|ε

?若输入串W=abd,请问每一步推导 产生 式选择是不是唯一的? ?给出语法树 唯一的 ?特点:
?含空产生式。 ?当A面临d时,d不属于FIRST(bAS),用A→ε 自动匹配,前提非终结符A的后继符号中含有d。

?如何选择唯一的产生式进行推导? FOLLOW集合。

9

FOLLOW(A)集合的定义 p77

S

A∈VN ? FOLLOW(A)={ a|S==*>?Aa?,a∈VT } …Aa… *>?A,则#∈FOLLOW(A) ?若S== ?#—输入串的结束符 也可看作是句子的括号 #S# ?FOLLOW(A)表示了句型中可能紧跟在A后面的终结符号 ? #∈FOLLOW(A) S ==> aA S → aA|d A → bAS|ε ? a∈FOLLOW(A) S==>aA==>abAS==>abAaA ? d∈FOLLOW(A)S==>aA==>abAS==>abAd ? 因为A的两个候选式FIRST(bAS)∩FOLLOW(A)=φ ,所以 当A与面临的输入符号i匹配时,可能出现几种选择? (1)i∈FIRST(bAS),选择A → bAS匹配 (2)i∈FOLLOW(A),选择A → ε 自动匹配 (3)出错 10

SELECT(A → α)集合的定义 p78
? 设G=(VT,VN,S,P) α ∈V* ? FIRST(α )={a|α ==*> aβ ,a∈VT} ?若α ==*>ε ,则SELECT(A→α )= FIRST(α ) ?若α ==*>ε ,则SELECT(A→α ) = (FIRST(α )-{ε })∪FOLLOW(A)

S → aA|d A → bAS|ε
S → aA|d A → bAS|K K → c|ε

?FOLLOW(A)={a,d,#} ?SELECT(A →bAS)=FIRST(bAS)={b} ?SELECT(A →ε) =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} ?FOLLOW(A)={a,d,#} FIRST(K)={c, ε} ?SELECT(A →bAS)=FIRST(bAS)={b} ?SELECT(A →K) =(FIRST(K)-ε) ∪FOLLOW(A)={c,a,d,#} 11

LL(1)文法的定义 p78

? 一个上下文无关文法是LL(1)文法的充分必要条件是, 对每个非终结符的两个不同的产生式,A→α ,A→β , 满足:SELECT(A→α )∩SELECT(A→β )= φ

S → aA|d A → bAS|ε

求所有SELECT集合: ?SELECT(S→aA)=FIRST(aA)={a} ?SELECT(S →d)=FIRST(d)={d} ?SELECT(A →bAS)=FIRST(bAS)={b} ?SELECT(A →ε) ? =(FIRST(ε)-ε) ∪FOLLOW(A)={a,d,#} 求每个非终结符不同产生式SELECT的交集: ?SELECT(S→aA)∩SELECT(S →d)=φ ?SELECT(A →bAS)∩SELECT(A →ε)=φ 所以,该文法是LL(1)文法。 12

LL(1)文法的定义 p78

? 一个上下文无关文法是LL(1)文法的充分必要条件是, 对每个非终结符的两个不同的产生式,A→α ,A→β , 满足:SELECT(A→α )∩SELECT(A→β )= φ

S → aAS|b A → bA|ε
存在问题: ?当A面临输入符 号b时,无法用唯 一的产生式去匹 配。

?FOLLOW(A)={a,b} 求所有SELECT集合: ?SELECT(S→aAS)=FIRST(aAS)={a} ?SELECT(S →b)=FIRST(b)={b} ?SELECT(A →bA)=FIRST(bA)={b} ?SELECT(A →ε) ? =(FIRST(ε)-ε) ∪FOLLOW(A)={a,b} 求每个非终结符不同产生式SELECT的交集: ?SELECT(S→aAS)∩SELECT(S →b)=φ ?SELECT(A →bA)∩SELECT(A →ε)={b}≠φ 所以,该文法不是LL(1)文法。 13

LL(1)分析 p78
?含义
?第一个 L 表示从左向右扫描输入符号串; ?第二个 L 表示生成最左推导; ?1 表示读入一个符号可确定下一步推导。

?LL(1)文法能够对输入串进行有效的。 ? 无回溯的自上而下分析。

14

LL(1)分析
?对于文法G,当面临的输入符号为a,要用 非终结符A进行匹配时,假设A的所有产生 式为 A→α 1| α 2 |?| α n 1)若a∈FIRST(α i ),则指派α i去执行任务 2)若a不属于任何候选首符集,则: ①若ε 属于某个FIRST(α i )且 a∈FOLLOW(A),则让A与ε 自动匹配 ②否则,a的出现是一种语法错误
章节目录
15

5.2 LL(1)文法的判别 p79
?FIRST集合的计算 ?FOLLOW集合的计算

?SELECT集合的计算
?LL(1)文法的判别举例 ?LL(1)文法判别课堂练习
章节目录
16

FIRST(α)的计算法 ——定义和关系图 p80
?FIRST(α )={ a|α ==*> a ?,a∈VT }
?若α ==*>ε ,则ε ∈ FIRST(α )

?计算文法符号X的FIRST(X) ?计算文法符号串α =X1X2?Xn的FIRST(α )

17

FIRST( X )的计算法 p80
重复以下计算,直到FIRST(X)不再增大为止: 1) 若 X∈VT,则 FIRST( X ) = { X }。
例 FIRST(+)={+} FIRST(i)={i}

2) 若 X∈VN,
若有X→a?,则将 a 加入FIRST(X); 例 E'→+TE' +∈FIRST(E’) F→(E)|i (,i∈FIRST(F) 若有X →ε ,则将ε 加入FIRST( X )。 例 E’→ε ε ∈FIRST(E’)
18

?3)若有 X → Y…,且 Y ∈VN ,
则 FIRST(Y)-{ε }加入FIRST(X); 例 F→(E)|i FIRST(F)={(,i} T→FT' FIRST(T)=FIRST(F)-{ε }={(,i}
-{ε } ?若有X → Y1…Yi-1Yi…Yk ,并对于某个i, 有1≤j≤i-1,ε ∈FIRST(Yj), 即Y1 ,…,Yi-1==*>ε , 则将所有FIRST( Yj )-{ε }∪FIRST( Yi )-{ε } 加入FIRST( X )中; ?若所有Y1,…,Yk==*>ε ,则将ε 加入到 FIRST( X )。
19

-{ε }

计算X→Y1?Yi-1Yi?Yk FIRST(X)集举例
若有文法G为:
FIRST集

X → Y 1 Y2 Y3 Y4 Y5 Y1 → a|ε Y2 → b|ε ==*>ε ==*>ε Y3 → c|ε Y4 → d|ε Y5 → e|fε

Y1 a,ε Y2 b,ε Y3 c,ε Y4 d,ε Y5 e,fε X a,b,c,d, e,f ε

因为Y5==*>ε , 所以ε ∈FIRST(X) 因为Y5==*>ε , 所以ε ∈FIRST(X) 20

计算表达式文法FIRST(X)集举例
文法G为:

?先找以终结符开头的产生式
FIRST( F ) = { ( ,i } FIRST( E' ) = { + ,ε }

E →T E’
E'→+ T E'|ε

T →F T'
T'→* F T'|ε

F →( E )|i

FIRST( T' ) = { * , ε } ?再找右部以非终结符开头的产生式 FIRST( T ) = FIRST( F ) FIRST( E ) = FIRST( T ) = { ( ,i }

21

计算FIRST(X)集合课堂练习
文法G为:
?先找以终结符开头的产生式

FIRST(A)={ a ,c } FIRST(B)={ d ,ε }
?再找右部以非终结符开头的产生式

S →Ap|Bq
A →a|cA B →dB|ε BEGIN

FIRST(S)= FIRST(A)-{ε }

因为B==>ε

ε ∈FIRST(S),因为S==*>ε

∪FIRST(B)-{ε } ∪FIRST(q) ={a,c,d,q}

22

FIRST(α) 的计算法
设α =X1 X2 … Xi-1 Xi … Xn,按以下方法构造集合

?若ε ∈ FIRST( X1 ) 即X1==>ε 则FIRST(α ) = FIRST( X1 ); ?若任何1≤j≤i-1,2≤i≤n,ε ∈FIRST ( Xj ) 则Xi前所有FIRST( Xj )-{ε }和FIRST( Xi ) 加入到 FIRST(α ) 中; ?若所有的1≤j≤n,ε ∈FIRST( Xj ) 则把ε 也加入FIRST(α )中; ?若α =ε ,则 FIRST(α )={ε }
23

计算表达式文法候选式FIRST(α)集举例
文法G为: E→TE’ E'→+TE’|ε 非终结符的FIRST集 FIRST(E)={(,i} FIRST(E')={+,ε } FIRST(T)={(,i} FIRST(T')={*,ε } FIRST(F)={(,i} T→FT’ T'→*FT’|ε F→(E)|i

候选式的FIRST集 FIRST(TE’)=FIRST(T)={(,i} FIRST(+TE’)={+} FIRST(FT’)=FIRST(F)={(,i} FIRST(*FT’)={*} FIRST((E))={(} FIRST(i)={i} FIRST(ε )={ε }
24

计算FIRST(α)集合课堂练习
文法G为: S →Ap|Bq A →a|cA B → dB|ε
候选式的FIRST集 FIRST(S)={a,c,d,q} FIRST(Ap)=FIRST(A)={a,c} FIRST(Bq)=FIRST(B)-{ε } FIRST(A)={a,c} ∪FIRST(q) FIRST(B)={d,ε } ={d,q} FIRST(a)={a} BEGIN FIRST(cA)={c} FIRST(dB)={d} FIRST(ε )={ε } 非终结符的FIRST集
小节目录
25

FOLLOW(A)的计算法 p82
?FOLLOW(A)= {a|S==*>?Aa?,a∈VT } ?若S==*>?A,则#∈FOLLOW(A)
重复以下计算,直到每个FOLLOW(A)不再增大为止:

?1)将 # 加入到 FOLLOW( S )中 例 # ∈ FOLLOW( E ) ?2)若A→α Bβ , 则将FIRST(β )-{ε }加入FOLLOW(B) 例 E→TE’ FIRST(E’)-{ε }加入FOLLOW(T) T→FT’ FIRST(T’)-{ε }加入FOLLOW(F)
26

FOLLOW( A ) 的计算法(续)
?3) 若 A → α B ,或 A → α Bβ , 且 β ==*>ε ,即ε ∈ FIRST(β ),A≠B 则将FOLLOW(A)所有元素加入FOLLOW(B)
例 E →T E’
E →T E’ E'→ε T →F T’ T →F T’ T'→ε

ε

FOLLOW(E)加入FOLLOW(E’)
FOLLOW(E)加入FOLLOW(T) FOLLOW(T)加入FOLLOW(T’) FOLLOW(T)加入FOLLOW(F)

27

计算表达式文法的FOLLOW集举例
相同不需处理

G:E→TE’ E'→+TE’|ε

T→FT’

T'→*FT’|ε

F→(E)|i

?#∈FOLLOW(开始符号)

#∈FOLLOW(E)

?对每个非终结符查看其在产生式右边的出现

FOLLOW(E) ={),#} FOLLOW(E')=FOLLOW(E)={),#} FOLLOW(T)=FIRST(E’)-{ε }∪FOLLOW(E) ={+,),#} FOLLOW(T')=FOLLOW(T)={+,),#} FOLLOW(F)=FIRST(T’)-{ε } ∪FOLLOW(T) ={*,+,),#}
28

计算FOLLOW(A)集合课堂练习
文法G为: S →Ap|Bq

A →a|cA

B → dB|ε

非终结符FOLLOW集 FIRST(S)={a,c,d,q} FOLLOW(S)={#} FOLLOW(A)=FIRST(p)-{ε } FIRST(A)={a,c} ={p} FIRST(B)={d,ε } FOLLOW(B)=FIRST(q)-{ε } ={q} BEGIN 非终结符的FIRST集

小节目录

29

?文法G:

SELECT集合的计算p84

(1)E →TE' (2)E'→+TE’|ε (3)T →FT' (4)T'→*FT’|ε (5)F →(E)|i

? ? ? ? ? ? ? ?

FIRST(TE’)={(,i} FOLLOW(E) ={),#} FIRST(+TE’)={+} FOLLOW(E') ={),#} FIRST(FT’)={(,i} FOLLOW(T) ={+,),#} FIRST(*FT’)={*} FOLLOW(T') ={+,),#} FOLLOW(F) ={*,+,),#} FIRST((E))={(} FIRST(i)={i} FIRST(ε )={ε } SELECT(E→TE’)=FIRST(TE’)={(,i} SELECT(E'→+TE’)= FIRST(+TE’) ={+} SELECT(E‘→ε )=(FIRST( ε )-{ε })∪FOLLOW(E')={),#} SELECT(T→FT’)=FIRST(FT’)={(,i} SELECT(T'→*FT’)=FIRST(*FT’)={*} SELECT(T'→ε )=(FIRST( ε )-{ε })∪FOLLOW(T')={+,),#} SELECT(F→(E))=FIRST((E))={(} 30 SELECT(F→i)=FIRST(i)={i} 小节目录

计算SELECT集合课堂练习
文法G为:S→Ap|Bq A→a|cA B→dB|ε
非终结符的FIRST集 FIRST(S)={a,c,d,q} FIRST(A)={a,c} FIRST(B)={d,ε } 非终结符FOLLOW集 FOLLOW(S)={#}
? ? ? ? ? ? SELECT(S→Ap)=FIRST(Ap)={a,c} SELECT(S→Bq)= FIRST(Bq)={d,q} SELECT(A→a)=FIRST(a)={a} SELECT(A→cA)=FIRST(cA)={c} SELECT(B→dB)=FIRST(dB)={d} SELECT(B→ε )= (FIRST( ε )-{ε })∪FOLLOW(B) ={q}

FOLLOW(A)={p}
FOLLOW(B)={q}

小节目录

31

表达式文法是 LL(1) 文法
?文法G:

(1)E →TE' (2)E'→+TE’|ε (3)T →FT' (4)T'→*FT’|ε (5)F →(E)|i

SELECT(E→TE’)={(,i} SELECT(E'→+TE’)={+} SELECT(E‘→ε )={),#} SELECT(T→FT’)={(,i} SELECT(T'→*FT’)={*} SELECT(T‘→ε )={+,),#} SELECT(F→(E))={(} SELECT(F→i)={i}

(1)和(3)无需判定,因只有一个候选式。 (2)SELECT(E‘→+TE’)∩SELECT(E‘→ε ) ={+}∩{),#}=φ (4)SELECT(T‘→*FT’)∩SELECT(T‘→ε ) ={*}∩{+,),#}=φ (5)SELECT(F→(E))∩SELECT(F→i)={(}∩{i}=φ 故 文法G是LL(1)文法
小节目录

32

?文法G:

(1)S→AB|bC (2)A→b|ε (3)B→aD|ε (4)C→AD|b (5)D→aS|c

LL(1) 文法判别课堂练习 p83
FIRST(S)={a,b,ε } FIRST(A)={b,ε } FIRST(B)={a,ε } FIRST(C)={a,b,c} FIRST(D)={a,c} FOLLOW(S)={#} FOLLOW(A)={a,c,#} FOLLOW(B)={#} FOLLOW(C)={#} FOLLOW(D)={#}

(1)SELECT(S→AB)∩SELECT(S→bC) =((FIRST(AB)-{ε })∪FOLLOW(S))∩FIRST(bC)={a,b,#}∩{b}≠φ (2)SELECT(A→b)∩SELECT(A→ε ) =FIRST(b)∩FOLLOW(A)= {b}∩{a,c,#}=φ (3)SELECT(B→aD)∩SELECT(B→ε ) =FIRST(aD)∩FOLLOW(B)= {a}∩{#}=φ (4) SELECT(C→AD))∩SELECT(C→b) =FIRST(AD)∩FIRST(b)= {a,b,c}∩{b}≠φ (5) SELECT(D→aS)∩SELECT(D→c) =FIRST(aS)∩FIRST(c)= {a}∩{c}=φ 故 文法G不是LL(1)文法 33

小节目录

5.4 不确定的自顶向下分析思想 p91
? 由于相同左部的产生式的右部FIRST集交集不为空 而引起回溯。 ? 由于相同左部非终结符的右部存在能==*>ε 的产 生式,且该非终结符的FOLLOW集中含有其他产生 式右部FIRST集的元素。

? 由于文法含有左递归引起回溯。

2013-6-27

34

自上而下分析面临的问题1 p91
?例 文法G[S] S→xAy A→ab|a ? 判断输入串 w = x a y是否为该文法的句子? S x S ==>xAy ==> xay y

A
a a b

问题 产生回溯的原因是什么?
回溯 试探成功 分析结束

试探 失败

2013-6-27

35

自上而下分析面临的问题 p92
?公共左因子——产生回溯
?例 文法G: S → xAy A → ab|a ?无法确定非终结符A面临输入符 号a时选用哪个关于A的候选式

S

S
S a

a

?左递归——无限循环(回溯)
?例 文法G: S → Sa|aba

… ?无法确定何时用S→aba产生式 w = abaaa
进行推导

?某些文法导致自上而下分析具有不确定性
2013-6-27

章节目录

36

5.3 1、消除回溯、提左因子 p84
?消除回溯目的
?对文法的任何非终结符,当它去匹配输入串 时,能够根据输入符号,准确地选择合适的候 选式去匹配 ?若需要非终结符A去匹配输入串,A的候选式 为A→α 1| α 2 |?| α n , A所面临的第一个 输入符号为a时,A能准确地选择α i去执行匹配 任务,则无需回溯

2013-6-27

37

提取公共左因子方法 p84
?对于所有形如 ?改写为 ?例如
?A→α β 1|α β 2|...|α β n|γ 的规则 其中,α 为左因子,γ 不以α 开头 ?A→α A'|γ 其中A’为新增加的非终结符 A'→β 1|β 2|...|β n

?提左因子后变换为
S → xAy A → aA’ A’ → b|ε

S → xAy A → ab|a

2013-6-27

38

提取公共左因子课堂练习 p85
?例如: A → ad|Bc B → aA|bB (隐式公共左因子) ?变换: A → ad|aAc|bBc B → aA|bB ?提左因子后变换为 A → aA’|bBc A’ → d|Ac B → aA|bB
2013-6-27 39

提取公共左因子注意事项 p87
? 变换后存在的无用产生式需要删除。
? 不一定每个文法都能在有限步骤内替换成无左公 共左因子的文法。

? 一个文法提取了公共左因子后,只解决了相同左 部产生式的FRIST集不相交问题,当改写后的文法 不含空产生式,且无左递归时,则改写后的文法 是LL(1)文法,若还有空产生式时,则还需要用 LL(1)文法的判别方式进行判断才能确定是否为 LL(1)文法。
2013-6-27

章节目录

40

5.3 2、 左递归的消除 p87
关于非终结符P的规则 ?直接左递归定义:若P → Pα |β α 、β ∈V* ?例如 E → E + T|T(含有E的左递归) T → T * F|F(含有T的左递归) F → ( E )|i
2013-6-27 41

消除直接左递归的方法 p88
改写为等价的右递归 等价 ?形如:P → Pα|β α非ε,β不以P开始 ?改写为:P→βP’(P’为新增加的非终结符) P'→αP'|ε ?改写前产生式可产生短语 P==>Pα==> βα 改写后产生式可产生短语 P==> βP’ ==> βαP' ==> βα ε
2013-6-27 42

举例:表达式文法直接左递归的 消除
?E → E + T|T ?T → T * F|F ?F → ( E )|i ?E ?T ?F → T E’ → F T’ → ( E )|i E' → + T E'|ε T' → * F T'|ε

2013-6-27

43

消除多个直接左递归 p88
?若有多个左递归的产生式如: P→Pα 1| Pα 2 |?| Pα m |β 1| β
2

|?|β

n

?消除左递归后变为: P→β 1P’ |β 2 P’|…|β nP’ P’ → α 1P’ | α 2 P’|…| α mP’| ε ?消除左递归要求文法: 1.无回路(A ==*> A) 2.无空产生式(A → ε )
2013-6-27 44

消除直接左递归课堂练习
?例如有文法: K→Ka | Kb| Kc | d | e BEGIN

?消除左递归后变为: K → dK’ |eK’ K’ →aK’ | bK’| cK’|ε
2013-6-27 45

间接左递归的定义 p68
?间接左递归定义: 若P ==+> Pα ?例如 间接左递归
S → Aa A → Sb|b

α ∈V*

S ==>Aa==>Sba 即S==+>Sb ?用S的产生式右部替换A右部的S得: A → Aab|b 变成A的产生式含有直接左递归
2013-6-27 46

间接左递归消除举例 p90
S → Qc|c ? 将Q的右部代入S: Q → Rb|b S → Sabc|abc|bc|c R → Sa|a ? 消除S的直接左递归: S=>Qc=>Rbc=>Sabc S →abcS’|bcS’|cS’ 是间接左递归 S’→abcS’|ε 消除方法1: Q → Sab|ab|b ? 将非终结符排序: R → Sa|a R Q S ? 将R的右部代入Q,S:? 整理化简:删除Q,R(无用) ? 消除左递归后得: Q → Sab|ab|b S → Qc|c (不变) S →abcS’|bcS’|cS’ S’→abcS’|ε
2013-6-27 47

间接左递归消除举例(续)
S → Qc|c ? 将Q的右部代入R: Q → Rb|b R → Rbca|bca|ca|a R → Sa|a ? 消除R的直接左递归: R →bcaR’|caR’|aR’ 消除方法2: R’→bcaR’|ε ? 将非终结符排序: S Q R ? 整理化简:S,Q(有用) ? 将S的右部代入Q,R: ? 消除左递归后得: Q → Rb|b(不变) S → Qc|c R → Qca|ca|a Q → Rb|b R →bcaR’|caR’|aR’ R’→bcaR’|ε
2013-6-27 48

消除左递归算法 p89
1.以某种顺序将文法的非终结符排列 ? 当非终结符的排列顺序不 P1,P2,?,Pn 2.FOR i:=1 TO n DO 同时,变换后的文法形式 BEGIN 可能不同,但是它们都和 FOR j:=1 TO i-1 DO 原文法是等价的 把形如Pi→Pjγ 的规则改写成 Pi→δ 1γ |δ 2γ |?|δ kγ ,其中 Pj→δ 1|δ 2|?|δ k是关于Pj的所有规则; 消除Pi的直接左递归 END 3.化简由2所得的文法,即去除那些从开始符号 出发永远无法到达的非终结符的产生式

章节目录
2013-6-27 49

5.5 确定的自顶向下分析方法 p92
?文法不含左递归 ?对于文法的每个非终结符 A 的任何两 个不同的产生式 A→α |β 1) FIRST(α )∩FIRST(β ) = φ 2) α ==*>?和β ==*>?不能同时成立 3) 如果β ==*>?,则 FISRT(α )∩FOLLOW(A)=φ ?满足以上条件的文法称为LL(1)文法 ?LL(1)文法可以用确定的自顶向下分析 方法实现。 章节目录
2013-6-27 50

5.5.1 递归下降分析程序构造 p92
LL(1)文法 构造 不带回溯的自上而下分析程序

分析程序 每个非终结符

一组递归过程
一个子过程

子过程的功能: 对相应非终结符产生式右部进行语法分析

分析程序从开始符号所对应的过程开始运行
2013-6-27 51

例 表达式文法的递归下降分析器
?消除左递归后的表达 式文法G为: E →TE' E'→+TE’|ε T →FT' T'→*FT’|ε F →(E)|i ?可以证明 G是一个LL(1)文法
2013-6-27

5个非终结符 构造 5个子过程 E( ) E’( ) T( ) T’( ) F( )
52

递归下降分析器构造说明
(1)E():完成对 E → T E’的右部分析 E
T E’

右部有非 终结符时 ,调用该 非终结符 对应的子 过程来完 成
2013-6-27

C语言 E( ) { T; E’; }

53

递归下降分析器构造说明
(2)E’():完成对 E’→ +T E’|ε 的右部分析 E’
+ T E’

其它 非+字符 自动匹配ε
c:当前所面临的输入符号 p++:把输入指针ip下移一位 E’() { if (c==‘+’) { p++; T; E’; } }
2013-6-27 54

表达式文法的递归下降分析器 举例
(3)T(): T → F T’ T
F T’

C语言练习 T( ) { F; T’; }
2013-6-27 55

表达式文法的递归下降分析器 举例
(4)T’(): T’→* F T’|ε F * T’
T’

其它 非*字符 自动匹配ε

C语言练习 T’() { if (c==‘*’) { p++; F; T’;} }
2013-6-27 56

F的子程序 F

(

E

)

C语言练习 F() { if (c==‘(‘) { p++; E; if (c==‘)’) p++; else error;} /*括号不匹配*/ else if (c==‘i’) p++; else error;/*F面临非(,i输入符号, 语法错误*/ } 2013-6-27

i 其它 非(,i字符出现语法错误

57

i+i的递归下降分析过程 E i + i #

匹配成功返回,指针下移 自动匹配,返回

分析成 功结束

E’ E’

匹配成功继续,指针下移 匹配成功返回,指针下移 自动匹配,返回 i 自动匹配,返回

F T’ + T ε F i

T’ε ε
58

生成语法分析树
2013-6-27

递归下降分析程序优缺点分析
?优点:
?1)直观、简单、可读性好 ?2)便于扩充

?缺点:
?1) 递归算法的实现效率低 ?2) 处理能力相对有限 ?3) 通用性差,难以自动生成

2013-6-27

59

递归下降分析程序课堂练习
?

文法G为: S →(T)|a+S|a T →T,S|S

?

消除左递归: S →(T)|a+S|a T →ST’ T’ →,ST’|ε

提取左因子: S →(T)|aS’ S’ → +S|ε T →ST’ T’ →,ST’|ε ? 4个子程序: S() S’() T() T’() BEGIN
?
60

2013-6-27

递归下降分析程序课堂练习答案
(1)S →(T)|aS’ S() { if(c=‘(‘) /*匹配第一候选式*/ { p++; T; if(c=‘)’) p++; else error; /*括号不匹配*/ } else if(c=‘a’){ p++;S’;}/*匹配第二候选式*/ else error; /*语法错误*/ }
2013-6-27 61

递归下降分析程序课堂练习答案
(2)S’→+S|ε S’() { if(c=‘+‘) { p++; S; } } (3)T →ST’ T() {S; T’; } (4)T’→,ST’|ε T’() {if(c=‘,’) {p++; S; T’;} }
章节目录
2013-6-27 62

5.5.2 预测分析程序 p93
?简介

?预测分析程序的工作过程
?预测分析表的构造

?综合练习

2013-6-27

章节目录

63

预测分析程序简介 p93
?实现LL(1)分析的另一种有效方法 ?使用一张二维分析表(预测分析表) 和一个分析栈(文法符号栈)联合进 行控制来实现自上而下分析技术

2013-6-27

节目录

64

预测分析程序工作过程 预测分析表说明 p93
?预测分析表实际上是一个矩阵M[A,a] A →α
i

M[A,a] =
待匹配 栈顶非 终结符
2013-6-27

当A面临a时所应选用 的候选式

空(error) A不可能与a匹配 出现语法错误
所面临 输入符 号
65

表达式文法的预测分析表p95 表5.3
非终 结符 E E' T T' F F→i T→FT’ T’→ε T’→*FT’ F→(E) 输入符号(终结符和#) i E→TE’ E’→+TE’ T→FT’ T’→ε T’→ε + * ( E→TE’ E’→ε E’→ε ) #

M[E’,+] = E’→+TE’ E’面临+时选用E’→+TE’ M[T’,)] = T’→ε T’面临)时选用T’→ε M[F,*] = error F面临*时出现语法错误 请试给出输入串w=i*i+i的预测分析过程?
2013-6-27 66

分析栈的说明
?分析栈用于存放分析过程中的文法符号

分析栈初始化时: ?栈底压入一个‘#’ ?次栈底压入文法开 top 始符S top 入栈操作push top
栈顶指 针 出栈操作pop



S #


top

stack
67

2013-6-27

预测分析器模型
输入缓冲区: …a…#
输出 所选用 产生式 序列

总控制程序 X ┆ # 栈
2013-6-27

查找

预测分析表
68

总控程序执行时可能动作p94
对于任何(X,a) X是栈顶符号 a是面临输入符号 (1) X∈VT 且 X=a=‘#’, 分析成功结束,输入串是一个合法句子 (2) X∈VT 且 X=a≠‘#’, X出栈,输入指针指向下一输入符号 (3) X∈VN ,查分析表 M [X,a] 若 M [X,a]= X→α i, X出栈,α i逆序入栈,输入指针不动 若 M [X,a]= 空, 则调用error程序,进行错误处理
2013-6-27 69

执行例子:i+i*i分析过程
栈 0 #E 1 #E'T 2 #E'T'F 3 #E'T'i 4 #E'T' 5 #E' 6 #E'T+ 7 #E'T
2013-6-27

输入缓冲区 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 i出栈,a下移 T' → ε E' → +TE' +出栈,a下移 T → FT'
70

i+i*i 分析过程续
栈 输入缓冲区 所用产生式 8 #E'T'F i*i# F → i 9 #E'T'i i*i# i出栈,a下移 10 #E'T' *i# T' → *FT' 11 #E‘T'F* *i# *出栈,a下移 12 #E'T'F i# F → i 13 #E'T'i i# i出栈,a下移 14 #E'T' # T' → ε 15 #E' # E' → ε 16 # # 分析成功结束 输出的产生式序列形成了按最左推导生成的语法分析树
2013-6-27 71

课堂练习一: i*i+i分析过程
0 1 2 3 4 5 6 7 栈 #E #E'T #E'T'F #E'T'i #E'T' #E'T'F* #E'T'F #E'T'i 输入缓冲区 i*i+i# i*i+i# i*i+i# i*i+i# *i+i# *i+i# i+i# i+i# 所用产生式 BEGIN E → TE' E'T入栈 T → FT' F → i i出栈,a下移 T'→*FT' *出栈,a下移 F → i i出栈,a下移
72

2013-6-27

8 9 10 11 12 13 14 15 16

栈 #E'T' #E' #E'T+ #E'T #E'T'F #E'T'i #E'T' #E' #

输入缓冲区 +i# +i# +i# i# i# i# # # #

所用产生式 T' → ε E' → +TE'
T → FT' F → i

i*i+i 分析 过程 续

T' → ε E' → ε # = #分析成功结束

2013-6-27

73

课堂练习一:i+i分析过程
栈 0 #E 1 #E'T 2 #E'T'F 3 #E'T'i 4 #E'T' 5 #E' 6 #E'T+ 7 #E'T
2013-6-27

输入缓冲区 i+i# i+i# i+i# i+i# +i# +i# +i# i#

所用产生式 BEGIN E → TE' T → FT' F → i T' → ε E' → +TE' T → FT'
74

i+i 分析过程续
栈 8 9 10 11 12 输入缓冲区 #E'T'F i# #E'T'i i# #E'T' # #E' # # # 所用产生式 F → i T' → ε E' → ε # = #分析成功

2013-6-27

75

总控程序实现算法描述 p93
BEGIN PUSH(STACK,’#’);PUSH(STACK,开始符号); a=第一个输入符号; FLAG:=TRUE; WHILE FLAG DO BEGIN X=POP(STACK); IF X∈VT THEN IF X=a THEN a=下一个符号 {终结符匹配} ELSE ERROR{与当前输入符号不匹配}
2013-6-27 76

总控程序实现算法描述 p93(续)
ELSE IF X=‘#’ THEN IF X=a FLAG:=FALSE ELSE ERROR X=a=‘#’ 分析 成功结束

IF M[A,a] = {X →X1 X2…Xk} 把 Xk…X2 X1一一推进STACK栈] ELSE ERROR END OF WHILE STOP {分析成功,过程完毕} END ELSE
2013-6-27

节目录

77

预测分析表的构造 p94-95
设有文法G,预测分析表构造过程: ?计算所有候选式α 的首符集 FIRST(α ) ?计算所有非终结符A的后继符集 FOLLOW(A) ?计算所有产生式的SELECT(A→α )集合 ?构造预测分析表 M

2013-6-27

78

预测分析表的构造算法p95
(1)对文法G的每个产生式 A→α ,执行(2) (2)对每个终结符或“#”记为a, 若a∈SELECT(A→α ),把 A→α 填入 M[A,a]

(3)把所有无定义的 M[A,a]标上“出错标志”

2013-6-27

79

预测分析表的构造算法举例 p95 表5.3
SELECT(E→TE’)={(,i} M[E,(]= E →TE’ M[E,i]= E →TE’ ?E’→+TE’ SELECT(+TE’)={+} M[E’,+]=E’→+TE’ ?E’→ε SELECT(E’)={),#} M[E’,)]=E’→ε M[E’,#]=E’→ε ?F→(E)|i M[F,(]=F→(E) M[F,i]= F→i 若文法G的分析表不含多重入口, 则G是LL(1)文法
2013-6-27 80

?E→TE’

SELECT(E→TE’)={(,i} SELECT(E'→+TE’)={+} SELECT(E‘→ε )={),#} SELECT(T→FT’)={(,i} SELECT(T'→*FT’)={*} SELECT(T‘→ε )={+,),#} SELECT(F→(E))={(} SELECT(F→i)={i}

预测分析法(状态矩阵法)
?1) 编写文法,消除二义性; ?2) 消除左递归、提取左因子; ?3) 求 FIRST 集合、 FOLLOW 集合和 SELECT集合 ?4)检查是不是 LL(1) 文法
?若不是 LL(1),说明文法的复杂性超过自上 而下方法的分析能力

?5)按照 LL(1) 文法构造预测分析表 ?6)实现预测分析器
2013-6-27

节目录

81

预测分析程序课堂综合练习
文法G为: S→aBc|bAB A→aAb|b B→b|ε
问题:构造预测分析表,并分析符 号串baabbb是否为该文法的句子? 2.非终结符FOLLOW集 FOLLOW(S)={#}

1.非终结符的FIRST集

FOLLOW(A) =FIRST(b) ∪FIRST(B)-{ε } FIRST(S)={a,b} S→bAB B==>ε ∪FOLLOW(S) FIRST(A)={a,b} ={b,#} FOLLOW(B) =FIRST(c) FIRST(B)={b,ε } S→bAB ∪FOLLOW(S) ={c,#}
2013-6-27 82

预测分析程序课堂综合练习(续)
文法G为:S→aBc|bAB A→aAb|b B→b|ε
3.构造预测分析表 FOLLOW(B)={c,#}

a S S→aBc

b S→bAB

c

#

A
B

A→aAb

A→b
B→b B→ε B→ε

若分析表无多重入口,则G是LL(1) 文法
2013-6-27 83

4. b a a b b b 分 析 过 程

符号栈 0 #S 1 #BAb 2 #BA 3 #BbAa 4 #BbA 5 #BbbAa 6 #BbbA 7 #Bbbb 8 #Bbb 9 #Bb 10#B 11#

输入缓冲区 baabbb# baabbb# aabbb# aabbb# abbb# abbb# bbb# bbb# bb# b# # #

所用产生式 S→bAB 移进b A→aAb 移进a A→aAb 移进a A→b 移进b 移进b 移进b B→ε 分析成功结束
节目录

综 合
练 习 续
84

2013-6-27

本章练习
1. 编译过程中,语法分析器的任务是 ①分析单词是怎样构成的 .

②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的 ④分析程序的结构 A ②和③ B ④ C ②③④ D ①②③④
.

2.语法分析的常用方法是 自顶向下分析法 和 自底向上分析法 3.自顶向下语法分析法会遇到的主要问题有 左递归 回溯 . 和

85

本章练习
4.LL(1)分析法中,第一个L的含义是 从左到右扫描输入串 ,第二 个L的含义是 每次进行最左推导 ,“1”的含义 是 对输入串中向前查看1个符号 .

5.一个文法G,若 ,则称它是LL(1)文法. A. G中不含左递归. B. G无二义性 C.G的LL(1)分析表不含多重定义 D.G中产生式不含左公因子 6.高级语言编译程序常用的语法分析方法中,递归下降分 析法属于 分析方法. A.自左至右 B.自顶向下 C.自底向上 D.自右向左
86

本章练习
7. 下列文法是左递归文法,试消除其左递归。 G[S]: S→ SaA| bB 解答: S→bB S’ S’→aA S’|ε A → aB | c A→aB|c B → Bb | d B→dB’
B’→bB’|ε

8.考虑文法G[S]: S→ aSb| P P →bPc|bQc Q →Qa|a 该文法消除左递归、提取左公因子后是不是LL(1)文法?

87

本章练习
9.有文法G[S]: S →BA A →BS|d B →aA|bS|c (1)证明文法G是LL(1)文法; (2)构造LL(1)分析表; (3)写出句子adccd的分析过程.

章节目录
88

作业 p99
?1 2 3 ?4 ?7

章节目录
89


相关文章:
编译原理第五章 自顶向下语法分析方法
第5章 自顶向下语法分析方法 第五章 自顶向下语法分析方法 课前索引 【课前思考】 为了了解自顶向下(自上而下)分析的一般过程和问题,请学员首先回顾在"文法和...
山东理工大学编译原理作业
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...山东理工大学编译原理作业_理学_高等教育_教育专区。...printf("\n 按任意键转入语法分析。。。\n"); ...
编译原理第五章 作业参考答案
编译原理习题解答 页 1/1 第五章 自顶向下语法分析方法 1.对文法 G[S] S a|∧|(T) T T,S|S (1) 给出(a,(a,a))和(((a,a),∧,(a)),a)...
山东理工大学《编译原理》考试
山东理工大学-编译原理内... 6页 7下载券 山东理工...自顶向下语法分析方法会遇到的主要问题有 和答:左...第五章 语法分析——自下而上分析 1.自下而上...
第05章 自顶向下语法分析方法
搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...编译原理第五章答案 7页 1财富值 初一数学教学反思...第5 章 自顶向下语法分析方法 第 1 题 对文法 ...
山东理工大学编译原理期末考试试题
2010-2011 第一学期期末试题《山东理工大学》一.(...乔姆斯基把文法分成___种类型,在编译原理中用来描述...3.自上而下语法分析法会遇到的主要问题有___和__...
编译原理第五章答案 (5000字)
编译原理第五章答案 (5000字)_计划/解决方案_实用文档。编译原理第五章答案 (5000字) 第5 章 自顶向下语法分析方法 第1题 对文法 g[s] s→a||(t)∧ ...
山东理工大学编译原理词法分析实验报告
搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...关键词:山东理工大学编译原理词法分析实验报告计科专业...单词的种类和值的表示方法; 3、编写词法分析程序 ...
编译原理自上而下语法分析
编译原理自而下语法分析_计算机软件及应用_IT/计算机_专业资料。编译原理自上而下的语法分析,用C#程序写的 1. 课程设计目的: 1.1 设计目的:通过编程实现语法...
第05章 自顶向下语法分析方法
编译原理》课后习题答案第五章 第 5 章 自顶向下语法分析方法 第1题 对文法 G[S] S→a|∧|(T) T→T,S|S (1) 给出(a,(a,a))和(((a,a),...
更多相关标签: