编译原理_第1~5章习题课答案

《编译原理_第1~5章习题课答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、chapter11、何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？源程序：用源语言编写的程序。目标程序：源程序经翻译程序过加工处理后生成的程序。翻译程序：将源程序转换为与其逻辑上等价的目标程序。编译程序：源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。解释程序：源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。①先翻译后执行①边解释边执行②执行速度快②有利于程序的调试③多次运算③1次运算2、一个典型的编译系统通常由有哪些部分组成？各部分的主要功能是什么？chapter1编译系统编译程序语

2、法分析语义分析与中间代码生成优化目标代码生成运行系统词法分析②语法分析(SyntaxAnalysis)：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。③语义分析(SyntacticAnalysis)：语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。chapter1①词法分析(LexicalAnalysis)：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。chapter1⑤代码优化(Opt

3、imizationofcode)：为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。⑥代码生成(Generationofcode)：目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。④中间代码生成(Generationofintermediatecode)：完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。chapter21.写出

4、C语言和Java语言的输入字母表。C语言：0~9数字，大小写英文字母，键盘上可见的字符Java语言：Unicode可以包括的所有字符。6.文法G6为:N→D

5、NDD→0

6、1

7、2

8、3

9、4

10、5

11、6

12、7

13、8

14、9（1）G6的语言是什么?G6的语言是：0~9的数字组成的任意非空串L(G6)={x

15、x∈{0,1,2,3,4,5,6,7,8,9}+}（2）给出句子0127、34和568的最左和最右推导。7、写一文法，使其语言是奇数集。要求：不以0打头。复杂的情况:分三部分末尾：以1

16、3

17、5

18、7

19、9结尾(一位):D→1

20、3

21、5

22、7

23、9开头：除了0的任意数字中

24、间部分：空或者任意数字串D→1

25、3

26、5

27、7

28、9C→CA

29、εA→0

30、B所以题目要求的文法G[N]可以写成：N→BCD

31、DD→1

32、3

33、5

34、7

35、9B→2

36、4

37、6

38、8

39、DC→CA

40、εA→0

41、BB→2

42、4

43、6

44、8

45、D9、证明文法:S→iSeS

46、iS

47、i是二义的。二义性的含义:如果文法存在某个句子对应两棵以上不同的语法树，或者两种以上不同的最左/右推导，则称这个文法是二义的。首先：找到此文法对应的一个句子iiiei其次：构造与之对应的两棵语法树SiSeSiSiiSiSiSeSii结论：因为该文法存在句子iiiei对应两棵不同的语法树，因而该文法是二义的。

48、11、给出下面语言的相应文法L1={anbnci

49、n≥1,i≥0}G1(S):S→ABA→aAb

50、abB→cB

51、ε从n，i的不同取值来把L1分成两部分：A→aAb

52、ab前半部分是anbn：后半部分是ci：B→Bc

53、ε所以整个文法G1[S]可以写为：L2={aibncn

54、n≥1,i≥0}G2(S):S→ABA→aA

55、εB→bBc

56、bcL3={anbnambm

57、m,n≥0}G3(S):S→ABA→aAb

58、εB→aBb

59、εL4={1n0m1m0n

60、n,m≥0}可以看成是两部分：剩下两边的部分就是：S→1S0中间部分是0m1m：A→0A1

61、ε所以G4

62、[S]可以写为：S→1S0

63、AA→0A1

64、ε

65、Achapter37.构造下列正规式相应的DFA。步骤:①.根据正规式画出对应的状态转换图;②.根据状态转换图画出对应的状态转换矩阵;③.根据状态转换矩阵得到重命名后的状态转换矩阵;④.根据重命名后的状态转换矩阵得出最后的DFA.问题：将状态转换图与DFA混淆。1(0

66、1)*101①.状态转换图abadb1(0

67、1)*101a1(0

68、1)*101dcef1εε01101ggg②.状态转换矩阵II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e

69、}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1abdcef1εε0101g