递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。

Presentation on theme: "递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。"— Presentation transcript:

1 递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。
递归下降法 递归下降法语法分析原理 对每个非终极符按其产生式结构产生相应语法分析子程序。 .遇到终极符:执行匹配命令(读入下一token)； .遇到非终极符:则执行调用命令； 文法递归相应子程序也递归， 递归子程序方法/递归下降法

2 例如一条产生式：Stm→while RelExp do Stm
则对应产生式右部的语法分析程序部分如下： begin Match($while)； RelExp()； Match($do)； Stm(); end

3 递归下降分析示图 begin Match($while);RelExp;Match($do); Stm end
while x > y do if x > y then x := y +x else y := x

4 2 递归下降法语法分析程序的构造 一、引进下面两个基本动作： ReadToken：从输入流把下一个TOKEN码读到变量token中.
Match(a)：检查token=a? 若是，则执行ReadToken，否则报错并作相应的处理. 其中a是终极符（TOKEN的语法信息）.

5 递归下降法算法 语法分析主程序：Begin ReadToken; S ； Match(#) end
当产生式形如:A1|2|…|n,则按下面的方法编写子程序A： procedure A( ) begin if tokenPredict(A1) then (1) else if tokenPredict(A2) then (2) else …… if tokenPredict(An) then (n) else err( ) end 其中对i=X1X2…Xn，(i)=’(X1);’(X2);…;’(Xn); 如果XVN，’(X)= X(); 如果XVT，’(X)= Match(X); //即if(token==X)ReadToken(); 如果X= ，() = skip(空语句). 语法分析主程序：Begin ReadToken; S ； Match(#) end

6 例：假设有文法 Z → a B a B → b B | c Predict(Z→aBa)={a}, Predict(B→bB)={b}, Predict{B→c}={c} 则相应的递归子程序可如下： procedure Z( ) begin if token=a then Match(a)；B；Match(a); else err( 1 ) end; (aBa) ’(a); ’( B); ’(a) procedure B ( ) begin if token = b then Match(b); B; else if token = c then Match(c); else err( 2 ) end; 语法分析主程序：Begin ReadToken; Z ； Match(#) End

7 语法分析主程序：Begin ReadToken; E ； Match(#) end
例： 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)) = { ( } 语法分析主程序：Begin ReadToken; E ； Match(#) end procedure E( ) begin if token { id , ( } then T； E’ ； else err( 1 ) end;

8 else if token { ) , # } then skip(); else err( 2 ) end;
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)) = { ( } 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure E’ ( ) begin if token=“+” then Match($+); T； E’ ; else if token { ) , # } then skip(); else err( 2 ) end;

9 例： 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)) = { ( } 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure T( ) begin if token { id , ( } then F； T ’ ； else err( 3 ) end;

10 else if token { +,) , # } then skip (); else err( 4 ) end;
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)) = { ( } 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure T’ ( ) begin if token=“ * ” then Match($* ); F； T’ ; else if token { +,) , # } then skip (); else err( 4 ) end;

11 Match( $( ); E; Match( $) ) else err( 5 ) end;
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)) = { ( } 例： E  T E’ E’  + T E’ |  T  F T’ T’  * F T’ |  F  id | ( E ) procedure F ( ) begin if token=“ id” then Match($id ) ; else if token=“(” then Match( $( ); E; Match( $) ) else err( 5 ) end;

12 例：i+i*i # 递归下降分析过程 E→TE’ E’→+TE’│ε T→FT’ T’→*FT’│ε F→(E)│i TE’ E # i +
语法分析主程序：Begin ReadToken; E ； Match(#) end TE’ E # i + + +TE’ T E’ FT’ i + i # M(+) + # + # ε i F T’ ε T FT’ E’ i skip # M(i) skip * * F T’ *FT’ i M(*) M(i) i # # # F T’ ε i M(i) skip

13 二、递归子程序方法的进一步讨论 产生式A→被选择的条件是： 当前的输入符属于predict(A→). 至多一个产生式被选择的条件是：
predict(A→k)  predict(A→j )=，当k  j 递归下降子程序方法的条件： predict(A→k) predict(A→j )=，当k  j

14 三、对递归下降分析法的评价 递归下降分析法的优点是：简单、直观、程序结构和层次清晰明了，易于手工实现；
递归下降分析法的缺点是：对文法要求高；另一个缺点是频繁的递归调用使得速度慢且占用空间多.