编译原理第二版课后习包括

1、编译原理课后习题答案第一章1章引论1题讲解以下术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：若是源语言为高级语言，目口号言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。2）源程序：源语言编写的程序称为源程序。3）目标程序：目口号言书写的程序称为目标程序。4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机没关。平时前端包括词法解析、语法解析、语义解析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错办理工作和符号表管理等工作。5）后端：指那些依赖于目标机而一般

2、不依赖源语言，只与中间代码相关的那些阶段，即目标代码生成，以及相关出错办理和符号表操作。6）遍：是对源程序或其等价的中间语言程序重新至尾审察并完成规定任务的过程。2题一个典型的编译程序平时由哪些部分组成？各部分的主要功能是什么？并画出编译程序的整体构造图。答案：一个典型的编译程序平时包括8个组成部分，它们是词法解析程序、语法解析程序、语义解析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误办理程序。其各部分的主要功能简述以下。词法解析程序：输人源程序，拼单词、检查单词和解析单词，输出单词的机内表达形式。语法解析程序：检查源程序中存在的形式语法错误，输出错误办理信息

3、。语义解析程序：进行语义检查和解析语义信息，并把解析的结果保存到各样语义信息表中。中间代码生成程序：依据语义规则，将语法解析程序解析出的语法单位变换成必然形式的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换办理。目标代码生成程序：将优化后的中间代码程序变换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各样信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”其实不意味

4、着它就是一个独立的表格管理模块，而是指编译程序拥有的表格管理功能。错误办理程序：办理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的，理程序告出的地址和性等信息，同的行合适的校正（修复），目的是使程序能向下行解析和理。注意：若是程序有哪些主要组成成分，只要回答六部分就可以。若是搞不清楚，就回答八部分。3何翻程序、程序和解程序？它三者之有何种关系？答案：翻程序是指将用某种言写的程序成另一种言形式的程序的程序，如程序和程序等。程序是把用高言写的源程序（加工）成与之等价的另一种用低言写的目程序的翻程序。解程序是解、行高言源程序的程序。解方式一般分两种：一种方式是，源程序功能的完好由

5、解程序担当和完成，即每出源程序的一条句的第一个，依据个把控制移到条句功能的程序部分，部分完成条句的功能的，完成后返回到解程序的控部分再人下一条句行解、行，这样屡次；另一种方式是，一翻一行，即每出源程序的一条句，解程序就将其翻成一段机器指令并行之，尔后再人下一条句行解、行，这样屡次。无是哪一种方式，其加工果都是源程序的行果。当前很多解程序采用上述两种方式的合方案，即先把源程序翻成简单解行的某种中代程序，尔后集中解行中代程序，最后获取运行果。广上，程序和解程序都属于翻程序，但它的翻方式不相同，解程序是翻（解）行，不生目代，出源程序的运行果。而程序只把源程序翻成目程序，出与源程序等价的目程序，而目程

6、序的行任由操作系来完成，即只翻不可以。4以下信息，指出可能是的哪个段（法解析、法解析、解析、代生成）告的。（1）else没有般配的if2）数下越界3）使用的函数没有定4）在数中出非数字字符答案：1）法解析2）解析3）法解析4）法解析5程序大体有哪几种开技？答案：（1）自：用某一高言写其自己的程序。2）交织：A机器上的程序能生B机器上的目代。3）自展：第一确定一个特其他核心言L0，用机器言或言写出它的程序T0，再把言L0充到L1，此L0?L1,并用L0写L1的程序T1，再把言L1充L2，有L1L2,并用L1写L2的程序T2，这样渐渐扩展下去，好似滚雪球相同，直到我们所要求的编译程序。（4）移植：

7、将A机器上的某高级语言的编译程序搬到B机器上运行。第题计算机执行用高级语言编写的程序有哪些路子?它们之间的主要差异是什么?答案：计算机执行用高级语言编写的程序主要路子有两种，即讲解与编译。Basic之类的语言，属于讲解型的高级语言。它们的特点是计算机其实不早先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用讲解器将其翻译为一条机器代码，予以执行，尔后再读入下一条高级语句，翻译为机器代码，再执行，这样屡次。总而言之，是边翻译边执行。像C，Pascal之类的语言，属于编译型的高级语言。它们的特点是计算机早先对高级语言进行全盘翻译，将其全部变为机器代码，再一致执行，即先翻译，后

8、执行。赶忙度上看，编译型的高级语言比讲解型的高级语言更快。编译原理课后习题答案第二章2章PL/0编译程序的实现1题PL/0语言赞同过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的储藏管理。答案：PL/0语言赞同过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动向储藏管理。（数组CODE存放的只读目标程序，它在运行时不改变。）运行时的数据区S是由讲解程序定义的一维整型数组，讲解执行时对数据空间S的管理依据后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动向链和静态链的方式分别解决递归调用和非局部变量的引用问题。2题若PL/0

9、编译程序运行时的储藏分配策略采用栈式动向分配，并用动向链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出以下程序执行到赋值语句b=10时运行栈的布局表示图。varx,y;procedurep;vara;procedureq;varb;begin(q)b=10;end(q);procedures;varc,d;procedurer;vare,f;begincallendbegincallendbegincallendbegincallend(r)q;(r);(s)r;(s);(p)s;(p);(main)p;(main).答案：程序执行到赋值语句b=10时运行栈的布局表示图为：3题写

10、出题2中当程序编译到r的过程体时的名字表table的内容。namekindlevel/valadrsize答案：2中当程序编译到r的过程体时的名字表table的内容为：namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0过程p的入口（待填）5avariable1dxqprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2过程r的入口5evariable3dxfvariable3dx+1注意：q和s是并列的过程，所以q定义的变量b被覆

11、盖。4题指出栈顶指针T，最新活动记录基地址指针B，动向链指针DL，静态链指针SL与返回地址RA的用途。答案：栈顶指针T，最新活动记录基地址指针B，动向链指针DL，静态链指针SL与返回地址RA的用途说明以下：T：栈顶存放器T指出了当前栈中最新分配的单元(T也是数组S的下标)。B：基址存放器，指向每个过程被调用时，在数据区S中给它分配的数据段初步地址，也称基地址。SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，搜寻该变量的地址。DL：动向链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程

12、前运行栈的状态。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令连续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL，RA。5题PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中以下指令各自的功能和所完成的操作。（）INT0A（）OPR00（）CALLA答案：PL/0编译程序所产生的目标代码中有3条特别重要的特别指令，这3条_指令在code中的地址和功能以及所完成的操作说明以下：INT0A在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。OPR00

13、在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址存放器B和栈顶存放器T的值，并将返回地址送到指令地址存放器以使P中，调用前的程序从断点开始连续执行。CALLA调用过程，完成填写静态链、动向链、返回地址，给出被调用过程的基地址值，送入基址存放器B中，目标程序的入口地址A的值送指令地址存放器P中，使指令从A开始执行。6题给出对PL/0语言作以下功能扩大时的语法图和EBNF的语法描述。扩大条件语句的功能使其为：if条件then语句else语句扩大repeat语句为：repeat语句；语句until条件答案：PL/0语言作以下功能扩大时的语法图和EBNF的语法描述

14、以下：扩大条件语句的语法图为：EBNF的语法描述为：条件语句:=if条件then语句else语句扩大repeat语句的语法图为：EBNF的语法描述为：重复语句:=repeat语句；语句until条件编译原理课后习题答案第三章第3章文法和语言第1题文法G(A,B,S,a,b,c,P,S)SAc|aB其中P为：AabBbc写出L(GS)的全部元素。答案：L(GS)=abc2题文法GN为：ND|NDD0|1|2|3|4|5|6|7|8|9GN的语言是什么？答案:GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9N=ND=NDD.=NDDDD.D=D.D也许：赞同0开头的非负整数？第题为只包

15、括数字、加号和减号的表达式，比方答案：9-25，3-1，等构造一个文法。GS:S-S+D|S-D|DD-0|1|2|3|4|5|6|7|8|9第4题已知文法ZaZb|abGZ：写出L(GZ)答案：的全部元素。Z=aZb=aaZbb=aaa.Z.bbb=aaa.ab.bbbL(GZ)=anbn|n=15题写一文法，使其语言是偶正整数的会集。要求：赞同0打头；不相赞同0打头。答案：赞同0开头的偶正整数会集的文法ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8不相赞同0开头的偶正整数会集的文法ENT|DTFT|GND|1|3|5|7|9D2|4|6|8FN|0GD|0第6题已知文法G

16、：:=:=*:=（）i试给出下述表达式的推导及语法树。（）i+(i+i)（）i+i*i答案：+iii)=（）=（）=（）=（i）=（i）=（i）=（ii）=（ii）=（ii）=i（ii）+*iii=*=*i=*i=i*i=i*i=i*i=ii*i7题证明下述文法G表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/答案：可为句子a+a*a构造两个不相同的最右推导:最右推导1表达式表达式运算符表达式表达式运算符a表达式*a表达式运算符表达式*a表达式运算符a*a表达式+a*aa+a*a最右推导2表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运

17、算符a表达式运算符表达式*a表达式运算符a*a表达式+a*aa+a*a8题文法GS为：SAc|aBAabBbc该文法可否为二义的？为什么？答案：对于串abc(1)S=Ac=abc(2)S=aB=abc即存在两不相同的最右推导。所以，该文法是二义的。也许：对输入字符串abc，能构造两棵不相同的语法树，所以它是二义的。SaBcSAcab9题考虑下面上下文没关文法：SSS*|SS+|a表示经过此文法如何生成串aa+a*，并为该串构造语法树。SSS*SS+aaa(2)GS的语言是什么？答案：此文法生成串aa+a*的最右推导以下S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*该文法生成的语

18、言是：*和+的后缀表达式，即逆波兰式。第10题文法SS(S)S|生成的语言是什么？该文法是二义的吗？说明原由。答案：（）嵌套的括号（）是二义的，由于对于（）（）可以构造两棵不相同的语法树。11题令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的全部短语、直接短语和句柄。答案：此句型对应语法树如右，故为此文法一个句型。也许：由于存在推导序列:E=E+T=E+T*F，所E+T*F句型此句型有对于E的短语有:E+T*F；有对于T的短语T*F直接短语为：T*F句柄为：T*F13题一个上下文没关文法生成句子abbaa的推导树以下：给出串abba

19、a最左推导、最右推导。该文法的产生式会集P可能有哪些元素？找出该句子的全部短语、直接短语、句柄。BaSABSaSBAbba答案：串abbaa最左推:S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2)生式有：SABS|Aa|AaBSBB|b可能元素有：aaababbaaaaabbaa(3)句子的短有：是相A的短是相S的短是相B的短bb是相B的短是相S的短abbaa是相S的短直接短有：ab句柄是：a14出生成下述言的上下文没关文法：（1）anbnambm|

20、n，m=02）1n0m1m0n|n，m=03）WaWr|W属于0|a*，Wr表示W的逆答案：（）SAAAaAb|（）S1S0|AA0A1|（）S0S0|1S1|16出生成下述言的三型文法：(1)an|n=0anbm|n,m=1(3)anbmck|n,m,k=0答案：SaS|(2)SaAAaA|BBbB|b(3)AaA|BBbB|CCcC|17题习题和习题11中的文法等价吗？答案：等价。18题讲解以下术语和看法：（）字母表（）串、字和句子（）语言、语法和语义答案：（）字母表：是一个非空有穷会集。（）串：符号的有穷序列。字：字母表中的元素。句子：若是Zx,xV*T则称x是文法G的一个句子。+编译原

21、理课后习题答案第四章4章词法解析1题构造以下正规式相应的DFA.（）1(0|1)*101（）(1010*|1(010)*1）*0（）a(a|b)*|ab*a)*b（）b(ab)*|bb)*ab答案：先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，由于D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:先构造NFA：X1AB1C0D1E0F1G0H1I0J1KL0Y用子集法将NFA确定化01XXYCGCGJT2=YT3=CGJDHKDHDHKAB

22、FKLT4=DHEIEIABEFILT5=ABFKLYCGT6=ABEFILEJYCGEJYABEFGJLYT7=ABEFGJLYEHYCGKEHYABEFHLYCGKABCFGJKLT8=ABEFHLYEYCGIEYABEFLYCGICGJIT9=ABCFGJKLDHYCGKDHYDHYT10=ABEFLYEYCGT11=CGJIDHJKDHJDHJT12=DHYEIT13=DHJEIKEIKABEFIKLT14=ABEFIKLEJYCGT0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、1、2、3、4、5、6、7、8、9、1

23、0、11、12、13、14表示。由于2、7、8、10、12中含Y，所以它们都为终态。11233456237389101112910313561473102813141101010110110101010101先构造NFA：先构造NFA：XaABa,bDaEaFCYbb用子集法将NFA确定化abXXT0=XAAABCDT1=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=ABCDYBEBYT4=ABCDEFBEFBEYT5=ABCDEYBEFBEY将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。由于

24、3、5中含Y，所以它们都为终态。b011232453234455450a1b32a54bababab先构造NFA：XAbBaFbGbHEYaCDbIb用子集法将NFA确定化：abXXT0=XAABDEFT1=ABDEFCIGCICIGT2=CIDYDYABDEFYT3=GHABEFHT4=ABDEFYCIGT5=ABEFHCIG将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。由于4中含有Y，所以它为终态。b01123452323DFA0b2a453bbabab的状态图：1b第题已知NFA（x,y,z,0,1,M,x,zM(x,1)=x，M(y,1)=，M(z,1

25、)=y），其中：M(x,0)=z，构造相应的DFA。，M(y,0)=x,y，,M(z,0)=x,z，答案：先构造其矩阵01xzxx,yx,zy用子集法将NFA确定化：01xzxzxzyxzxzxyyxyxyxyzxxyzxyzxy将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。由于B、C、F中含有z，所以它为终态。01ABABCDCCEEFAFE1FED0B1010101C编译原理课后习题答案第四章3题将以下列图确定化：答案：用子集法将NFA确定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名状态子集，令VQ为A、QU为B、V

26、Z为C、V为D、QUZ为E、Z为F。.01SABACBBDECFFDF.ECEFFFDFA的状态图：4题将以下列图的（a）和（b）分别确定化和最小化：答案：初始分划得0：终态组0，非终态组1,2,3,4,5对非终态组进行审查：1,2,3,4,5a0,1,3,50,1,3,5既不属于0，也不属于1,2,3,4,54a0，所以获取新分划1：0，4，1,2,3,51,2,3,5进行审查：1,5b42,3b1,2,3,5，故获取新分划2：0，4，1,5，2,31,5a1,52,3a1,3，故状态2和状态3不等价，获取新分划3：0，2，3，4，1,5这是最后分划了最小DFA：第5题构造一个DFA，它接收

27、=0,1上全部满足以下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。答案：按题意相应的正规表达式是(0*10)*0*，或0*(0|10)*0*构造相应的DFA，第一构造NFA为用子集法确定化：II0I1X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y222重新命名状集：S0112342244333DFA的状：可将DFA最小化：1,2,4，非3，1,2,401,2,4，1,2,413，所以1,2,4等价状，可合并。第无符号数的正式：=dd*|dd*.dd*|.dd*|dd*10(s|)dd*|10(s|)dd*|.dd*10(s|)dd

28、*|dd*.dd*10(s|)dd*化，画出的DFA，其中d=0,1,2,9，s=，答案：先构造NFA：Xd.BdFGdH10dAC10dDsdYdsd用子集法将NFA确定化：?s10dXXAT0=XABFABFGAT1=BCCGHDET5=GHT6=HHT7=DEEYEYT8=EYT9=YY将XA、B、FG、A、C、G、H、DE、E、Y重新命名，分别用0、1、2、3、4、5、6、7、8、9表示。终态有0、3、4、6、9。?s10d01234563123474668999DFA的状态图：?d65ddd7890110ds?1010ddsddd7题给文法GS：SaA|bQAaA|bB|bBbD|a

29、QQaQ|bD|bDbB|aAEaB|bFFbD|aE|b构造相应的最小的DFA。答案：先构造其NFA：SaAaZQbBDaEbFbbabaabbbab用子集法将NFA确定化：abSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。由于3、中含有z，所以它们为终态。ab012113224325416516625DFA的状态图：0aa52b3aab416baabbbabP0（0,1,2,5,6,3,4）用b进行切割：P1（0,5,6,1,2,3,4）再用b进行切割：P2（0,5,6,1,2,3,4）再用a、b进行切割，

30、仍不变。再令为A，1，2为B，3，4为C，5，6为D。最小化为：Aa,bDCaaBbabb第题给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0答案：解方程组S的解：S=0A|1BA=1S|1B=0S|0将A、B产生式的右部代入S中S=01S|01|10S|10=（01|10）S|（01|10）所以：S=(01|10)*(01|10)9题将以下列图的DFA最小化，并用正规式描述它所识其他语言。1a26c3cb57bbabbbdda答案：P0（1,2,3,4,5,6,7）用b进行切割：P1（1,2,3,4,5,6,7）再用a、b、c、d进行切割，仍不变。再令1,2为A，3，4为B，5为

31、C，6，7为D。最小化为：AaDbdBbcabr=b*a(c|da)*bb*=b*a(c|da)*b+编译原理课后习题答案第五章5章自顶向下语法解析方法1题对文法GSSa|(T)TT,S|S(1)给出(a,(a,a)和(a,a),(a),a)的最左推导。对文法G，进行改写，尔后对每个非终结符写出不带回溯的递归子程序。经改写后的文法是否是LL(1)的?给出它的展望解析表。(4)给出输入串(a,a)#的解析过程，并说明该串可否为G的句子。答案：对(a,(a,a)的最左推导为：(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a)对(a,a)

32、,(a),a)的最左推导为：(T)(T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(S,S,S),S)(T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),S,S),S)(a,a),S),S)(a,a),(T),S)(a,a),(S),S)(a,a),(a),S)(a,a),(a),a)改写文法为：SaSS(T)TSNN,SNN非终结符FIRST集FOLLOW集Sa,(#,)Ta,().N,.).对左部为N的产生式可知：FIRST（,SN）=，FIRST（）=FOLLOW（N）=)由于SELECT(N,SN)SELE

33、CT(N)=，)=所以文法是LL(1)的。展望解析表（PredictingAnalysisTable）a(),#Sa(T)TSNSNSNN,SN也可由展望解析表中无多重入口判断文法是LL(1)的。对输入串（a,a）#的解析过程为：栈（STACK）当前输入符（CUR_CHAR）节余输入符（INOUT_STRING）所用产生式（OPERATION）#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#(aaa,aa)#a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可见输入串（a,a）#是文法的句子。3题已知文法GS：SMH|aHLSo|KdML|LeHfMK|bLM判断G是否是LL(1)文法，若是是，构造LL(1)解析表。答案：文法张开为：0）SMH1）Sa2）HLSo3）H4）KdML5）K6）LeHf7）MK8）MbLM非终结符FIRST集FOLLOW集Sa,d,b,e#,o.Md,b.e,#,o.H,e.#,f,o.Le.a,d,b,e,o,#Kd,.e,#,o.对相同左部的产生式可知：SELECT(SMH)SELECT(Sa)=d,b,e，#,o