編譯原理期末考試試題（卷）(C卷)

./編譯原理期末考試試卷〔C卷一、單項(xiàng)選擇題〔每小題2分,共30分1、編譯程序是對(duì)______程序進(jìn)行翻譯。A.自然語(yǔ)言B.匯編語(yǔ)言C.高級(jí)語(yǔ)言D.機(jī)器語(yǔ)言B.S→ABA→aB→bS→ABAB.S→ABA→aB→bS→ABA→Aa|aB→Bb|bD.S→D.S→aSb|εC.S→aSb|ab3、設(shè)有文法G=<,{S,B},S,{S→bB,B→bS|ε}>,下列哪個(gè)符號(hào)串不是該文法的句子。A.bB.bbC.bbbD.bbbbb4、下圖DFA所識(shí)別的語(yǔ)言為_(kāi)______。00BA00BA11111100D00DCA.含有偶數(shù)個(gè)0偶數(shù)個(gè)1的二進(jìn)制串B.含有偶數(shù)個(gè)0奇數(shù)個(gè)1的二進(jìn)制串C.含有奇數(shù)個(gè)0偶數(shù)個(gè)1的二進(jìn)制串D.含有奇數(shù)個(gè)0奇數(shù)個(gè)1的二進(jìn)制串5、下述正規(guī)式等價(jià)的是。A.<a|b>*與<a*b*>*B.<ab>*與a*b*C.<a|b>*與<ab>*D.<a|b>*與a*|b*6、設(shè)有一個(gè)LR<1>項(xiàng)目集I={X→.bB,aB→.,a}則該項(xiàng)目集__________。A.不含沖突項(xiàng)目B.含有移進(jìn)-歸約沖突C.含有歸約-歸約沖突D.含有移進(jìn)-待約沖突7、LR語(yǔ)法分析棧中存放的狀態(tài)是識(shí)別文法規(guī)范句型__________的DFA狀態(tài)。A.句柄B.前綴C.活前綴D.項(xiàng)目8、有文法如S→rDD→D,i|i則FIRSTVT<D>=_________。A.{i}B.{i,}C.{ir}D.{ir,}9、有文法如S→rDD→D,i|i則i和,的優(yōu)先關(guān)系是_________。A.沒(méi)有優(yōu)先關(guān)系B.等于C.低于D.高于10、算符優(yōu)先分析法從左到右掃描輸入串,采用移進(jìn)-歸約的方式,當(dāng)棧頂出現(xiàn)___________時(shí)進(jìn)行歸約。A.素短語(yǔ)B.最左素短語(yǔ)C.句柄D.直接短語(yǔ)11、局部?jī)?yōu)化是局限于一個(gè)_________范圍內(nèi)的一種優(yōu)化。A.程序B.函數(shù)C.基本塊D.循環(huán)12、在編譯中,動(dòng)態(tài)存儲(chǔ)分配的含義是_________。A.在運(yùn)行階段對(duì)源程序中的量進(jìn)行存儲(chǔ)分配B.在編譯階段對(duì)源程序中的量進(jìn)行存儲(chǔ)分配C.在說(shuō)明階段對(duì)源程序中的量進(jìn)行存儲(chǔ)分配D.以上都不正確13、以下說(shuō)法正確的是_________。A.對(duì)任何一個(gè)編譯程序來(lái)說(shuō),產(chǎn)生中間代碼不是不可缺少的一部分。B.在屬性文法中,文法的終結(jié)符只有綜合屬性,不存在繼承屬性。C.自下而上語(yǔ)法制導(dǎo)翻譯中語(yǔ)法分析棧與語(yǔ)義分析棧必需同步操作。D.以上都正確14、后綴式abcd+*的中綴表達(dá)式是_________。A.ab*<c+d>B.a<b*c+d>C.a<b*<c+d>>D.a*<b+c>d15、有翻譯模式如下：D→intL{print<L.s>;}L→id{L.s=1;}L→L1,id{L.s=L1.s+1;}采用移進(jìn)歸約的分析方法,當(dāng)分析器的輸入為inta,b,c時(shí),輸出的結(jié)果是。A.4B.3C.2D.1三、應(yīng)用題〔1、4、5每題10分,2、3每題15分,共60分2、有文法如下：S→TLT→int|floatL→idRR→,idR|ε<1>.計(jì)算文法的每個(gè)非終結(jié)符的FIRST和FOLLOW集合；<1>〔8分FIRST<S>={int,float}FOLLOW<S>={#}FIRST<T>={int,float}FOLLOW<T>={id}FIRST<L>={id}FOLLOW<L>={#}FIRST<R>={,ε}FOLLOW<R>={#}4、有定義算術(shù)表達(dá)式的文法如下：E→E+T|E-T|TT→T*F|T/F|FF→PF|PP→<E>|i構(gòu)造句型E-T*PF+i的語(yǔ)法樹(shù)；并指出該句型的所有短語(yǔ)、直接短語(yǔ)、素短語(yǔ)、句柄。4、句型E-T*PF+i的語(yǔ)法樹(shù)：〔5分短語(yǔ)：E-T*PF+i、E-T*PF、T*PF、PF、i直接短語(yǔ)：PF、i素短語(yǔ)：PF、i句柄：PF123456789101112131415CABDAACBDBCADCB.編譯原理期末考試試卷〔B卷一、簡(jiǎn)述編譯程序的工作過(guò)程?！?0編譯程序的工作過(guò)程,是指從輸入源程序開(kāi)始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程,是非常復(fù)雜的,就其過(guò)程而言,一般可以劃分為五個(gè)工作階段：①詞法分析,對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解,識(shí)別出一個(gè)個(gè)的單詞；②語(yǔ)法分析,根據(jù)語(yǔ)言的語(yǔ)法規(guī)則,把單詞符號(hào)串分解成各類(lèi)語(yǔ)法單位；③語(yǔ)義分析與中間代碼產(chǎn)生,即對(duì)各類(lèi)語(yǔ)法單位,分析其漢一并進(jìn)行初步翻譯；④代碼優(yōu)化,以期產(chǎn)生更高效的代碼；⑤目標(biāo)代碼生成,把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言指令形式。二、給出下面的正規(guī)表達(dá)式〔15以01結(jié)尾的二進(jìn)制數(shù)串；能被5整除的十進(jìn)制整數(shù)；包含偶數(shù)個(gè)1或偶數(shù)個(gè)0的二進(jìn)制數(shù)串?！?〔0|1*01〔2digit=0|1|2|3|4|5|6|7|8|9digit*〔0|5〔3〔〔0*10*1*0*|〔〔1*01*0*1*三、對(duì)下面的文法G：S→a|b|〔TT→T,S|S<1>消去文法的左遞歸,得到等價(jià)的文法G2；<2>判斷文法G2是否LL〔1文法,如果是,給出其預(yù)測(cè)分析表。〔15G2：S→a|b|〔TT→ST’T’→,ST’|εG2是LL〔1文法。ab〔,#SS→aS→bS→〔TTT→ST’T→ST’T→ST’T’T’→εT’→,ST’四、對(duì)下面的文法G：S→ABA→A00|0B→B11|1<1>消去文法的左遞歸,得到等價(jià)的文法G2；<2>判斷文法G2是否LL〔1文法,如果是,給出其預(yù)測(cè)分析表?！?5G’：S→ABA→0A’A’→00A’|εB→1B’B’→11B’|ε文法G’[S]是LL<1>文法。預(yù)測(cè)分析表：01#SS→ABAA→0A’A’A’→00A’A’→εBB→1B’B’B’→11B’B’→ε五、設(shè)有文法G[A]：A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|c計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集；試判斷該文法是否為L(zhǎng)L〔1文法?！?5FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL〔1文法。編譯原理期末考試試卷〔D卷三、應(yīng)用題〔1、4、5每題10分,2、3每題15分,共60分1、為正規(guī)式<a|b>*a<a|b>構(gòu)造等價(jià)且狀態(tài)最少的確定有限自動(dòng)機(jī)。〔要求給出主要步驟2、有文法如下：S→BAA→BS|dB→aA|bS|c<1>.計(jì)算文法的每個(gè)非終結(jié)符的FIRST和FOLLOW集合；<2>.判斷文法是否LL〔1文法,如果是,給出其預(yù)測(cè)分析表,否則說(shuō)明理由。4、有文法如下：T→T*F|FF→PF|PP→<T>|i證明T*iP是該文法的一個(gè)句型,但不是規(guī)范句型；指出T*iP的所有短語(yǔ)、直接短語(yǔ)、素短語(yǔ)、句柄。三、應(yīng)用題〔1、4、5每題10分,2、3每題15分,共60分abAaaabAaaBCbNFA如圖〔5分：NFA如圖〔5分：〔也可是其它等價(jià)的FAIIaIb1{A}{A,B}{A}2{A,B}{A,B,C}{A,C}3{A,B,C}{A,B,C}{A,C}4{A,C}{A,B}{A}用子集法得到的狀態(tài)轉(zhuǎn)換矩陣：用子集法得到的狀態(tài)轉(zhuǎn)換矩陣：確定化〔3分后的DFA如圖,已是狀態(tài)最少的。如不說(shuō)明是最簡(jiǎn)的扣1分。確定化〔3分后的DFA如圖,已是狀態(tài)最少的。如不說(shuō)明是最簡(jiǎn)的扣1分?；?jiǎn)〔2分11babaa234bab注：初態(tài)或終態(tài)錯(cuò)扣1分注：初態(tài)或終態(tài)錯(cuò)扣1分2、<1>〔6分FIRST<S>={a,b,c}FOLLOW<S>={#,a,b,c,d}FIRST<A>={a,b,c,d}FOLLOW<A>={#,a,b,c,d}FIRST<B>={a,b,c}FOLLOW<B>={a,b,c,d}<2>因?yàn)槲姆ú缓筮f歸,關(guān)于A的兩個(gè)規(guī)則的SELECT集不相交,關(guān)于B的3個(gè)規(guī)則的SELECT集兩兩不相交,所以文法是LL〔1文法〔2分。預(yù)測(cè)分析表〔7分如下：abcd#SS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→c4、對(duì)于符號(hào)串T*iP存在如下推導(dǎo)：〔或畫(huà)一顆語(yǔ)法樹(shù)證明是句型TT*FT*PFT*PPT*iP所以T*iP是該文法的一個(gè)句型,但不存在一個(gè)規(guī)范推導(dǎo)能推導(dǎo)出該句型,所以不是規(guī)范句型?！?分短語(yǔ)：T*iP、iP、i、p直接短語(yǔ)：i、p素短語(yǔ)：i句柄：i2.考慮文法G[S]:S→<T>|a+S|aT→T,S|S消除文法的左遞歸及提取公共左因子。解：消除文法G[S]的左遞歸：

S→<T>|a+S|a

T→ST′

T′→,ST′|ε

提取公共左因子：

S→<T>|aS′

S′→+S|ε

T→ST′

T′→,ST′|ε24.已知文法G[S]S→S*aF|aF|*aFF→+aF|+a消除文法左遞歸和提公共左因子。答：消除左遞歸S→aFS’|*aFS’S’→*aFS’|εF→+aF|+a提公共左因子,文法G’<S>S→aFS’|*aFS’S’→*aFS’|εF→+aF’F’→F|ε1、設(shè)文法G<S>:S→^|a|<T>T→T,S|S⑴消除左遞歸；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；⑶構(gòu)造預(yù)測(cè)分析表<1>消除左遞,文法變?yōu)镚’[S]：S→^|a|<T>'T→ST’|ST’→,ST’|ε此文法無(wú)左公共左因子。10.設(shè)文法G<S>:S→<T>|aS|aT→T,S|S⑴消除左遞歸和提公共左因子；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；⑶構(gòu)造預(yù)測(cè)分析表。.<1>S→<L>|aS’S’→S|εL→SL’L’→,SL’|ε<2>FIRST<S>={a,<}FIRST<S’>={a,<,ε}FIRST<L>={a,<}FIRST<L’>={,,ε}FOLLOW<S>={,,>,#}FOLLOW<S’>={,,>,#}FOLLOW<L>={>}FOLLOW<L’>={>}<3><>a,#SS→<L>S→aS’S’S’→SS’→εS’→SS’→εS’→εLL→SL’L→SL’L’→,SL’L’L’→ε已知文法G<S>：S—>a|<T>T—>T,S|S①給出句子<<a,a>,a>的最左推導(dǎo)并畫(huà)出語(yǔ)法樹(shù)；②給出句型<T,a,<T>>所有的短語(yǔ)、直接短語(yǔ)、素短語(yǔ)、最左素短語(yǔ)、句柄和活前綴。解：〔1最左推導(dǎo)：S<T><T,S><S,S><a,S><a,<T>><a,<T,S>><a,<S,S>><a,<a,S>><a,<a,a>>語(yǔ)法樹(shù)：如圖A-16所示。圖A-16<a,<a,a>>的語(yǔ)法樹(shù)〔2句型<T,a,<T>>的短語(yǔ)、直接短語(yǔ)、素短語(yǔ)、最左素短語(yǔ)、句柄、活前綴及語(yǔ)法樹(shù)〔圖A-17。短語(yǔ)：a||T,a||<T>||T,a,<T>||<T,a,<T>>直接短語(yǔ)：a||<T>素短語(yǔ)：a||<T>最左素短語(yǔ)：a句柄：a活前綴：||<||<T||<T,||<T,a圖A-17<T,a,<T>>的語(yǔ)法樹(shù)二、構(gòu)造下列正則表達(dá)式的確定性的有限狀態(tài)自動(dòng)機(jī)?！?2%aba<a|b>*a答：二、設(shè)={0,1}上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成,請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式,并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。<8分>答：構(gòu)造相應(yīng)的正規(guī)式：<0|1>*1<0|1><3分>NFA:<2分>111043211043200確定化：<3分>I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1