自上而下的语法分析.ppt

《自上而下的语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章自上而下的语法分析4.1带回溯的自上而下分析法概述4.2直接左递归的消除4.3不带回溯的自上而下分析法的基本原理4.4提取左因子4.5first集和follow集4.6递归下降分析法4.7预测分析法从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。14.1带回溯的自上而下分析法概述从根结点出发，试图用一切可能的办法，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。㈠分析过程概述例已知文法G：S→xAyA→**

2、*和输入串α=x*y。①初始时，指示器P指向α的第一个符号x。②从S推导，因最左子结

3、和输入串第1个符号相匹配，故P指向下一符号*。③因第二个子结是非终结符A，从A采用第一个候选进行推导。从A推导出的左子结和指示器P所指的符号一致，故P指向下一个符号y。④因A的第二个子结*和指示器P所指的符号不一致，这意味着A的第一个候选不适用于构造α的语法树，应该回溯。将A的子树注销，P恢复进入A时的值。⑤用A的第二个候选进行推导，因子树A的子结和指示器P所指的符号*一致，则P指向下一个符号y。⑥因S的第三个子结和指示器P所指的符号一致，故α是一个句子。2显然上述分析过程本质上是一个试探过程，是反复使用不同产生式谋求匹配输入串的过程。㈡问题和困

4、难①对于左递归文法定义的语言，不能采用自上而下的语法分析法。②存在虚假匹配，回溯不可避免。③编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。④当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。⑤带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。总上所述，必须消除分析过程中的回溯，只有不带回溯的分析方法才是实际可使用的。34.2直接左递归的消除程

5、序设计语言文法的左递归性通常是由左递归规则直接引起的，由规则推导所产生的间接左递归的情况较少见。㈠实例引入例：已知左递归文法G：S→Sa

6、b，构造文法G的等价文法G'，G'不含左递归。解：文法G'如下所示S→bS'S'→aS'

7、ε∵SSaSaa…ban或Sb∴L(G)={ban∣n≥0}∵SbS'baS'…ban或SbS'b∴L(G')={ban∣n≥0}∵L(G)=L(G')∴文法G和G'等价，而文法G'不含左递归。4㈡直接左递归消除方法假定关于非终结符P的规则为P→Pα

8、β其中，β不以P开头。可以把关于P的规则变换为如下

9、形式：P→βP'P'→αP'

10、ε由于二者推导出的句型均为βαn(n≥0)，故上述变换是等价的。例文法G：E→E+T

11、TT→T*F

12、FF→(E)

13、i

14、x

15、y经消除直接左递归后变成E→TE'E'→+TE'

16、εT→FT'T'→*FT'

17、εF→(E)

18、i

19、x

20、y5㈢直接左递归消除一般规则及等价性证明设非终结符P的产生式如下P→Pα1

21、Pα2

22、…

23、Pαm

24、β1

25、β2

26、…

27、βn其中，βi（1≤i≤n）不以P开头。可将P的规则改成如下等价形式，即可消除左递归。P→β1P'

28、β2P'

29、…

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

31、α2P'

32、…

33、αmP'

34、ε证：P→Pα1

35、Pα2

36、

37、…

38、Pαm

39、β1

40、β2

41、…

42、βn等价于P→P（α1

43、α2

44、…

45、αm）

46、（β1

47、β2

48、…

49、βn）令α=α1

50、α2

51、…

52、αm、β=β1

53、β2

54、…

55、βn，则上式为：P→Pα

56、β。消除直接左递归后变成P→βP'P'→αP'

57、ε6证：P→Pα1

58、Pα2

59、…

60、Pαm

61、β1

62、β2

63、…

64、βn等价于P→P（α1

65、α2

66、…

67、αm）

68、（β1

69、β2

70、…

71、βn）令α=α1

72、α2

73、…

74、αm、β=β1

75、β2

76、…

77、βn，则上式为：P→Pα

78、β。消除直接左递归后变成P→βP'P'→αP'

79、ε用α1

80、α2

81、…

82、αm替代α，用β1

83、β2

84、…

85、βn替代β，则有P→（β1

86、β2

87、…

88、βn

89、）P'P'→（α1

90、α2

91、…

92、αm）P'

93、ε等价于P→β1P'

94、β2P'

95、…

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

97、α2P'

98、…

99、αmP'

100、ε74.3不带回溯的自上而下分析法的基本原理设文法G有产生式：A→α1

101、α2

102、…

103、αn㈠带回溯的自上而下的分析法采用试探法，对于α1、α2直至αn逐一试探。㈡不带回溯的自上而下的分析法在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。对于文法某一句型，只要该文法不是二义文法，从非终结符A出发的最左推导只有一个候选是正确的。如果该候选式获得匹配，那么这个匹配决不会是虚假的。若该候选式无法完成匹配任务，则任何其它候选

104、式也肯定无法完成。8算法思想如下：①引入候选式α的first集定义first(α)={a∣αa……，a∈VT}。first(α)直观意