编译原理自上而下语法分析.ppt

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

1、第四章自上向下语法分析语法分析的任务本章要点：自上而下语法分析的思想LL（1）方法递归下降分析预测分析基本思想主旨对任何输入串，试图用一切可能，从文法的开始符号出发，自上而下地为输入串建立一棵语法树，或者为输入串寻找一个最左推导。本质上是一种试探过程要解决的基本问题例：G[S]：S→xAyA→**

2、*考虑输入串x*y对于特定的非终结符号，使用哪个产生式来替换？带回溯的自上而下语法分析存在的困难和缺点文法的递归性虚假匹配错误的位置难以确定效率低，代价高无回溯的自上向下分析技术先决条件：无左递归既没有直接左递归，也没有间接左递归。无回溯

3、性对于任一非终结符号U的产生式右部x1

4、x2

5、…

6、xn，各xi的首终结符号两两不相交。文法的左递归性定义：文法的左递归性是指文法具有以下形式的直接左递归：U→Ux

7、y或间接左递归：U=>+Ux具有左递归性的文法举例E→E+T

8、TT→T*F

9、FF→(E)

10、i消除文法的直接左递归P→Pα1

11、…

12、Pαn

13、β1

14、…

15、βm改写为：P→β1P′

16、…

17、βmP′P′→α1P′

18、…

19、αnP′

20、ε例子消除左递归前E→E+T

21、TT→T*F

22、FF→(E)

23、i消除左递归后E→TE′E′→+TE′

24、εT→FT′T′→*FT′

25、εF→(E)

26、i间接左递归举例S→Q

27、c

28、cQ→Rb

29、bR→Sa

30、a以上文法不含直接左递归，但S，Q，R都是左递归的，因为：S=>Qc=>Rbc=>SabcQ=>Rb=>Sab=>QabcR=>Sa=>Qca=>Rbca消除文法的左递归前提：如果一个文法不含回路（形如P⇒+P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。消除文法的一切左递归的算法1、把文法的所有非终结符按任一顺序排序2、FORi=1TOnDO(1)FORj=1TOi-1DO把形如Pi→Pjγ的规则改写成Pi→δ1γ

31、

32、…

33、δkγ其中Pj→δ1

34、…

35、δk是关于Pj的所有规则(2)消除关于规则的直接左递归3、化简由2所得的文法例子A→BcdB→Ce

36、fC→Ab

37、c消除回溯的基本思想必须保证对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号，指派它的一个候选（右部）去执行任务，并且此候选的工作结果应是确定无疑的：即要么匹配成功，要么不可能获得匹配。消除回溯对文法的要求1、首先，文法不得含有左递归；2、设文法G不含左递归，对G的所有非终结符的每个候选α定义其终结首符集FIRST(α)为FIRST(α)={a

38、α=>*a…,a∈VT}特别

39、是，若α=>*ε，则规定ε∈FIRST(α)。如果非终结符A的所有候选首符集两两不相交，那么，当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选去执行任务。这个候选就是那个终结首符集含a的α。消除回溯方法：提取公共左因子假设关于A的产生式是A→δβ1

40、δβ2

41、…

42、δβn

43、γβn+1那么，可以将其改写为A→δA′

44、γβn+1A’→β1

45、β2

46、…

47、βn经过反复提取左因子，就能够把每个非终结符（包括新引进者）的多有候选首符集变成为两两不相交。代价：引入大量新的非终结符和空产生式。G[S]：S→BxB→x

48、ε考虑

49、输入串xFOLLOW(U)={b

50、S=>*xUby,b∈VT,x,y∈（VN∪VT)*}；特别地，#FOLLOW(S)。LL(1)分析条件文法不含左递归设U是文法G的任一个非终结符，其产生式为U→x1

51、x2

52、…

53、xn如果FIRST(xi)∩FIRST(xj)=Ф(i≠j,i,j=1,2,…,n)当ε∈FIRST(xi)时，有FIRST(xi)∩FOLLOW(U)=Ф则文法G为LL(1)文法。LL(1)方法基本思想：从S出发，生成句子的最左推导。选择合适产生式：从左到右扫描源程序，每次通过向前查看1个字符，选择合适的产生式。适用范围：

54、仅对LL(1)文法适用。FIRST(α)和FOLLOW(U)定义：1、FIRST(α)={a

55、α=>*aβ,a∈VT,β∈（VN∪VT)*}；特别地，如果α=>*，那么，我们规定FIRST(α)。2、FOLLOW(U)={b

56、S=>*xUby,b∈VT,x,y∈（VN∪VT)*}；特别地，#FOLLOW(S)。直观地讲：FIRST(u)包含了u对应的字的所有可能的首终结符号。FOLLOW(U)表示了句型中可能紧跟再U后面的终结符号。FIRST(α)构造算法对于X∈(VN∪VT）,FIRST(X)的构造1：若XVT，则FIRS

57、T(X)={X}2：若XVN，且有产生式X→a…,aVT，则aFIRST(X)；如果X→，那么FIRST(X)。3：若有产生式X→Y…,YVN,则FIRST(Y){}⊏FIRST(X);如果有产生式X→