第四章 自顶向下语法分析方法 语法分析的主要工作：是识别由词法分析给出的单词 序列是否是给定的正确句子（程序）。

Presentation on theme: "第四章 自顶向下语法分析方法 语法分析的主要工作：是识别由词法分析给出的单词 序列是否是给定的正确句子（程序）。"— Presentation transcript:

1 第四章 自顶向下语法分析方法 语法分析的主要工作：是识别由词法分析给出的单词 序列是否是给定的正确句子（程序）。
语法分析常用的方法：自顶向下的语法分析和自底向 上的语法分析两大类。

2 自顶向下分析思想 自顶向下的方法： 从文法的开始符号（设为〈程序〉）开始进行分析，逐渐
推导的往下构造语法树，使其树叶正好构造所给定的源程序串。 自顶向下方法的关键： 是确定在推导过程中选择候选式的问题。当进行推导时， 一个非终结符可能对应多个产生式，这样我们就无法事先知道 应该用哪个产生式，因此必须对文法作一些限制，以便在任何情况下都能确定应该用的产生式。 自顶向下的主要思想： 从开始符出发导出句型并一个符号一个符号地与给定终结 符串进行匹配。如果全部匹配成功，则表示开始符号可推导出 给定的终结符串。因此判定给定终结符号串是正确句子。

3 自顶向下的缺点: 在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。 所以自顶向下分析法又分为确定的和不确定的两种： 确定的分析方法需对文法有一定的限制，但由于实现方法简单，直观，便于手工构造或自动生成语法分析器，因此仍是目前常有的方法之一。 不确定的方法即回溯的分析方法。这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因此极少使用。

4 4.2 自上而下分析面临的问题 解：推导过程为： 例4.1若有文法G[S]： S → pA S → qB A → cAd A → a
4.2 自上而下分析面临的问题 例4.1若有文法G[S]： S → pA S → qB A → cAd A → a 若有输入串w = pccadd. S p A c d a 考察自顶向下的推导过程。 解：推导过程为： pA pcAd pccAdd pccadd S     其相应的语法树见右图： 这个文法的特点： [1]每个产生式的右部都由终结符号开始。 [2]如果两个产生有相同的左部，那么它们的右部由不同的终结符开始。 显然对于这样的推导中完全可以根据当前的输入符号决定选择哪个产生式往下推导。因此分析过程是唯一的。

5 解：自顶向下的推导过程为： 例4.2 若有文法G2[S]： S Ap S Bq A a A cA B b B dB
若有输入串w = ccap. 考察自顶向下的推导过程。 S p A c a 解：自顶向下的推导过程为： Ap cAp ccAp     ccap S 其相应的语法树见右图： 这个文法的特点： [1]产生式的右部不全是由终结符号开始。 [2]如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。 [3]文法中无空产生式。

6 小结： 在上述推导过程中，对于产生式中相同左部含有非终结符打头的右部时，在推导中选用哪个产生式是不能直接知道的。
对W=ccap为输入串时，其第一个符号为c，这时从S出发选择S → Ap，还是选择S →Bq。其根据是要知道 A或B它们是否能推导以c打头的符号串，即它们的首符集是什么。若c是Ap的首符集的元素，且不在Bq的首符集中，则选择S →Ap往下推导。反之，若c在Bq的首符集中，不在Ap的首符集中，则选择S →Bq往下推导。其它情况为不确定推导或出错。 因此，在推导前有必要求出每个文法符号的首符集。

7 设G=(VN ，VT ，P，S）是上下文无关文法，α是G的任一符号串，则有：
一.首符集，后继符集与选择集的定义： 定义4-1（首符集定义）： 设G=(VN ，VT ，P，S）是上下文无关文法，α是G的任一符号串，则有： FIRST（α）={a | α * aβ,a∈ VT， α、β ∈V* }  特别地，若α * ε，则规定ε ∈FIRST(α)  即： FIRST(α)是从α出发推导出的所有符号串首终结符或可能的ε构成的集合。

8 文法G2[S]： S Ap S Bq A a A cA B b B dB 这样在文法 G2中，关于S的两个产生式虽然都以非终结符开始，但它们右部符号串可以推导出首符集合互不相交，因此可根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。因此是确定的自顶向下分析。

9 解： 当文法中有空产生式时,如例： 例4.3: 若有文法G3[S]: S→aA S →d A→ bAS A→ε 若有输入串W=abd。
考察自顶向下的推导过程。 S a A b A S 解： ε d S abAS abS abd  aA    相应语法树为右图：

10 小 结： 从上述推导过程中我们可以在第二步到第三步的推导 中，即abAS abS时，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始集合都不包括d，但有ε，因此对于d的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号。所以这时选用产生式A →ε 往下推导，而当前A后面的符号为S，S产生式右部的开始符号包括了d，所以匹配。  由此可以看出，当某一非终结符的产生式中含有空产 生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。为此可定义一个文法符号的后继符集合为： （定义4.2）

11 定义4.2: 设G=(VN , VT ,P,S)是上下文无关文法，A∈VN的后继符集合为：
FOLLOW(A)={a | S * …Aa… ,a∈VT}  特别地，若S * …A,则#∈FOLLOW(A) (这里#不是文法中的符号，而一个特别的表示输入串的结束符或称句子括号如 #输入串#） 表示：所有在句型中紧挨着A出现的终结符或#均是 FOLLOW(A)的元素。   因此当文法中含有形如： A→α和 A→β的产生式时，其中A∈VN ,α,β∈V*,当α和β不同时推导出空串时，设α * ε，β * ε，则当FIRST(α) ∩(FIRST(β)∪FOLLOW(A))=φ时，对于非终结符A的替代仍可唯一地确定候选。 \

12 定义4.3 定义选择集合SELECT如下： 定义4.3：对于给出上下文无关文法的产生式A→α,A∈ VN,α∈V*，则
FIRST(α)， 当α　ε时 FIRST(α)∪FOLLOW(A)，否则 ﹨ * 

13 三种集合的构造算法： 注：三种集合均为终结符集 （一） 求FIRST(X)的算法 对每一文法符号X∈(VN∪VT），求FIRST(X).
(a)若X∈VT,则令FIRST(X)={X}; (b)若X∈VN,且有产生式X→a….,(a∈VT)，则令a∈FIRST(X); (c) 若X∈VN,有X→ε，则令 ε∈FIRST(X); (d)若 X∈VN, y1, y2,…..yi都∈VN,且有产生式X→ y1 y2…..yn, (e)当(d)中所有yi * ε(i= 1,2,….,n),  当y1, y2,…..yi-1 都 * ε时，（其中1≤i≤n),则FIRST(y1)-ε, FIRST(y2)-ε,….,FIRST(yi-1 )-ε,FIRST(yi)都包含在 FIRST(X)中。 则 FIRST(X)=FIRST(y1)∪FIRST(y2)∪….∪FIRST(yn)∪{ε} 反复使用上述（b)～(d) 步直到每个符号的FIRST集合不再增加 为止。

14 （二）求 FIRST(α)的算法（α= x1 x2 …. xn):
1.若n=0,即α=ε,则令FIRST(α)={ε}; 2.否则，对1≤i≤n,求FIRST(xi) 3.若n=1,则令 FIRST(α)=FIRST(x1); 4.若n≥2且对一切j=1,2,….,i-1都有ε∈FIRST(xj). 则令FIRST(xi )-{ε} FIRST(α),其中2≤i≤n; 若对一切 j=1,2,…,n都有ε∈FIRST(xj),则令ε∈FIRST(α) 或：1.把FIRST(x1)中所有非ε元素加入到FIRST(α)中，即 FIRST(α )=FIRST(x1)-{ε }; 若FIRST(x1)包含有ε，则把FIRST(x2)的所有非ε元素加入到 FIRST(α)中，即FIRST(α)=FIRST(α)∪ (FIRST(x2)-{ε}); 若FIRST(x1)和FIRST(x2)都包含有 ε，则把FIRST(x3)的所有 非ε元素加到FIRST(α)中；…… 照此方法继续，一直到考察到xn。 2.若FIRST(xi ),i= 1,2,…,n;即每个FIRST(xi )中都有ε。则将ε加 到FIRST(α)中。特别地， 若 α=ε ，则FIRST(α)={ε}.

15 (三).求FOLLOW(A)的算法(A∈ VN):
(a)对文法开始符号S，令# ∈ FOLLOW(S). (b)若B→αAβ是一个产生式，则令FIRST(β)-{ε} 属于FOLLOW(A); (c) 若B→αA是一个产生式，或B→αAβ是一个产生 式且有ε∈FIRST(β)，则令FOLLOW(B)是 FOLLOW(A)的子集。即把FOLLOW(B)的所有元素 加入到FOLLOW(A)中。 (d)反复使用(b)直到每个非终结符的 FOLLOW集合 不再增加为止。

16 (四) 求SELECT(A→α)的算法： (a)求FIRST(α)； (b)若ε∈FIRST(α),则令SELECT(A→α)=FIRST(α) 否则求FOLLOW(A), 并令SELECT(A→α)=FIRST(α) ∪ FOLLOW(A). 例：有文法：E→TE' E'→+TE' |ε T→FT' T'→*FT' |ε F→i | ( E ) 求其三种集合。

17 解： 例：有文法：E→TE' E'→+TE'|ε T→FT' T'→*FT'|ε F→i| (E) 求其三种集合。
FIRST(E)=FIRST(T)=FIRST(F)={i, ( } FIRST(E')={+,ε} FIRST(T')={*，ε} FOLLOW(E)=FOLLOW(E')={ ),#} FOLLOW(T)=FOLLOW(T')={+,),#} FOLLOW(F)={*,+,),#} SELECT(E→TE')=FIRST(T)={i,( } SELECT(E'→+TE')=FIRST(+TE')={+} SELECT(E'→ε)=FIRST(ε)∪FOLLOW(E')={ε,),#} SELECT(T→FT')=FIRST(F)={i,(} SELECT(T'→*FT')=FIRST(*FT')={*} SELECT(T'→ε)=FIRST(ε)∪FOLLOW(T')={ε,+,),#} SELECT(F→i)=FIRST(i)={i} SELECT(F→（E))=FIRST(i) ={(}

18 4.3 LL(1)分析法 例：设有文法G[S]：S→aAS ， S→b ， A→bA ， A →ε
非终结符A的两个不同产生式，A →α ,A →β ；满足 SELECT(A →α ) ∩ SELECT(A →β )= Ф 。 其中， α、 β不能同时 * ε。  例：设有文法G[S]：S→aAS ， S→b ， A→bA ， A →ε SELECT(S→aAS)=FIRST(aAS)={a} SELECT(S→b)={b} SELECT(A→bA)={b} SELECT(A→ε)=FIRST(ε)∪FOLLOW(A)={a,b,ε} ∵SELECT(S→aAS)∩SELECT(S→b)={a}∩{b}=φ SELECT(A→bA)∩SELECT(A→ε)={b}∩{a,bε}≠φ 故文法 G[S]不是LL(1)文法。

19 文法的等价变换 确定的自顶向下分析要求给定语言的文法必须是 LL(1) 形式，然而，不一定每个语言都是LL(1)文法，对一个语言的
而，我们设法消除文法中的左递归，提取左公共因子对文法 进行等价变换。 1.提取左公共因子 若文法中含有形如：A→α β| α γ的产生式，这导致了对相同的产生式右部的FIRST集相交。 即有SELECT(A→ α β )SELECT(A→ α γ)≠φ 不满足LL(1)文法的充要条件。等价交换为： A→ α(β| γ) A→ α A' A'→ β| γ

20 更一般地: 结论： 对A→ α β1| α β2 | …| α βn提取左公因子为： A→ α A' A'→ β1| β2 | …| βn
若在βi , βj , βk…中仍含有左公共因子，可再进行提取，这样反复进行提取直到所引进的新非终结符的有关产生式均无左公共因子为止。 结论： 一个文法提取了左公共因子后，只解决了相同左部产生式的 右部FIRST集不相交问题。当改写后的文法不含有空产生式，且 无左递归时，则改写后的文法是LL(1)文法。否则还需用LL(1)文法的判别方法进行判断才能确定是否为LL(1)文法。

21 2.消除左递归 a)把直接左递归改写为右递归： 一个文法含有下列形式的产生式之一时： 1)A→A β, A∈VN, β∈V*
2)A→B β, B→A α, A,B∈VN, α ,β∈V* 则称该文法是左递归的。 含有左递归的文法不能采取自顶向下分析法。 消除左递归方法有： a)把直接左递归改写为右递归： 设有文法产生式：A→Aβ|γ. 其中β非空， γ不以A打头。 可写为：A→γA' A'→βA' | ε 一般情况下，假定关于A的产生式是： A→A α1| A α2 | … | A αm| β1| β2 | …| βn 其中， αi(1≤i≤m)均不为空， βj(1≤j≤n)均不以A打头。 则消除直接左递归后改写为： A→ β1 A' | β2 A' | … | βn A' A'→ α1 A' | α2 A' | … | αm A' | ε

22 例： 解： E→TE' 有文法G(E)：E→E +T |T A→Aβ|γ T→T*F | F 改写为： F→i| (E) A→γA'
消除该文法的直接左递归。 A→Aβ|γ 改写为： A→γA' A'→βA' | ε 解： E→TE' E'→+TE'|ε T→FT ' T'→*FT'|ε F→i| (E)

23 b)消除间接左递归： 对于间接左递归的消除需要先将间接左递归变为直接左 递归，然后再按a)清除左递归。 以文法G6为例： 消除左递归后得到：
(1)A→aB (2)A→Bb (3)B→Ac (4)B→d 消除左递归后得到： B→aBcB' |dB' B'→bcB' |ε 再把原来其余的产生式A→aB,A→Bb加入，最终得到等价文法为: (1) A→aB (2) A→Bb (3) B→(aBc|d)B' (4) B'→bcB'|ε 用产生式(1)，(2)的右部代替产生 式(3)中的非终结A得到左部为B的 产生式: (1)B→aBc (2)B→Bbc (3)B→d

24 c)消除文法中一切左递归的算法 设非终结符按某种规则排序为A1, A2,… An 。 For i:=1 to n do begin For j:=1 to i-1 do 若Aj的所有产生式为： Aj →δ1| δ2 | … | δn 替换形如Ai → Aj γ的产生式为： Ai →δ1γ |δ2γ | … |δnγ end 消除Ai中的一切直接左递归

25 4.4 递归下降分析程序构造 在程序语言的语法定义中有许多采用递归定义。我们在对 它进行语法分析时，编制的处理程序也采取递归的方式，可使其
4.4 递归下降分析程序构造 在程序语言的语法定义中有许多采用递归定义。我们在对 它进行语法分析时，编制的处理程序也采取递归的方式，可使其 结构简单易读。但由于频繁地调用子程序大大地降低了分析速度。 一、递归下降法的主要思想是：对每个非终结符按其产生式 结构写出相应语法分析子程序。因为文法递归相应子程序也 递归，子程序的结构与产生式结构一致。所以称此种方法 称为递归子程序法或递归下降法。 二、用程序表示递归子程序的内部结构： 设A是一个非终结符：A→β1 A→β2 ┊ A→βn

26 A→β1 A→β2 ┊ A→βn 则写 ζ(A)  if char∈first(β1 ) thenζ(β1 )
else if char∈first(β2 ) then ζ(β2 ) else… if char∈first(βn ) then ζ(βn) else ERROR 其中ζ(βi)表示调用处理符号串βi的子程序。 A→β A→β ┊ A→βn 对A的任一右部i 设为： βi = y1 y2 … yn 则定义ζ( βi)  beginζ(y1);ζ(y2);…;ζ(yn) end 其中yj可分为下列两种情况（j=1,…,n): 1) yj∈VT,则 ζ( yj)  if char≠ yj then ERROR else READ(char) 2) yj∈VN,则ζ(yj)表示调用关于yj的递归子程序。 对文法加限制： 1。任一非终结符B都不是左递归的，否则会产生死循环。 2。对A的任意两个右部βi , βj ,有：first(βi)∩first(βj)=φ First(βi)表示βi所能导出串的第一个符号的集合。显然，每个 βi的first(βi)是互不相同的，否则则无法判断应执行哪个ζ(βi )。

27 例1. 设有文法G: A →aABa B→bBb | a
则有ζ(A)  if char=a then ζ(aABa) else ERROR  if char=a then beginζ(a);ζ(A);ζ(B);ζ(a) end else ERROR begin if chara then ERROR else READ(char); ζ(A); ζ(B); if chara then ERROR else READ(char) end

28 B→bBb | a ζ(B)  if char = b then ζ(bBb)
else if char=a then (a) else ERROR  if char =b then begin ζ(b); ζ(B); ζ(b) end else if char=a then(a) else ERROR  if char=b then begin if charb then ERROR else READ(char); ζ(B); if charb then ERROR else READ(char) end else if char=a then if char a then ERROR else READ(char) else ERROR

29 例2： 关于〈表达式〉的处理： 即：E→T | E +T
<表达式>∷=<项>| <表达式>+<项> <项>∷=<因子>| <项>*<因子> <因子>∷=<变量>| (<表达式>) <变量>∷= i | i(<表达式>) 即：E→T | E +T T→F | T *F F→P | (E) P →i | i (E) 为了处理方便，把上述文法变为： E→T{+T} T→F{*F} F→P| (E) P→i| i(E) E: procedure E; begin T; while char="+" do begin READ(char); T end end

30 E: procedure E; begin T; while char="+" do begin READ(char); T end end E→T{+T} T→F{*F} F→P| (E) P→ i| i(E) T: procedure T; begin T; while char = "*" do begin READ(char); F end end F: procedure F; begin if char ="(" then begin READ(char); E; if ≠ char ")" then ERROR else READ(char) end else P

31 begin if char ≠" i " then ERROR else begin READ(char);
E→T{+T} T→F{*F} F→P| (E) P→ i| i(E) P: procedure P begin if char ≠" i " then ERROR else begin READ(char); if char ="(" then begin READ(char); E; if char≠ ")" then ERROR else READ(char) end 有时间则作递归下降分析的演示

32 4.5 预测分析程序 LL(k)文法是采取确定的自左至右扫描（输入串）和自顶向下分析技术的最大一类文法。LL系指：自左向右扫描（输入串），自上而下进行最左推导。 一般来说，一个文法当其分析器对输入串进行自左至右扫描并采用自顶向下方法进行分析的过程中，如果每步仅利用当前的非终结符（事实上此时它已位于分析栈顶）和至多向前查看k个输入符号就能唯一 决定采取什么动作，那么这个文法称为LL(K)文法。 对于大多数程序设计语言而言。K=1就足够了。因此我们将主要讨论k=1的情形。

33 一、LL(1)方法的分析过程 设分析的当前格局为（x1x2 …. xn#, y1y2 …. ym#) 其中xi表示句型的前端部分，诸yj表示输入流的后端部分（终结符串）。则可能有下述动作之一： 1.替代：当x1∈VN时，则选相应的候选式去替换x1 。 2.匹配：当x1∈VT时，它与y1进行匹配，其结果为两种可能，如 果匹配成功，则去掉x1和y1（即指针后移一位）否则报错。 3.接受：当格局为(#, #）时，报告分析成功结束。 从实现的角度来说，上述替换过程需要花较多的时间，因为 它除了把一个候选式替换掉x1,还需要x2 … xn统统进行移位处理, 这时很麻烦的。我们的处理方法是用栈来保存x1x2 … xn,而且 是把xn作为栈底， x1作为栈顶，那么上述的替换动作就简单了， 只需在栈顶进行替换。即去掉x1把候选式的符号串按逆序方式 压入栈中即可。

34 例： 设有文法：S→aBc|bB B→bB|d 且给定输入串abbbdc，看其自顶向下的分析过程。 Bc# bbdc# ↑ 栈： 流： S#
bBc# bbbdc# ↑  替  匹  替  匹 bBc# bbdc# ↑ Bc# bdc# ↑ bBc# bdc# ↑  替  匹  替 Bc# dc# ↑ dc# ↑  匹  替 c# ↑ # ↑  匹  匹 接受 结束

35 分析矩阵的元素M[A,a]中的下标A为非终结符，a为终结符或句子结束标记"#"，矩阵元素M[A,a]的内容为一条关于A的产生式。
二、LL(1)方法的实现： LL(1)方法在实现时用到一个LL(1)分析矩阵和一个分析栈以及预测分析程序。 分析矩阵的元素M[A,a]中的下标A为非终结符，a为终结符或句子结束标记"#"，矩阵元素M[A,a]的内容为一条关于A的产生式。 它表明当用非终结符A向下推导而当前输入符为a时，所应采用的候选式。当矩阵元素为空时，则表示用A往下推导时遇到了不应该出现的符号，即A与a不能匹配。因此应该转向出错处理。 预测分析程序见下图：

36 流程图： 开始 "# " "S" 进栈，读输入流一符号 a 栈顶元素出栈并送X 对产生式右部
x1 x2…xn按逆序即xnxn-1…x1 压入栈中 y y X∈VT? X=a? 读入符号 a N y N N M[A,a]为产生式？ N X="# "? 出错处理 N y N X=a? 出错处理 此时输入流也到尾部。 y 结束

37 例：现以表达式文法为例构造预测分析表。 G[E]: E→E+T | T T→T*F | F F→i |(E)
SELECT(E→TE')={(,i} SELECT(E'→+TE')={+} SELECT(E'→ε}={ε,),#} SELECT(T→FT')={(, i } SELECT(T'→*FT')={*} SELECT(T'→ε)={ε,+,),#} SELECT(F→i)={i} SELECT(F→(E))={(} 可知具有相同左部的产生式的SELECT集合互不相交，所以该 文法是LL(1)文法。 解：(1)判断G[E]是否为LL(1)文法,因文法中含有左递归，故必须先消去左递归，使文法 变为： E→TE' E'→+TE'|ε T→FT' T'→*FT'|ε F→i|(E) 求三种集合（前面已举例， 图略）最后得到： 有时间则作预测分析的演示

38 （2）构造预测分析表 对每个终结符或"#"号用a表示，则若a∈SELECT(A→α)。
令M[A,a]=A→α(一般为了简化，取M[A,a]=α) 把所有无定义的M[A,a]标上ERROR（一般在表中用空白表示）。 上例的分析表为： ( E ) i F ε * FT' T' FT' T +TE' E' TE' E # ) ( * + SELECT(E→TE')={(,i} SELECT(E'→+TE')={+} SELECT(E'→ε}={ε,),#} SELECT(T→FT')={(, i} SELECT(T'→*FT')={*} SELECT(T'→ε)={ε,+,),#} SELECT(F→i)={i} SELECT(F→(E))={(}

39 下面采用预测分析法对输入串i+i*i#进行分析。
( E ) i F ε * FT' T' FT' T +TE' E' TE' E # ) ( * + 步骤 分析栈 输入队列 动作 所用产生式 #E i+i*i# 替代 E→TE' #E'T i+i*i# 替代 T→FT' #E'T'F i+i*i# 替代 F→i #E'T'i i+i*i# 匹配 #E'T' i*i# 替代 T'→ε #E' i*i# 替代 E'→+TE'

40 步骤 分析栈 输入队列 动作 所用产生式 #E'T i*i# 匹配 #E'T i*i# 替代 T→FT' #E'T'F i*i# 替代 F→i #E'T'i i*i# 匹配 #E'T' *i# 替代 T'→FT' #E'T'F* i# 匹配 #E'T'F i# 替代 F→i #E'T'i i# 匹配 #E'T' # 替代 T'→ε #E' # 替代 E'→ε # # 接受

41 作业：1，3