編譯原理期末復(fù)習(xí)必看習(xí)題

1、第一章1. 什么是編譯程序編譯程序？什么是解釋程序解釋程序？二者的區(qū)別區(qū)別？l1、編譯程序：l是一種翻譯程序，它特指把某種高級程序設(shè)計(jì)語言翻譯成具體計(jì)算機(jī)上的低級程序設(shè)計(jì)語言。l2、解釋程序：l解釋程序(interpreter)也是一種翻譯程序，將某高級語翻譯成具體計(jì)算機(jī)上的低級程序設(shè)計(jì)語言.l兩者區(qū)別：l（1）前者有目標(biāo)程序而后者無目標(biāo)程序；l（2）前者運(yùn)行效率高而后者便于人機(jī)對話2、敘述編譯程序的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)和實(shí)現(xiàn)機(jī)制實(shí)現(xiàn)機(jī)制根據(jù)語言和環(huán)境的不同，編譯程序?qū)崿F(xiàn)時(shí)是把 圖中的各階段劃分成若干遍；典型的情況是兩遍的編譯程序： 第一遍 :詞法分析 、語法分析和語義分析。即前端完成分析，一般與

2、機(jī)器無關(guān)。 第二遍 :目標(biāo)代碼生成和目標(biāo)代碼優(yōu)化。即后端完成綜合，一般與機(jī)器有關(guān)。 每遍中的各階段的工作是穿插進(jìn)行的，例如：使語法分析器處于核心位置,而把詞法分析器作為子程序；當(dāng)語法分析需要下一個(gè)單詞時(shí)，就調(diào)用詞法分析器，識別一個(gè)單詞。詞法詞法分析分析語法語法分析分析語義語義分析分析代 碼代 碼生成生成源源語語言言目目標(biāo)標(biāo)語語言言 錯(cuò)錯(cuò) 誤誤 處處 理理 符符 號號 表表 管管 理理優(yōu)化優(yōu)化處理處理1、P36:8 ; i+i*i最左E-E+T-T+T-F+T-i+T-i+T*F-i+F*F-i+i*F-i+i*ii+i*i最右E-E+T-E+T*F-E+T*i-E+F*i-E+i*i-T+i*

3、i-F+i*i-i+i*ii*(i+i)最左E-T-T*F-F*F-i*F-i*(E)-i*(E+T)-i*(T+T)-i*(F+T)-i*(i+T)-i*(i+F)-i*(i+i)i*(i+i)最右E-T-T*F-T*(E)-T*(E+T)-T*(E+F)-T*(E+i)-T*(T+i)-T*(F+i)-T*(i+i)-F*(i+i)-i*(i+i)2、試構(gòu)造下述語言L的文法： L= ambn |m0,n1; S - AB A - Aa | B - Bb | bor S - AB A - aA | B - bB | b3、試求下述文法G(Z)所定義的語言： G(Z): Z-b|bB , B-

4、bZZ = bZ = bB = bbZ = bbbZ = bB = bbZ = bbbB = bbbbZ = bbbbbZ = b2n-1 , n11.P64，8(1),(3)給出正規(guī)表達(dá)式：以01結(jié)尾的二進(jìn)制數(shù)串分析題意，要求的是二進(jìn)制小，即由0和1構(gòu)成的串，并且必須以01結(jié)尾，所以本題可以分兩部分去完成，一部分實(shí)現(xiàn)由0和1構(gòu)成的任意串，一部分即01，然后將它們連接到一起就可以了，所以本題的解答是:(0|1)*01。（3）包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制數(shù)串。本題求二進(jìn)制串，并且要求包含奇數(shù)個(gè)0或奇數(shù)個(gè)1，由于0和1都可以在二進(jìn)制串中任何地方出現(xiàn)，所以本題只需要考慮一種情況，另外一種情況也可以

5、類似求得?？紤]包含奇數(shù)個(gè)0的字符串:由于只關(guān)心0的個(gè)數(shù)的奇偶數(shù)，我們可以把二進(jìn)制串分成多段來考慮，第1段為二進(jìn)制串的開始到第1個(gè)0為止，這一段包含1個(gè)0，并且0的前面有0個(gè)或多個(gè)1，對于剩下的二進(jìn)制串按照每段包含兩個(gè)0的方式去劃分，即以0開始，以0結(jié)尾，中間可以有0個(gè)或多個(gè)1，和果一個(gè)二進(jìn)制串被這樣劃分完后，剩下的部分如果全部是全1串(這些全1串在前面劃分的串之間或最后)，則該二進(jìn)制串就具有奇數(shù)個(gè)0，所以該二進(jìn)制串可以這樣描述:以第1段(1*0)開始，后面由全1串(1*)以及包含兩個(gè)0的串(01*0)組成，所以包含奇數(shù)個(gè)0的正規(guī)表達(dá)式為:1*0(1|01*0)*，本題的解答則是:1*0(1|0

6、1*0)*|0*1(0|10*1)*。2.給定正規(guī)式(a|b)*a(a|b)，構(gòu)造其最小DFA M。(參見書圖 3.7)首先將其分為終態(tài)集3,4和非終態(tài)集0,1,2，由于0 a=1，0b=2，2a=1，2b=2都是集合0,1,2的子集，但1a=3，1b=4，屬于3,4的子集，故將其劃分為0,2，1。對3、4也是如此，即最后劃分為：0,2、1、3、4，按順序重新命名為1、2、3、4。(見書p57頁)1. 考慮下面文法G1:S-a|(T),T-T,S|S (1)消去G1的左遞歸。（書上p69）（2）改寫后的文法是否為LL(1)文法？(書P73) 給出預(yù)測分析表(書P76)。（1）消除左遞歸: S-

7、a|(T) T- ST T-,S T|（2）FIRST(S)= a , , ( FIRST(T)= a , , ( FIRST(T)= , First(a)=a,First()=,First( (T) )= ( S的所有候選的首符集不相交 (First 和 Follow集的構(gòu)造方法見書P78)First(,ST)=, ,First()=, T的所有候選的首符集不相交Follow(T)=Follow(T)= ) Follow(S)=) , #first(T)Follow(T)= a(),#SSaSS(T) TTSTTSTTST T T T ,ST 2.P82，第4題。 對文法S -S S (S)

8、|AB B -S| A aC C (S)|(1)構(gòu)造LL(1)分析表(2)給出對句子a-a(a)的分析過程。 (1)First(S)=- ( aFirst(A)=aFirst(B)=- First(C)=( Follow(S)=) #Follow(B)=) #Follow(A)=- ) #Follow(C)=- ) #LL(1)分析表-a()#SS-SS-ABS-(S)BB-SB-B-AA-aCCC-C-(S)C-C-步驟符號棧輸入串所用產(chǎn)生式0#Sa-a(a)#1#BAa-a(a)#S-AB2#BCaa-a(a)#A-aC3#BC-a(a)#4#B-a(a)#C-5#S-a(a)#B-S6#

9、S-a(a)#7#S-a(a)#S-S8#Sa(a)#9#BAa(a)#S-AB10#BCaa(a)#A-aC11#BC(a)#12#B)S(a)#C-(S)13#B)S(a)#14#B)S(a)#15#B)Sa)#16#B)BAa)#S-AB17#B)BCaa)#A-aC18#B)BC)#19#B)B)#C-20#B)#B-21#B)#22#B#23#B-P133.1令文法G1為：E-E+T | TT-T*F | FF-(E) | I證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語，直接短語和句柄答案：因?yàn)镋=E+T=E+T*F所以E+T*F是該文法的一個(gè)句型。短語:E+T*F, T*F

10、,直接短語:T*F句柄:T*F第五章P133.3S-a | | (T)T-T, S | S(1)計(jì)算FIRSTVT和LASTVT.(2)計(jì)算優(yōu)先關(guān)系。以上文法是一個(gè)優(yōu)先文法嗎？(3)給出輸入串(a,(a,a)的算符優(yōu)先分析過程。答案：(1)FIRSTVT(S)=a (FIRSTVT(T)=, A (LASTVT(S)=A )LASTVT(T)=, A )(2) a(),a ( = , (3)第七章1.給出下面表達(dá)式的逆波蘭表示a*(-b+c)ab-c+*a+b*(c+d/e)abcde/+*+2.請將表達(dá)式-(a+b)*(c+d)-(a+b+c)分別表示成三元式、間接三元式和四元式序列。三元式

11、序列：(1) (+,a,b）(2) (,(1),-)(3) (+,c,d)(4) (*,(2),(3)(5) (+,a,b)(6) (+,(5),c)(7) (-,(5),(6)三元式表 間接碼表(1) (+,a,b)(1)(2) (,(1),-)(2)(3) (+,c,d)(3)(4) (*,(2),(3)(4)(5) (+,(1),c)(1)(6) (-,(4),(5)(5)(6)四元式序列：(1)（+,a,b,T1）(2) (,T1,-,T2)(3) (+,c,d,T3)(4) (*,T2,T3,T4)(5) (+,a,b,T5)(6) (+,T5,c,T6)(7) (-,T4,T6,T

12、7)P218.4:寫出下面賦值語句：A:=B*(-C+D)的三地址代碼。答案：T1:=-CT2:=T1+DT3:=B*T2A:=T3P218.6寫出布什爾A or (B and not (C or D) ) 的四元式序列(1)(jnz,A,-,0)(2)(j,-,-,3)(3)(jnz,B,-,5)(4)(j,-,-,0)(5)(jnz,c,-,4)(6)(j,-,-,7)(7)(jnz,d,-,5)(8)(j,-,-,1) 最后E.turelist=1,8,E.falelish=4,5,7 P218.7 :把下面的語句翻譯成四元式序列：While AC and BD doIf A=1 the

13、n C:=C+1 elsewhile A=D do A:=A+2;.(1)(j,A,C,3)(2)(j,-,-,16)(3)(j,B,D,5)(4)(j,-,-,16)(5)(j=,A,1,7)(6)(j,-,-,10)(7)(+,C,1,T1)(8)(:=,T1,-,C)(9)(j,-,-,1)(10)(j=,A,D,12)(11)(j,-,-,1)(12)(+,A,2,T2)(13)(:=,T2,-,A)(14)(j,-,-,10)(15)(j,-,-,1)(16)第十章P306.3 :試對以下基本塊B1和B2：B1：B2:A:=B*CB:=3D:=B/CD:=A+CE:=A+DE:=A*CF:=2*EF:=D+EG:=B*CG:=B*FH:=G*GH:=A*CF:=H*GI:=A*CL:=FJ:=H+IM:=LK:=B*5L:=K+JM:=L分別應(yīng)用DAG對他們進(jìn)行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四元式序列。（1）假設(shè)只有G,L,M在基本塊后面還要被引用。（2）假設(shè)只有L在基本塊后面還要被引用。P306.3