《编译原理第二版课后习答案_1.docx》由会员分享,可在线阅读,更多相关《编译原理第二版课后习答案_1.docx(34页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、编译原理第二版课后习答案(编译原理)课后习题答案第一章第1章引论第1题解释下列术语:1编译程序2源程序3目的程序4编译程序得前端5后端6遍答案:1编译程序:假如源语言为高级语言,目的语言为某台计算机上得汇编语言或机器语言,则此翻译程序称为编译程序。2源程序:源语言编写得程序称为源程序。3目的程序:目的语言书写得程序称为目的程序。4编译程序得前端:它由这样一些阶段组成:这些阶段得工作主要依靠于源语言而与目的机无关。通常前端包括词法分析、语法分析、语义分析与中间代码生成这些阶段,某些优化工作可以在前端做,也包括与前端每个阶段相关得出错处理工作与符号表管理等工作。5后端:指那些依靠于目的机而一般不依
2、靠源语言,只与中间代码有关得那些阶段,即目的代码生成,以及相关出错处理与符号表操作。6遍:就是对源程序或其等价得中间语言程序从头到尾扫视并完成规定任务得经过。第2题一个典型得编译程序通常由哪些部分组成?各部分得主要功能就是什么?并画出编译程序得总体构造图。答案:一个典型得编译程序通常包含8个组成部分,它们就是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目的代码生成程序、表格管理程序与错误处理程序。其各部分得主要功能简述如下。词法分析程序:输人源程序,拼单词、检查单词与分析单词,输出单词得机内表达形式。语法分析程序:检查源程序中存在得形式语法错误,输出错误处理信
3、息。语义分析程序:进行语义检查与分析语义信息,并把分析得结果保存到各类语义信息表中。中间代码生成程序:根据语义规则,将语法分析程序分析出得语法单位转换成一定形式得中间语言代码,如三元式或四元式。中间代码优化程序:为了产生高质量得目的代码,对中间代码进行等价变换处理。目的代码生成程序:将优化后得中间代码程序转换成目的代码程序。表格管理程序:负责建立、填写与查找等一系列表格工作。表格得作用就是记录源程序得各类信息与编译各阶段得进展情况,编译得每个阶段所需信息多数都从表格中读取,产生得中间结果都记录在相应得表格中。能够讲整个编译经过就就是造表、查表得工作经过。需要指出得就是,这里得“表格管理程序并不
4、意味着它就就是一个独立得表格管理模块,而就是指编译程序具有得表格管理功能。错误处理程序:处理与校正源程序中存在得词法、语法与语义错误。当编译程序发现源程序中得错误时,错误处理程序负责报告出错得位置与错误性质等信息,同时对发现得错误进行适当得校正修复,目得就是使编译程序能够继续向下进行分析与处理。注意:假如问编译程序有哪些主要构成成分,只要回答六部分就能够。假如搞不清楚,就回答八部分。第3题何谓翻译程序、编译程序与解释程序?它们三者之间有何种关系?答案:翻译程序就是指将用某种语言编写得程序转换成另一种语言形式得程序得程序,如编译程序与汇编程序等。编译程序就是把用高级语言编写得源程序转换加工成与之
5、等价得另一种用低级语言编写得目的程序得翻译程序。解释程序就是解释、执行高级语言源程序得程序。解释方式一般分为两种:一种方式就是,源程序功能得实现完全由解释程序承当与完成,即每读出源程序得一条语句得第一个单词,则根据这个单词把控制转移到实现这条语句功能得程序部分,该部分负责完成这条语句得功能得实现,完成后返回到解释程序得总控部分再读人下一条语句继续进行解释、执行,如此反复;另一种方式就是,一边翻译一边执行,即每读出源程序得一条语句,解释程序就将其翻译成一段机器指令并执行之,然后再读人下一条语句继续进行解释、执行,如此反复。无论就是哪种方式,其加工结果都就是源程序得执行结果。目前很多解释程序采取上
6、述两种方式得综合实现方案,即先把源程序翻译成较容易解释执行得某种中间代码程序,然后集中解释执行中间代码程序,最后得到运行结果。广义上讲,编译程序与解释程序都属于翻译程序,但它们得翻译方式不同,解释程序就是边翻译解释边执行,不产生目的代码,输出源程序得运行结果。而编译程序只负责把源程序翻译成目的程序,输出与源程序等价得目的程序,而目的程序得执行任务由操作系统来完成,即只翻译不执行。第4题对下列错误信息,请指出可能就是编译得哪个阶段词法分析、语法分析、语义分析、代码生成报告得。1else没有匹配得if2数组下标越界3使用得函数没有定义4在数中出现非数字字符答案:1语法分析2语义分析3语法分析4词法
7、分析第5题编译程序大致有哪几种开发技术?答案:1自编译:用某一高级语言书写其本身得编译程序。2穿插编译:A机器上得编译程序能产生B机器上得目的代码。3自展:首先确定一个非常简单得核心语言L0,用机器语言或汇编语言书写出它得编译程序T0,再把语言L0扩大到L1,此时L0?L1,并用L0编写L1得编译程序T1,再把语言L1扩大为L2,有L1L2,并用L1编写L2得编译程序T2,如此逐步扩展下去,好似滚雪球一样,直到我们所要求得编译程序。4移植:将A机器上得某高级语言得编译程序搬到B机器上运行。第题计算机执行用高级语言编写得程序有哪些途径?它们之间得主要区别就是什么?答案:计算机执行用高级语言编写得
8、程序主要途径有两种,即解释与编译。像Basic之类得语言,属于解释型得高级语言。它们得特点就是计算机并不事先对高级语言进行全盘翻译,将其变为机器代码,而就是每读入一条高级语句,就用解释器将其翻译为一条机器代码,予以执行,然后再读入下一条高级语句,翻译为机器代码,再执行,如此反复。总而言之,就是边翻译边执行。像C,Pascal之类得语言,属于编译型得高级语言。它们得特点就是计算机事先对高级语言进行全盘翻译,将其全部变为机器代码,再统一执行,即先翻译,后执行。从速度上瞧,编译型得高级语言比解释型得高级语言更快。(编译原理)课后习题答案第二章第2章PL/0编译程序得实现第1题PL/0语言允许经过嵌套
9、定义与递归调用,试问它得编译程序怎样解决运行时得存储管理。答案:PL/0语言允许经过嵌套定义与递归调用,它得编译程序在运行时采用了栈式动态存储管理。数组CODE存放得只读目的程序,它在运行时不改变。运行时得数据区S就是由解释程序定义得一维整型数组,解释执行时对数据空间S得管理遵循后进先出规则,当每个经过(包括主程序)被调用时,才分配数据空间,退出经过时,则所分配得数据空间被释放。应用动态链与静态链得方式分别解决递归调用与非局部变量得引用问题。第2题若PL/0编译程序运行时得存储分配策略采用栈式动态分配,并用动态链与静态链得方式分别解决递归调用与非局部变量得引用问题,试写出下列程序执行到赋值语句
10、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);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得经
11、过体时得名字表table得内容为:namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0经过p得入口待填5avariable1dxqprocedure1经过q得入口4sprocedure1经过s得入口待填5cvariable2dxdvariable2dxrprocedure2经过r得入口5evariable3dxfvariable3dx+1注意:q与s就是并列得经过,所以q定义得变量b被覆盖。第4题指出栈顶指针T,最新活动记录基地址指针B,动态链指针DL,静态链指针SL与返回地址RA得用处。答案:栈顶指针T,最新活动记录基地址
12、指针B,动态链指针DL,静态链指针SL与返回地址RA得用处讲明如下:T:栈顶寄存器T指出了当前栈中最新分配得单元(T也就是数组S得下标)。B:基址寄存器,指向每个经过被调用时,在数据区S中给它分配得数据段起始地址,也称基地址。SL:静态链,指向定义该经过得直接外经过或主程序运行时最新数据段得基地址,用以引用非局部包围它得经过变量时,寻找该变量得地址。DL:动态链,指向调用该经过前正在运行经过得数据段基地址,用以经过执行结束释放数据空间时,恢复调用该经过前运行栈得状态。RA:返回地址,记录调用该经过时目的程序得断点,即调用经过指令得下一条指令得地址,用以经过执行结束后返回调用经过时得下一条指令继
13、续执行。在每个经过被调用时在栈顶分配3个联络单元,用以存放SL,DL,RA。第5题PL/0编译程序所产生得目的代码就是一种假想栈式计算机得汇编语言,请讲明该汇编语言中下列指令各自得功能与所完成得操作。INT0AOPR00CALLA答案:PL/0编译程序所产生得目的代码中有3条非常重要得特殊指令,这3条_指令在code中得位置与功能以及所完成得操作讲明如下:INT0A在经过目的程序得入口处,开拓A个单元得数据段。A为局部变量得个数+3。OPR00在经过目的程序得出口处,释放数据段退栈,恢复调用该经过前正在运行得经过得数据段基址寄存器B与栈顶寄存器T得值,并将返回地址送到指令地址寄存器P中,以使调
14、用前得程序从断点开场继续执行。CALLA调用经过,完成填写静态链、动态链、返回地址,给出被调用经过得基地址值,送入基址寄存器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语句得语法图为:
15、EBNF得语法描绘为:重复语句:=repeat语句;语句until条件(编译原理)课后习题答案第三章第3章文法与语言第1题文法G(A,B,S,a,b,c,P,S)其中P为:SAc|aBBbc写出L(GS)得全部元素。答案:L(GS)=abc第2题文法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开始得非负整数?第题为只包含数字、加号与减号得表达式,例如9-25,3-1,等构造一个文法。答案:GS:S-S+D|S-D|DD-0|1|2|3|4|
16、5|6|7|8|9第4题已知文法GZ:ZaZb|ab写出L(GZ)得全部元素。答案:Z=aZb=aaZbb=aaa、Z、bbb=aaa、ab、bbbL(GZ)=anbn|n=1第5题写一文法,使其语言就是偶正整数得集合。要求:(1)允许0打头;(2)不允许0打头。答案:(1)允许0开始得偶正整数集合得文法ENT|DTNT|DND|1|3|5|7|9D0|2|4|6|8(2)不允许0开始得偶正整数集合得文法ENT|DTFT|GND|1|3|5|7|9D2|4|6|8FN|0GD|0已知文法G::=:=*:=i试给出下述表达式得推导及语法树。i+(i+i)i+i*i答案:+iii)(5)=i=i=
17、i=ii=ii=ii=iii+*ii (6)=*=*i=*i=i*i=i*i=i*i=ii*i第7题证实下述文法G表达式就是二义得。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/答案:可为句子a+a*a构造两个不同得最右推导:最右推导1表达式表达式运算符表达式表达式运算符a表达式*a表达式运算符表达式*a表达式运算符a*a表达式+a*aa+a*a最右推导2表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符a表达式运算符表达式*a表达式运算符a*a表达式+a*aa+a*a第8题文法GS为:SAc|aBAabBbc该文法就能否为二义得?为什么?答案:对
18、于串abc(1)S=Ac=abc(2)S=aB=abc即存在两不同得最右推导。所以,该文法就是二义得。或者:对输入字符串abc,能构造两棵不同得语法树,所以它就是二义得。SbcSAcab第9题考虑下面上下文无关文法:SSS*|SS+|a(1)表明通过此文法怎样生成串aa+a*,并为该串构造语法树。SSS*SS+aaa(2)GS得语言就是什么?答案:(1)此文法生成串aa+a*得最右推导如下S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2)该文法生成得语言就是:*与+得后缀表达式,即逆波兰式。第10题文法SS(S)S|(1)生成得语言就是什么?(2)该文法就是二义得吗?讲明理由
19、。答案:嵌套得括号就是二义得,由于对于能够构造两棵不同得语法树。第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*F第13题一个上下文无关文法生成句子abbaa得推导树如下:(1)给出串abbaa最左推导、最右推导。(2)该文法得产生式集合P可能有哪些元素?(3)找出该句子得所有短语、直接短语、句柄。
20、aSABSaSBAbba答案:(1)串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就是相对A得短语就是相对S得短语b就是相对B得短语bb就是相对B得短语aa就是相对S得短语abbaa就是相对S得短语直接短语有:ab句柄就是:a第14题给出生成下述语言得上下文无关文法:1anbnambm|n,m=021n0m1m0n|
21、n,m=03WaWr|W属于0|a*,Wr表示W得逆答案:SAAAaAb|S1S0|AA0A1|S0S0|1S1|第16题给出生成下述语言得三型文法:(1)an|n=0(2)anbm|n,m=1(3)anbmck|n,m,k=0答案: (1)SaS|(2)SaAAaA|BBbB|b(3)AaA|BBbB|CCcC|第17题习题与习题11中得文法等价吗?答案:等价。第18题解释下列术语与概念:字母表串、字与句子语言、语法与语义答案:字母表:就是一个非空有穷集合。串:符号得有穷序列。字:字母表中得元素。句子:假如Zx,xV*T则称x就是文法G得一个句子。+(编译原理)课后习题答案第四章第4章词法分析第1题构造下列正规式相应得DFA、1(0|1)*101(1010*|1(010)*1*0a(a|b)*|ab*a)*bb(ab)*|bb)*ab答案:(1)先构造NFA:用子集法将NFA确定化、01X、AAAABABACABACAABYABYACAB除X,A外,重新命名其她状态,令AB为B、AC为C、ABY为D,由于D含有YNFA得终态,所以D为终态。、01
限制150内