山東理工大學《編譯原理》考試

第一章引論1．高級程序設計語言的翻譯主要有兩種方式：和，二者的根本區(qū)別在于。答：解釋編譯是否生成目標程序。2．編譯程序決大多數(shù)時間是花在方面。A詞法分析B語法分析C語義分析D代碼生成E中間代碼生成F代碼優(yōu)化G表格管理H出錯管理答：G3．什么是遍？是否任何一種高級語言都能通過一遍掃描完成編譯？答：遍是對源程序或源程序的中間表示從頭到尾地掃描一次，并做相關的處理工作，生成新的源程序的中間形式或目標文件。并非所有的語言都能通過一遍掃描完成編譯。如果該語言結(jié)構復雜，那么必須通過多次掃描才能真正完成編譯工作。影響編譯遍的次數(shù)的主要因素有：源語言；機器目（標機）；編譯方法。第二章高級語言及其語法描述1．巴科斯—瑙爾范式（EBNF）是一種廣泛采用的工具。A描述規(guī)則B描述語言C描述文法D描述句子答：C2．由文法的開始符號經(jīng)0步或多步推導產(chǎn)生的文法符號序列是。A短語B句柄C句型D句子答：C3．請給出描述語言L={a2m+1bm+1|m>=0}∪{a2m+1bm+2|m>=0}的文法。解答：將語言句子的描述稍做變形，得：a2mabbm和a2mabbbm于是，得到文法如下：G[Z]:Z→aaZb|ab|bb4.文法G[S]:S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc它是喬姆斯基哪一型文法？它生成的語言是什么？答：從規(guī)則形式上可以看出，文法G是喬姆斯基1型文法，即上下文有關文法。它生成的語言是L={anbncn|n>=1}。第三章詞法分析1.不是NFA的成分。A有窮字母表B初始狀態(tài)集合C終止狀態(tài)集合D有限狀態(tài)集合答：B。2．構造一個DFA，其輸入字母表是{0，1}，它能接受以0開始以1結(jié)尾的所有序列，要求寫出正規(guī)式。答：r=0(0|1)1*NFA為：10，12εε0131xy確定化II0I1{x}{1,2，3}{1,2,3}{2,3}Φ{2,3,y}{2,3}{2,3}{2,3,y}{2,3}{2,3,y}{2,3,y}重命名011+22Φ44433334-確定化后的DFA如圖：0301110201化簡：{1，2,3}{4}4{1，2,3}0={2,3}{2，3}1={4}{1}1=Φ分兩組{2，3}{1}{2,3}不可再分留2刪3得化簡后的DFA為：10021014第四章語法分析——自上而下分析1．自頂向下語法分析方法會遇到的主要問題有和。答：左遞歸回溯2.LL（1）分析法中，第一個L的含義是，第二個L的含義是，“1”的含義是。答：從左到右掃描輸入串最左推導分析時每一步只需向前查看一個符號23.下列文法是左遞歸文法，試消除其左遞歸。G[S]：S→SaA|bBA→aB|cB→Bb|d解答：S→bBS’S’→aAS’|εA→aB|cB→dB’B’→bB’|ε4.考慮下面的文法G：S→a|∧|(T)T→T,S|S⑴消去G的左遞歸；⑵經(jīng)改寫后的文法是否是LL（1）的？給出它的預測分析表。解答：⑴按照T，S的順序消除左遞歸，得到文法：G,[S]：S→a|∧|(T)T→ST,T,→,ST|ε,⑵首先計算每個非終結(jié)符的FIRST集合和FOLLOW集合：FIRST（S）={a,∧,(}FOLLOW(S)={,,),#}FIRST（T）={a,∧,(}FOLLOW(T)={)}FIRST（T,）={,,ε}FOLLOW(T,)={)}構造預測分析表如下表所示：A∧(),#SS→aS→∧S→(T)TT→ST,T→ST,T→ST,T,T,→εT,→,ST,從表中可以看出沒有多重入口，所以改造后的文法是LL（1）文法。第五章語法分析——自下而上分析1．自下而上語法分析的基本思想是：從待輸入的符號串出發(fā)，利用文法的產(chǎn)生式步步向上，試圖到文法的。答：直接歸約，歸約開始符號2．規(guī)范歸約每次歸約的是當前句型的，算符優(yōu)先文法每次歸約，二者都是不斷移進輸入符號，直到符號棧的棧頂出的是當前句型的現(xiàn)的尾，再向前找到的頭，然后歸約。答：句柄最左素短語可歸約串可歸約串3．對下列文法G[S′]：（1）計算文法中每個非終結(jié)符的FIRSTVT和LASTVT集合；（2）構造文法的算符優(yōu)先關系表；（3）給出輸入串cadbc的算符優(yōu)先分析過程。文法G[S]：S′→#S#S→SaF|F3F→FbP|PP→c|d解答：(1)FIRSTVT(S)={a,b,c,d}LASTVT(S)={a,b,c,d}FIRSTVT(F)={b,c,d}LASTVT(F)={b,c,d}FIRSTVT(P)={c,d}LASTVT(P)={c,d}FIRSTVT(S’)={#}LASTVT(S’)={#}(2)文法G的優(yōu)先關系表abcd#a><<<>b><<<>c>>d>>>#<<<<=c⑶分析過程步驟符號棧輸入串動作0#cadbc##<a,移進1#cadbc#c>a,歸約P→c2#Padbc##<a,移進3#Padbc#a<d,移進4#Padbc#d>b,歸約P→d5#PaPbc#a<b,移進6#PaPbc#b<c#,移進7#PaPbc#c>#,規(guī)約P→c8#PaPbP#b>#,規(guī)約F→FbP9#PaF#a>#,規(guī)約S→SaF10#S#接受4．已知文法G[A]：A→(A)|a(1)請構造該文法的以LR(0)項日集為狀態(tài)的識別活前綴的DFA。(2)構造該文法的LR(0)分析表，并回答該文法是LR(O)文法嗎?(3)構造該文法的SLR(1)分析表，并回答該文法是SLR(1)文法嗎？(4)構造該文法的以LR(1)項目集為狀態(tài)的識別活前綴的DFA。(5)構造該文法的LR（1）分析表。(6)構造該文法的LALR(1)分析表。解答：(1)首先構造拓廣文法如下：0A’→A4l2A→(A)A→a構造該文法的以LR(0)項日集為狀態(tài)的識別活前綴的DFA如圖所示文法的以LR[0]項目集為狀態(tài)的識別活前綴的DFA(2)構造文法的LR(0)分析表如表所示。表中無多重定義，所以該文法是LR(0)文法。文法的LR(0)分析表)(3)因為FOLLOW(A)＝{，#}，所以得到文法的SLR(1)分析表如表所示。表中無多重定義，所以該文法是SLR(1)文法。文法的SLR(l)分析表5(4)構造該文法的以LR(1)頂目集為狀態(tài)的識別活前綴的DFA如圖所示(5)構造該文法的LR(1)分析表如表所示。6(6)狀態(tài)I3和I6、I2和I5、I4利I8、I7和I9，是同心狀態(tài)，將它們分別合并后不產(chǎn)生沖突，所以得到該文法的LALR(1)分析表如表所示。第六章屬性文法和語法制導翻譯1．在屬性文法中，屬性用于“自下而上”傳遞信息，而屬性用于“自上而下”傳遞信息。2.下列文法由開始符號S產(chǎn)生一個二進制數(shù)，令綜合屬性val給出該數(shù)的值：SLL|LLLB|BB0|1試設計求Sval的屬性文法，其中，已知B的綜合屬性val，給出由B產(chǎn)生的二進位的7結(jié)果值。例如，輸入101.101時，Sval＝5.625，其中第一個二進位的值是4，最后一個二進位的值時是0.125解答：語義動作子程序如下：產(chǎn)生式語義動作S，S{print(Sval)}SLL{Sval:=Lval+Lval/2}L2length121SL{Sval:=Lval}2LLB{Lval:=Lval*2+Bval11Llength:=Llength+1}1LB{Lval:=Bval;Llength:=1}B0{Bval:=0}B1{Bval:=1}第七章語義分析和中間代碼生成1.⑴給出下列表達式的逆波蘭表示（后綴式）：a+b*ca<=b+c∧a>d∨a+b≠e⑵寫出下列語句的逆波蘭表示（后綴式）：<變量>：＝<表達式>IF<表達式>THEN<語句1>ELSE<語句2>⑶寫出算術表達式A+B*(C-D)+E/(C-D)**N的四元式，三元式和間接三元式序列。解答：⑴abc*+abc+<=ad>∧ab+e≠∨⑵<變量><表達式>：＝<表達式>p1BZ<語句1>p2BR<語句2>↑p1↑p2⑶四元式序列：⑴（-,C,D,T1）⑵(*,B,T1,T2)⑶(+,A,T2,T3)⑷(-,C,D,T4)⑸(**,T4,N,T5)⑹(/,E,T5,T6)⑺(+,T3,T6,T7)三元式序列：⑴（-,C,D）⑵(*,B,⑴)⑶(+,A,⑵)⑷(-,C,D)⑸(**,⑷,N)⑹(/,E,⑸)⑺(+,⑶,⑹)8

間接三元式序列：間接碼表三元式表⑴⑴（-,C,D）⑵⑵(*,B,⑴)⑶⑶(+,A,⑵)⑴⑷(**,⑴,N)⑷⑸(/,E,⑷)⑸⑹(+,⑶,⑸)⑹2.將下列語句翻譯成四元式序列。while(a>b)doif(c<d)thenx:=y*zelsex:=y+z解答：100(j>,a,b,102)106(j,_,_,100)101(j,_,_,110)107(+,y,z,T2)102(j<,c,d,104)108(:=,T2,_,x)103(j,_,_,107)109(j,_,_,100)104(*,y,z,T1)110105(:=,T1,_,x)第八章符號表1．在語義分析階段，符號表所登記的信息將用于和，在目標代碼生成階段，符號表是的依據(jù)。答：語義檢查，產(chǎn)生中間代碼，地址分配2．編譯過程中，每當掃描識別出一個名字后，編譯程序就查閱，看該名字是否在其中，如果該名字是一個新名字就將它填進里。答：符號表符號表3．判斷題：⑴名字就是標識符，標識符就是名字。（）⑵對每個過程指定順序號，目的是為了確定過程中名字的作用域。（）⑶符號表的內(nèi)容在詞法分析階段填進并在以后各個階段得到使用。（）⑷編譯開始時，符號表都是空的。（）⑸編譯工作的相當一大部分時間是花費在查填符號表上。（）⑹程序在運時行發(fā)現(xiàn)的錯誤能夠反映它在源程序中的確切位置。（）⑺“運算符與運算對象類型不符”屬于語法錯誤。（）解答：⑴錯⑵對⑶錯⑷錯⑸對⑹錯⑺錯第九章運時行存儲空間組織1．在PASCAL語言中，為了在過程的嵌套調(diào)用過程中實現(xiàn)對非局部名字的訪問，可以采用和活動紀錄，或和活動紀錄的方式。答：靜態(tài)鏈過程嵌套層次表2．編譯程序中常用的存儲分配策略包括、和堆式動態(tài)存儲分配策略。答：靜態(tài)存儲分配策略棧式動態(tài)存儲分配策略93．如下示意的Pascal源程序：programmain;vara,b,c:integer;procedureX(i,j:integer);vard,e:real;procedureY;varf,g:real;begin?end;{Y}procedureZ(k:integer);varh,i,j:real;begin?end;{Z}begin?10:Y;?11:Z;?end;{X}begin?(a,b);?end.{main}并已知在運行時刻，以過程為單位對程序中的變量進行動態(tài)存儲分配。當運行主程序而調(diào)用過程語句X時，試分別給出以下時刻的運行棧的內(nèi)容和Display的內(nèi)容。⑴已開始而尚未執(zhí)行完畢標號為10的語句；⑵已開始而尚未執(zhí)行完畢標號為11的語句。解答：15e（局）26j（局）14d（局）24g（局）23f（局）136XDisplay表25i（局）24h（局）1202216YDisplay表11j(形參)2316ZDisplay表226216109i（形參）2(形參個數(shù))2(全局Display)200YDisplay表190(形參個數(shù))210ZDisplay表20k(形參)81812(全局Display)7返回地址191(形參個數(shù))1812(全局Display)17返回地址17返回地址16Y6（老SP）6X0（老SP）5Mainc（局）4b（局）16Z6（老SP）3a（局）20（Display）1返回地址0Main0（老SP）(1)已開始而尚未執(zhí)行完畢標號為10的語句時運行棧的內(nèi)容0－15和左側(cè)表16－24右側(cè)表20-22是Display表的內(nèi)容10（2）已開始而尚未執(zhí)行完畢標號為11的語句時運行棧的內(nèi)容是中間表0－15右側(cè)表16－26的內(nèi)容，右側(cè)表20－22的內(nèi)容是此時Display表的內(nèi)容。第十章優(yōu)化1.在循環(huán)中可采用、和刪除歸納變量三種優(yōu)化措施。答：代碼外提，強度削弱2.根據(jù)優(yōu)化所涉及的范圍，可將優(yōu)化可分為，和循環(huán)優(yōu)化。答：局部優(yōu)化，全局優(yōu)化3.試對以下基本塊構造其DAG圖，分別利用DAG圖對它們進行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四元式序列：（1）假設只有G，L，M在基本塊后面還要被引用；（2）假設只有L在基本塊后面還要被引用。B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L解答：該基本塊的DAG圖：L,Mn9n7G*+F,Jn1B3n6n8K15+D,Hn5E,In4*+n2A0n3C0(1)假設只有G，L，M在基本塊后面還要被引用，該基本塊優(yōu)化后的四元式序列為：D:=A+CE:=A*CF:=D+EG:=3*FL:=15+FM:=L(2)假設只有L在基本塊后面還要被引用,該基本塊優(yōu)化后的四元式序列為:D:=A+CE:=A*C11F:=D+EL:=15+F第十一章目標代碼生成1.指令的執(zhí)行代價定義為+.答:該指令訪問內(nèi)存的次數(shù)1(取該指令訪問內(nèi)存的次數(shù))2.設有基本塊PT0:=3T1:=8/T0T2:=S–CT3:=S+CR:=T0*T3H:=RT4:=10/T1T5:=S+CT6:=T4*T5H:=T6/T2(1)構造其DAG圖，寫出用DAG圖優(yōu)化后的三地址代碼序列；(2)假定只有R，H在基本塊出口是活躍的，試寫出優(yōu)化后的三地址代碼序列；(3)假