吉林大学：《编译原理》课程教学资源（PPT课件讲稿）自顶向下分析——递归下降法

自顶向下分析递归下降法 递归下降法( Recursive- Descent Parsing) 对每个非终极符按其产生式结构产生相应 语法分析子程序 终极符产生匹配命令 非终极符则产生调用命令 文法递归相应子程序也递归,所以称这种 方法为递归子程序方法或递归下降法

自顶向下分析——递归下降法 递归下降法(Recursive-Descent Parsing) 对每个非终极符按其产生式结构产生相应 语法分析子程序. 终极符产生匹配命令 非终极符则产生调用命令 文法递归相应子程序也递归，所以称这种 方法为递归子程序方法或递归下降法

例:Stm→ while Exp do Stm 则对应产生式右部的语法分析程序部 分如下: b egIn Match(Swhi le Exp Match (Sdo) Stm end

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

whi le x>y do if xz then x:= xty else x Begin Match(Swhi le); Exp: Match(do); Stm End

while x>y do if x>z then x:= x+y else x:= y Begin Match($while); Exp; Match($do); Stm End

当产生式中形如:A→β1β2|…βn 则按下面的方法编写子程序A procedure A() begin if tokenePredict(A→>β1)then(β1)else if token∈ Predict(A→>β2)then0(β2)else if token∈ Predict(A→>βn) then e(βn)else err o end 其中对β=X1X2…,Xn,θ()=(X1))(X2);…:0(Xn) 如果XeV,03(X)=X 如果XeVr,’(X= Match(X) 如果X=e,0(8)=skip(空语句)

⚫ 当产生式中形如: 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) 如果X=  , () = skip(空语句)

假设有文法 Z→aBa B→bB|c 则相应的递归子程序可如下: ReadToken procedure Z() procedure B() beg in beg in if token=a then Match(a): if token b then Match(b) B B Readtoken33Mth(2)° Ise f token =c else err() then Match end ese err d enc 主程序: Begin ReadToken;zend

假设有文法 Z → a B a B → b B | c 则相应的递归子程序可如下： procedure Z( ) begin if token=a then Match(a)； B； Match(a) else err( ) end; procedure B ( ) begin if token = b then Match(b); B; else if token = c then Match(c); else err( ) end; 主程序：Begin ReadToken; Z end ReadToken ReadToken