递归下降法 1 递归下降法语法分析原理 递归子程序方法/递归下降法 对每个非终极符按其产生式结构产生相应语法分析子程序。 递归下降法 1 递归下降法语法分析原理 对每个非终极符按其产生式结构产生相应语法分析子程序。 .遇到终极符:执行匹配命令(读入下一token); .遇到非终极符:则执行调用命令; 文法递归相应子程序也递归, 递归子程序方法/递归下降法
例如一条产生式:Stm→while RelExp do Stm 则对应产生式右部的语法分析程序部分如下: begin Match($while); RelExp(); Match($do); Stm(); end
递归下降分析示图 begin Match($while);RelExp;Match($do); Stm end while x > y do if x > y then x := y +x else y := x
2 递归下降法语法分析程序的构造 一、引进下面两个基本动作: ReadToken:从输入流把下一个TOKEN码读到变量token中. Match(a):检查token=a? 若是,则执行ReadToken,否则报错并作相应的处理. 其中a是终极符(TOKEN的语法信息).
递归下降法算法 语法分析主程序:Begin ReadToken; S ; Match(#) end 当产生式形如:A1|2|…|n,则按下面的方法编写子程序A: procedure A( ) begin if tokenPredict(A1) then (1) else if tokenPredict(A2) then (2) else …… if tokenPredict(An) then (n) else err( ) end 其中对i=X1X2…Xn,(i)=’(X1);’(X2);…;’(Xn); 如果XVN,’(X)= X(); 如果XVT,’(X)= Match(X); //即if(token==X)ReadToken(); 如果X= ,() = skip(空语句). 语法分析主程序:Begin ReadToken; S ; Match(#) end
例:假设有文法 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
语法分析主程序:Begin ReadToken; E ; Match(#) end 例: E T E’ E’ + T E’ | T F T’ T’ * F T’ | F id | ( E ) Predict( ETE’ ) = 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;
else if token { ) , # } then skip(); else err( 2 ) end; Predict( ETE’ ) = 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;
例: E T E’ E’ + T E’ | T F T’ T’ * F T’ | F id | ( E ) Predict( ETE’ ) = 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;
else if token { +,) , # } then skip (); else err( 4 ) end; Predict( ETE’ ) = 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;
Match( $( ); E; Match( $) ) else err( 5 ) end; Predict( ETE’ ) = 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;
例: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
二、递归子程序方法的进一步讨论 产生式A→被选择的条件是: 当前的输入符属于predict(A→). 至多一个产生式被选择的条件是: predict(A→k) predict(A→j )=,当k j 递归下降子程序方法的条件: predict(A→k) predict(A→j )=,当k j
三、对递归下降分析法的评价 递归下降分析法的优点是:简单、直观、程序结构和层次清晰明了,易于手工实现; 递归下降分析法的缺点是:对文法要求高;另一个缺点是频繁的递归调用使得速度慢且占用空间多.