吉林大学：《编译原理》课程教学资源（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

口产生式A→β被选择的条件是: 当前的输入符属于 predict(A→β)。 口至多一个产生式被选择的条件是: predict(A→P)∩ predict(A→B1)=,当k≠j 口递归子程序方法的条件: (1) predict(A→P)∩ predict(A→B1)=,当k≠j (2)任一非终极符A都不是左递归的

❑递归子程序方法的条件： (1)predict(A→k ) predict(A→j )=，当k  j (2)任一非终极符A都不是左递归的。 ❑产生式A→被选择的条件是： 当前的输入符属于predict(A→)。 ❑至多一个产生式被选择的条件是： predict(A→k )  predict(A→j )=，当k  j

文法的等价变换 某个非终极符A有如下的两个产生式: A→αβ,A→ay(即有左公共前缀) 某个非终极符A有直接左递归产生式: A→A 消除左公共前缀 消除左递归

文法的等价变换 • 某个非终极符A有如下的两个产生式： A→ ，A→  (即有左公共前缀) • 某个非终极符A有直接左递归产生式： A→ A  | ...... ⚫ 消除左公共前缀 ⚫ 消除左递归

消除公共前缀 ●变换步骤: 1.产生式形如:A→OB1|aB2l.|aβnly y表示不以α开头的字符串 2.引进非终极符A’,使产生式替换为 A→aA|y A→>β1|B21.βn

消除公共前缀 ⚫ 变换步骤： 1.产生式形如：A→1|2|…|n|  表示不以开头的字符串。 2.引进非终极符A’ ，使产生式替换为： A →  A |  A → 1|2 |…| n

消除公共前缀的例子 stm→ id stm Stm -id Exp stm→:=Exp stm→id(ExpL)→Stm′→(ExpL) ExpL→Exp ExpL→ Exp ExpL′ ExpL→Exp,ExpL EXpL′→, Exp ExpL′ ExpL′→λ

Stm → id := Exp Stm → id (ExpL) ExpL → Exp ExpL → Exp,ExpL Stm → id Stm Stm → := Exp Stm → ( ExpL ) ExpL → Exp ExpL ExpL → , Exp ExpL ExpL →   消除公共前缀的例子

消除公共前缀的例子2 ●A→Bc楂换。A一>bB提图·A ●A→ad ●A→ad A→>a(d|A A→aAc ●B→>aA →●B-aA ●B→>bB ●B→aA ●B→>bB ●B→>bB ●A→)aA A→>bBc 引进A。A→d B→)aA ●A→Ac B→bB

消除公共前缀的例子2 ⚫ A →ad ⚫ A →Bc ⚫ B →aA ⚫ B →bB ⚫ A →ad ⚫ A →aAc ⚫ A →bBc ⚫ B →aA ⚫ B →bB ⚫ A→a(d|Ac) ⚫ A →bBc ⚫ B →aA ⚫ B →bB ⚫ A →aA ⚫ A →d ⚫ A → Ac A →bBc B →aA B →bB 替换  提因子  引进A’ 