編譯原理第1頁共1頁《編譯原理》課程綜合復(fù)習(xí)資料一、單選題1．文法：G：S→xSx|y所識別的語言是（）。A.xyxB.(xyx)*C.x*yx*D.xnyxn(n≥0)答案：D2．若狀態(tài)k含有項(xiàng)目“A→α·”，且僅當(dāng)輸入符號a∈FOLLOW(A)時(shí)，才用規(guī)則“A→α”歸約的語法分析方法是（）。A.LALR分析法B.LR(0)分析法C.LR(1)分析法D.SLR(1)分析法答案：D3．詞法分析器的輸出結(jié)果是（）。A.單詞自身值B.單詞在符號表中的位置C.單詞的種別編碼D.單詞的種別編碼和自身值答案：D4．給定文法A→bA|ca，為該文法句子的是（）。A.bbaB.cabC.bcaD.cba答案：C5．若B為非終結(jié)符，則A→·B為（）。A.移進(jìn)項(xiàng)目B.歸約項(xiàng)目 C.接受項(xiàng)目 D.待約項(xiàng)目答案：D6．就文法的描述能力來說，有（）。A.SLR(1)?LR(0)B.LR(1)?LR(0)C.SLR(1)?LR(1)D.無二義文法?LR(1)答案：C7．如圖所示自動(dòng)機(jī)M，請問下列哪個(gè)字符串不是M所能識別的（）。A.bbaa B.abba C.abab D.aabb答案：D8．文法G：S→xSx|y所識別的語言是（）。A.xyxB.(xyx)*C.xnyxn(n≥0)D.x*yx*答案：C9．表達(dá)式(┐A∨B)∧(C∨D)的逆波蘭表示為（）。A.┐AB∨∧CD∨B.A┐B∨CD∨∧C.AB∨┐CD∨∧D.A┐B∨∧CD∨答案：B10．如果文法G是無二義的，則它的任何句子α（）。A.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同答案：A11．編譯原理是對（）。A.機(jī)器語言的執(zhí)行B.匯編語言的翻譯C.高級語言的翻譯D.高級語言程序的解釋執(zhí)行答案：C12．通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，語義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等六個(gè)部分，還應(yīng)包括（）。A.模擬執(zhí)行器B.解釋器C.表格處理和出錯(cuò)處理D.符號執(zhí)行器答案：C13．若a為終結(jié)符，則A→α·aβ為（）項(xiàng)目。A.歸約B.移進(jìn)C.接受D.待約答案：B14．文法S→aaS|abc定義的語言是（）。A.{a2kbc|k>0}B.{akbc|k>0} C.{a2k-1bc|k>0}D.{akakbc|k>0}答案：C15．兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的（）。A.狀態(tài)數(shù)相等B.有向弧數(shù)相等C.所識別的語言相等D.狀態(tài)數(shù)和有向弧數(shù)相等答案：C二、判斷題1．正則文法其產(chǎn)生式為A->a，A->Bb，A,B∈VN，a、b∈VT。答案：錯(cuò)2．自上而下分析法是一種“移進(jìn)—?dú)w約”法。答案：錯(cuò)3．進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。答案：錯(cuò)4．產(chǎn)生式是定義語法范疇的一種書寫規(guī)則。答案：對5．要構(gòu)造行之有效的自上而下的分析器，則必須消除左遞歸。答案：錯(cuò)6．一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。答案：對7．自下而上的分析法是一種“移進(jìn)—?dú)w約”法。答案：對8．如果文法G是二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。答案：錯(cuò)9．編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。答案：錯(cuò)10．計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。答案：錯(cuò)11．遞歸下降法允許任一非終極符是直接左遞歸的。答案：對12．文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。答案：對13．靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。答案：錯(cuò)14．如果文法G是無二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。答案：對15．逆波蘭法表示的表達(dá)式亦稱前綴式。答案：對三、問答題1．給出與正規(guī)式R＝（ab）*（a|b*）ba等價(jià)的NFA。答案：與正規(guī)式R等價(jià)的NFA如下圖：2．文法G[E]為：E→E+T|TT→T*F|FF→(E)|i試給出句型(E+F)*i的短語，簡單(直接)短語，句柄和最左素短語。答案：短語有：(E+F)*i，(E+F)，E+F，F(xiàn)，i簡單(直接)短語有：F，i句柄是：F最左素短語是：E+F3．寫出表達(dá)式(a+b)/(a-b)-a(a+b*c)的三元式序列。答案：⑴.(+,a,b)⑵.(-,a,b)⑶.(/,⑴,⑵)⑷.(*,b,c)⑸.(+,a,⑷)⑹.(-,⑶,⑸)4．翻譯成四元式序列。Whilea＞0∨b＜0doBeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；答案：(1)(j>,a,0,(3))如果a大于0，跳轉(zhuǎn)到標(biāo)記為(3)的位置。(2)(j<,b,0,(3))如果b小于0，跳轉(zhuǎn)到標(biāo)記為(3)的位置。(3)(j,,,(9))否則，跳轉(zhuǎn)到標(biāo)記為(9)的位置。(4)(:=,X,,X+1)計(jì)算X+1并將結(jié)果賦給變量X。(5)(j>,a,0,(7))如果a大于0，跳轉(zhuǎn)到標(biāo)記為(7)的位置。(6)(j,,,(8))否則，無條件跳轉(zhuǎn)到標(biāo)記為(8)的位置。(7)(:=,a,,a-1)將a-1的結(jié)果賦給變量a。(8)(j,,,(9))無條件跳轉(zhuǎn)到標(biāo)記為(9)的位置。(9)(j>,a,0,(11))如果a大于0，跳轉(zhuǎn)到標(biāo)記為(11)的位置。(10)(j,,,(12))否則，無條件跳轉(zhuǎn)到標(biāo)記為(12)的位置。(11)(:=,b,,b+1)將b+1的結(jié)果賦給變量b。(12)(...)標(biāo)記(12)指示循環(huán)結(jié)束。5．給出文法G[S]的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。G[S]為：S→D;D|DD→DB|BB→a|bI0:答案：I0:四、綜合題1．判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表。S→aHH→aMd|dM→Ab|εA→aM|e答案：首先計(jì)算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集S{a}{#}H{a，d}{#}M{a，e，ε}{d，b}A{a，e}由于predict（H→aMd）∩predict（H→d）={a}∩egc6eka=predict（M→Ab）∩predict（M→ε）={a，e}∩{d，b}=predict（A→aM）∩predict（A→e）={a}∩{e}=所以該文法是LL(1)文法，LL(1)分析表如下表。adbe#S→aHH→aMd→dM→Ab→ε→ε→AbA→aM→e2．某語言的文法G為：E→aTd|εT→Eb|a證明G不是LR(0)文法而是SLR(1)文法，請給出該文法的SLR(1)分析表。答案：拓廣文法G'，增加產(chǎn)生式S'→E在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目E→·aTd和歸約項(xiàng)目E→·存在移進(jìn)-歸約沖突，所以G不是LR(0)文法。.若產(chǎn)生式排序?yàn)椋?0)S′→E(1)E→aTd(2)E→ε(3)T→Eb(4)T→aG′的LR(0)項(xiàng)目集族及識別活前綴的DFA如下圖：由產(chǎn)生式知：Follow(E)={#，b}Follow(T)=6eukec6在I0，I2中：Follow(E)∩{a}={#，b}∩{a}=在I5中：Follow(E)∩{a}={#，b}∩{a}=Follow(T)∩{a}=66ci46g∩{a}=Follow(T)∩Follow(E)=666smk6∩{#，b}=所以在I0，I2，I5中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決，所以G′是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r33．給定文法G[S]：S→ABA→aB|bS|cB→AS|d⑴請給出每一個(gè)產(chǎn)生式右部的First集；⑵請給出每一個(gè)非終結(jié)符號的Follow集；⑶請構(gòu)造該文法的LL(1)分析表；⑷什么是LL(1)文法？該文法是LL(1)文法嗎？為什么？答案：（1）First(AB)={a，b，c}First(aB)={a}First(bS)=First(c)={c}First(AS)={a，b，c}First(d)=aiymkwu（2）Follow(S)={#，a，b，c，d}Follow(A)={a，b，c，d}Follow(B)={#，a，b，c，d}（3）LL(1)分析表VNVTabcd#SS→ABS→ABS→ABAA→aBA→bSA→CBB→ASB→ASB→ASB→d（4）對于文法G的每一個(gè)非終結(jié)符U的產(chǎn)生式U→α1|α2|…|αn，如果SELECT(U→αi)→SELECT(U→αj)=→（i≠j,i,j=1,2,…,n），則文法G是一個(gè)LL(1)文法。該文法是LL(1)文法。因?yàn)镾ELECT(A→aB)→SELECT(A→bS)→SELECT(A→C)=→SELECT(B→AS)→SELECT(B→d)=→4．給定文法G[S]：S→SaA|aA→AbS|b⑴請構(gòu)造該文法的以LR(0)項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的DFA。⑵請構(gòu)造該文法的LR(0)分析表。⑶什么是LR(0)文法？該文法是LR(0)文法嗎？為什么？⑷什么是SLR(1)文法？該文法是SLR(1)文法嗎？為什么？答案：⑴拓廣文法G[S′]:S′→S⑴S→SaA⑵S→a⑶A→AbS⑷A→b⑸該文法的以LR(0)項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的DFA：⑵該文法的LR(0)分析表：狀態(tài)ACTIONGOTOab#SA0S211S3acc2r3r3r33S544r2r2/S6r25r5r5r56S277r4/S3r4r4⑶LR(0)文法：該文法的以LR(0)項(xiàng)目集為狀態(tài)的識別規(guī)范句型活前綴的DFA中沒有沖突狀態(tài)。該文法不是LR(0)文法因?yàn)榇嬖跊_突狀態(tài)：I4和I7⑷SLR(1