编译原理之递归下降法.ppt

《编译原理之递归下降法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自顶向下分析——递归下降法递归下降法(Recursive-DescentParsing)对每个非终极符按其产生式结构产生相应语法分析子程序.终极符产生匹配命令非终极符则产生调用命令文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。例：Stm→whileExpdoStm则对应产生式右部的语法分析程序部分如下：beginMatch($while)；Exp；Match($do)；Stmendwhilex>ydoifx>zthenx:=x+yelsex:=yBeginMatch($while);Exp;Match($do);StmEnd当产生式中形如:A1

2、2

3、…

4、n则按下

5、面的方法编写子程序A：procedureA()beginiftokenPredict(A1)then(1)elseiftokenPredict(A2)then(2)else……iftokenPredict(An)then(n)elseerr()end其中对i=X1X2…Xn，(i)=’(X1);’(X2);…;’(Xn);如果XVN，’(X)=X如果XVT，’(X)=Match(X)如果X=,()=skip(空语句)假设有文法Z→aBaB→bB

6、c则相应的递归子程序可如下：procedureZ()beginiftoken=athenMat

7、ch(a)；B；Match(a)elseerr()end;procedureB()beginiftoken=bthenMatch(b);B;elseiftoken=cthenMatch(c);elseerr()end;主程序：BeginReadToken;ZendReadTokenReadToken递归子程序方法的条件：(1)predict(A→k)predict(A→j)=，当kj(2)任一非终极符A都不是左递归的。产生式A→被选择的条件是：当前的输入符属于predict(A→)。至多一个产生式被选择的条件是：predict(A→k)predict(A→j)=，当kj

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

9、......消除左公共前缀消除左递归消除公共前缀变换步骤：产生式形如：A1

10、2

11、…

12、n

13、表示不以开头的字符串。2.引进非终极符A’，使产生式替换为：AA

14、A1

15、2

16、…

17、nStm→id:=ExpStm→id(ExpL)ExpL→ExpExpL→Exp,ExpLStm→idStmStm→:=ExpStm→(ExpL)ExpL→ExpExpLExpL→,ExpExpLExpL→消除公共前缀的例子消除公共前缀的例子2A

18、adABcBaABbBAadAaAcAbBcBaABbBAa(d

19、Ac)AbBcBaABbBAaAAdAAcAbBcBaABbB替换提因子引进A’左递归一个文法含有下列形式的产生式时（1）AAAVN,V*（2）ABBAA,BVN,,V*其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有A+A…，则称文法为左递归的。消除左递归对直接左递归形如：AA

20、消除左递归为：AAAA

21、消除左递归间接左递归形如：AB

22、BA

23、b消除左递归：转为直接左递归形式：AA

24、b

25、或者BB

26、

27、

28、b按照直接左递归方式消除。去掉多余的产生式例：[1]A→B1

29、a[2]B→C2

30、b[3]C→A3

31、cAB1C21A321[3]C→(B1

32、a)3

33、c[3]C→C213

34、b13

35、a3

36、c[4]C→(b13

37、a3

38、c)C[5]C→213C

39、[1],[2],[4],[5]与原文法等价作业写出下面文法G[p]的递归下降语法分析程序:PbeginSLendSLS

40、SL;SSi

41、i:=E

42、i:S

43、ifEthenS

44、whileEdoSEi

45、(E)

46、E+E