編譯技術(shù)期末試題及答案一、單項(xiàng)選擇題（每題3分，共30分）1.編譯程序是對（）。A.匯編程序的翻譯B.高級語言程序的翻譯C.機(jī)器語言的執(zhí)行D.高級語言的解釋執(zhí)行2.詞法分析器的輸出結(jié)果是（）。A.單詞的種別編碼B.單詞在符號表中的位置C.單詞的自身值D.單詞的種別編碼和自身值3.文法G：S→aS|b，該文法是（）。A.正則文法B.上下文無關(guān)文法C.上下文有關(guān)文法D.短語結(jié)構(gòu)文法4.算符優(yōu)先分析法每次都是對（）進(jìn)行歸約。A.最左直接短語B.最左素短語C.句柄D.最左短語5.一個(gè)句型中的最左（）稱為該句型的句柄。A.短語B.直接短語C.素短語D.終結(jié)符號6.代碼優(yōu)化的目的是（）。A.節(jié)省時(shí)間B.節(jié)省空間C.節(jié)省時(shí)間和空間D.把編譯程序進(jìn)行等價(jià)變換7.編譯程序使用（）區(qū)別標(biāo)識符的作用域。A.說明標(biāo)識符的過程或函數(shù)名B.說明標(biāo)識符的語句行號C.說明標(biāo)識符的塊號D.說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次8.中間代碼生成時(shí)所依據(jù)的是（）。A.詞法規(guī)則B.語法規(guī)則C.語義規(guī)則D.等價(jià)變換規(guī)則9.若項(xiàng)目集Ik含有A→α·，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號a∈FOLLOW(A)時(shí)，才采取“用A→α歸約”的動作的一定是（）。A.LALR分析法B.LR(0)分析法C.SLR(1)分析法D.LR(1)分析法10.一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是一組非終結(jié)符號，一組終結(jié)符號，一個(gè)開始符號，以及一組（）。A.句子B.句型C.單詞D.產(chǎn)生式二、判斷題（每題2分，共20分）1.編譯程序是一種解釋程序。（）2.詞法分析和語法分析本質(zhì)上都是對源程序的掃描。（）3.一個(gè)文法所有句型的集合形成該文法所能接受的語言。（）4.算符優(yōu)先分析法是一種自頂向下的語法分析方法。（）5.一個(gè)句型的句柄一定是該句型的最左直接短語。（）6.代碼優(yōu)化只能在目標(biāo)代碼生成之后進(jìn)行。（）7.符號表的作用是記錄源程序中各個(gè)標(biāo)識符的屬性和特征。（）8.中間代碼不依賴于具體的計(jì)算機(jī)。（）9.LR分析法是一種自底向上的語法分析方法。（）10.上下文無關(guān)文法可以描述所有的自然語言。（）三、簡答題（每題10分，共30分）1.簡述編譯程序的工作過程。2.什么是算符優(yōu)先關(guān)系？如何確定算符之間的優(yōu)先關(guān)系？3.簡述代碼優(yōu)化的主要類型和優(yōu)化的一般原則。四、綜合題（每題20分，共20分）已知文法G[S]：S→aAA→bA|c（1）構(gòu)造該文法的FIRST集和FOLLOW集。（2）判斷該文法是否為LL(1)文法，若是，給出理由；若不是，說明如何將其改造為LL(1)文法。答案一、單項(xiàng)選擇題1.B。編譯程序的主要功能是將高級語言程序翻譯成目標(biāo)機(jī)器能夠執(zhí)行的機(jī)器語言程序。2.D。詞法分析器將源程序的字符流識別為一個(gè)個(gè)單詞，輸出單詞的種別編碼和自身值。3.A。該文法的產(chǎn)生式形式符合正則文法的定義，即右部最多只有一個(gè)非終結(jié)符且在最右邊。4.B。算符優(yōu)先分析法每次歸約的是最左素短語。5.B。一個(gè)句型中的最左直接短語稱為該句型的句柄。6.C。代碼優(yōu)化的目的是節(jié)省程序運(yùn)行的時(shí)間和占用的空間。7.D。編譯程序使用說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次區(qū)別標(biāo)識符的作用域。8.C。中間代碼生成時(shí)依據(jù)語義規(guī)則對語法分析的結(jié)果進(jìn)行語義處理。9.C。SLR(1)分析法在面臨輸入符號時(shí)，根據(jù)FOLLOW集確定歸約動作。10.D。上下文無關(guān)文法由非終結(jié)符號、終結(jié)符號、開始符號和產(chǎn)生式組成。二、判斷題1.×。編譯程序是將源程序一次性翻譯成目標(biāo)程序，而解釋程序是邊解釋邊執(zhí)行，二者不同。2.√。詞法分析掃描源程序的字符流識別單詞，語法分析掃描單詞序列分析語法結(jié)構(gòu)。3.×。一個(gè)文法所有句子的集合形成該文法所能接受的語言，句型包含句子和非終結(jié)符。4.×。算符優(yōu)先分析法是一種自底向上的語法分析方法。5.√。句柄的定義就是最左直接短語。6.×。代碼優(yōu)化可以在中間代碼生成階段和目標(biāo)代碼生成階段進(jìn)行。7.√。符號表用于記錄標(biāo)識符的屬性和特征，方便編譯過程中的管理。8.√。中間代碼是一種獨(dú)立于具體計(jì)算機(jī)的中間表示形式。9.√。LR分析法通過自底向上的方式進(jìn)行語法分析。10.×。上下文無關(guān)文法不能描述所有的自然語言，自然語言具有復(fù)雜的語義和語境。三、簡答題1.編譯程序的工作過程通常分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六個(gè)階段。詞法分析：對源程序的字符流進(jìn)行掃描，識別出一個(gè)個(gè)單詞。語法分析：根據(jù)語法規(guī)則，對單詞序列進(jìn)行分析，判斷其是否符合語法結(jié)構(gòu)。語義分析：對語法分析的結(jié)果進(jìn)行語義檢查和處理，確定其含義。中間代碼生成：將源程序轉(zhuǎn)換為一種中間表示形式，便于后續(xù)的優(yōu)化和目標(biāo)代碼生成。代碼優(yōu)化：對中間代碼進(jìn)行優(yōu)化，提高程序的執(zhí)行效率和節(jié)省空間。目標(biāo)代碼生成：將優(yōu)化后的中間代碼轉(zhuǎn)換為目標(biāo)機(jī)器能夠執(zhí)行的機(jī)器語言程序。2.算符優(yōu)先關(guān)系是指在算符優(yōu)先分析法中，算符之間的優(yōu)先順序關(guān)系。確定算符之間優(yōu)先關(guān)系的方法如下：首先構(gòu)造算符優(yōu)先關(guān)系表?？梢酝ㄟ^定義算符之間的優(yōu)先關(guān)系規(guī)則，如規(guī)定某些算符的優(yōu)先級高于其他算符。對于給定的文法，根據(jù)產(chǎn)生式的形式確定算符之間的相鄰關(guān)系，進(jìn)而確定優(yōu)先關(guān)系。例如，如果產(chǎn)生式中有相鄰的算符，根據(jù)其在產(chǎn)生式中的位置和文法的語義確定優(yōu)先順序。3.代碼優(yōu)化的主要類型包括局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。局部優(yōu)化：在基本塊內(nèi)進(jìn)行的優(yōu)化，如刪除冗余運(yùn)算、合并常量等。循環(huán)優(yōu)化：對循環(huán)結(jié)構(gòu)進(jìn)行的優(yōu)化，如循環(huán)不變代碼外提、強(qiáng)度削弱等。全局優(yōu)化：在整個(gè)程序范圍內(nèi)進(jìn)行的優(yōu)化，如公共子表達(dá)式刪除等。優(yōu)化的一般原則包括等價(jià)原則、有效原則和合算原則。等價(jià)原則要求優(yōu)化后的代碼與原代碼在邏輯上等價(jià)；有效原則要求優(yōu)化后的代碼在時(shí)間和空間上更高效；合算原則要求優(yōu)化的成本要低于優(yōu)化帶來的收益。四、綜合題（1）FIRST集：FIRST(S)={a}FIRST(A)={b,c}FOLLOW集：FOLLOW(S)={}FOLLOW(A)={}（2）計(jì)算SELECT集：對于產(chǎn)生式S→aA，SELECT(S→aA)={a}對于產(chǎn)生式A→bA，SELECT(A→bA)