編譯原理試卷二.doc

一、 選擇1.下面說(shuō)法正確的是：A 一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)；B 一個(gè)正規(guī)語(yǔ)言可能對(duì)應(yīng)多個(gè)正規(guī)文法； 2.算符優(yōu)先分析與規(guī)范歸約相比的優(yōu)點(diǎn)是：A 歸約速度快B 對(duì)文法限制少3.一個(gè)LR（1）文法合并同心集后若不是LALR（1）文法： A 則可能存在移進(jìn)/歸約沖突B 則可能存在歸約/歸約沖突C 則可能存在移進(jìn)/歸約沖突和歸約/歸約沖突4.下面說(shuō)法正確的是：A Lex是一個(gè)詞法分析器的生成器B Yacc是一個(gè)語(yǔ)法分析器二、 問(wèn)答題問(wèn)答第1題(5分) 將文法GS 改寫為等價(jià)的GS，使GS不含左遞歸和左公共因子。GS： SSAe|Ae AdAbA|dA|d解：文法GS 改寫為等價(jià)的不含左遞歸和左公共因子的GS為： S AeSS AeS| A dA A AB| B bA |問(wèn)答第2題(10分) 判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。SaD DSTe|TbH|H Hd|首先計(jì)算文法的 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.問(wèn)答第3題(5分) 給出與正規(guī)式R（(ab)*|b）*（a|(ba)*）a 等價(jià)的NFA。解：與正規(guī)式R（(ab)*|b）*（a|(ba)*）a 等價(jià)的NFA如下圖問(wèn)答第4題解：根據(jù)所給的PL/0示意程序完成下列要求。（1）(4分) 給出 當(dāng)程序執(zhí)行到A過(guò)程體的write(c) 語(yǔ)句時(shí)的棧式存儲(chǔ)分配布局和用Display 顯示表時(shí)A過(guò)程最新活動(dòng)記錄的內(nèi)容； （2）(2分) 說(shuō)明在過(guò)程D中，當(dāng)執(zhí)行c:=b*a；語(yǔ)句時(shí)，變量c和b的存取位置是如何確定的（請(qǐng)?zhí)钤谙旅娴南鄳?yīng)括號(hào)內(nèi)）。c的存取位置=（ ） b的存取位置=（ ）PL/0示意程序?yàn)椋簐ar 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）當(dāng)程序執(zhí)行到A過(guò)程體的write(c) 語(yǔ)句時(shí)的棧式存儲(chǔ)分配布局和用Display 顯示表時(shí)A過(guò)程最新活動(dòng)記錄的內(nèi)容如下圖。當(dāng)程序執(zhí)行到A過(guò)程時(shí)棧式存儲(chǔ)分配布局和棧中過(guò)程最新活動(dòng)記錄的內(nèi)容（2）在過(guò)程D中，當(dāng)執(zhí)行c:=b*a；語(yǔ)句時(shí)，變量c和b的存取位置可如下確定：由于D過(guò)程的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中的偏移量）問(wèn)答第5題（6分）試對(duì) 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型 )問(wèn)答第11題（5分）已知PL/0語(yǔ)言的的語(yǔ)法圖和EBNF如下： 語(yǔ)法圖: 當(dāng)型循環(huán)語(yǔ)句 (while)(do) EBNF為： ：= while do 試在方框中填入相應(yīng)程序（或用文字說(shuō)明）以完成它的語(yǔ)法語(yǔ)義處理程序。 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;問(wèn)答第12題(4分) 下面矩陣中列元素所指的數(shù)據(jù)對(duì)象在PL/0編譯時(shí)，是在哪幾個(gè)過(guò)程（參考行 元素所列）中生成或使用的,請(qǐng)?jiān)诰仃嚤碇行辛袑?duì)應(yīng)的空格中畫。 .詞法分析語(yǔ)法分析代碼生成