編譯原理試卷二.doc

一、 選擇1.下面說法正確的是：A 一個正規(guī)式只能對應一個確定的有限狀態(tài)自動機；B 一個正規(guī)語言可能對應多個正規(guī)文法； 2.算符優(yōu)先分析與規(guī)范歸約相比的優(yōu)點是：A 歸約速度快B 對文法限制少3.一個LR（1）文法合并同心集后若不是LALR（1）文法： A 則可能存在移進/歸約沖突B 則可能存在歸約/歸約沖突C 則可能存在移進/歸約沖突和歸約/歸約沖突4.下面說法正確的是：A Lex是一個詞法分析器的生成器B Yacc是一個語法分析器二、 問答題問答第1題(5分) 將文法GS 改寫為等價的GS，使GS不含左遞歸和左公共因子。GS： SSAe|Ae AdAbA|dA|d解：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為： S AeSS AeS| A dA A AB| B bA |問答第2題(10分) 判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應的LL(1)分析表。SaD DSTe|TbH|H Hd|首先計算文法的 FIRST集和FOLLOW集如下表。 文法的 FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集Sa.# ，b ，d ，e.Da ，.# ，b ，d ，e Tb ，d ，e.Hd ，.e. 由于select（DSTe）select（D）=a# ，b ，d ，e =select（TbH）select（TH）=be =select（Hd）select（H）= d e =所以該文法是LL(1)文法，LL(1)分析表如下表。 LL(1)分析表aebd#SaD.DSTeTH.bHH.Hd.問答第3題(5分) 給出與正規(guī)式R（(ab)*|b）*（a|(ba)*）a 等價的NFA。解：與正規(guī)式R（(ab)*|b）*（a|(ba)*）a 等價的NFA如下圖問答第4題解：根據(jù)所給的PL/0示意程序完成下列要求。（1）(4分) 給出 當程序執(zhí)行到A過程體的write(c) 語句時的棧式存儲分配布局和用Display 顯示表時A過程最新活動記錄的內(nèi)容； （2）(2分) 說明在過程D中，當執(zhí)行c:=b*a；語句時，變量c和b的存取位置是如何確定的（請?zhí)钤谙旅娴南鄳ㄌ杻?nèi)）。c的存取位置=（ ） b的存取位置=（ ）PL/0示意程序為：var c;procedure M; procedure A;begin (* A *) write(c);end (* A *) procedure Z; var a,b;procedure D begin (* D *) c:=b*a；call A; end ；(* D *)begin (* Z *) call D; end ；(* Z *) begin (*M *) call Z; end ；(* M *) begin (*main *) call M; end. (* main *)解：（1）當程序執(zhí)行到A過程體的write(c) 語句時的棧式存儲分配布局和用Display 顯示表時A過程最新活動記錄的內(nèi)容如下圖。當程序執(zhí)行到A過程時棧式存儲分配布局和棧中過程最新活動記錄的內(nèi)容（2）在過程D中，當執(zhí)行c:=b*a；語句時，變量c和b的存取位置可如下確定：由于D過程的display表內(nèi)容為： d（3）D的SPd（2）Z的SPd（1）M的SPd（0）Main的SP所以c的存取位置=（d（0）中Main的SP+c在Main中的偏移量） b的存取位置=（d（2）中Z的SP+b在Z中的偏移量）問答第5題（6分）試對 while (ab and ab goto( )( )真鏈頭 E.true= (2)goto( )( )真出口鏈( )(3)if ab goto( 3 )( 1 )真鏈頭 E.true= 5(2)goto( 5 )( 3 )真出口鏈( 5,3 )(3)if a0，m 0 ( ) （2） L2= anbncnbm | n0,m0 ( ) （3） L3= anbmc| n0,m0 ( ) （4） GA:AaB| BAb|a ( )（5） GE:EE+E|E*E|(E)|i ( )解： （1） L1= a0n1nbdm | n0，m 0 ( 2 型 ) （2） L2= anbncnbm | n0,m0 ( 1型 ) （3） L3= anbmc| n0,m0 ( 3型 ) （4） GA:AaB| BAb|a ( 2型 ) （5） GE:EE+E|E*E|(E)|i ( 2型 )問答第11題（5分）已知PL/0語言的的語法圖和EBNF如下： 語法圖: 當型循環(huán)語句 (while)(do) EBNF為： ：= while do 試在方框中填入相應程序（或用文字說明）以完成它的語法語義處理程序。 if sym = whilesymthen begin getsym;condition(dosym + fsys); if sym = dosymthen getsym else error()；statement(fsys); end;解：if sym = whilesymthen begin getsym;condition(dosym + fsys);if sym = dosymthen getsym else error()；statement(fsys); end;問答第12題(4分) 下面矩陣中列元素所指的數(shù)據(jù)對象在PL/0編譯時，是在哪幾個過程（參考行 元素所列）中生成或使用的,請在矩陣表中行列對應的空格中畫。 .詞法分析語法分析代碼生成