编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法

Presentation on theme: "编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法"— Presentation transcript:

1 编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第六章 自底向上优先分析方法 第七章 LR分析方法 第八章 语法制导翻译和中间代码生成 第九章 符号表 第一○章 代码优化 第一一章 代码生成

2 第5章 自顶向下语法分析方法 语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。 确定
第5章 自顶向下语法分析方法 语法分析是编译程序的核心部分：在词法分析的基础上，识别单词符号序列是否是给定文法的正确句子（程序）。 确定 不确定 自顶向下分析 常用方法 算符优先分析 LR分析 自底向上分析

3 自顶向下语法分析方法 自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。
如果能够推导出，则该输入串是给定文法的句子； 如果不能推导出，则该输入串不是给定文法的句子。

4 自顶向下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？

5 自顶向下语法分析方法 自顶向下分析法分确定性和不确定性两种。 自顶向下的确定性分析法对文法有一定的限制，但实现简单直观，便于手工或自动构造；
自顶向下的不确定性分析法是带有回溯的分析方法，效率低，代价高，极少使用。

6 第5章 自顶向下语法分析方法 一、确定的自顶向下分析思想 二、LL(1)文法的判别 三、某些非LL(1)文法到LL(1)文法等价变换
第5章 自顶向下语法分析方法 一、确定的自顶向下分析思想 二、LL(1)文法的判别 三、某些非LL(1)文法到LL(1)文法等价变换 四、不确定的自顶向下分析思想 五、确定的自顶向下分析方法

7 自顶向下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？

8 1、方法：从开始符号出发，不断替换非终结符，根据当前的单词符号就可以唯一选定要替换的产生式。
一、确定的自顶向下分析思想 1、方法：从开始符号出发，不断替换非终结符，根据当前的单词符号就可以唯一选定要替换的产生式。 例1：文法G(S)：S→pA S→qB A→cAd A→a 输入串 W=pccadd 自顶向下的推导过程为:

9 SpA  pcAd  pccAdd  pccadd
相应的语法树： c d A S P S P A S P A c d A S P    c d A a

10 例1：文法G(S)：S→pA S→qB A→cAd A→a 该文法的特点： （1）每个产生式的右部都由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符开始。 对于这样的文法，其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导，因此，分析过程是唯一确定的。

11 （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。
例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 该文法的特点： （1）产生式的右部不全是由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。 （3）无空产生式。 ccap 如何根据输入串的第1个符号来确定产生式呢？

12 例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 当输入W=ccap推导： 自顶向下的推导过程为：

13 例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 当输入W=ccap推导： 自顶向下的推导过程为： S Ap cAp ccAp ccap 语法树为： S A P c S A P c S A P c  S A P   a

14 （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。
例2：文法G(S)为： S →Ap S → Bq A →a∣cA B→b∣dB 该文法的特点： （1）产生式的右部不全是由终结符号开始； （2 ）如果两个产生式有相同的左部，则它们的右部由不同的终结符或非终结符开始。 （3）无空产生式。 ccap 如何根据输入串的第1个符号来确定产生式呢？

15 则：FIRST(Ap)=？； FIRST(Bq)=？
针对产生式规则的右部产生开始符号集合 2、开始符号集合的定义： 设G=（VT，VN， P ，S ）是上下文无关文法， 开始符号集合为First()={ a |  aβ，a∈VT，  、β∈V*} 规则右部的开始符号集包括所有终结符 a，使得规则右部经过若干推导后得到的字符串以a为起始。 若 ε，则规定∈First() 。 * * 例3：上例中文法是： SAp|Bq A  a | cA B  b | dB 则：FIRST(Ap)=？； FIRST(Bq)=？

16 则：FIRST(Ap)={a，c}； FIRST(Bq)={b，d}
针对产生式规则的右部产生开始符号集合 2、开始符号集合的定义： 设G=（VT，VN， P ，S ）是上下文无关文法， 开始符号集合为First()={ a |  aβ，a∈VT，  、β∈V*} 规则右部的开始符号集包括所有终结符 a，使得规则右部经过若干推导后得到的字符串以a为起始。 若 ε，则规定∈First() 。 * * 例3：上例中文法是： SAp|Bq A  a | cA B  b | dB 则：FIRST(Ap)={a，c}； FIRST(Bq)={b，d}

17 如何根据输入串的第1个符号来确定产生式呢？
根据当前输入符号属于哪个产生式右部的开始符号集合而决定选择相应产生式进行推导。

18 例3：文法G[S] ： S  aA | d A  bAS|ε 若输入W=abd，则推导过程为：

19 例3：文法G[S] ： S  aA | d A  bAS|ε 若输入W=abd，则推导过程为：
S aA  abAS  abS  abd 语法树为： S a A  b  d

20 3、后跟符号集合的定义： 当某一非终结符的产生式中含有空产生式时，第二步推导的产生式该如何确定呢？根据后跟符号集合确定
设G=（VT，VN，P，S）是上下文无关文法，A∈VN，S是开始符号， Follow(A)={a | S uAβ且a∈VT，a ∈First(β)，u∈VT*，β∈V+}。针对非终结符 若S  uAβ，且β  ε，则#∈Follow(A) （#表示输入串的结束符，或句子括号） * * * 可写成为： Follow(A)＝｛a|S…Aa…， a∈VT｝ 若S…A，则#∈Follow(A)。 * *

21 Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。
例4：在例2中文法G[S]为：S  Ap | Bq A  a | cA B  b | dB 求Follow集。 解：Follow(S)={？} Follow(A)={？} Follow(B)={？}

22 换句话说： Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。 例4：在例2中文法G[S]为：S  Ap | Bq A  a | cA B  b | dB 求Follow集。 解：Follow(S)={#} Follow(A)={p} Follow(B)={q}

23 自上而下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ 根据规则的选择集合来确定。

24 4、选择集合的定义 给定上下文无关文法的产生式A，AVN， V*，若ε，则Select（A）=First()，
若ε，则Select(A)=（First()-{ε}）∪Follow(A) * * 给定输入串，根据产生式规则的选择集合选择产生式进行推导。

25 5、LL(1)文法的定义： 一个上下文无关文法是LL(1)文法的充分必要条件是对每个非终结符A的两个不同产生式：
A，Aβ满足Select(A)∩Select(Aβ)=，其中、β不同时推出 只有对满足LL(1)文法的句子，才能进行确定的自顶向下分析： 给定输入串，就可以根据产生式规则的选择集合确定唯一的产生式进行推导。

26 LL(1)的含义：从左L向右扫描输入串，分析过程中采用最左L推导，只需向右看1个符号就可确定如何推导（选择哪个产生式进行推导）。

27 例5：上例3文法： SaA|d AbAS|ε 证明该文法为LL(1)文法。

28 SAa aA ε * 例5：上例3文法： SaA|d AbAS|ε 证明该文法为LL(1)文法。
不难看出：Select(Sa A)=First(aA)＝{a} Select (Sd)= First(d)={d} Select (AbAS)={b} Select (Aε)=（first(ε)-{ε} ）∪follow(A)={a,d,#} Select (S aA) ∩Select(Sd)＝ { a｝∩{d}= Select(AbAS) ∩ Select(Aε) ＝｛b｝∩{a,d,#}=｛  ｝ 所以上述文法是LL(1)文法。 * SaA abAS abAd S aA abAS abAaA 所以Follow(A)={a,d,#}

29 例：设文法G[S]为： S  aAS | b A  bA |ε 判别是否是LL(1)文法。

30 解：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} 因此，该文法不是LL（1）文法，因而也就不可能用确定的自顶向下分析。

31 当需要选用自顶向下分析技术时，首先必须判定所给的文法是否是LL(1)文法。

32 二、 LL(1)文法的判别 解：(1) 计算first集： 方法一：计算first 集合的算法：
例：若文法G[S]为： S  AB | bC A ε | b B ε | aD C AD | b D aS | c 判别文法是否是LL(1)文法。 解：(1) 计算first集： 方法一：计算first 集合的算法： 对于每一个文法符号xV，计算first(x)的方法如下：

33 若xVN，且有xa…，aVT，则afirst(x) 若xVN，x  ，则first(x)
若xVT，则first(x)＝{x} 若xVN，且有xa…，aVT，则afirst(x) 若xVN，x  ，则first(x) 若xVN，y1，y2，…，yi都VN，产生式xy1y2…yn，当y1，y2，…yi-1都 时(1≤i≤n)， 则first(y1)－{}， first(y2)－{}，…， first(yi－1)－{}，first(yi)都包含在first(x)中。 e) 当上式中所有yi   (1≤i≤n)， 则first(x)＝first(y1) ∪first(y2) ∪…∪first(yn) ∪ {} * *

34 按上面的规则可得上例文法中每个文法符号的first集合如下：
S  AB | bC A ε | b B ε | aD C AD | b D aS | c first(S)= first(A)= first(B)= first(C)= first(D)=

35 按上面的规则可得上例文法中每个文法符号的first集合如下：
S  AB | bC A ε | b B ε | aD C AD | b D aS | c first(S)={first(A)-{}} ∪{first(B)-{}} ∪{} ∪{b}={a,b, } first(A)={b} ∪{}={b, } first(B)={} ∪{a}={a, } first(C)={first(A)-{}} ∪first(D) ∪first(b)={a,b, c} first(D)={a} ∪{c}={a,c}

36 一个文法符号串的first集合计算方法：
如果文法符号串V*, =X1X2…Xn, 1、当X1ε，则first()=first(X1) 2、当对任何j（1≤j≤i-1，2 ≤i ≤n），εfirst(Xj) 则first()=(first(X1)-{ε}) ∪(first(X2)-{ε}) ∪…∪(first(Xi-1)-{ε}) ∪first(Xi) 3、当first(Xj)都含有ε时(1 ≤ j ≤ n)，则first()=first(X1) ∪first(X2) ∪…∪first(Xj) ∪{ε} *

37 根据上面规则，每个产生式的右部符号串开始符号集合为：
first(AB)= first(bC)= first(ε)= first(aD)= first(AD)= first(b)= first(aS)= first(c)=

38 根据上面规则，每个产生式的右部符号串开始符号集合为：
first(AB)=first(A) ∪first(B) ∪{ε}={a, b, ε} first(bC)={b} first(ε)={ ε} 根据规则3 因为A ε Bε first(aD)={a} first(AD)=(first(A)-{ε}) ∪first(D)={a,b,c} first(b)={b} first(aS)={a} first(c)={c} 根据规则2 因为A ε Dε

39 方法二：由关系图法求文法符号的first集合
1、每个文法符号对应图中的一个结点，终结符结点用符号本身标记，非终结符结点用first(A)标记。 2、若文法中有AX， ε，则从对应A的结点到对应X结点连一条箭弧。 3、凡是从first(A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。 4、根据判别步骤1确定ε是否为某非终结符first的成员，若是则将ε加入该非终结符的first集中。 *

40 (1) 规则1：终结符结点用符号本身标记，本文法中有a,b,c。 (3)规则2：AX， ε，则A到X画一条箭弧。
文法为： S  AB | bC A ε | b B ε | aD C AD | b D aS | c b first(C) first(S) first(A) first(B) first(D) S  AB看成＝ ε，X＝A, =B 因此从S到A画一条弧。 S  AB看成＝ A，X＝B, =ε A  ε,因此从S到B画一条弧。 S  bC看成＝ ε，X＝b, =C 因此从S到b画一条弧。 同理：从A到b，从B到a， 从C到A、D、b， 从D到a、c画一条弧。 a c (1) 规则1：终结符结点用符号本身标记，本文法中有a,b,c。 (3)规则2：AX， ε，则A到X画一条箭弧。 (2) 规则1：非终结符结点用first(A)标记。本文法中有S,A,B,C,D。

41 (4)规则3： first(A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。
(5)规则4： 若ε是某非终结符first的成员，则将ε加入该非终结符的first集中。 所以，first(S)＝｛a,b｝ first(A)＝｛b｝ first(B)＝｛a｝ first(C ) ＝｛a,b,c｝ first(D)＝｛a,c｝ 所以，first(S)＝｛a,b, ε｝ first(A)＝｛b, ε ｝ first(B)＝｛a, ε ｝ first(C ) ＝｛a,b,c｝ first(D)＝｛a,c｝

42 （2）计算Follow 集： 方法一：根据Follow定义计算，算法如下： 求follow集的算法： (1)设S为开始符号，则#follow(S); (2) Follow(A)是所有句型中出现在紧接A之后的终结符或“#”。

43 (Ⅱ) 构造集合FOLLOW的算法 设S, A, B∈Vn , 算法：连续使用以下规则，直至FOLLOW集合不再扩大 若S为开始符号,则把“#”加入FOLLOW(S)中 (2)若A  αBβ (β≠ε),则把FIRST(β)-{ε}加入FOLLOW(B) (3)若A  αB 或A  αBβ， 且βε则把FOLLOW(A)加 入FOLLOW(B) *

44 文法为： S  AB | bC A ε | b B ε | aD C AD | b D aS | c Follow(S)= Follow(A)= Follow(B)= Follow(C)= Follow(D)=

45 S为开始符号，#加入follow(S)中。
文法为： S  AB | bC A ε | b B ε | aD C AD | b D aS | c Follow(S)={#} Follow(A)={a，#，c} Follow(B)={#} Follow(C)={#} Follow(D)={#} S为开始符号，#加入follow(S)中。 S AB B Bb A AaD S AB A  A AB AaD  bC bADbAc 方法二：根据关系图法求非终结符Follow集。(略)

46 (3) 计算Select集： 选择集合的定义 文法为： S  AB | bC A ε | b B ε | aD C AD | b
D aS | c (3) 计算Select集： 选择集合的定义 给定上下文无关文法的产生式A，AVN， V*，若ε，则Select（A）=First()， 若ε，则Select(A)=（First()-{ε}）∪Follow(A)

47 (3) 计算Select集： 每个产生式的Select集合计算为:
Select(SAB)= first (AB)/{ε}∪Follow(S)={b,a,#} Select(S bC)= first (bC)={b} Select(Aε)= first (ε)/{ε}∪Follow (A)={c,a,#} Select(Ab)= first (b) ={b } Select(Bε)= first (ε) /{ε} ∪Follow (B)={ #} Select(BaD)= first (aD) ={a} Select(CAD)= first (AD) ={b,a,c} 因为A B 

48 Select(Cb)= first (C) ={b }
Select(DaS)= first (aS) ={ a } Select(Dc)= first (c) ={c} 所以select的交集为： Select(SAB) ∩Select (SbC)= {b} ≠  Select(Aε) ∩ Select (Ab)=  Select(Bε) ∩ Select (BaD)= Select(CAD) ∩ Select (Cb)= {b}  Select(DaS) ∩ Select (Dc)=  因此该文法不是LL(1)文法。

49 三、 某些非LL(1)文法到LL(1)文法的等价变换
   1、 提取左公共因子 若文法中含有形如A|的产生式，这导致了对相同左部的产生式其右部的First集相交,也就是Select(A)∩Select(A)  ，不满足LL(1)文法的充分必要条件. 则须进行提取左公共因子的等价变换: A (|) 写成一般形式： AA’ A’  

50 例1：若文法G1的产生式为： SaSb SaS Sε 提取左公因子后得：

51 例1：若文法G1的产生式为： SaSb SaS Sε 提取左公因子后得：SaS( b |ε) 进一步变换：SaSA Ab Aε

52 例2：若文法G2的产生式： Aad ABc BaA BbB 解： A  ad A  aAc A  bBc B  aA B  bB Aa(d|Ac) AaA’ A’ d A’ Ac

53 上例不难验证经提取左公共因子后文法仍不是LL(1)文法 。 经过文法提取左公共因子后的文法不一定是 LL(1)文法。
最后变换为： A aA’ A  bBc A’  d A’ Ac B  aA B  bB 上例不难验证经提取左公共因子后文法仍不是LL(1)文法 。 经过文法提取左公共因子后的文法不一定是 LL(1)文法。

54 经过文法提取左公共因子后的文法，若有多余的产生式，则必须进行化简 。
例3：若有文法G3的产生式：SaSd S  Ac A  aS A  b

55 文法中非终结符A变成不可到达的符号,产生式也就变为多余的，所以应删除.
解：文法替换：SaSd S  aSc Sbc A  aS A  b SaS(d|c) SaSA A d|c Sbc AaS Ab 文法中非终结符A变成不可到达的符号,产生式也就变为多余的，所以应删除. SaSA A d|c Sbc

56 此外也存在某些文法不能在有限步骤内提取左公共因子。
例4: 若有文法G4的产生式: S Ap|Bq A aAp|d B aBq|e SaApp|aBqq Sdp|eq AaAp|d B aBq|e Sa(App|Bqq) SAp|Bq AaAp|d B aBq|e

57 SaS SApp|Bqq Sdp|eq AaAp|d B aBq|e SaS Sdp|eq SaAppp|aBqqq S'dpp|eqq AaAp|d B aBq|e

58 SaS Sdp|eq SaS Sdpp|eqq SAppp|Bqqq AaAp|d B aBq|e
上面例子说明： 不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。 一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法。否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。

59 称为左递归文法。其中a)是直接递归，b)是间接递归。
2、消除左递归 1. 一个文法含有下列形式的产生式时， a) AA AVN, V* b) AB B A A,BVN, ， V* 称为左递归文法。其中a)是直接递归，b)是间接递归。 如果一个 文法是左递归时，则不能采用自顶向下分析法。 例1：文法S Sa S b 是直接左递归 输入串：baaa# 所产生的语言是：L＝{ ban | n≥0}

60 ※ 消除左递归的变换方法： 是间接左递归 例2： 文法为：AaB ABb BAc Bd (1) 消除直接左递归：
输入串：adbcbcbc# 是间接左递归 ※ 消除左递归的变换方法： (1) 消除直接左递归： 方法：改为右递归。如 SSa 改写为： Sb S Sb Sa S|ε

61 (2) 消除间接左递归： 方法：间接左递归直接左递归右递归 例3：文法G6为: AaB AaB ABb ABb BaBc
(2) 消除间接左递归： 方法：间接左递归直接左递归右递归 例3：文法G6为: AaB ABb BAc Bd AaB ABb BaBc BBbc Bd BaBc|d BBbc B(aBc|d)B' B'bcB'|

62 对文法中一切左递归的消除要求文法中不含回路，即无AA的推导。 满足该文法的充分条件是：文法中不包含形如AA的有害规则和Aε的产生式。
AaB ABb B(aBc|d)B Bbc B|ε 对文法中一切左递归的消除要求文法中不含回路，即无AA的推导。 满足该文法的充分条件是：文法中不包含形如AA的有害规则和Aε的产生式。 ＋

63 四、不确定的自顶向下分析思想 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？
LL(1)文法：确定的自顶向下分析法：根据规则的选择集合来确定。 非LL(1)文法：不确定的自顶向下分析法－带回溯的自顶向下分析法 “不确定”的意思：当某个非终结符的产生式有多个候选，而面临当前的输入符号无法确定选用哪个产生式，从而引起回溯。

64 1、由于相同左部的产生式的右部First集交集不为空而引起回溯。
下面讲三个例子说明回溯： 1、由于相同左部的产生式的右部First集交集不为空而引起回溯。 例：文法SxAy Aab|a 求输入串为xay语法树。

65 first(ab)与first(a)的交集不为空
例：文法SxAy Aab|a 求输入串为xay语法树。 first(ab)与first(a)的交集不为空 S x A y S x A y S x A y 回溯 a b a 回溯，用Aa就匹配 SxAy 若选择Aab，就于xay不匹配

66 2、由于相同左部非终结符的右部能，且该非终结符Follow集中含有其右部First集的元素而引起回溯。
* 2、由于相同左部非终结符的右部能，且该非终结符Follow集中含有其右部First集的元素而引起回溯。 例：S  aAS |b A bAS | 求对输入串ab#的推导树。

67 2、由于相同左部非终结符的右部能，且该非终结符Follow集中含有其右部First集的元素而引起回溯。
* A Follow(A)={a,b} first(bAs)={b} 例：S  aAS |b A bAS | 求对输入串ab#的推导树。 S a A S a A S a A 回溯 b A  S b

68 3、由于文法含有左递归而引起回溯。 例：SSa Sb 若推导baa#

69 3、由于文法含有左递归而引起回溯。 例：SSa Sb 若推导baa# S a S a S a S a S 回溯 回溯 b b b
消除左递归后，再试一遍 b

70 3、由于文法含有左递归而引起回溯。 例：SbS’ S’aS’ S’   若推导baa#

71 由以上例子可以看出：带回溯的自顶向下分析是一个试探过程，当分析不成功时则推翻分析，退回到适当位置再重新试探其余可能的推导。
因此，需要记录所选过的产生式，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。（为证明输入串不合法，需要穷举或遍例所有的推导） 编译程序真正实现时往往边分析边插入语义动作，因而带回溯分析代价很高，效率很低，在实用编译程序中几乎不用。

72 五、确定的自顶向下分析方法 1、递归子程序法： 要求文法满足LL(1)文法。是比较简单直观易于构造的一种语法分析方法。
PL/0编译程序的语法分析部分就是采用的递归子程序法。 基本思想是：对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。

73 例：递归子程序实现 表达式的语法分析 表达式的EBNF 〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉} 〈项〉∷=〈因子〉{（*|/）〈因子〉} 〈因子〉∷=ident|number|‘（’〈表达式〉‘）’

74 〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉}
procedure expr; begin if sym in [ plus, minus ] then begin getsym; term; end else term; while sym in [plus, minus] do begin getsym; term; end end;

75 〈项〉∷=〈因子〉{（*|/）〈因子〉}
Procedure term; begin factor; while sym in [times,slash] do begin getsym;factor end end;

76 〈因子〉∷=ident|number|‘（’〈表达式〉‘）’
Procedure factor; begin if sym=ident then getsym else if sym=number if sym=‘(‘ then begin getsym; expr; if sym=‘)’ else error end end;

77 五、确定的自顶向下分析方法 2、预测分析方法： 自顶向下分析的另一种方法 预测分析器的组成： 预测分析程序 先进后出栈
预测分析表－与文法有关

78 预测分析表可用一个矩阵表示。矩阵元素M[A,a]中的A表示非终结符， a表示终结符或句子结束符#，矩阵元素M[A,a]中的内容是一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理。 如何构造预测分析表？

79 (Ⅲ) 构造分析表 终结符号 基本思想是: 当文法中某一非终结符呈现在栈顶时,根据当前的输入符号,分析表应指示要用该非终结符里的哪一条规则去匹配输入串(即进行下一步最左推导) 根据这个思想,我们不难把构造分析表算法构造出来! 非终结符号 79 79

80 表驱动的预测分析程序模型

81 (2)分析过程： ‘#’‘S’进栈，当前终结符送a 上托栈顶符号放入X 若产生式为 y 读下一 Xx1x2…xn y 个符号 按逆序即
xn…x2x1入栈 y 读下一 个符号 y XVT？ X＝a？ n n X=’#’？ y y n M(X,a)是 产生式吗？ n X＝a？ error n y error END

82 1.把#和文法识别符号E推进栈,并读入输入串的第一 个符a,重复下述过程直到正常结束或出错.
执行程序主要实现如下操作: 1.把#和文法识别符号E推进栈,并读入输入串的第一 个符a,重复下述过程直到正常结束或出错. 2.测定栈顶符号X和当前输入符号a,执行如下操作: (1)若X=a=#，分析成功，停止。E匹配输入串成功. (2)若X=a≠#，把X推出栈，再读入下一个符号。 (3)若X∈Vn，查分析表M（详细步骤见下页） 82 82

83 c) M[X, a] = X::=ε ---a为X的后继符号 则将X弹出栈 （不读下一符号） 继续分析。
(3)若X∈Vn，查分析表M。 a) M[X,a]= X∷=UVW 则将X弹出栈，将UVW压入 注：U在栈顶 （最左推导） b) M[X, a] = error 转出错处理 c) M[X, a] = X::=ε a为X的后继符号 则将X弹出栈 （不读下一符号） 继续分析。 83 83

84 分析算法 BEGIN 首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE；
WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在Ｘ中； IF X  Vt THEN IF X=a THEN 把下一个输入符号读进a 　 ELSE ERROR ELSE IF X=‘#’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF [X,b]={X –> X1X2..XK} THEN 把XK，X K-1,..,X1一一推进栈 ELSE　ERROR END OF WHILE; STOP/*分析成功，过程完毕*／ END

85 预测分析表构造算法 1.对文法G的每个产生式Ａ 执行第二步 和第三步；
2.对每个终结符aFIRST()，把Ａ 加  至[A,a]中， 3.若 FIRST()，则对任何bFOLLOW(A) 　　　　 把Ａ 加至[A,b]中， 4.把所有无定义的[A,a]标上“出错标志”。 可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的

86 (3)实例分析：给定文法，构造预测分析表，并针对输入串i+i*i#构造预测分析过程。
例：文法为：E E+T | T T  T*F | F F  i | (E) 步骤： （1） 判断文法是否为LL(1)文法。 如果文法中含有左递归，必须先消除左递归： （2）构造预测分析表 ： Select(A  ) （3）列出预测分析过程

87 (3)实例分析：给定文法，构造预测分析表，并针对输入串i+i*i#构造预测分析过程。
例：文法为：E E+T | T T  T*F | F F  i | (E) 构造步骤有： S Sa S bS' S b S'aS'| E E+T E T    判断文法是否为LL(1)文法。  由于文法中含有左递归，所以必须先消除左递归： E  TE E  +TE|ε E E+T | T

88 TFT  T*FT|ε T  T*F | F ETE E+TE|ε TFT  T*FT|ε F  i | (E) 文法变为：

89 T+FT'T+(E)T' T+(TE')T'T+(T)T'
  求First集合： First(E)={ ( ，i } First(E )={ + ，ε} First(T)={ ( ，i } First (T )={ * ，ε} First (F)={ ( ，i } ∵ETE T不， E'不 ∴First(E)=first(T) =first(F)={ ( , i } ETE' FT'E' (E)T'E' ETE' FT'E' (E)T'E‘ (TE')T'E' 求Follow集： Follow (E)={  ，#} Follow (E )={  ，#} Follow (T)={ + ， ，#} Follow (T )={ + ， ，#} Follow (F)={* ，+ ， ，#} ETE' T+T'E' T+T T+FT'T+(E)T' T+(TE')T'T+(T)T' ETE' FT'E' FT' F*FT' F*(E)T‘ F*(TE')T'F*(FT'E')T‘ F*(FT')T'

90 由上可知有相同左部产生式的Select集合的交集为空，所以文法是LL (1)
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)

91 若aSelect(Aa)，则Aa放入M[A,a]中。 i + * ( ) #
构造预测分析表 ： 方法：对每个终结符或#用a表示。 若aSelect(Aa)，则Aa放入M[A,a]中。 i + * ( ) # E TE' E' +TE'    T FT' FT ' T' *FT ' F i (E)

92 对于某句子的分析过程： 下面用预测分析程序，栈和预测分析表对输入串i+i*i#进行分析，给出栈的变化过程如下： 步骤 分析栈 剩余输入串 所用产生式 1 #E i+i*i# ETE 2 #ET TFT  3 #ETF Fi 4 #ETi i匹配 5 #ET +i*i# Tε 6 #E E+TE

93 7 #ET+ +i*i# +匹配 8 #ET i*i# TFT ' 9 #ETF F  i 10 #ETi i匹配 11 #ET *i# T  *FT 12 #ETF* *匹配 13 i# 14 15 # T  ε 16 #E E  ε 17 接受

94 表驱动的预测分析程序模型

95 (2)分析过程： ‘#’‘S’进栈，当前终结符送a 上托栈顶符号放入X 若产生式为 y 读下一 Xx1x2…xn y 个符号 按逆序即
xn…x2x1入栈 y 读下一 个符号 y XVT？ X＝a？ n n X=’#’？ y y n M(X,a)是 产生式吗？ n X＝a？ error n y error END

96 1.把#和文法识别符号E推进栈,并读入输入串的第一 个符a,重复下述过程直到正常结束或出错.
执行程序主要实现如下操作: 1.把#和文法识别符号E推进栈,并读入输入串的第一 个符a,重复下述过程直到正常结束或出错. 2.测定栈顶符号X和当前输入符号a,执行如下操作: (1)若X=a=#，分析成功，停止。E匹配输入串成功. (2)若X=a≠#，把X推出栈，再读入下一个符号。 (3)若X∈Vn，查分析表M（详细步骤见下页） 96 96

97 c) M[X, a] = X::=ε ---a为X的后继符号 则将X弹出栈 （不读下一符号） 继续分析。
(3)若X∈Vn，查分析表M。 a) M[X,a]= X∷=UVW 则将X弹出栈，将UVW压入 注：U在栈顶 （最左推导） b) M[X, a] = error 转出错处理 c) M[X, a] = X::=ε a为X的后继符号 则将X弹出栈 （不读下一符号） 继续分析。 97 97

98 分析算法 BEGIN 首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE；
WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在Ｘ中； IF X  Vt THEN IF X=a THEN 把下一个输入符号读进a 　 ELSE ERROR ELSE IF X=‘#’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF [X,b]={X –> X1X2..XK} THEN 把XK，X K-1,..,X1一一推进栈 ELSE　ERROR END OF WHILE; STOP/*分析成功，过程完毕*／ END

99 例题 例：已知文法G[S]：S aH H  aMd | d M  Ab | ε A  aM | e
（1）判断该文法是否是LL(1)文法，若是，请构造相应的LL(1)预测分析表 （2）给出对输入串aaabd#的预测分析过程，并说明该输入串是否是该文法的句子。

100 课后作业 P99 练习：1、5