2021年編譯原理題庫

第一章什么是編譯器？編譯程序構(gòu)造分為幾種階段，各階段任務是什么？遍、編譯前端及編譯后端含義？編譯程序生成方式有哪些？第二章1.寫一文法，使其語言是偶正整數(shù)集合。規(guī)定：（1）容許0打頭（2）

不容許0打頭解：（1）容許0開頭偶正整數(shù)集合文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8（2）不容許0開頭偶正整數(shù)集合文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|02.證明下述文法G［〈表達式〉］是二義?！幢磉_式〉∷=a|(〈表達式〉)|〈表達式〉〈運算符〉〈表達式〉〈運算符〉∷=+|-|*|/解：可為句子a+a*a構(gòu)造兩個不同最右推導：最右推導1〈表達式〉T〈表達式〉〈運算符〉〈表達式〉T〈表達式〉〈運算符〉aT〈表達式〉*aT〈表達式〉〈運算符〉〈表達式〉*aT〈表達式〉〈運算符〉a*aT〈表達式〉+a*aTa+a*a最右推導2〈表達式〉T〈表達式〉〈運算符〉〈表達式〉T〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉T〈表達式〉〈運算符〉〈表達式〉〈運算符〉aT〈表達式〉〈運算符〉〈表達式〉*aT〈表達式〉〈運算符〉a*aT〈表達式〉+a*aTa+a*a3.給出生成下述語言上下文無關(guān)文法：（1）{anbnambm|n，m>=0}（2）{1n0m1m0n|n，m>=0}解：（1）{anbnambm|n，m>=0}S→AAA→aAb|ε(2){1n0m1m0n|n，m>=0}S→1S0|AA→0A1|ε第三章1、構(gòu)造一種DFA，它接受∑={a，b}上所有滿足下述條件字符串：字符串中每個a均有至少一種b直接跟在其右邊。解：已知∑={a，b}，依照題意得出相應正規(guī)式為：(b*abb*)*依照正規(guī)式畫出相應DFAM，如下圖所示用子集法將其擬定化XY(b*abb*)*XY(b*abb*)*XYb*abb*1XYb123456bbaIIaIb{X,1,2,3,Y}{4}{2,3}{4}—{5,6,1,2,3,Y}{2,3}{4}{2,3}{5,6,1,2,3,Y}{4}{6,1,2,3,Y}{6,1,2,3,Y}{4}{6,1,2,3,Y}IIaIb0121—3212314414由DFA得狀態(tài)圖用最小化辦法化簡得：{0}，{1}，{2}，{3,4}，按順序重新命名DFAM’10210243aaaabbbbb0312aaabbb第四章練習1：文法G[V]：V→N|N[E]E→V|V+EN→i與否為LL(1)文法，如不是，如何將其改導致LL(1)文法。解：LL(1)文法基本條件是不含左遞歸和回溯（公共左因子），而G[V]中具有回溯，因此先消除回溯得到文法G’[V]：G’[V]：V→NV’V’→ε|[E]E→VE’E’→ε|+EN→i由LL(1)文法充要條件可證G’[V]是LL(1)文法練習2：有文法G[s]:S→BAA→BS|dB→aA|bS|c(1)證明文法G是LL(1)文法。(2)構(gòu)造LL(1)分析表。(3)寫出句子adccd分析過程解：(1)一種LL(1)文法充要條件是：對每一種非終結(jié)符A任何兩個不同產(chǎn)生式A→α|β，有下面條件成立：①FIRST(α)∩FIRST(β)=Φ;②若β*Tε，則有FIRST(α)∩FOLLOW(A)=Φ對于文法G[s]：S→BAA→BS|dB→aA|bS|c其FIRST集如下：FIRST(B)={a，b，c}；FIRST(A)={a，b，c，d}；FIRST(S)={a，b，c}。其FOLLOW集如下：一方面，F(xiàn)OLLOW(S)={#};對S→BA有：FIRST(A)\{ε}加入FOLLOW(B)，即FOLLOW(B)={a，b，c，d};對A→BS有：FIRST(S)\{ε}加入FOLLOW(B)，即FOLLOW(B)={a，b，c，d};對B→aA有：FOLLOW(B)加入FOLLOW(A)，即FOLLOW(A)={a，b，c，d};對B→bS有：FOLLOW(B)加入FOLLOW(S)，即FOLLOW(S)={#，a，b，c，d};由A→BS|d得：FIRST(BS)∩FIRST(d)={a，b，c}∩gtguc5m=Φ;由B→aA|bS|c得：FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩∩{c}=Φ。由于文法G[s]不存在形如β→ε產(chǎn)生式，故無需求解形如FIRST(α)∩FOLLOW(A)值。也即，文法G[S]是一種LL(1)文法。(2)由G[s]:S→BAA→BS|dB→aA|bS|cFIRST(B)={a，b，c}；FOLLOW(B)={a，b，c，d}；FIRST(A)={a，b，c，d}；FOLLOW(A)={a，b，c，d};FIRST(S)={a，b，c}。FOLLOW(S)={#，a，b，c，d}可構(gòu)造LL(1)預測分析表如下：

abcd#SS→BAS→BAS→BA

AA→BSA→BSA→BSA→d

BB→aAB→bSB→c

SS→BAS→BAS→BA

AA→BSA→BSA→BSA→d

BB→aAB→bSB→c

(3)在分析表控制下，句子adccd分析過程如下：第五章1已知文法G[S]為：

S→a|∧|(T)T→T,S|S(1)計算G[S]FIRSTVT和LASTVT。(2)構(gòu)造G[S]算符優(yōu)先關(guān)系表并闡明G[S]與否為算符優(yōu)先文法。(3)給出輸入串(a,(a,a))#算符優(yōu)先分析過程。解：文法：

S→a|∧|(T)T→T,S|S展開為：

S→aS→∧S→(T)

T→T,ST→S(1)FIRSTVT--LASTVT表非終結(jié)符FIRSTVT集LASTVT集S{a∧(}{a∧)}T{a∧(，}{a∧)，}(2)算符優(yōu)先關(guān)系表如下：表中無多重入口因此是算符優(yōu)先（OPG）文法。

a∧(),#a

∧

()

,#

≮≮

≮

≮≮

≮

≮≮

≮≯≯≒≯≯≯≯≮≯≯≯≯≯≒(3)輸入串（a,(a,a)）#算符優(yōu)先分析過程為：棧當前字符剩余輸入串動作#

#(

#(a

#(N

#(N,

#(N,(

#(N,(a

#(N,(N

#(N,(N,

#(N,(N,a

#(N,(N,N

#(N,(N

#(N,(N)

#(N,N

#(N

#(N)

#N(

a

,

,

(

a

,

,

a

)

)

)

)

)

)

#

#a,(a,a))#,(a,a))#(a,a))#(a,a))#

a,a))#

,a))#

a))#

a))#))#

)#

)#

)#

#

#

#Movein

Movein

Reduce：S→a

Movein

Movein

Movein

Reduce：S→a

Movein

Movein

Reduce：S→a

Reduce：T→T,S

Movein

Reduce：S→(T)

Reduce：T→T,S

Movein

Reduce：S→(T)第六章例1：有文法：S→(L)|aL→L,S|S給此文法配上語義動作子程序(或者說為此文法寫一種語法制導定義)，它輸出配對括號個數(shù)。如對于句子(a,(a,a))，輸出是2。解：加入新開始符號S'和產(chǎn)生式S'→S，設(shè)num為綜合屬性，代表值屬性，則語法制導定義如下：產(chǎn)生式語義規(guī)則S'→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num例2：構(gòu)造屬性文法，能對下面文法，只運用綜合屬性獲得類型信息。D→L,id|LL→TidT→int|real解：屬性文法（語法制導）定義：產(chǎn)生式語義規(guī)則D→L,idD.type:=L.typeaddtype(id.entry,L.type)D→LD.type:=L.typeL→TidL.type:=T.typeaddtype(id.entry,T.type)T→intT.type:=integerT→realT.type:=real第七章例1：給出下面表達式逆波蘭表達(后綴式)：(1)a*(-b+c)(2)if(x+y)*z=0thens:=(a+b)*celses:=a*b*c解：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表達if-then-else運算）例2：請將表達式-(a+b)*(c+d)-(a+b)分別表達到三元式、間接三元式和四元式序列。解：三元式間接三元式(1)(+a，b)間接三元式序列間接碼表(2)(+c，d)(1)(+a，b)(1)(3)(*(1)，(2))(2)(+c，d)(2)(4)(-(3)，/)(3)(*(1)，(2))(3)(5)(+a，b)(4)(-(3)，/)(4)(6)(-(4)，(5))(5)(-(4)，(1))(1)(5)四元式(1)(+，a，b，t1)(2)(+，c，d，t2)(3)(*，t1，t2，t3)(4)(-，t3，/，t4)(5)(+，a，b，t5)(6)(-，t4，t5，t6)例3：請將下列語句while(A<B)doif(C>D)thenX:=Y+Z翻譯成四元式解：假定翻譯四元式序列從（100）開始：（100）ifA<Bgoto（102）（101）goto（107）（102）ifC>Dgoto（104）（103）goto（100）（104）T∶=Y+Z（105）X∶=T（106）goto（100）（107）例4：寫出for語句翻譯方案解：產(chǎn)生式動作S→forEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)||gen(S.last“:=”E.final)||gen(“if”S.first“>”S.last“goto”S.next)||gen(S.curr“:=”S.first)||gen(S.begin“:”)||gen(“if”S.curr“>”S.Last“goto”S.next)||S1.code||gen(S.curr:=succ(S.curr))||gen(“goto”S.begin)E→v:=initialtofinalE.init:=initial.placeE.final:=final.place第八章例1：C語言中規(guī)定變量標記符定義可分為extern，externstatic，auto，localstatic和register五種存儲類：(1)對五種存儲類所定義每種變量，分別闡明其作用域。(2)試給出適合上述存儲類變量內(nèi)存分派方式。(3)符號表中登記存儲類屬性，在編譯過程中支持什么樣語義檢查。解：(1)extern定義變量，其作用域是整個C語言程序。externstatic定義變量，其作用域是該定義所在C程序文獻。auto定義變量，其作用域是該定義所在例程。localstatic定義變量，其作用域是該定義所在例程。且在退出該例程時，該變量值仍保存。register定義變量，其作用域與auto定義變量同樣。這種變量值，在寄存器有條件時，可存儲在寄存器中，以提高運營效率。(2)對extern變量，設(shè)立一種全局靜態(tài)公共區(qū)進行分派。對externstatic變量，為每個C程序文獻，分別設(shè)立一種局部靜態(tài)公共區(qū)進行分派。對auto和register變量，設(shè)定它們在該例程動態(tài)區(qū)中相對區(qū)頭位移量。而例程動態(tài)區(qū)在運營時再做動態(tài)分派。對localstatic變量，為每個具備此類定義例程，分別設(shè)立一種內(nèi)部靜態(tài)區(qū)進行分派。(3)實行標記符變量重復定義合法性檢查，及引用變量作用域范疇合法性檢查。第九章例1：下面程序執(zhí)行時，輸出a分別是什么？若參數(shù)傳遞辦法分別為(1)傳名；(2)傳地址；(3)得成果；4)傳值。

programmain(input,output);

procedurep(x,y,z)；

begin

y∶=y+1；

z∶=z+x;

end；

begin

a∶=2；

b∶=3；

p(a+b,a,a)；

printa

end.解：(1)參數(shù)傳遞辦法為“傳名”時，a為9。(2)參數(shù)傳遞辦法為“傳地址”，a為8。(3)參數(shù)傳遞辦法為“得成果”，a為7。(4)參數(shù)傳遞辦法為“傳值”，a為2。例2：過程參數(shù)傳遞方式有幾種？簡述“傳地址”和“傳值”實現(xiàn)原理。解：參數(shù)傳遞方式有下述幾種：傳值，傳地址，傳名，得成果“傳值”方式，這是最簡樸參數(shù)傳遞辦法。即將實參計算出它值，然后把它傳給被調(diào)過程。詳細來講是這樣：1.形式參數(shù)當作過程局部變量解決，即在被調(diào)過程活動記錄中開辟了形參存儲空間，這些存儲位置即是咱們所說實參或形式單元。2.調(diào)用過程計算實參值，并將它們右值（r-value）放在為形式單元開辟空間中。3.被調(diào)用過程執(zhí)行時，就像使用局部變量同樣使用這些形式單元。“傳地址”方式，也稱作傳地址，或引用調(diào)用。調(diào)用過程傳給被調(diào)過程是指針，指向?qū)崊⒋鎯ξ恢弥羔槨?.如實參是一種名字或是具備左值表達式，則左值自身傳遞過去。2.如實參是一種表達式，比喻a+b或2，而沒有左值，則表達式先求值，并存入某一位置，然后該位置地址傳遞過去。3.被調(diào)過程中對形式參數(shù)任何引用和賦值都通過傳遞到被調(diào)過程指針被解決成間接訪問。例3：下面是一種Pascal程序

programPP(input,output)

varK:integer;

functionF(N:integer):integer

begin

ifN<=0thenF:=1

elseF:=N*F(N-1);

end;

begin

K:=F(10);

...

end;

當?shù)诙危ㄟf歸地）進入F后，DISPLAY內(nèi)容是什么？當時整個運營棧內(nèi)容是什么？解：第十章例1：何謂代碼優(yōu)化？進行優(yōu)化所需要基本是什么？解：對代碼進行等價變換，使得變換后裔碼運營成果與變換前代碼運營成果相似，而運營速度加快或占用存儲空間減少，或兩者均有。優(yōu)化所需要基本是在中間代碼生成之后或目的代碼生成之后。例2：編譯過程中可進行優(yōu)化如何分類？最慣用代碼優(yōu)化技術(shù)有哪些？解：根據(jù)優(yōu)化所涉及程序范疇，可以分為：局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。最慣用代碼優(yōu)化技術(shù)有1.刪除多余運算2.代碼外提3.強度削弱4.變換循環(huán)控制條件5.合并已知量與復寫傳播6.刪除無用賦值例3：試對如下基本塊B2：B：=3D：=A+CE：=A*CF：=D+EG：=B*FH：=A+CI：=A*CJ：=H+IK：=B*5L：=K+JM：=L應用DAG對它們進行優(yōu)化，并就如下兩種狀況分別寫出優(yōu)化后四元式序列：（1）假設(shè)只有G、L、M在基本塊背面還要被引用。（2）假設(shè)只有L在基本塊背面還要被引用。解：基本塊相應DAG如下：B：=3D：=A+CE：=A*CF：=D+EG：=B*FH：=A+CI：=A*CJ：=H+IK：=B*5L：=K+JM：=L例1一種編譯程序代碼生成要著重考慮哪些問題?解：代碼生成器設(shè)計要著重考慮目的代碼質(zhì)量問題，而衡量目的代碼質(zhì)量重要從占用空間和執(zhí)行效率兩個方面綜合考慮。課后習題答案：P36-6(1)是0~9構(gòu)成數(shù)字串(2)最左推導:最右推導:P36-8文法：最左推導:最右推導:語法樹：/********************************P36-9句子iiiei有兩個語法樹：P64–7(1)XYXYX1X1234Y511011擬定化：01{X}φ{(diào)1,2,3}φφφ{(diào)1,2,3}{2,3}{2,3,4}{2,3}{2,3}{2,3,4}{2,3,4}{2,3,5}{2,3,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4}0320103201001101654016540111最小化：002102100101543015430111P64–12(a)a10a,b10a擬定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ給狀態(tài)編號：ab012112203333a10a10abbb3232ba最小化：aa210bb210ab(b)032bba032abaab541ba541aa已經(jīng)擬定化了,進行最小化最小化：021bba021abaP81–1(1)按照T,S順序消除左遞歸遞歸子程序：procedureS;begin ifsym='a'orsym='^' thenabvance elseifsym='(' thenbegin advance;T; ifsym=')'thenadvance; elseerror; end elseerrorend;procedureT;begin S;end;procedure;begin ifsym=',' thenbegin advance; S; endend;其中:sym:是輸入串指針I(yè)P所指符號advance:是把IP調(diào)至下一種輸入符號error:是出錯診察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}預測分析表a^(),#ST是LL(1)文法 P81–2文法：(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考慮下列產(chǎn)生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ因此,該文法式LL(1)文法.(3)+*()ab^#EE'TT'FF'P(4)procedureE;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT；E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance；Eend elseifsym<>')'andsym<>'#'thenerrorendprocedureT;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF；T'end elseerrorend procedureT';begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP；F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance；F'endendprocedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance；E; ifsym=')'thenadvance elseerror end elseerrorend;P133–1短語：E+T*F，T*F,直接短語：T*F句柄：T*FP133–2文法：(1)最左推導:最右推導:(2)(((a,a),^,(a)),a)(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移進-歸約”過程：環(huán)節(jié) 棧 輸入串 動作0 # (((a,a),^,(a)),a)# 預備1 #( ((a,a),^,(a)),a)# 進2 #(( (a,a),^,(a)),a)# 進3 #((( a,a),^,(a)),a)# 進4 #(((a ,a),^,(a)),a)# 進5 #(((S ,a),^,(a)),a)# 歸6 #(((T ,a),^,(a)),a)# 歸7 #(((T, a),^,(a)),a)# 進8 #(((T,a ),^,(a)),a)# 進9 #(((T,S ),^,(a)),a)# 歸10 #(((T ),^,(a)),a)# 歸11 #(((T) ,^,(a)),a)# 進12 #((S ,^,(a)),a)# 歸13 #((T ,^,(a)),a)# 歸14 #((T, ^,(a)),a)# 進15 #((T,^ ,(a)),a)# 進16 #((T,S ,(a)),a)# 歸17 #((T ,(a)),a)# 歸18 #((T, (a)),a)# 進19 #((T,( a)),a)# 進20 #((T,(a )),a)# 進21 #((T,(S )),a)# 歸22 #((T,(T )),a)# 歸23 #((T,(T) ),a)# 進24 #((T,S ),a)# 歸25 #((T ),a)# 歸26 #((T) ,a)# 進27 #(S ,a)# 歸28 #(T ,a)# 歸29 #(T, a)# 進30 #(T,a )# 進31 #(T,S )# 歸32 #(T )# 歸33 #(T) # 進34 #S # 歸P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)a^(),a>>^>>(<<<=<)>>,<<<>>是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)a^(),f44244g55523 （4）棧 輸入字符串 動作# （a,(a,a)）# 預備#( a，(a,a))# 進#(a ，(a,a))# 進#(s ，(a,a))# 歸#(t ，(a,a))# 歸#（t, (a,a)）# 進#（t,（ a,a））# 進#（t,（a ,a））# 進#（t,（s ,a））# 歸#（t,（t ,a））# 歸#（t,（t, a））# 進#（t,（t,a ））# 進#（t,（t,s ））# 歸#（t,（t ））# 歸#（t,（t） ）# 進#（t,s ）# 歸#（t ）# 歸#（t ） # 進#s # 歸P164–1答：表達式（4*7+1）*2附注語法樹如下圖：digit.lexval=2F.val=2Edigit.lexval=2F.val=2E.val=58ndigit.lexval=4digit.lexval=7digit.lexval=1F.val=4F.val=7F.val=1T.val=4*T.val=28E.val=28+T.val=1E.val=1E.val=29()F.val=29T.val=29T.val=58*L答：(1)aab+(2)aab+P165–11答：（1）D→idL {D.type:=L.type；addtype(id.type,L.type)}L→，idL1 {L.type:=L1.type；addtype(id.type,L1.type)}L→：T {L.type:=T.type}T→integer {T.type:=integer}T→real {T.type:=real}P217–1a*(-b+c) HYPERLINKmailto:ab@c+*ab@c+*a+b*(c+d/e) abcde/+*+-a+b*(-c+d) HYPERLINKmailto:a@bc@d+*+a@bc@d+*+A(CornotD) AnotCD not ornot or (AandB)or(notCorD) ABandCnotDoror(AorB)and(CornotDandE) ABorCDnotEandorand if(x+y)*z=0then(a+b)↑celsea↑b↑c xy+z*0=ab+c↑abc↑↑￥ 或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P2P217–3-(a+b)*(c+d)-(a+b+c)三元式序列:+，a，b@，(1)，-+，c，d*，(2)，(3)+，a，b+，(5)，c-，(4)，(6)間接三元式序列:三元式表：+，a，b@，(1)，-+，c，d*，(2)，(3)+，(1)，c-，(4)，(5)間接碼表：(1)(2)(3)(4)(1)(5)(6)四元式