资源描述：
《南邮《编译原理》习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《编译原理》习题解答：第一次作业：P142、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？答：被翻译的程序称为源程序；翻译出来的程序称为目标程序或目标代码；将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；编译程序是将高级语言写的源程序翻译成目标语言的程序。关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4图1.3。P143、编译
2、程序是由哪些部分组成？试述各部分的功能？答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。P144、语法分析和语义分析有什么不同？试举例说明。答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量x：=y符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。补充：为什么要对单词进行内部
3、编码？其原则是什么？对标识符是如何进行内部编码的？答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。第二次作业：P381、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。T2T1＝{011，0010，0111，01010，100111，1001010}T1*＝{ε，11，010，1111，11010，01011，01
4、0010……}T2+＝{0，01，1001，00，001，01001，010，0101……}P38-398、设有文法G[S]：S∷＝aAbA∷＝BcA
5、BB∷＝idt
6、ε试问下列符号串（1）aidtcBcAb（2）aidtccb（4）abidt是否为该文法的句型或句子。（1）SaAbaBcAbaidtcAbaidtcBcAb句型但不是句子；（2）SaAbaBcAbaidtcAbaidtcBcAbaidtccAbaidtccBbaidtccb；是句型也是句子；（4）该文法的句子或句型的最后一个字符串一定是字符“b”；第三次作业：P3911、试分别描述下列文法所产生的
7、语言（文法开始符号为S）：（1）S∷＝0S
8、01（2）S∷＝aaS
9、bc（1）L(G)＝{0n1
10、n≥1}；{解题思路：将文法转换为正规表达式}（2）L(G)＝{a2nbc
11、n≥0}。P3912、试分别构造产生下列语言的文法：（1）{abna
12、n=0，1，2，3……}（3）{aban
13、n≥1}（5）{anbmcp
14、n，m，p≥0}（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝aAaA∷＝bA
15、ε（3）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P：S∷＝abAA∷＝aA
16、a（5）①G＝{VN，VT，P，S}，V
17、N＝{S，A，B，C}，VT＝{a，b，c}，P：S∷＝ABCA∷＝aA
18、εB∷＝bB
19、εC∷＝cC
20、ε②G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b，c}，P：S∷＝aS
21、bS
22、cS
23、εP3915.设文法G规则为：S：：=ABB：：=a
24、SbA：：=Aa
25、bB对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。（2）baabaab(3)bBABb解（2）SABAaSbbBABabBaa句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄aS（3）ABbBSbAB短语bB,AB,ABb，bBABb简单短语bB,A
26、B，句柄bB第四次作业P4124.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？1.S::=aBB::=cBB::=bC::=c2.S::=aBB::=bCC::=cC::=ε3.S::=aAbaA::=aBaA::=aaAB::=bA::=a4.S::=aCdaC::=BaC::=aaAB::=b5.S::=ABA::=aB::=bCB::=bC::=c6.S::=ABA::=aB::=bCC::=cC::=ε7.S::=aAS::=εA::=aAA::=aBA::=aB::=b8.S::=aAS::=εA::=bAbA::=a短语结构
27、文法（0）
