编译原理——第五章-3.ppt

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

1、1编译方法中国人民大学信息学院陈文萍2第五章语法分析——自下而上分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析法5.4语法分析器的自动产生工具YACC35.1自下而上分析基本问题自下而上语法分析试图将一个字符串反向归约至开始符号比自上而下语法分析更有效率，对语法的限制更少移进－归约过程移进：将一个终结符推进栈归约：当栈顶形成某个产生式的候选式时，把这些符号从栈中弹出，把产生式的左部符号压入栈4文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dbbcdeA3）#abbcde#归约(A→b)A5）#a

2、Abcde#归约(A→Ab)B8）#aAcde#归约(B→d)S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进4）#aAbcde#移进6）#aAcde#移进7）#aAcde#移进9）#aAcBe#移进11）#S#接受对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcdea5规范归约短语、直接短语、句柄的定义：文法G[S]，SαAδ，且Aβ则称β是句型αβδ相对于非终结符A的短语。若有Aβ，则

3、称β是句型αβδ相对于该规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约:设α是文法G的一个句子，称序列αn,αn-1,…,α0是α的一个规范规约，如果此序列满足：αn＝αα0为文法的开始符，即α0＝S对任何i,0

4、右排列，这棵子树只有而且必须有父子两代SaAcBeAbbSaAcBeAbSddaAcBed7规约TintT+int

5、移进T+

6、int移进int

7、*int+int移进int*

8、int+int移进

9、int*int+intE

10、规约ET+ET+E

11、规约ETT+T

12、移进T

13、+int规约Tint*Tint*T

14、+int规约Tintint*int

15、+int文法G[E]：ET+E

16、TTint*T

17、int

18、(E)ETE+int*intTintT8移进－归约过程(1)+int*intint

19、int*int+int文法G[E]：ET+E

20、TT

21、int*T

22、int

23、(E)9移进－归约过程(2)+int*intintint

24、*int+int

25、int*int+int文法G[E]：ET+E

26、TTint*T

27、int

28、(E)10移进－归约过程(3)+int*intintint

29、*int+intint*

30、int+int

31、int*int+int文法G[E]：ET+E

32、TTint*T

33、int

34、(E)11移进－归约过程(4)+int*intintint

35、*int+intint*

36、int+int

37、int*int+intint*int

38、+int文法G[E]：ET+E

39、TTint*T

40、i

41、nt

42、(E)12移进－归约过程(5)+int*intintTint

43、*int+intint*

44、int+int

45、int*int+intint*T

46、+intint*int

47、+int文法G[E]：ET+E

48、TTint*T

49、int

50、(E)13移进－归约过程(6)T+int*intintTint

51、*int+intint*

52、int+int

53、int*int+intT

54、+intint*T

55、+intint*int

56、+int文法G[E]：ET+E

57、TTint*T

58、int

59、(E)14移进－归约过程(7)T+int*intintTT+

60、intint

61、*

62、int+intint*

63、int+int

64、int*int+intT

65、+intint*T

66、+intint*int

67、+int文法G[E]：ET+E

68、TTint*T

69、int

70、(E)15移进－归约过程(8)T+int*intintTT+int

71、T+

72、intint

73、*int+intint*

74、int+int

75、int*int+intT

76、+intint*T

77、+intint*int

78、+int文法G[E]：ET+E

79、TTint*T

80、int

81、(E)16移进－归约过程(9)T+int*intTintTT+int

82、T+

83、intint

84、*int+intint

85、*

86、int+int

87、int*int+intT+T

88、T

89、+intint*T

90、+intint*int

91、+int文法G[E]：ET+E

92、TTint*T

93、int

94、(E)17移进－归