編譯原理教程課后習(xí)題答案

編譯原理教程課后習(xí)題答案【篇一：編譯原理教程課后習(xí)題答案——第一章】完成下列選擇題：(1)構(gòu)造編譯程序應(yīng)掌握a.源程序b.目標(biāo)語言c.編譯方法d.以上三項(xiàng)都是(2)編譯程序絕大多數(shù)時(shí)間花在上。a.出錯(cuò)處理b.詞法分析c.目標(biāo)代碼生成d.表格管理(3)編譯程序是對。a.匯編程序的翻譯b.高級語言程序的解釋執(zhí)行c.機(jī)器語言的執(zhí)行d.高級語言的翻譯【解答】(1)d(2)d(3)d1.2計(jì)算機(jī)執(zhí)行用高級語言編寫的程序有哪些途徑？它們之間的主要區(qū)別是什么？【解答】計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。在解釋方式下，翻譯程序事先并不采用將高級語言程序全部翻譯成機(jī)器代碼程序，然后執(zhí)行這個(gè)機(jī)器代碼程序的方法，而是每讀入一條源程序的語句，就將其解釋(翻譯)成對應(yīng)其功能的機(jī)器代碼語句串并執(zhí)行，而所翻譯的機(jī)器代碼語句串在該語句執(zhí)行后并不保留，最后再讀入下一條源程序語句，并解釋執(zhí)行。這種方法是按源程序中語句的動(dòng)態(tài)執(zhí)行順序逐句解釋(翻譯)執(zhí)行的，如果一語句處于一循環(huán)體中，則每次循環(huán)執(zhí)行到該語句時(shí)，都要將其翻譯成機(jī)器代碼后再執(zhí)行。在編譯方式下，高級語言程序的執(zhí)行是分兩步進(jìn)行的：第一步首先將高級語言程序全部翻譯成機(jī)器代碼程序，第二步才是執(zhí)行這個(gè)機(jī)器代碼程序。因此，編譯對源程序的處理是先翻譯，后執(zhí)行。從執(zhí)行速度上看，編譯型的高級語言比解釋型的高級語言要快，但解釋方式下的人機(jī)界面比編譯型好，便于程序調(diào)試。這兩種途徑的主要區(qū)別在于：解釋方式下不生成目標(biāo)代碼程序，而編譯方式下生成目標(biāo)代碼程序。1.3請畫出編譯程序的總框圖。如果你是一個(gè)編譯程序的總設(shè)計(jì)師，設(shè)計(jì)編譯程序時(shí)應(yīng)當(dāng)考慮哪些問題？【解答】編譯程序總框圖如圖1-1所示。作為一個(gè)編譯程序的總設(shè)計(jì)師，首先要深刻理解被編譯的源語言其語法及語義；其次，要充分掌握目標(biāo)指令的功能及特點(diǎn)，如果目標(biāo)語言是機(jī)器指令，還要搞清楚機(jī)器的硬件結(jié)構(gòu)以及操作系統(tǒng)的功能；第三，對編譯的方法及使用的軟件工具也必須準(zhǔn)確化?？傊傇O(shè)計(jì)師在設(shè)計(jì)編譯程序時(shí)必須估量系統(tǒng)功能要求、硬件設(shè)備及軟件工具等諸因素對編譯程序構(gòu)造的影響等。程序子程序或分程序語句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用【篇二：編譯原理教程課后習(xí)題答案——第四章】txt>4.1完成下列選擇題：(1)四元式之間的聯(lián)系是通過實(shí)現(xiàn)的。a.指示器b.臨時(shí)變量c.符號表d.程序變量(2)間接三元式表示法的優(yōu)點(diǎn)為。a.采用間接碼表，便于優(yōu)化處理b.節(jié)省存儲空間，不便于表的修改c.便于優(yōu)化處理，節(jié)省存儲空間d.節(jié)省存儲空間，不便于優(yōu)化處理(3)表達(dá)式(┐a∨b)∧(c∨d)的逆波蘭表示為a.┐ab∨∧cd∨b.a┐b∨cd∨∧c.ab∨┐cd∨∧d.a┐b∨∧cd∨(4)有一語法制導(dǎo)翻譯如下所示：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何謂“語法制導(dǎo)翻譯”？試給出用語法制導(dǎo)翻譯生成中間代碼的要點(diǎn)，并用一簡例予以說明?！窘獯稹空Z法制導(dǎo)翻譯(sdts)直觀上說就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序(稱語義動(dòng)作或語義子程序)，并且在語法分析的同時(shí)執(zhí)行這些子程序。也即在語法分析過程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配(對于自上而下分析)或用于歸約(對于自下而上分析)時(shí)，此產(chǎn)生式相應(yīng)的語義子程序進(jìn)入工作，完成既定的翻譯任務(wù)。用語法制導(dǎo)翻譯(sdts)生成中間代碼的要點(diǎn)如下：(1)按語法成分的實(shí)際處理順序生成，即按語義要求生成中間代碼。(2)注意地址返填問題。(3)不要遺漏必要的處理，如無條件跳轉(zhuǎn)等。例如下面的程序段：if(i0)a=i+e-b*d;elsea=0;在生成中間代碼時(shí)，條件“i0”為假的轉(zhuǎn)移地址無法確定，而要等到處理“else”時(shí)方可確定，這時(shí)就存在一個(gè)地址返填問題。此外，按語義要求，當(dāng)處理完(i0)后的語句(即“i0”為真時(shí)執(zhí)行的語句)時(shí)，則應(yīng)轉(zhuǎn)出當(dāng)前的if語句，也即此時(shí)應(yīng)加入一條無條件跳轉(zhuǎn)指令，并且這個(gè)轉(zhuǎn)移地址也需要待處理完else之后的語句后方可獲得，就是說同樣存在著地址返填問題。對于賦值語句a=i+e-b*d，其處理順序(也即生成中間代碼順序)是先生成i+e的代碼，再生成b*d的中間代碼，最后才產(chǎn)生“-”運(yùn)算的中間代碼，這種順序不能顛倒。4.3令s.val為文法g[s]生成的二進(jìn)制數(shù)的值，例如對輸入串101.101，則s.val=5.625。按照語法制導(dǎo)翻譯方法的思想，給出計(jì)算s.val的相應(yīng)的語義規(guī)則，g(s)如下：g[s]:s→l.l|ll→lb|bb→0|1【解答】計(jì)算s.val的文法g′[s]及語義動(dòng)作如下：產(chǎn)生式語義動(dòng)作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試構(gòu)造一個(gè)翻譯方案，僅使用綜合屬性，把每個(gè)標(biāo)識符的類型填入符號表中(對所用到的過程，僅說明功能即可，不必具體寫出)。【解答】此題只需要對說明語句進(jìn)行語義分析而不需要產(chǎn)生代碼，但要求把每個(gè)標(biāo)識符的類型填入符號表中。對d、l、t，為其設(shè)置綜合屬性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;}過程調(diào)用語句的語義子程序。在所生成的四元式序列中，要求在轉(zhuǎn)子指令之前的參數(shù)四元式par按反序出現(xiàn)(與實(shí)現(xiàn)參數(shù)的順序相反)。此時(shí)，在翻譯過程調(diào)用語句時(shí)，是否需要語義變量(隊(duì)列)queue？【解答】為使過程調(diào)用語句的語義子程序產(chǎn)生的參數(shù)四元式par按反序方式出現(xiàn)，過程調(diào)用語句的文法為s→calli(arglist)arglist→earglist→arglist(1),e按照該文法，語法制導(dǎo)翻譯程序不需要語義變量隊(duì)列queue，但需要一個(gè)語義變量棧stack，用來實(shí)現(xiàn)按反序記錄每個(gè)實(shí)在參數(shù)的地址。翻譯過程調(diào)用語句的產(chǎn)生式及語義子程序如下：(1)arglist→e{建立一個(gè)arglist.stack棧，它僅包含一項(xiàng)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棧頂項(xiàng)彈出并送入p單元之中；emit(par,_,_,p);end;emit(call,_,_,entry(i));}4.6設(shè)某語言的while語句的語法形式為s→whileedos(1)其語義解釋如圖4-1所示。(1)寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2)寫出每個(gè)產(chǎn)生式對應(yīng)的語義動(dòng)作。假圖4-1習(xí)題4.6的語句結(jié)構(gòu)圖【解答】本題的語義解釋圖已經(jīng)給出了翻譯后的中間代碼結(jié)構(gòu)。在語法制導(dǎo)翻譯過程中，當(dāng)掃描到while時(shí)，應(yīng)記住e的代碼地址；當(dāng)掃描到do時(shí)，應(yīng)對e的“真出口”進(jìn)行回填，使之轉(zhuǎn)到s(1)代碼的入口處；當(dāng)掃描到s(1)時(shí)，除了應(yīng)將e的入口地址傳給s(1).chain之外，還要形成一個(gè)轉(zhuǎn)向e入口處的無條件轉(zhuǎn)移的四元式，并且將e.fc繼續(xù)傳下去。因此，應(yīng)把s→whileedos(1)改寫為如下的三個(gè)產(chǎn)生式：w→whilea→wedos→as(1)每個(gè)產(chǎn)生式對應(yīng)的語義子程序如下：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改寫布爾表達(dá)式的語義子程序，使得i(1)ropi(2)不按通常方式翻譯為下面的相繼兩個(gè)四元式：(jrop,i(1),i(2),0)(j,__,__,0)而是翻譯成如下的一個(gè)四元式：(jop,i(1),i(2),0)使得當(dāng)i(1)ropi(2)為假時(shí)發(fā)生轉(zhuǎn)移，而為真時(shí)并不發(fā)生轉(zhuǎn)移(即順序執(zhí)行下一個(gè)四元式)，從而產(chǎn)生效率較高的四元式代碼?！窘獯稹堪匆蟾脑烀枋霾紶柋磉_(dá)式的語義子程序如下：(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表示關(guān)系運(yùn)算符與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按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while(ac∧bd){if(a≥1)c=c+1;elsewhile(a≤d)a=a+2;}【解答】該語句的四元式序列如下(其中e1、e2和e3分別對應(yīng)a＜c∧b＜d、a≥1和a≤d，并且關(guān)系運(yùn)算符優(yōu)先級高)：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)/*轉(zhuǎn)回內(nèi)層while語句開始處*/112(j,_,_,100)/*轉(zhuǎn)回外層while語句開始處*/1134.9已知源程序如下：prod=0;i=1;while(i≤20){prod=prod+a[i]*b[i];i=i+1;}試按語法制導(dǎo)翻譯法將上述源程序翻譯成四元式序列(設(shè)a是數(shù)組a的起始地址，b是數(shù)組b的起始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié))?！窘獯稹吭闯绦蚍g為下列四元式序列：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)請證實(shí)aacabcbaadbed是文法g[s]的一個(gè)句型；(2)請寫出該句型的所有短語、素短語以及句柄；(3)為文法g[s]的每個(gè)產(chǎn)生式寫出相應(yīng)的翻譯子程序，使句型aacabcbaadbed經(jīng)該翻譯方案后，輸出為131042521430?！窘獯稹?1)根據(jù)文法g[s]畫出aacabcbaadbed對應(yīng)的語法樹如圖4-2所示。由圖4-2可知aacabcbaadbed是文法g[s]的一個(gè)句型。ssaaabcsdaabb圖4-2aacabcbaadbed對應(yīng)的語法樹abbecsabsada【篇三：編譯原理及實(shí)踐教程(黃賢英王柯柯編著)習(xí)題答案】，2，3：解答：略！4.解答：a：①b：③c：①d：②5.解答：用e表示表達(dá)式，t表示項(xiàng)，f表示因子，上述文法可以寫為：e→t|e+tt→f|t*ff→(e)|i最左推導(dǎo)：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最右推導(dǎo)：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)終結(jié)符號為：{or,and,not,(,),true,false}非終結(jié)符號為：{bexpr,bterm,bfactor}開始符號為：bexpr(2)句子not(trueorfalse)的語法樹為：7.解答：(1)把a(bǔ)nbnci分成anbn和ci兩部分，分別由兩個(gè)非終結(jié)符號生成，因此，生成此文法的產(chǎn)生式為：s→aba→aab|abb→cb|?(2)令s為開始符號，產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè)，令e為一個(gè)非終結(jié)符號，產(chǎn)生含相同個(gè)數(shù)的a和b的所有串，則產(chǎn)生式如下：s→ae|ea|bss|sbs|ssbe→aebe|beae|?(3)設(shè)文法開始符號為s，產(chǎn)生的w中滿足|a|≤|b|≤2|a|。因此，可想到s有如下的產(chǎn)生式（其中b產(chǎn)生1到2個(gè)b）：s→asbs|bsasb→b|bb(4)解法一：s→〈奇數(shù)頭〉〈整數(shù)〉〈奇數(shù)尾〉|〈奇數(shù)頭〉〈奇數(shù)尾〉|〈奇數(shù)尾〉〈奇數(shù)尾〉→1|3|5|7|9〈奇數(shù)頭〉→2|4|6|8|〈奇數(shù)尾〉〈整數(shù)〉→〈整數(shù)〉〈數(shù)字〉|〈數(shù)字〉〈數(shù)字〉→0|〈奇數(shù)頭〉解法二：文法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有如下兩個(gè)不同的最左推導(dǎo)：s=asbs=abs=abasbs=ababs=ababs=asbs=absasbs=abasbs=ababs=abab所以此文法是二義性的。(2)句子abab的兩個(gè)相應(yīng)的最右推導(dǎo)：s=asbs=asbasbs=asbasb=asbab=ababs=asbs=asb=absasb=absab=abab(3)句子abab的兩棵分析樹：(a)(b)(4)此文法產(chǎn)生的語言是：在{a，b}上由相同個(gè)數(shù)的a和b組成的字符串。9，10：解答：略！第3章習(xí)題解答：1.解答：*它所接受的語言可以用正則表達(dá)式表示為00(0|1)，表示的含義為由兩個(gè)0開始的后跟任意個(gè)（包含0個(gè)）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)[分析]設(shè)s是符合要求的串，|s|=2k+1(k≥0）。則s→s10|s21，|s1|=2k(k0），|s2|=2k(k≥0）。且s1是{0,1}上的串，含有奇數(shù)個(gè)0和奇數(shù)個(gè)1。s2是{0,1}上的串，含有偶數(shù)個(gè)0和偶數(shù)個(gè)1。考慮有一個(gè)自動(dòng)機(jī)m1接受s1，那么自動(dòng)機(jī)m1如下：和l(m1)等價(jià)的正規(guī)式