编译原理习题大全

《编译原理习题大全》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章1、编译过程包括哪几个主要阶段及每个阶段的功能。答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析

2、，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。第2章1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(()),()(())等，甚至包括0对括号）文法为：Sà(L)

3、LS

4、LLàS

5、e2、已知文法G：EàE+T

6、E-T

7、TTàT*F

8、T/F

9、FF

10、à(E)

11、i（1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。（2）i-i+i哪个算符优先。【解答】（1）最左推导：EÞE+TÞT+TÞF+TÞi+TÞi+T*FÞi+F*FÞi+i*FÞi+i*iEÞTÞT*FÞF*FÞi*FÞi*(E)Þi*(E-T)Þi*(T-T)Þi*(F-T)Þi*(i-T)Þi*(i-F)Þi*(i-i)最右推导：EÞE+TÞE+T*FÞE+T*iÞE+F*iÞE+i*iÞT+i*iÞF+i*iÞi+i*iEÞTÞT*FÞT*(E)ÞT*(E-T)ÞT*(E-F)ÞT*(

12、E-i)ÞT*(T-i)ÞT*(F-i)ÞT*(i-i)ÞF*(i-i)Þi*(i-i)i+i*i以及i*(i-i)的语法树如下所示：（2）i-i+i的语法树如下图所示。从上图的语法树可知：“-”的位置位于“+”的下层，也就是前面两个i先进行“-”运算，再与后面的i进行“+”运算，所以“-”的优先级高于“+”的优先级。3、文法G:EàET+

13、TTàTF*

14、FFàFP↑

15、PPàE

16、i（1）试证明符号串TET+*i↑是G的一个句型(要求画出语法树).（2）写出该句型的所有短语,直接短语和句柄.【解答】（1）采用最右推导：E

17、ÞTÞFÞFP↑ÞFi↑ÞPi↑ÞEi↑ÞTi↑ÞTF*i↑ÞTP*i↑ÞTE*i↑ÞTET+*i↑语法树如下图所示。从文法G的起始符号出发，能够推导出符号串TET+*i↑，所以给定符号串是文法G的句型。(2)该句型的短语有：ET+,TET+*,i,TET+*i↑直接短语有：ET+,i句柄是：ET+4、已知文法G：SàiSeS

18、iS

19、i，该文法是二义文法吗？为什么？【解答】该文法是二义文法。因为对于句子iiiei存在两种不同的最左推导：第1种推导：SÞiSeSÞiiSeSÞiiieSÞiiiei第2种推导：SÞiSÞi

20、iSeSÞiiieSÞiiiei第3章1、用正规式描述下列正规集：（1）C语言的十六进制整数；（2）以ex开始或以ex结束的所有小写字母构成的符号串；（3）十进制的偶数。【解答】（1）C语言十六进制整数以0x或者0X开头，所以一般形式应该为（+

21、-

22、e）(0x

23、0X)AA*，其中前面括号表示符号，可以有正号、负号，也可以省略（用e表示）默认是正数，A表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的串）。下面进一步确定A的取值，A应该为（0

24、1

25、2

26、3

27、4

28、5

29、6

30、7

31、8

32、9

33、a

34、b

35、

36、c

37、d

38、e

39、f

40、A

41、B

42、C

43、D

44、E

45、F），所以整个正规式应该为：(+

46、-

47、e)(0x

48、0X)(0

49、1

50、2

51、3

52、4

53、5

54、6

55、7

56、8

57、9

58、a

59、b

60、c

61、d

62、e

63、f

64、A

65、B

66、C

67、D

68、E

69、F)(0

70、1

71、2

72、3

73、4

74、5

75、6

76、7

77、8

78、9

79、a

80、b

81、c

82、d

83、e

84、f

85、A

86、B

87、C

88、D

89、E

90、F)*也可以写成：A：0

91、1

92、2

93、3

94、4

95、5

96、6

97、7

98、8

99、9

100、a

101、b

102、c

103、d

104、e

105、f

106、A

107、B

108、C

109、D

110、E

111、F（+

112、-

113、e）(0x

114、0X)AA*从上面看出，在用正规式描述正规集时，如本例题所示，采用自顶向下，逐步求精的方法，先描述正规集的一般规律，再对细节进

115、行描述。（2）以ex开始的小写字母符号串应该为ex（小写字母）*，以ex结尾的小写字母符号串应该为（小写字母）*ex，所以整个正规集描述为：ex（小写字母）*

116、（小写字母）*ex。（3）十进制偶数个位为0、2、4、6、8，前面其他数位为0、1、2、3、4、5、6、7、8、9，因此整个正规集表示为（+

117、-

118、e）A*B，其中A表示（0