第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类： 自顶向下语法分析方法(Top-Down) ，亦称面向目标的分析方法;

Presentation on theme: "第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类： 自顶向下语法分析方法(Top-Down) ，亦称面向目标的分析方法;"— Presentation transcript:

1 第三章 语法分析 自顶向下语法分析思想 语法分析方法的分类： 自顶向下语法分析方法(Top-Down) ，亦称面向目标的分析方法;
　　三个重要的集合：First集、Follow集、Predict集 自底向上语法分析方法(Bottom-Up) 。

2 1. 自顶向下语法分析概述 自顶向下语法分析方法，亦称面向目标的分析方法。
思想：从文法的开始符出发企图用最左推导推导出与输入的单词串完全相匹配的句子。若输入的单词串是给定文法的句子，则必能推出，反之必然以推导失败而终止。 自顶向下语法分析方法分为： 1、非确定的自顶向下语法分析方法; 2、确定的自顶向下语法分析方法：实现方法简单、直观，便于手工构造和自动生成，是目前常用的语法分析方法。 递归下降方法； LL（1）方法。

3 S a x x a a 2 非确定的自顶向下语法分析方法（带回溯过程的自顶向下语法分析方法） 已知G[S]: S→Ay | BAy
A→aA│a B→xB│x 输入串为xay是否正确。 S  Ay  aAy  ay a  BAy  xBAy  xxBAy BAy  xxAy x  xAy xaAy  xaaAy x  xaay a  xay a

4 非确定的自顶向下语法分析方法是一种穷举的试探方法，由于回溯导致语法推导重来、不能确切报告错误位置、效率低、代价高，因此，尽管这种方法适合于更广泛的文法，但也只是一种理论上可行的方法，极少使用。
确定的自顶向下语法可以根据当前输入自动确定选择相应的产生式进行推导，其难点为： 当非终极符有多个候选式时，如何确定地选择某个候选式。 如何记录推导的进程。

5 3 确定的自顶向下分析思想 例 G[S] : S  Ap | Bq A  a | cA B  b | dB
3 确定的自顶向下分析思想 例 G[S] : S  Ap | Bq A  a | cA B  b | dB 对给定的终极符串ccap，推导过程： S A p 选择产生式方法：根据当前输入符号与当前非终极符的哪个候选式可以推导出的首字符相匹配，就选哪个候选式。 c A c A 从左到右扫描输入串：c c a p S  Ap  cAp  ccAp  ccap a 5

6 第一个重要集：First集 定义：设G=(VT，VN，S，P)是上下文无关文法, (VTVN)*，则字符串的First集：
{ a VT | * a ...}  (if  * then {} else  ) “首符”集——符号串经过推导能够得到的所有可能的首个终极符集合 作用：可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。 6

7 自顶向下分析思想（续）文法不包含空产生式
A First()={a1,a2,…,an} A First()={b1,b2,…,bm} A First()={c1,c2,…,cm} 只要A的所有产生式的First集不相交，即 First() 　First()  First()= 对非终结符A的替换可惟一地确定候选式,就是当前字符属于哪个候选式右部的First集，就选哪个产生式的右部替代左部非终结符。 7

8 自顶向下分析思想（续）文法包含空产生式 例 G[S] : S  aA | d A  bAS |  对给定的终极符串abd，推导过程：
例3 文法特点： 　文法含有空产生式。 选择产生式方法：是否运用某个非终结符A的空产生式，要看紧跟该非终结符右边可能出现的终结符集是否与当前输入符号相匹配。 S a A 从左到右扫描输入串：a b d b A S S  aA  abAS  abS  abd  d 8

9 第二个重要集合： Follow集 定义：设G=(VT，VN，S，P)是上下文无关文法, AVN，S是开始符号，则非终极符A的Follow集： Follow(A) = { a VT | S+ ...Aa...}  (if S*... A then {#} else  ) 其中：#表示输入串的结束标志。 “跟随符”集——非终极符A在推导过程中可能跟随在其后面的终极符集合 作用：当文法中存在产生式形如：A+ 时，如果当前的字符属于Follow(A)，则可以用空串取代A的出现。 9

10 A First()={b1,b2,…,bm, } Follow(A)={c1,c2,…,ck}
A First()={a1,a2,…,an} A First()={b1,b2,…,bm, } Follow(A)={c1,c2,…,ck} 只有当A的多条产生式不能同时推导出空，则当满足下式时，对非终结符A的替换仍可惟一地确定候选。 First()  ((First()- )  Follow(A))= 10

11 第三个重要集合：Predict集 定义：设G=(VT，VN，S，P)是上下文无关文法，AVN，AP，则规则A的Predict集：
Predict(A) First() 当First() = (First()-{})Follow(A)当First() “预测符”集——产生式A能推导出的第一个终极符集合 11

12 4 自顶向下方法使用条件 产生式A被选择的条件是： 当前的输入符属于predict(A)。 至多一个候选式被选择的条件是：
4 自顶向下方法使用条件 产生式A被选择的条件是： 当前的输入符属于predict(A)。 至多一个候选式被选择的条件是： 若kj predict(Ak)predict(Aj)= 满足该条件的文法称为LL(1)文法，也是自顶向下分析技术的文法。 第1个L：自顶向下分析是从左向右扫描输入串 第2个L：分析过程使用最左推导 1：只需向右看输入符的一个字符便可决定选择哪个产生式进行推导。 12

13 First() ，当First()不含 = (First()-{})  Follow(A) ，当First()含
5 产生式Predict集的计算方法 Predict(A→ ) First() ，当First()不含 = (First()-{})  Follow(A) ，当First()含 方法关键：计算产生式A→ 的Predict集主要是计算右部串的First集和左部非终极符A的Follow集。

14 5.1 对每一文法符号X计算First(X)集 若X VT ： First(X)={X}
若X VN : 对X的每一个产生式进行如下处理: Step1.形如: X  , 则:   First(X) Step2.形如:X a… , a VT则 : a  First(X) Step3.对形如: XY1Y2…Yi-1Yi…Yn 若：Y1,Y2, … ,Yi VN且Y1,Y2, … ,Yi-1*  则: First(Y1)- {} , First(Y2)- {}, … , First(Yi-1)- {}, First(Yi)都包含在First(X)中。 若： Yi VN且Yi *  (i=1,2,…n), 则: First(Y1) , First(Y2), … , First(Yn) 都包含在First(X)中。

15 计算符号串的First()集算法要点
若符号串=X1X2…Xn， 当X1,X2, … , Xi-1*，Xi 不能 * ， 则: First()=1i-1(First(Xj)-{})  First(Xi) 若所有Xi 都能*， First()= 1n First(Xj)

16 文法符号 First集 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ | 
F  id | ( E ) E { id, ( } E’ {  ,+ } T { id, ( } {  } T’ ,* { id, ( } F

17 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E )
文法符号 First集 E E’ T T’ F { id, ( } { +, } { *,  } 符号串 First集 { id, ( } T E’ F T’ { id, ( } E’ T’ T { +, *, id, ( } E’ T’ { +, *,  }

18 例 First集 # void <C程序>  <预处理> <函数> #
，需要考察<预处理>的Follow集 void <C程序>  <预处理> <函数> <预处理>  #include <文件名串> |  <函数>  void id (<参数表>) { <语句组> } … …

19 例 S  Bd B  AC A  aX |  C  cY |  A的Follow集需要考察A后部C的First集：
当First(A后部C) ： Follow(A):=(First(C)－{})Follow(B)

20 5.2计算非终极符Follow（A）集算法要点
1: 对所有AVN 且 A非开始符 : 令Follow(A):={ }； 对开始符 S : 令Follow(S):={ # }； 2:若有产生式BxA， 如果First() 则： Follow(A):= First() 否则 Follow(A):=(First()－{})Follow(B) 3: 重复2，直至对所有AVN，Follow(A)收 敛为止。

21 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ F  id | ( E ) 文法符号 First集 E E’ T T’ F { id, ( } { +, } { *,  } Follow集 { # , ) } { # , ) } { + , # , ) } } { + , # , ) { , + , # , ) } *

22 确定的自顶向下语法分析 求取每个产生式A→ 的Predict集，根据当前输入字符匹配哪个候选式的Predict集来选择产生式。
Predict(A→ ) = First() ，当First()不含 (First()-{})  Follow(A) ，当First()含 至多有一个产生式被选择的条件是： predict(Aβk)predict(Aβj)=，当kj 该条件就是不带回溯的自顶向下语法分析方法（确定的自顶向下语法分析方法）的条件。 满足该条件的文法称为LL(1)文法，递归下降子程序文法。

23 Predict( ETE’ ) = first(TE’) = { id , ( }
文法符号 First集 Follow集 E { id, ( } { ), # } E’ { +, } T { +, ), # } T’ { *,  } F { *, +, ), # } 例： 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(E’ +TE’ ) ∩ Predict(E’  ) = 

24 Predict(T’ *FT’ ) ∩ Predict(T’   ) = 
文法符号 First集 Follow集 E { id, ( } { ), # } E’ { +, } T { +, ), # } T’ { *,  } F { *, +, ), # } 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) Predict( T’ *FT’ ) = first(*FT’) = { * } Predict( T’   ) = follow(T’) = { + , ) , # } Predict( F id ) = first(id) = { id } Predict( F (E) ) = first((E)) = { ( } Predict(T’ *FT’ ) ∩ Predict(T’   ) =  Predict(F id ) ∩ Predict(F (E) ) =  　所以是LL（1）文法

25 Predict(A  a) ∩ Predict(A  ) =  Predict(B b) ∩ Predict(B  ) = 
文法符号 First集 Follow集 例： S  ABc A  a A   B b B   # S { a, b,c } { } Predict(A  a) ∩ Predict(A  ) =  Predict(B b) ∩ Predict(B  ) =  　所以是LL（1）文法 A {  ,a } { b,c } B  ,b { } { c } Predict(S  ABc) = first(ABc) = { a,b,c } Predict(A  a) = first(a) = { a } Predict(A  ) = follow(A) = {b,c } Predict(B b) = first(b) = {b} Predict(B  ) = follow(B) = {c }

26 可能使用此产生式规则的当前token集合
对象 含义 特征 First集 长度可能不为1的符号串β 可能出现在β首字符位置的符号集合 可包括ℇ Follow集 一个非终极符B 可能出现在B后面的终极符集合 不包括ℇ可包括# Predict集 一条产生式规则 A->α 可能使用此产生式规则的当前token集合 26

27 6 非LL(1)文法 含有左公因子的文法为非LL（1）文法 由于文法的左递归。 例：有如下文法G[S]： S aSb S  aS

28 再验证所以非终结符的所有候选式是否满足LL(1)条件，即：
非LL(1)文法到LL(1)文法的等价转换 消除左公共前缀 消除直接左递归 和间接左递归 再验证所以非终结符的所有候选式是否满足LL(1)条件，即： 若kj predict(Ak)predict(Aj)= 注意1：即使文法没有公共前缀和左递归也并不意味着文法一定是LL(1)文法，有时还需要其它的转换方法。 注意2：通常程序设计语言的文法大都可以转换成LL(1)文法，但已经证明，非LL(1)文法是存在的，即有些文法是无法变换成LL(1)文法的。

29 例：设有如下文法： Stm  Label : UnLabeledStm Stm  id UnLabeledStm  id:=Exp Label  id Stm  id : UnLabeledStm Stm  id UnLabeledStm  id:=Exp Stm  id Stm’ Stm’  : UnLabeledStm |  UnLabeledStm  id:=Exp

30 1、计算每个非终极符的First集、Follow集. 2、计算每个产生式的Predict集合. 3、判断该文法是否为LL(1)文法？
练习题： 已知文法G[S]: SAB | bC A  | b B   | aD C  AD | b D  aS | c 1、计算每个非终极符的First集、Follow集. 2、计算每个产生式的Predict集合. 3、判断该文法是否为LL(1)文法？

31 文法 符号 First集 step1 step2 step3 S A B C D {b } {b,  } {a, } {b}
SAB | bC A  | b B   | aD C  AD | b D  aS | c 文法 符号 First集 step1 step2 step3 S A B C D {b } {b,  } {a, } {b} {a, c } {b, a, } {b, } {a, } {b,a,c} {a, c } { } {}

32 文法符号 First集 S { a, b,  } A { b, } B { a, } C { a, b, c } D { a, c }
SAB | bC A  | b B   | aD C  AD | b D  aS | c 文法符号 First集 S { a, b,  } A { b, } B { a, } C { a, b, c } D { a, c } First(AB ) = { a,b,  } First( bC ) = { b } First() = { } First( b ) = { b } First() = { } First(aD ) = {a } First(AD ) = {a,b,c } First(b) = { b }

33 文法符号 First集 Follow集 S { a, b,  } { # } A { b, } { a, c, # } B
SAB | bC A  | b B   | aD C  AD | b D  aS | c 文法符号 First集 Follow集 S { a, b,  } { # } A { b, } { a, c, # } B { a, } {# } C { a, b, c } D { a, c }

34 Predict(SAB ) = （First(AB)-{})  Follow(S) )= { a,b,# }
First(AB ) = { a,b,  } Predict(SAB ) = （First(AB)-{})  Follow(S) )= { a,b,# } First( bC ) = { b } Predict(S bC ) = First( bC )= { b } First( ) = { } Predict( A  ) = Follow(A) = { a, c , # } First(b ) = { b } Predict( Ab ) = First( b )= { b } First( ) = { } Predict( B  ) = Follow(B) = { # } First( aD ) = {a } Predict( B  aD ) = First( aD )= {a } First(AD ) = {a,b,c } Predict( C AD ) = First( AD )= {a,b,c } First(b) = { b } Predict( C b) = First( b )= { b } 文法符号 First集 Follow集 S { a, b,  } { # } A { b, } { a, c, # } B { a, } {# } C { a, b, c } D { a, c }

35 由于：Predict(SAB ) ∩Predict(S bC ) = { b }
Predict(SAB ) = { a,b,# } Predict(S bC ) = { b } Predict( A  ) = { a, c , # } Predict( Ab ) = { b } Predict( B  ) = { # } Predict( B  aD ) = {a } Predict( C AD ) = {a,b,c } Predict( C b) = { b } 由于：Predict(SAB ) ∩Predict(S bC ) = { b } Predict( C AD ) ∩Predict( C b) = { b } 所以该文法不是LL(1)文法. 文法符号 First集 Follow集 S { a, b,  } { # } A { b, } { a, c, # } B { a, } {# } C { a, b, c } D { a, c }