编译原理第4章.ppt

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

1、第四章语法分析——自上而下分析1、语法分析的地位－是编译程序的核心部分2、语法分析的任务－识别由词法分析得出的单词序列是否是给定文法的句子3、语法分析的理论基础－上下文无关文法和下推自动机4、语法分析的方式1）自上而下语法分析反复使用不同产生式进行推导以谋求与输入符号串相匹配2）自下而上语法分析对输入符号串寻找不同产生式进行归约直到文法开始符号注：这里所说的输入符号串指词法分析所识别的单词第四章自上而下语法分析（3）4.1语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序

2、的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图4.1所示。第四章自上而下语法分析（3）4.1语法分析器的功能语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。源程序编译前端中间代码代码优化中间代码代码生成器目标程序符号表语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。并建立一棵与输入串相匹配的语法分析树。按照语法分析树的建立方法，可以把语法分析办法分成两类：一类是自上而下分析法，另一类是自下而上分析法4.2自上而下分析面临

3、的问题自上而下分析就是从文法的开始符号出发，向下推导，推出句子。自上而下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。例4.1假定有文法（1）S→xAy(2）A→**

4、*（4.1）以及输入串x*y(记为α）。为了自上而下构造α的语法树，我们首先按文法的开始符号产生根结s，并让指示器IP指向输入串的第一个符号x。然后，用S的规则（此处关于S的规则仅有一条）

5、把这棵树发展为SXAY非终结符A有两个候选，试着用它的第一个候选去匹配输入串，于是把语法树发展为子树A的最左子结和IP所指的符号*相符，然后我们再把IP调为指向下一符号并让A的第二个子结进入工作。但A的第二子结*和当前所指的符号y不一致。因此，A告失败。这意味着A的第一个候选此刻不适用于构造α的语法树。这时应该回头（回溯），看A是否还有别的候选。SXAY**为了这种回溯，我们一方面应把A的第一候选所发展的子树注销掉，另一方面应把IP恢复为进入A时的原值，也就是让它重新指向第二个输入符号，。现在我们试探A的第二个候选，即考虑如下

6、的语法树：XAYS*由于子树A只有一个子结，而且它和IP所指的符号相一致，于是，A完成了匹配任务。在A获得匹配后，指示器IP应指向下一个未被触及符号y。在s的第二子结A完成匹配后，接着就轮到第三个子结y进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了为α构造语法树的任务，证明了α是一个句子。自上而下分析法存在的困难文法的左递归性问题PPα回溯虚假匹配难于知道输入串中出错的确切位置效率很低，代价极高4.3LL（1）分析法自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递

7、归性，并找出克服回溯的充分必要条件。消除左递归和克服回溯左递归的消除假定关于非终结符P的规则为：P→Pα

8、β其中，β不以P开头。那么，我们可以把P的规则改写为如下的非直接左递归形式：P→βP′P'→αP'

9、ε例文法E→E+T

10、TT→T*F

11、FF→(E)

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

13、εT→FT'T'→*FT'

14、εF→(E)

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

16、Pα2

17、...

18、Pαm

19、β1

20、β2

21、...

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

23、β2P'

24、...

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

26、α2P'

27、...

28、αmP'

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

30、

31、cQ→Rb

32、bR→Sa

33、a虽不具有直接左递归，但S,Q,R都是左递归的，例如有S=>Qc=>Rbc=>Sabc消除左递归方法：(1)将间接左递归改造为直接左递归将文法中所有如下形式的产生式：Pi→Pjγ

34、β1

35、β2

36、…

37、βnPj→δ1

38、δ2

39、δ3

40、…

41、δk改写成：Pi→δ1γ

42、δ2γ

43、δ3γ

44、…

45、δkγ

46、β1

47、β2

48、…

49、βn消除左递归方法：（2）消除直接左递归P→Pα1

50、Pα2

51、...

52、Pαm

53、β1

54、β2

55、...

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

57、β2P'

58、...

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

60、α2P'

61、...

62、αmP'

63、ε（3）化

64、简改写后的文法，即去除那些从开始符号出发却永远无法到达的非终结符的产生规则。最终得到无左递归的文法。消除回溯（方法：提取左公共因子）A→δβ1

65、δβ2

66、...

67、δβn

68、δ

69、γ1

70、γ2

71、..

72、γm(每个γ不以δ开头)改写为A→δA'

73、γ1

74、γ2

75、..

76、γmA'→β1

77、β2

78、..