《編譯原理》期末模擬試題及答案一、是非題(請在括號內(nèi)，正確的劃4錯誤的劃x)(每個2分，共20分)1.對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。(x)2．甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。(x)3．遞歸下降分析法是自頂向上分析方法。(4)4．產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。(x)5．LR法是自頂向下語法分析方法。(4).在SLR(1)分析法的名稱中，S的含義是簡單的。(4).綜合屬性是用于“自上而下”傳遞信息。(x)8．符號表中的信息欄中登記了每個名字的屬性和特征等有關(guān)信息，0類型、種屬、所占單元大小、地址等等。(x)9．程序語言的語言處理程序是一種應(yīng)用軟件。(x)10．解釋程序適用于COBOL和FORTRAN語言。(x)二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)文法G產(chǎn)生的的全體是該文法描述的語言。A．()句型B．()終結(jié)符集C．()非終結(jié)符集D．()句子若文法G定義的語言是無限集，則文法必然是。A．A．()遞歸的C．()二義性的B．()前后文無關(guān)的D．()無二義性的四種形式語言文法中，1型文法又稱為文法。A．()短語結(jié)構(gòu)文法B．()前后文無關(guān)文法C．()前后文有關(guān)文法D．()正規(guī)文法一個文法所描述的語言是。A．()唯一的B．()不唯一的C．()可能唯一，好可能不唯一D．()都不對和代碼優(yōu)化部分不是每個編譯程序都必需的。A．()語法分析B．()中間代碼生成C．()詞法分析D．()目標(biāo)代碼生成是兩類程序語言處理程序。A．()高級語言程序和低級語言程序B．()解釋程序和編譯程序C．()編譯程序和操作系統(tǒng)D．()系統(tǒng)程序和應(yīng)用程序數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的的信息。A.()維數(shù)B．()類型C．()維上下界D．()各維的界差一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號一個開始符號，以及一組。A．()句子B．()句型C．()單詞D．()產(chǎn)生式文法分為四種類型，即0型、1型、2型、3型。其中2型文法是。A.()短語文法B．()正則文法C．()上下文有關(guān)文法D．()上下文無關(guān)文法10．文法G所描述的語言是的集合。A.()文法G的字母表V中所有符號組成的符號串B．()文法G的字母表V的閉包V*中的所有符號串C．()由文法的開始符號推出的所有終極符串D.()由文法的開始符號推出的所有符號串三、填空題(每空1分，共10分)1．一個句型中的最左簡單短語稱為該句型的___句柄__。2．對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為__語義規(guī)則___。3．一個典型的編譯程序中，不僅包括__詞法分析___、__語法分析___、__中間代碼生成___、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。從功能上說，程序語言的語句大體可分為__執(zhí)行性___語句和__說明性___語句兩大類。掃描器的任務(wù)是從__源程序___中識別出一個個___單詞符號__。產(chǎn)生式是用于定義__語法范疇___的一種書寫規(guī)則。四、簡答題(20分).寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。解：文法G(N)：N—AB|BA—AC|DB-1|3|5|7|9D—B|2|4|6|8Ct0|D.設(shè)文法G(S)：S—(L)|aS|aL—L,sis(1)消除左遞歸和回溯；(2)計算每個非終結(jié)符的FIRST和FOLLOW。

解：(1)S—(L)|aS'FOLLOW(S)={#,,,FOLLOW(S)={#,,,)}FOLLOW(S')={#,,,)}FOLLOW(L)={)}FOLLOW(L'〕={)}FIRST)S)={(,a}FIRST(S')={,a,￡}FIRST(L)={(,a}FIRST(L')={,,￡}.已知文法G(E)E—T|E＋TT—F|T*FF—(E)|i(1)給出句型(1*F+i)的最右推導(dǎo)；(2)給出句型(1*F+i)的短語、素短語。解：(1)最右推導(dǎo)：E->T->F->(E)->(E＋T)->(E＋F)->(E＋i)->(T＋i)->(T*F＋i)(2)短語：(T*F+i),T*F+i,T*F,i素短語：T*F,i.Whilea>0Vb<0doBeginX：=X+1；ifa>0thena：=a—1elseb：=b+1End；翻譯成四元式序列。解：(j>,a,0,5)(j，—，—，3)(j<,b,0,5)(j,—,—,15)(5)(+,x,1,T1)

(：=,T1,一,x)⑺位，a,0,9)(j，－，－，12)(－,a,1,T2)(：=,T2,一,a)(j,－,－,1)(＋,b,1,T3)(：=,T3,一,b)(j,－,－,1)五.計算題（10分）已知NFA=({x,y,z},{0,1},M,{x},{z}),其中：并最小化。M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x},M(y,1)=p,M(z,1)={y},構(gòu)造相應(yīng)的DFA并最小化。IIo-e-closurs(Move萬江())).Ii-c-dosure(Move克茂說A[k]A[k]E團CEkjz]D[y]C氏z]C區(qū)z]E區(qū)y]：D[y]：E區(qū)y]-E區(qū)y]fN,交工］A[k]；F[x;弘z]F[x;z]E[k,y]換為DFA下面將該DFA最小化：(1)首先將它的狀態(tài)集分成兩個子集：P1={A,D,E},P2={B,C,F}(2)區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F,C等價。由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D,E不等價(見下步)，從而B與C,F可以區(qū)分。有P21={C,F},P22={B}。(3)區(qū)分P1:由于A,E輸入0到終態(tài)，而D輸入0不到終