编译原理教程课后习题答案

编译原理教程课后习题答案【篇一：编译原理教程课后习题答案——第一章】完成下列选择题：(1)构造编译程序应掌握a.源程序b.目标语言c.编译方法d.以上三项都是(2)编译程序绝大多数时间花在上。a.出错处理b.词法分析c.目标代码生成d.表格管理(3)编译程序是对。a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译【解答】(1)d(2)d(3)d1.2计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。1.3请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。程序子程序或分程序语句表达式数据引用算符函数调用【篇二：编译原理教程课后习题答案——第四章】txt>4.1完成下列选择题：(1)四元式之间的联系是通过实现的。a.指示器b.临时变量c.符号表d.程序变量(2)间接三元式表示法的优点为。a.采用间接码表，便于优化处理b.节省存储空间，不便于表的修改c.便于优化处理，节省存储空间d.节省存储空间，不便于优化处理(3)表达式(┐a∨b)∧(c∨d)的逆波兰表示为a.┐ab∨∧cd∨b.a┐b∨cd∨∧c.ab∨┐cd∨∧d.a┐b∨∧cd∨(4)有一语法制导翻译如下所示：s→bab{print″1″}a→(b{print″2″}a→a{print″3″}b→aa){print″4″}若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为a.32224441b.34242421c.12424243d.34442212【解答】(1)b(2)a(3)b(4)b4.2何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。【解答】语法制导翻译(sdts)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。用语法制导翻译(sdts)生成中间代码的要点如下：(1)按语法成分的实际处理顺序生成，即按语义要求生成中间代码。(2)注意地址返填问题。(3)不要遗漏必要的处理，如无条件跳转等。例如下面的程序段：if(i0)a=i+e-b*d;elsea=0;在生成中间代码时，条件“i0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i0)后的语句(即“i0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。4.3令s.val为文法g[s]生成的二进制数的值，例如对输入串101.101，则s.val=5.625。按照语法制导翻译方法的思想，给出计算s.val的相应的语义规则，g(s)如下：g[s]:s→l.l|ll→lb|bb→0|1【解答】计算s.val的文法g′[s]及语义动作如下：产生式语义动作g′[s]：s′→s{print(s.val)}s→l{s.val:=l.val}l→l1b{l.val:=l1.val*2+b.vall.length:=l1.length+1}l→b{l.val:=b.vall.length:=2}b→1{b.val:=1}b→0{b.val:=0}4.4下面的文法生成变量的类型说明：d→idll→,idl|:tt→integer|real试构造一个翻译方案，仅使用综合属性，把每个标识符的类型填入符号表中(对所用到的过程，仅说明功能即可，不必具体写出)。【解答】此题只需要对说明语句进行语义分析而不需要产生代码，但要求把每个标识符的类型填入符号表中。对d、l、t，为其设置综合属性type，而过程enter(name,type)用来把名字name填入到符号表中，并且给出此名字的类型type。翻译方案如下：d→idl{enter(,l.type);}l→,idl(1){enter(,l(1).type);l.type=l(1).type;}l→:t{l.type=t.type;}t→integer{t.type=integer;}t→real{t.type=real;}过程调用语句的语义子程序。在所生成的四元式序列中，要求在转子指令之前的参数四元式par按反序出现(与实现参数的顺序相反)。此时，在翻译过程调用语句时，是否需要语义变量(队列)queue？【解答】为使过程调用语句的语义子程序产生的参数四元式par按反序方式出现，过程调用语句的文法为s→calli(arglist)arglist→earglist→arglist(1),e按照该文法，语法制导翻译程序不需要语义变量队列queue，但需要一个语义变量栈stack，用来实现按反序记录每个实在参数的地址。翻译过程调用语句的产生式及语义子程序如下：(1)arglist→e{建立一个arglist.stack栈，它仅包含一项e.place}(2)arglist→arglist(1)，e{将e.place压入arglist(1).stack栈，arglist.stack=arglist(1).stack}(3)s→calli(arglist){whilearglist.stack≠nulldobegin将arglist.stack栈顶项弹出并送入p单元之中；emit(par,_,_,p);end;emit(call,_,_,entry(i));}4.6设某语言的while语句的语法形式为s→whileedos(1)其语义解释如图4-1所示。(1)写出适合语法制导翻译的产生式；(2)写出每个产生式对应的语义动作。假图4-1习题4.6的语句结构图【解答】本题的语义解释图已经给出了翻译后的中间代码结构。在语法制导翻译过程中，当扫描到while时，应记住e的代码地址；当扫描到do时，应对e的“真出口”进行回填，使之转到s(1)代码的入口处；当扫描到s(1)时，除了应将e的入口地址传给s(1).chain之外，还要形成一个转向e入口处的无条件转移的四元式，并且将e.fc继续传下去。因此，应把s→whileedos(1)改写为如下的三个产生式：w→whilea→wedos→as(1)每个产生式对应的语义子程序如下：w→while{w.quad=nxq;}a→wedo{backpatch(e.tc,nxq);a.chain=e.fc;a.quad=w.quad;}s→as(1){backpatch(s(1).chain,a.quad);emit(j,_,_,a.quad);s.chain=a.chain;}4.7改写布尔表达式的语义子程序，使得i(1)ropi(2)不按通常方式翻译为下面的相继两个四元式：(jrop,i(1),i(2),0)(j,__,__,0)而是翻译成如下的一个四元式：(jop,i(1),i(2),0)使得当i(1)ropi(2)为假时发生转移，而为真时并不发生转移(即顺序执行下一个四元式)，从而产生效率较高的四元式代码。【解答】按要求改造描述布尔表达式的语义子程序如下：(1)e→i{e.tc=null;e.fc=nxq;emit(jez,entry(i),__,0);}(2)e→i(1)ropi(2){e.tc=null;e.fc=nxq;emit(jop,entry(i(1)),entry(i(2));)/*op表示关系运算符与rop相反*/(3)e→(e(1)){e.tc=e(1).tc;e.fc=e(1).fc;}(4)e→┐e(1){e.fc=nxq;emit(j,__,__,0);backpatch(e(1).fc,nxq);}(5)ea→e(1)∧{ea.fc=e(1).fc;}(6)e→eae(2){e.tc=e(2).tc;e.fc=merg(ea.fc,e(2).fc);}(7)e0→e(1)∨{e0.tc=nxq;emit(j,__,__,0);backpatch(e(1).fc,nxq);}(8)e→e0e(2){e.fc=e(2).fc;backpatch(e0.tc,nxq);}4.8按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(ac∧bd){if(a≥1)c=c+1;elsewhile(a≤d)a=a+2;}【解答】该语句的四元式序列如下(其中e1、e2和e3分别对应a＜c∧b＜d、a≥1和a≤d，并且关系运算符优先级高)：100(j,a,c,102)101(j,_,_,113)/*e1为f*/102(j,b,d,104)/*e1为t*/103(j,_,_,113)/*e1为f*/104(j=,a,1,106)/*e2为t*/105(j,_,_,108)/*e2为f*/106(+,c,1,c)/*c:=c+1*/107(j,_,_,112)/*跳过else后的语句*/108(j≤,a,d,110)/*e3为t*/109(j,_,_,112)/*e3为f*/110(+,a,2,a)/*a:=a+2*/111(j,_,_,108)/*转回内层while语句开始处*/112(j,_,_,100)/*转回外层while语句开始处*/1134.9已知源程序如下：prod=0;i=1;while(i≤20){prod=prod+a[i]*b[i];i=i+1;}试按语法制导翻译法将上述源程序翻译成四元式序列(设a是数组a的起始地址，b是数组b的起始地址；机器按字节编址，每个数组元素占四个字节)。【解答】源程序翻译为下列四元式序列：100(=,0,_,prod)101(=,1,_,i)102(j≤,i,20,104)103(j,_,_,114)104(*,4,i,t1)105(-,a,4,t2)106(=[],t2,t1,t3)107(*,4,i,t4)108(-,b,4,t5)109(=[],t5,t4,t6)110(*,t3,t6,t7)111(+,prod,t7,prod)112(+,i,1,i)113(j,_,_,102)1144.10给出文法g[s]:s→saa|aa→abb|bb→csd|e(1)请证实aacabcbaadbed是文法g[s]的一个句型；(2)请写出该句型的所有短语、素短语以及句柄；(3)为文法g[s]的每个产生式写出相应的翻译子程序，使句型aacabcbaadbed经该翻译方案后，输出为131042521430。【解答】(1)根据文法g[s]画出aacabcbaadbed对应的语法树如图4-2所示。由图4-2可知aacabcbaadbed是文法g[s]的一个句型。ssaaabcsdaabb图4-2aacabcbaadbed对应的语法树abbecsabsada【篇三：编译原理及实践教程(黄贤英王柯柯编著)习题答案】，2，3：解答：略！4.解答：a：①b：③c：①d：②5.解答：用e表示表达式，t表示项，f表示因子，上述文法可以写为：e→t|e+tt→f|t*ff→(e)|i最左推导：e=e+t=e+t+t=t+t+t=f+t+t=i+t+t=i+f+t=i+i+t=i+i+f=i+i+ie=e+t=t+t=f+t=i+t=i+t*f=i+f*f=i+i*f=i+i*i最右推导：e=e+t=e+f=e+i=e+t+i=e+f+i=e+i+i=t+i+i=f+i+i=i+i+ie=e+t=e+t*f=e+t*i=e+f*i=e+i*i=t+i*i=f+i*i=i+i*ii+i+i和i+i*i的语法树如下图所示。i+i+i、i+i*i的语法树6.解答：(1)终结符号为：{or,and,not,(,),true,false}非终结符号为：{bexpr,bterm,bfactor}开始符号为：bexpr(2)句子not(trueorfalse)的语法树为：7.解答：(1)把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：s→aba→aab|abb→cb|?(2)令s为开始符号，产生的w中a的个数恰好比b多一个，令e为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：s→ae|ea|bss|sbs|ssbe→aebe|beae|?(3)设文法开始符号为s，产生的w中满足|a|≤|b|≤2|a|。因此，可想到s有如下的产生式（其中b产生1到2个b）：s→asbs|bsasb→b|bb(4)解法一：s→〈奇数头〉〈整数〉〈奇数尾〉|〈奇数头〉〈奇数尾〉|〈奇数尾〉〈奇数尾〉→1|3|5|7|9〈奇数头〉→2|4|6|8|〈奇数尾〉〈整数〉→〈整数〉〈数字〉|〈数字〉〈数字〉→0|〈奇数头〉解法二：文法g=({s,a,b,c,d},{0,1,2,3,4,5,6,7,8,9},p,s)s→ab|ba→ac|db→1|3|5|7|9d→2|4|6|8|bc→0|d(5)文法g=({n,s,n,m,d},{0,1,2,3,4,5,6,7,8,9},s,p)s→n0|n5n→md|?m→1|2|3|4|5|6|7|8|9d→d0|dm|?(6)g[s]：s→asa|bsb|csc|a|b|c|?8.解答：(1)句子abab有如下两个不同的最左推导：s=asbs=abs=abasbs=ababs=ababs=asbs=absasbs=abasbs=ababs=abab所以此文法是二义性的。(2)句子abab的两个相应的最右推导：s=asbs=asbasbs=asbasb=asbab=ababs=asbs=asb=absasb=absab=abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串。9，10：解答：略！第3章习题解答：1.解答：*它所接受的语言可以用正则表达式表示为00(0|1)，表示的含义为由两个0开始的后跟任意个（包含0个）0或1组成的符号串的集合。2.解答：a:④b:③c:②d:②e:④3，4．解答：略！5．解答：6．解答：(1)(0|1)*01(2)((1|2|…|9)(0|1|2|…|9)*|?)(0|5)(3)(0|1)*(011)(0|1)*(4)1*|1*0(0|10)*(1|?)(5)a*b*c*…z*(6)(0|10*1)*1(7)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*(8)[分析]设s是符合要求的串，|s|=2k+1(k≥0）。则s→s10|s21，|s1|=2k(k0），|s2|=2k(k≥0）。且s1是{0,1}上的串，含有奇数个0和奇数个1。s2是{0,1}上的串，含有偶数个0和偶数个1。考虑有一个自动机m1接受s1，那么自动机m1如下：和l(m1)等价的正规式