自上而下的语法分析

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

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推导，因最左子结和输入串第1个符号相匹配，故P指向下一符号*。

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

4、编译程序的语法分析和语义分析通常是同时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。④当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。⑤带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，因此效率很低，这种分析法几乎没有实用价值。总上所述，必须消除分析过程中的回溯，只有不带回溯的分析方法才是实际可使用的。34.2直接左递归的消除程序设计语言文法的左递归性通常是由左递归规则直接引起的，由规则推导所产生的间接左递归的情况较少见。㈠实例引入例：已知左递归文法G：S→Sa

5、

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的规则变换为如下形式：P→βP'P'→αP'

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

10、TT→T*F

11、FF→(E)

12、i

13、x

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

15、'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、Pαm

38、β1

39、β2

40、…

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

42、α2

43、…

44、αm）

45、（β1

46、β2

47、…

48、βn）令α=α1

49、α2

50、…

51、αm、β=β1

52、β2

53、…

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

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

56、ε6证：P→P

57、α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）P'P'→（α1

89、α2

90、…

91、αm）P'

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

93、β2P'

94、…

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

96、α2P'

97、…

98、αmP'

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

100、α2

101、…

102、αn㈠带回溯的自上而下的分析法采用试探法，对于α1、α2直至αn逐一

103、试探。㈡不带回溯的自上而下的分析法在推导时，根据面临的输入符号去找出A的那个唯一正确的候选式。对于文法某一句型，只要该文法不是二义文法，从非终结符A出发的最左推导只有一个候选是正确的。如果该候选式获得匹配，那么这个匹配决不会是虚假的。若该候选式无法完成匹配任务，则任何其它候选式也肯定无法完成。8算法思想如下：①引入候选式α的first集定义first(α)={a∣αa……，a∈VT}。first(α)直观意