《编译原理》习题解答 南京邮电大学版.doc

《《编译原理》习题解答 南京邮电大学版.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译原理》习题解答：第一次作业：P142、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4图1.3。P143、编译程序是由哪些

2、部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。P144、语法分析和语义分析有什么不同？试举例说明。答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：=y符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。P155、编译程序分遍由哪些因素决定？答：计算机存储

3、容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。补充：1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。补充：2、赋值语句：A：=5*C的语法和语义指的是什么？答：语法分析将检查该语句是否符合赋值语句规则，语义是指将5

4、*C的结果赋值为A。第二次作业：P381、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。T2T1＝{011，0010，0111，01010，100111，1001010}T1*＝{ε，11，010，1111，11010，01011，010010……}T2+＝{0，01，1001，00，001，01001，010，0101……}P383、令A＝{0，1，2}，写出集合A+和A*的七个最短符号串。４８A+：0，1，2，00，01，02，10（有多种可能）A*：ε，0，1，2，00，01，02（有多种可能）P385、试证明：A+＝AA*＝A

5、*A。证明：A+＝A1∪A2∪……∪An∪……A*＝A0（即{ε}）∪A+AA*＝A（A0∪A+）＝A∪A2∪A3∪A4……＝A+＝A+∪A＝（A0∪A+）A＝A*A（证毕）P387、设有文法G[S]：S∷＝AA∷＝B

6、IFATHENAELSEAB∷＝C

7、B+C

8、+CC∷＝D

9、C*D

10、*DD∷＝X

11、(A)

12、-D试写出VN和VT。VN＝{S，A，B，C，D}VT＝{IF，THEN，ELSE，+，*，X，(，)，-}P38-398、设有文法G[S]：S∷＝aAbA∷＝BcA

13、BB∷＝idt

14、ε试问下列符号串（1）aidtcBcAb（3）ab（5）aidtcidtcidtb是否为该

15、文法的句型或句子。（1）SaAbaBcAbaidtcAbaidtcBcAb句型但不是句子；（3）SaAbaBbaεbab是句型也是句子；（5）SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcBbaidtcidtcidtb句型也是句子。P3910、给定文法：S∷＝aB

16、bAA∷＝aS

17、bAA

18、aB∷＝bS

19、aBB

20、b该文法所描述的语言是什么？L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。P3911、试分别描述下列文法所产生的语言（文法开始符号为S）：（1）S∷＝0S

21、01（2）S∷＝aaS

22、bc（3）S::=aSd

23、aAdA::=aAc

24、bc

25、（4）S::=ABA::=aAb

26、abB::=cBd

27、ε（1）L(G)＝{0n1

28、n≥1}；{解题思路：将文法转换为正规表达式}（2）L(G)＝{a2nbc

29、n≥0}；４８（1）L(G)＝{aibcjdk

30、i,j,k≥1,i=j+k-1}；或者L(G)＝{aj+k-1bcjdk

31、j,k≥1}；（2）L(G)＝{anbncmdm

32、m≥0,n≥1}。P3912、试分别构造产生下列语言的文法：（1）{abna

33、n=0，1，2，3……}（2）{anbn

34、n=1，2，3，4……}（3）{aban

35、n≥1}（4）{