編譯原理試卷及答案

裝訂線裝訂線內不要答題學號姓名班級東北大學秦皇島分校裝訂線裝訂線內不要答題學號姓名班級課程名稱：編譯原理試卷：(B)答案考試形式：閉卷授課專業(yè)：計算機科學與技術考試日期：年月日試卷：共2頁題號一二三四總分得分閱卷人填空題（每空2分，共30分）1、編譯程序的整個過程可以從邏輯上劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標代碼生成等幾個階段，另外還有兩個重要的工作是理和出錯處理。表格管2、規(guī)范規(guī)約中的可歸約串是句柄，算符優(yōu)先分析中的可歸約串是最左素短語。3、語法分析方法主要可分為自頂向下和自底向上兩大類。4、LR（0）文法的項目集中不會出現(xiàn)移進-歸約沖突和歸約-歸約沖突。5、數(shù)據(jù)空間的動態(tài)存儲分配方式可分為棧式和堆式兩種。6、編譯程序是指能將源語言程序翻譯成目標語言程序的程序。7、確定有窮自動機DFA是NFA的一個特例。8、表達式(a+b)*c的逆波蘭表示為ab+c*。選擇題（每題2分，共20分）1、LR語法分析棧中存放的狀態(tài)是識別B的DFA狀態(tài)。A、前綴B、可歸前綴C、項目D、句柄2、D不可能是目標代碼。 A、匯編指令代碼B、可重定位指令代碼C、絕對機器指令代碼D、中間代碼3、一個控制流程圖就是具有C的有向圖A、唯一入口結點B、唯一出口結點C、唯一首結點D、唯一尾結點4、設有文法G[S]：S→b|bB B→bS ，則該文法所描述的語言是C。A、L（G）={bi|i≥0}B、L（G）={b2i|i≥0}C、L（G）={b2i+1|i≥0}D、L（G）={b2i+1|i≥1}5、把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由B完成的。A、編譯器B、匯編器C、解釋器D、預處理器6、在目標代碼生成階段，符號表用于D。A、目標代碼生成B、語義檢查C、語法檢查D、預處理器地址分配07、規(guī)范歸約是指B。A、最左推導的逆過程B、最右推導的逆過程C、規(guī)范推導D、最左歸約逆過程8、使用A可以定義一個程序的意義。A、語義規(guī)則B、詞法規(guī)則C、語法規(guī)則D、左結合規(guī)則9、經過編譯所得到的目標程序是D。A、三元式序列B、四元式序列C、間接三元式D、機器語言程序或匯編語言程序10、在一個基本塊內進行的代碼優(yōu)化是B。A、全局優(yōu)化B、局部優(yōu)化C、循環(huán)優(yōu)化D、代碼外提三、簡答題（3小題，共30分）1、已知文法G[S]：S→Ac|aB A→abB→bc 證明該文法具有二義性（本題6分）證明：因為該文法的句型abc存在如下兩棵語法樹：所以，該文法具有二義性裝訂線裝訂線內不要答題學號姓名班級3、若有文法G[S]：S→bAbA裝訂線裝訂線內不要答題學號姓名班級解：4、構造正規(guī)表達式（a|b）*b的DFA并化簡。（14分）解：先構造其NFA如下：確定化為DFA：將其最小化如下：四、綜合題（20分）設有文法G[S]：S→BA A→BS|d B→aA|bS|c證明文法G是LL（1）文法。構造LL（1）分析表。寫出句子adccd的分析過程。解：（1）可見，文法G是是LL（1）文法。（2）（3）備注:學生不得在試題紙上答題(含填空題、選擇題等客觀題一、填空題（每空1分，共20分）1．編譯過程一般分為、、中間代碼生成、和目標代碼生成五個階段。2．語法分析最常用的兩類方法是和分析法。3．確定的有窮自動機是一個，通常表示為。4．所謂最右推導是指。5．語法分析器的任務是。6．如果一個文法的任何產生式的右部都不含有的非終結符，則這種文法稱為文法。7．進行確定的自上而下語法分析要求語言的文法是無和的。8．LR分析法是一種的語法分析方法。9．根據(jù)優(yōu)化對象所涉及的程序范圍，代碼優(yōu)化分為、和等。10．常用的優(yōu)化技術包括：、、強度削弱、復寫傳播、等。二、是非題（下列各題，你認為正確的，請在題后的括號內打“√”，錯的打“×”。每題2分，共20分）1．正規(guī)文法產生的語言都可以用上下文無關文法來描述?！?)2．僅考慮一個基本塊，不能確定一個賦值是否真是無用的?！ǎ?．如果一個文法是遞歸的，則其產生的語言的句子是無窮個?！ǎ?．四元式之間的聯(lián)系是通過符號表實現(xiàn)的?！ǎ?．文法的二義性和語言的二義性是兩個不同的概念?！ǎ?．一個LL(l)文法一定是無二義的?！?)7．在規(guī)范規(guī)約中用最左素短語來刻劃可歸約串?！?)8．目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題?！?)9．編譯程序是對匯編程序的翻譯。……（）10．逆波蘭法表示的表達式亦稱前綴式。……………()三、簡答題（每題5分，共15分）1、簡述棧式存儲管理策略；2、何謂DAG；3、何謂文法的二義性；四、給出下述文法對應的正規(guī)式（7分）S→0A|1BA→1S|1B→0S|0五、已知文法G(E)：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i證明E+T*F是該文法的一個句型，并指出該句型的所有短語、直接短語和句柄。（8分）六、設有文法G[S]：SaBc|bABAaAb|bBb|ε構造其LL(1)分析表，并分析符號串baabbb是否是該文法的句子.(10分)七、設有文法G[E]:E(E)|ε試判斷該文法是否為SLR(1)文法，若不是，請說明理由；若是請構造SLR(1)分析表。(10分)八、假設可用寄存器為R0和R1，試寫出下列四元式序列對應的目標代碼。（10分）T1=B-CT2=A*T1T3=D+1T4=E-FT5=T3*T4參考答案一、填空題(1X20=20分)1．詞法分析、語法分析、代碼優(yōu)化2．自上而下、自下而上3．五元組、DFA=(K,∑,M,S,Z)4．任何一步都是對中最右非終結符進行替換5．分析一個文法的句子結構6．相鄰、算符7．左遞歸、公共左因子8．自下而上9．局部優(yōu)化、循環(huán)優(yōu)化、局部優(yōu)化10．刪除公共子表達式、代碼外提、變換循環(huán)控制條件、合并已知量、刪除無用賦值（任選3個）二、是非題（2X10=20分）1、×2、√3、√4、×5、√6、√7、×8、√9、×10、×三、簡答題（見書中相應部分）（5X3=15分）四、解：首先得正規(guī)式方程組：S=0A+1BA=1S+1B=0S+0求解該方程組得：S=(01|10)(01|10)*（8分）五、解（2分）是文法G[S]的句型。短語：E+T*F,T*F（2分）直接短語：T*F（2分）句柄：T*F（2分）六、解：、因為FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}(2分),所以構造文法G[S]的LL（1）分析表（5）如下：aBc#SaBcbABAaAbbBbεε符號串baabbb是該文法的句子(3分)（分析過程略）。七(2分)所以該文法為SLR(1)文法。其分析表如下：(8分)狀態(tài)ACTIONGOTO()#E0S2r2r211acc2S2r2r233S44r1r1八、目標代碼為：(10分)LDR0,BSUBR0,CLDR1,A