语法分析——自上而下分析.ppt

《语法分析——自上而下分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第四章语法分析——自上而下分析4.1语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。并建立一棵与输入串相匹配的语法分析树。按照语法分析树的建立方法，可以把语法分析办法分成两类：一类是自上而下分析法，另一类是自下而上分析法4.2自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。自上而下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者

2、说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。例4.1假定有文法（1）S→xAy(2）A→**

3、*（4．1）以及输入串x*y(记为α）。为了自上而下构造α的语法树，我们首先按文法的开始符号产生根结s，并让指示器IP指向输入串的第一个符号x。然后，用S的规则（此处关于S的规则仅有一条）把这棵树发展为SXAY非终结符A有两个候选，试着用它的第一个候选去匹配输入串，于是把语法树发展为子树A的最左子结和IP所指的符号*相符，然后我们再把IP调为指向下一符号并让A的第二个子结进入工作。但A的第二子结*和当前所指的符号y不一致。因

4、此，A告失败。这意味着A的第一个候选此刻不适用于构造α的语法树。这时应该回头（回溯），看A是否还有别的候选。SXAY**为了这种回溯，我们一方面应把A的第一候选所发展的子树注销掉，另一方面应把IP恢复为进入A时的原值，也就是让它重新指向第二个输入符号，。现在我们试探A的第二个候选，即考虑如下的语法树：XAYS*由于子树A只有一个子结，而且它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器IP应指向下一个未被触及符号y。在s的第二子结A完成匹配后，接着就轮到第三个子结y进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了为α构造语法树的任务，证明了

5、α是一个句子。自上而下分析法存在的困难文法的左递归性问题回溯虚假匹配难于知道输入串中出错的确切位置效率很低，代价极高4.3LL（1）分析法LL(1)分析法又称预测分析法,是一种不带回溯的非递归自上而下分析法。LL(1)的含义:第一个L表明自左至右扫描输入串;第二个L表明最左推导;1表明向右查看一个符号。自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递归性，并找出克服回溯的充分必要条件。消除左递归和克服回溯左递归的消除直接消除见诸于产生式中的左递归是比较容易的。假定关于非终结符P的规则为：P→Pα

6、β其中，β不以P开头。那么，我们可

7、以把P的规则改写为如下的非直接左递归形式：P→βP′P'→αP'

8、ε例文法E→E+T

9、TT→T*F

10、FF→(E)

11、i消除左递归E→TE'E'→+TE'

12、εT→FT'T'→*FT'

13、εF→(E)

14、i一般情况P→Pα1

15、Pα2

16、...

17、Pαm

18、β1

19、β2

20、...

21、βn消除P的左递归P→β1P'

22、β2P'

23、...

24、βnP'P'→α1P'

25、α2P'

26、...

27、αmP'

28、ε间接左递归例如文法：S→Qc

29、cQ→Rb

30、bR→Sa

31、a虽不具有直接左递归，但S,Q,R都是左递归的，例如有S=>Qc=>Rbc=>Sabc解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入到Q中有关的候选式

32、：QSab

33、ab

34、b现在Q同样不含直接左递归，把它带入S的有关候选式：SSabc

35、abc

36、bc

37、c经消除S的直接左递归后我们们得到整个文法SabcS’

38、bcS’

39、cS’S’abcS’

40、QSab

41、ab

42、bRSa

43、a由于关于Q,R的规则式多余的则可化简得到：SabcS’

44、bcS’

45、cS’S’abcS’

46、消除左递归算法：(1)把文法G的所有非终结符按任一顺序排列成P1,P2,...Pn；按此顺序执行(2)FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pjγ的规则改写成Pi→δ1γ

47、δ2γ

48、...

49、δkγ，其中Pj→δ1

50、δ2

51、...

52、δ

53、k是关于Pj的所有规则消除关于Pi规则的直接左递归性END提左因子A→δβ1

54、δβ2

55、...

56、δβn

57、γ1

58、γ2

59、..

60、γm改写为A→δA'

61、γ1

62、γ2

63、..

64、γmA'→β1

65、β2

66、...

67、βn首符集令G是一个不含左递归的文法，对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为：FIRST(α)={a

68、α=>a...,a€VT}若α=>ε,则ε€FIRST(α)**如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选αi和αj，有FTRST(αi）∩FIRST(α