编译原理第二版课后习答案.doc

资源描述

1、编译原理课后习题答案第一章第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序得前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上得汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写得程序称为源程序。（3）目标程序：目标语言书写得程序称为目标程序。（4）编译程序得前端：它由这样一些阶段组成：这些阶段得工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析与中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关得出错处理工作与符号表

2、管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关得那些阶段，即目标代码生成，以及相关出错处理与符号表操作。（6）遍：就是对源程序或其等价得中间语言程序从头到尾扫视并完成规定任务得过程。第2题一个典型得编译程序通常由哪些部分组成？各部分得主要功能就是什么？并画出编译程序得总体结构图。答案：一个典型得编译程序通常包含8个组成部分，它们就是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序与错误处理程序。其各部分得主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词与分析单词，输出单

3、词得机内表达形式。语法分析程序：检查源程序中存在得形式语法错误，输出错误处理信息。语义分析程序：进行语义检查与分析语义信息，并把分析得结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出得语法单位转换成一定形式得中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量得目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后得中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写与查找等一系列表格工作。表格得作用就是记录源程序得各类信息与编译各阶段得进展情况，编译得每个阶段所需信息多数都从表格中读取，产生得中间结果都记录在相

4、应得表格中。可以说整个编译过程就就是造表、查表得工作过程。需要指出得就是，这里得“表格管理程序”并不意味着它就就是一个独立得表格管理模块，而就是指编译程序具有得表格管理功能。错误处理程序：处理与校正源程序中存在得词法、语法与语义错误。当编译程序发现源程序中得错误时，错误处理程序负责报告出错得位置与错误性质等信息，同时对发现得错误进行适当得校正（修复），目得就是使编译程序能够继续向下进行分析与处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第3题何谓翻译程序、编译程序与解释程序？它们三者之间有何种关系？答案：翻译程序就是指将用

5、某种语言编写得程序转换成另一种语言形式得程序得程序，如编译程序与汇编程序等。编译程序就是把用高级语言编写得源程序转换（加工）成与之等价得另一种用低级语言编写得目标程序得翻译程序。解释程序就是解释、执行高级语言源程序得程序。解释方式一般分为两种：一种方式就是，源程序功能得实现完全由解释程序承担与完成，即每读出源程序得一条语句得第一个单词，则依据这个单词把控制转移到实现这条语句功能得程序部分，该部分负责完成这条语句得功能得实现，完成后返回到解释程序得总控部分再读人下一条语句继续进行解释、执行，如此反复；另一种方式就是，一边翻译一边执行，即每读出源程序得一条语句，解释程序就将其翻译

6、成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。无论就是哪种方式，其加工结果都就是源程序得执行结果。目前很多解释程序采取上述两种方式得综合实现方案，即先把源程序翻译成较容易解释执行得某种中间代码程序，然后集中解释执行中间代码程序，最后得到运行结果。广义上讲，编译程序与解释程序都属于翻译程序，但它们得翻译方式不同，解释程序就是边翻译（解释）边执行，不产生目标代码，输出源程序得运行结果。而编译程序只负责把源程序翻译成目标程序，输出与源程序等价得目标程序，而目标程序得执行任务由操作系统来完成，即只翻译不执行。第4题对下列错误信息，请指出可能就是编译得哪个阶

7、段（词法分析、语法分析、语义分析、代码生成）报告得。（1）else没有匹配得if （2）数组下标越界（3）使用得函数没有定义（4）在数中出现非数字字符答案：（1）语法分析（2）语义分析（3）语法分析（4）词法分析第5题编译程序大致有哪几种开发技术？答案：（1）自编译：用某一高级语言书写其本身得编译程序。（2）交叉编译：A机器上得编译程序能产生B机器上得目标代码。（3）自展：首先确定一个非常简单得核心语言L0，用机器语言或汇编语言书写出它得编译程序T0，再把语言L0扩充到L1，此时L0L1,并用L0编写L1得编译程序T1，再把语言L1扩充为L2，有L1L2,并用L

8、1编写L2得编译程序T2，如此逐步扩展下去，好似滚雪球一样，直到我们所要求得编译程序。（4）移植：将A机器上得某高级语言得编译程序搬到B机器上运行。第题计算机执行用高级语言编写得程序有哪些途径?它们之间得主要区别就是什么? 答案：计算机执行用高级语言编写得程序主要途径有两种，即解释与编译。像Basic之类得语言，属于解释型得高级语言。它们得特点就是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而就是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，就是边翻译边执行。像C，Pasca

9、l之类得语言，属于编译型得高级语言。它们得特点就是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上瞧，编译型得高级语言比解释型得高级语言更快。编译原理课后习题答案第二章第2章PL/0编译程序得实现第1题 PL/0语言允许过程嵌套定义与递归调用，试问它得编译程序如何解决运行时得存储管理。答案： PL/0语言允许过程嵌套定义与递归调用，它得编译程序在运行时采用了栈式动态存储管理。（数组CODE存放得只读目标程序，它在运行时不改变。）运行时得数据区S就是由解释程序定义得一维整型数组，解释执行时对数据空间S得管理遵循后进先出规则，当每个

10、过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配得数据空间被释放。应用动态链与静态链得方式分别解决递归调用与非局部变量得引用问题。第2题若PL/0编译程序运行时得存储分配策略采用栈式动态分配，并用动态链与静态链得方式分别解决递归调用与非局部变量得引用问题，试写出下列程序执行到赋值语句b=10时运行栈得布局示意图。 varx,y; procedurep; vara; procedureq; varb; begin(q) b=10; end(q); procedures; varc,d; procedurer; vare,f; begin(r) callq; end(r)

11、; begin(s) callr; end(s); begin(p) calls; end(p); begin(main) callp; end(main)、答案：程序执行到赋值语句b=10时运行栈得布局示意图为：第3题写出题2中当程序编译到r得过程体时得名字表table得内容。 namekindlevel/valadrsize 答案：题2中当程序编译到r得过程体时得名字表table得内容为： namekindlevel/valadrsize xvariable0dx yvariable0dx+1 pprocedure0过程p得入口（待填）5 avariable1dx qproced

12、ure1过程q得入口4 sprocedure1过程s得入口（待填）5 cvariable2dx dvariable2dx rprocedure2过程r得入口5 evariable3dx fvariable3dx+1 注意：q与s就是并列得过程，所以q定义得变量b被覆盖。第4题指出栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA得用途。答案：栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址 RA得用途说明如下： T：栈顶寄存器T指出了当前栈中最新分配得单元(T也就是数组S得下标)。 B：基址寄存器，指向每个过程被调用时，在

13、数据区S中给它分配得数据段起始地址，也称基地址。 SL：静态链，指向定义该过程得直接外过程（或主程序）运行时最新数据段得基地址，用以引用非局部（包围它得过程）变量时，寻找该变量得地址。 DL：动态链，指向调用该过程前正在运行过程得数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈得状态。 RA：返回地址，记录调用该过程时目标程序得断点，即调用过程指令得下一条指令得地址，用以过程执行结束后返回调用过程时得下一条指令继续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL，RA。第5题 PL/0编译程序所产生得目标代码就是一种假想栈式计算机得汇编语言，请

14、说明该汇编语言中下列指令各自得功能与所完成得操作。（）INT0A （）OPR00 （）CALLA 答案： PL/0编译程序所产生得目标代码中有3条非常重要得特殊指令，这3条_指令在code中得位置与功能以及所完成得操作说明如下： INT0A 在过程目标程序得入口处，开辟A个单元得数据段。A为局部变量得个数+3。 OPR00 在过程目标程序得出口处，释放数据段（退栈），恢复调用该过程前正在运行得过程得数据段基址寄存器B与栈顶寄存器T得值，并将返回地址送到指令地址寄存器P中，以使调用前得程序从断点开始继续执行。 CALLA 调用过程，完成填写静态链、动态链、返回地址，给出被调用过程得基地

15、址值，送入基址寄存器B中，目标程序得入口地址A得值送指令地址寄存器P中，使指令从A开始执行。第6题给出对PL/0语言作如下功能扩充时得语法图与EBNF得语法描述。 (1)扩充条件语句得功能使其为： if条件then语句else语句 (2)扩充repeat语句为： repeat语句；语句until条件答案：对PL/0语言作如下功能扩充时得语法图与EBNF得语法描述如下： (1)扩充条件语句得语法图为： EBNF得语法描述为：条件语句:=if条件then语句else语句 (2)扩充repeat语句得语法图为： EBNF得语法描述为：重复语句:=repeat语句；语句until条件编译原

16、理课后习题答案第三章第3章文法与语言第1题文法G(A,B,S,a,b,c,P,S)其中P为： SAc|aB Aab Bbc 写出L(GS)得全部元素。答案： L(GS)=abc 第2题文法GN为： ND|ND D0|1|2|3|4|5|6|7|8|9 GN得语言就是什么？答案: GN得语言就是V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD、=NDDDD、D=D、D 或者：允许0开头得非负整数？第题为只包含数字、加号与减号得表达式，例如9-25，3-1，等构造一个文法。答案： GS: S-S+D|S-D|D D-0|1|2|3|4|5|6|7|8|9 第4题

17、已知文法GZ： ZaZb|ab 写出L(GZ)得全部元素。答案： Z=aZb=aaZbb=aaa、Z、bbb=aaa、ab、bbb L(GZ)=anbn|n=1 第5题写一文法，使其语言就是偶正整数得集合。要求： (1)允许0打头； (2)不允许0打头。答案： (1)允许0开头得偶正整数集合得文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 (2)不允许0开头得偶正整数集合得文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 第6题已知文法G： := :=* :=（）i 试给出下述表达式得推导及语法树。（）i+(

18、i+i) （）i+i*i 答案： + + i i i （) (5) = = =（） =（） =（） =（i） =（i） =（i） =（ii） =（ii） =（ii） =i（ii） + * i i i (6) = =* =*i =*i =i*i =i*i =i*i =ii*i 第7题证明下述文法G表达式就是二义得。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/ 答案：可为句子a+a*a构造两个不同得最右推导: 最右推导1表达式表达式运算符表达式表达式运算符a 表达式*a 表达式运算符表达式*a 表达式运算符a*a 表达式+a*a a+a*a 最右推导2表达式表达式运算

19、符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符a 表达式运算符表达式*a 表达式运算符a*a 表达式+a*a a+a*a 第8题文法GS为： SAc|aB Aab Bbc 该文法就是否为二义得？为什么？答案：对于串abc (1)S=Ac=abc(2)S=aB=abc 即存在两不同得最右推导。所以，该文法就是二义得。或者：对输入字符串abc，能构造两棵不同得语法树，所以它就是二义得。 S aB bc S Ac ab 第9题考虑下面上下文无关文法： SSS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 S SS* SS+a aa (2

21、为存在推导序列:E=E+T=E+T*F，所以E+T*F句型此句型相对于E得短语有:E+T*F；相对于T得短语有T*F 直接短语为：T*F 句柄为：T*F 第13题一个上下文无关文法生成句子abbaa得推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法得产生式集合P可能有哪些元素？ (3)找出该句子得所有短语、直接短语、句柄。 B a S ABS a SBA bba 答案： (1)串abbaa最左推导: S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推导： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbb

22、aa=Abbaa=abbaa (2)产生式有：SABS|Aa|AaBSBB|b 可能元素有：aaababbaaaaabbaa (3)该句子得短语有： a就是相对A得短语就是相对S得短语 b就是相对B得短语 bb就是相对B得短语 aa就是相对S得短语 abbaa就是相对S得短语直接短语有：ab 句柄就是：a 第14题给出生成下述语言得上下文无关文法：（1）anbnambm|n，m=0 （2）1n0m1m0n|n，m=0 （3）WaWr|W属于0|a*，Wr表示W得逆答案：（） SAA AaAb| （） S1S0|A A0A1| （） S0S0|1S1| 第16题给出生成下述语言得三

24、）(1010*|1(010)*1）*0 （）a(a|b)*|ab*a)*b （）b(ab)*|bb)*ab 答案： (1)先构造NFA：用子集法将NFA确定化、01 X、A AAAB ABACAB ACAABY ABYACAB 除X，A外，重新命名其她状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA 得终态），所以D为终态。、01 X、A AAB BCB CAD DCB DFA得状态图：: (2)先构造NFA： X1A B 1C0D1E 0 F1G0H1I0J1K L 0 Y 用子集法将NFA确定化 01 XX T0=XA AABFL T1=ABFLYCG YY CGCGJ

25、T2=Y T3=CGJDHK DHDH KABFKL T4=DHEI EIABEFIL T5=ABFKLYCG T6=ABEFILEJYCG EJYABEFGJLY T7=ABEFGJLYEHYCGK EHYABEFHLY CGKABCFGJKL T8=ABEFHLYEYCGI EYABEFLY CGICGJI T9=ABCFGJKLDHYCGK DHYDHY T10=ABEFLYEYCG T11=CGJIDHJK DHJDHJ T12=DHYEI T13=DHJEIK EIKABEFIKL T14=ABEFIKLEJYCG 将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10

26、、T11、T12、T13、T14重新命名，分别用0、 1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因为2、7、8、10、12中含有Y，所以它们都为终态。 01 01 123 2 345 46 523 673 789 81011 9129 10103 11135 126 1314 1473 010 12 12 7 108 3 4 5 6 9 111314 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 01 0 1 0 1 (3)先构造NFA：先构造NFA： XaA B a,b DaEaF C Y b b 用子集法将NFA确定化 ab XX T0=X

27、A AABCD T1=ABCDBEBY BEABCDE BYABCDY T2=ABCDEBEFBEY BEFABCDEF BEYABCDEY T3=ABCDYBEBY T4=ABCDEFBEFBEY T5=ABCDEYBEFBEY 将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y，所以它们都为终态。 ab 01 123 245 323 445 545 0a1b3 2 a 5 a4 b a b a b a b (4)先构造NFA： XA b B a FbGbH E Y a CDb Ib 用子集法将NFA确定化： ab XX T0=XA AABD

28、EF T1=ABDEFCIG CICI GG T2=CIDY DYABDEFY T3=GH HABEFH T4=ABDEFYCIG T5=ABEFHCIG 将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y，所以它为终态。 ab 01 123 24 35 423 523 DFA得状态图： 0b1b 2 a 4 5 3 b b a b a b 第题已知NFA（x,y,z,0,1,M,x,z），其中：M(x,0)=z，M(y,0)=x,y，,M(z,0)=x,z， M(x,1)=x，M(y,1)=，M(z,1)=y，构造相应得DFA。答案：先构造

29、其矩阵 01 xzx yx,y zx,zy 用子集法将NFA确定化： 01 xzx zxzy xzxzxy yxy xyxyzx xyzxyzxy 将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F 中含有z，所以它为终态。 01 ABA BCD CCE DE EFA FFE DFA得状态图： A 01 0 F E D 0 B 1 0 1 0 1 0 1 C 编译原理课后习题答案第四章第3题将下图确定化：答案：用子集法将NFA确定化：、01 SVQQU VQVZQU QUVQUZ VZZZ VZ、 QUZVZQUZ ZZZ 重新命名状态子集，令

30、VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。、01 SAB ACB BDE CFF DF、 ECE FFF DFA得状态图：第4题将下图得（a）与（b）分别确定化与最小化：答案：初始分划得 0：终态组0，非终态组1,2,3,4,5 对非终态组进行审查： 1,2,3,4,5a0,1,3,5 而0,1,3,5既不属于0，也不属于1,2,3,4,5 4a0，所以得到新分划 1：0，4，1,2,3,5 对1,2,3,5进行审查： 1,5b4 2,3b1,2,3,5，故得到新分划 2：0，4，1,5，2,3 1,5a1,5 2,3a1,3，故状态2与状态3不等价，得到新分划 3：

31、0，2，3，4，1,5 这就是最后分划了最小DFA：第5题构造一个DFA，它接收=0,1上所有满足如下条件得字符串：每个1都有0直接跟在右边。并给出该语言得正规式。答案：按题意相应得正规表达式就是(0*10)*0*，或0*(0|10)*0*构造相应得DFA，首先构造NFA为用子集法确定化： II0I1 X,0,1,3,Y 0,1,3,Y 2 1,3,Y 0,1,3,Y 0,1,3,Y 1,3,Y 1,3,Y 2 2 2 重新命名状态集： S01 1 2 3 4 2 2 4 4 3 3 3 DFA得状态图：可将该DFA最小化：终态组为1,2,4，非终态组为3，1,2,401,2

32、,4，1,2,413，所以1,2,4为等价状态，可合并。第题设无符号数得正规式为： =dd*|dd*、dd*|、dd*|dd*10(s|)dd* |10(s|)dd*|、dd*10(s|)dd* |dd*、dd*10(s|)dd* 化简，画出得DFA，其中d=0,1,2,9，s=，答案：先构造NFA： X d 、B d FG d H 10 d A C 10 d D s Ed Y d s d 用子集法将NFA确定化： s10d XXA T0=XABFA BB FFG AA T1=BC CC T2=FGGH GG HH T3=ABFA T4=CDC DDE T5=GH T6=HH T7=

34、 D a E b F b b a b a a b bb b a b 用子集法将NFA确定化： ab SAQ AABZ QQDZ BZQD DZAB DAB BQD 将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、 4中含有z，所以它们为终态。 ab 012 113 224 325 416 516 625 DFA得状态图： 0 a a 5 2 b 3 a a b 4 1 6 b a a b b b a b 令P0（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进行

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

36、 P1（1,2,3,4,5,6,7）再用a、b、c、d进行分割，仍不变。再令1,2为A，3，4为B，5为C，6，7为D。最小化为： A a CD b d B b c a b r=b*a(c|da)*bb*=b*a(c|da)*b+ 编译原理课后习题答案第五章第5章自顶向下语法分析方法第1题对文法GS Sa|(T) TT,S|S (1)给出(a,(a,a)与(a,a),(a),a)得最左推导。 (2)对文法G，进行改写，然后对每个非终结符写出不带回溯得递归子程序。 (3)经改写后得文法就是否就是LL(1)得?给出它得预测分析表。 (4)给出输入串(a,a)#得分析过程，并说明该串就是否为G得句子。答案： (1)对(a,(a,a)得最左推导为： S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a) 对(a,a),(a),a)得最左推导为： S(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

展开阅读全文