《編譯原理》考試試題及答案（附錄）一、 判斷題：TOC\o"1-5"\h\z一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。 （X）一個(gè)句型的直接短語是唯一的。 （X）已經(jīng)證明文法的二義性是可判定的。 （X）每個(gè)基本塊可用一個(gè)DAG表示。 （V）每個(gè)過程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （V）6.2型文法一定是3型文法。 （x）一個(gè)句型一定句子。 （X）算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。 （應(yīng)是最左素短語） （X）采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對中間代碼進(jìn)行優(yōu)化。 （V）編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 （x）一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 （x）目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 （）遞歸下降分析法是一種自下而上分析法。 （）并不是每個(gè)文法都能改寫成LL（1）文法。 （）15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 （ ）一個(gè)LL（1）文法一定是無二義的。 （）17.逆波蘭法表示的表達(dá)試亦稱前綴式。 （）18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 （）19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 （）一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 （ ）21.3型文法一定是2型文法。 （）22.如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。 （）二、 填空題：（最右推導(dǎo)）稱為規(guī)范推導(dǎo)。編譯過程可分為（詞法分析），（語法分析），（語義分析和中間代碼生成），（代碼優(yōu)化）和（目標(biāo)代碼生成）五個(gè)階段。TOC\o"1-5"\h\z如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（ ）。從功能上說，程序語言的語句大體可分為（ ）語句和（ ）語句兩大類。語法分析器的輸入是（ ），其輸出是（ ）。掃描器的任務(wù)是從（ ）中識別出一個(gè)個(gè)（ ）。符號表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（ ）等等。一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為（ ）。一個(gè)句型的最左直接短語稱為句型的（ ）。常用的兩種動(dòng)態(tài)存貯分配辦法是（ ）動(dòng)態(tài)分配和（ ）動(dòng)態(tài)分配。一個(gè)名字的屬性包括（ ）和（ ）。常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個(gè)級別。語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。預(yù)測分析程序是使用一張（ ）和一個(gè)（ ）進(jìn)行聯(lián)合控制的。常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為是（）態(tài);而且實(shí)際上至少要有一個(gè)（）態(tài)。根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ）,（ ）和（ ）三個(gè)級別。語法分析是依據(jù)語言的（ ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語言的（ ）規(guī)則進(jìn)行的。TOC\o"1-5"\h\z一個(gè)句型的最左直接短語稱為句型的（ ）。一個(gè)文法G，若它的預(yù)測分析表M不含多重定義，則該文法是（ ）文法。對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用（ ）策略，PASCAL采用（ ）策略。如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（ ）。最右推導(dǎo)亦稱為（ ），由此得到的句型稱為（ ）句型。語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。對于文法G，僅含終結(jié)符號的句型稱為（ ）。27.所謂自上而下分析法是指（）。28.語法分析器的輸入是（），其輸出是（）。29.局限于基本塊范圍的優(yōu)化稱（）。30.預(yù)測分析程序是使用一張（）和一個(gè)（）進(jìn)行聯(lián)合控制的。31.2型文法又稱為（）文法；3型文法又稱為（）文法。32.每條指令的執(zhí)行代價(jià)定義為（）。33.算符優(yōu)先分析法每次都是對（）進(jìn)行歸約。三、 名詞解釋題：局部優(yōu)化二義性文法DISPLAY表詞法分析器最左推導(dǎo)語法文法基本塊語法制導(dǎo)翻譯短語待用信息規(guī)范句型掃描器超前搜索15.句柄語法制導(dǎo)翻譯規(guī)范句型素短語語法待用信息語義四、 簡答題：寫一個(gè)文法G,使其語言為不以0開頭的偶數(shù)集。已知文法G（S）及相應(yīng)翻譯方案S^aAb{print"1”}S^a {print"2”}A-AS{print“3”}A^c {print"4”}輸入acab,輸出是什么？已知文法G（S）S-bAaA-（B|aB—Aa)寫出句子b(aa)b的規(guī)范歸約過程。考慮下面的程序：…procedurep(x,y,z)；beginy：=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A,A,B);PrintA,Bend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出A,B的值是什么?文法G(S)S—dABA—aA|aB—Bb|e描述的語言是什么？證明文法G(S)S—SaS|e是二義性的。已知文法G(S)S—BAA—BS|dB—aA|bS|c的預(yù)測分析表如下abcd#SS—BAS—BAS—BAAA—BSA—BSA—BSA—dBB—aAB—bSB—c給出句子adccd的分析過程。寫一個(gè)文法G,使其語言為L(G)={aibmc】anbn| l>=0,m>=1,n>=2}已知文法G(S):S—a|(T)T—T,S|S的優(yōu)先關(guān)系表如下： 關(guān)系a(),a.>.>(<.<.=.<.).>.>,<.<..>.>請計(jì)算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題?一字母表N={a,b},試寫出N上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式?；镜膬?yōu)化方法有哪幾種？寫一個(gè)文法G,使其語言為L(G)={abncn|n^G}考慮下面的程序：…procedurep(x,y,z);beginy：=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b,b,a);printaend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么?寫出表達(dá)式a+b*(c-d)/e的逆波蘭式和三元序列。證明文法G(A)A-AA|(A)|￡是二義性的。令S={a,b}，則正規(guī)式a*b|b*a表示的正規(guī)集是什么？何謂DISPLAY表？其作用是什么？2G.考慮下面的程序：…procedurep(x,y,z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b,a-b,a);printaend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？寫一個(gè)文法G,使其語言為L(G)={anbncm|n>G為奇數(shù)，m>G為偶數(shù)}寫出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。一個(gè)文法G別是LL(1)文法的充要條件是什么？已知文法G[S]S-S*aF|aF|*aFF-+aF|+a消除文法左遞歸和提公共左因子。符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？五、計(jì)算題：設(shè)文法G(S):S-"|a|⑴T-T,S|S⑴消除左遞歸；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；⑶構(gòu)造預(yù)測分析表語句ifEthenS改寫文法，使之適合語法制導(dǎo)翻譯；寫出改寫后產(chǎn)生式的語義動(dòng)作。設(shè)文法G(S)：S-(T)|aTT+S|S計(jì)算FIRSTVT和LASTVT；構(gòu)造優(yōu)先關(guān)系表。設(shè)某語言的for語句的形式為fori:=E⑴toE(2)doS其語義解釋為i:=E(i)LIMIT:=E(2)again:ifi<=LIMITthenBeginS;i:=i+1gotoagainEnd;寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；寫出每個(gè)產(chǎn)生式對應(yīng)的語義動(dòng)作。把語句whilea<10doifc>0thena:=a+1elsea:=a*3-1;翻譯成四元式序列。設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設(shè)基本塊出口時(shí)只有M還被引用，請寫出優(yōu)化后的四元序列。已知文法G(S)S-a|"|(T)TT,S|S給出句子(a,(a,a))的最左推導(dǎo)；給出句型((T,S),a)的短語，直接短語，句柄。對于C語言doSwhileE語句(1)改寫文法，使之適合語法制導(dǎo)翻譯；(2)寫出改寫后產(chǎn)生式的語義動(dòng)作。已知文法G(S)S^aAcBeA-Ab|bB—d給出句子abbcde的最左推導(dǎo)及畫出語法樹；給出句型aAbcde的短語、素短語。設(shè)文法G(S):S—(T)|aS|aT—T,S|S⑴消除左遞歸和提公共左因子；⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；⑶構(gòu)造預(yù)測分析表。把語句ifX>0vY<0thenwhileX>0doX:=A*3elseY:=B+3;翻譯成四元式序列。已知文法G(S)E—E+T|TT—T*F|FF—(E)|i給出句型(i+i)*i+i的最左推導(dǎo)及畫出語法樹；給出句型(E+T)*i+F的短語，素短語和最左素短語。設(shè)文法G(S)：S—T|SvTT—U|TaUU—i|-U計(jì)算FIRSTVT和LASTVT；構(gòu)造優(yōu)先關(guān)系表。參考答案一、 是非題：x 2.x 3.X 4.” 5.” 6.x 7.X 8.X 9.” 10.X 11.X” 13.X 14.” 15.” 16.” 17.X 18.” 19.” 20.X 21.” 22.”二、 填空題：（最右推導(dǎo)）（詞法分析），（語法分析），（中間代碼生成），（代碼優(yōu)化），（目標(biāo)代碼生成）（二義性的）（執(zhí)行性），（說明性）（單詞符號），（語法單位）。（源程序），（單詞符號）（類型、種屬、所占單元大小、地址）（現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址）（句柄）（棧式），（堆式）（類型），（作用域）（傳地址），（傳值），（傳名）（局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）（自上而下），（自下而上）（分析表），（符號棧）（傳地址），（傳值），（傳名）（初），（終）（局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）（語法），（語義）（句柄）（LL（1）文法）（靜態(tài)），（動(dòng)態(tài)）（二義性文法）（規(guī)范推導(dǎo)），（規(guī)范）（自上而下），（自下而上）（句子）（從開始符號出發(fā)，向下推導(dǎo)，推出句子）（單詞符號），（語法單位）（局部優(yōu)化）（分析表），（符號棧）（上下文無關(guān)文法），（正規(guī)）（指令訪問主存次數(shù)加1）（最左素短語）三、 名詞解釋題：局部優(yōu)化 局限于基本塊范圍的優(yōu)化稱。二義性文法 如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義性文法。DISPLAY表----過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動(dòng)記錄的起始地址。詞法分析器——執(zhí)行詞法分析的程序。最左推導(dǎo) 任何一步a二〉B都是對a中的最右非終結(jié)符替換。語法 一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。文法 描述語言的語法結(jié)構(gòu)的形式規(guī)則?；緣K 指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語句，出口就是其中的最后一個(gè)語句。語法制導(dǎo)翻譯 在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法制導(dǎo)翻譯。 冰短語 令G是一個(gè)文法，S劃文法的開始符號，假定aB5是文法G的一個(gè)句型，如果有S=>aA5且A三；B，則稱B是句型aB5相對非終結(jié)符A的短語。待用信息 如果在一個(gè)基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。規(guī)范句型 由規(guī)范推導(dǎo)所得到的句型。掃描器 執(zhí)行詞法分析的程序。超前搜索 在詞法分析過程中，有時(shí)為了確定詞性，需超前掃描若干個(gè)字符。句柄 一個(gè)句型的最左直接短語。語法制導(dǎo)翻譯 在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義程序進(jìn)行翻譯的方法叫做語法制導(dǎo)翻譯。規(guī)范句型 由規(guī)范推導(dǎo)所得到的句型。素短語 素短語是指這樣一個(gè)短語，至少含有一個(gè)終結(jié)符，并且，除它自身外不再含任何更小的素短語。語法 是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。一待用信息 如果在一個(gè)基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。語義 定義程序的意義的一組規(guī)則。四、簡答題：所求文法是G[S]:S-AB|BA0A-AD|CB-2|4|6|8C-1|3|5|7|9|BD-0|C輸出是4231句子b(aa)b的規(guī)范歸約過程: 步驟符號棧輸入串動(dòng)作0#b(aa)b#預(yù)備1#b(aa)b#移進(jìn)2#b(aa)b#移進(jìn)3#b(aa)b#移進(jìn)4#b(Aa)b#歸約5#b(Ma)b#移進(jìn)6#b(Ma)b#移進(jìn)7#b(Bb#歸約8#bAb#歸約9#bAb#移進(jìn)10#S#接受傳地址A=6,B=16傳值A(chǔ)=2,B=4L(G)={danbm|n>0,mN0}證明：因?yàn)槲姆℅[S]存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。S=〉SaS=〉SaSaS=〉aSaS=〉aaS=〉aa

S=>SaS=>aS=>aSaS=>aaS=>aa7.句子adccd的分析過程：步驟符號棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#S—BA2#AAaadccd#B—aA3#AAdccd#4#Addccd#A—d5#Accd#6#SBccd#A—BS7#Scccd#B—c8#Scd#9#ABcd#B—c10#Acd#11#Ad#12#dd#A—d13##8.所求文法是G[S]:S-ABA-aAc|DD—bD|bB—aBb|aabb目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題：如何使生成的目標(biāo)代碼較短；如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；如何充分利用指令系統(tǒng)的特點(diǎn)。正規(guī)式a(a|b)*。刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。文法G[S]:S—aB|aB—bc|bBc傳值a=2傳地址a=15逆波蘭式：abcd-*e/+三元序列： oparg1arg2(1)_cd(2)*b⑴(3)/(2)e(4)+a(3)證明：因?yàn)槲姆℅[S]存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。A=>AA=>(A)A=>()A=>()A=>AA=>A=>(A)=>()(a*b|b*a)={a,b,ab,ba,aab,bba }Display表：嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外層過程的最新活動(dòng)記錄起始地址，display表就是用于登記每個(gè)外層過程的最新活動(dòng)記錄起始地址。傳地址a=12傳值a=5所求文法是G[S]:S-ACA^aaAbb|abC^ccC|cc逆波蘭式abc+e*bc+f/+:=三元序列oparg1arg2(1)+bc(2)*(1)e(3)+bc(4)/(3)f(5)+(2)(4)(6):=a(5)一個(gè)文法G別是LL(1)文法的充要條件是：FIRST(a)CFIRST(B)=①如果B=*〉JFIRST(a)CFOLLOW(A)=①消除左遞歸S-aFS'|*aFS’S'f*aFS'|￡F-+aF|+a提公共左因子，文法G'(S)S-aFS'|*aFS'S'-*aFS'|￡F-+aF'F'-F|￡作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計(jì)算題：1.消除左遞，文法變?yōu)镚'[S]：S-"|a|(T)'T-ST'|ST'-,ST' |￡此文法無左公共左因子。構(gòu)造相應(yīng)的FIRST和FOLLOW集合：FIRST(S)={a,"(}，F(xiàn)OLLOW(S)={札，，)}

FIRST(T)={a,"(},FOLLOW(T)={}}FIRST(T’)={,,e},FOLLOW(F)={)}⑶構(gòu)造預(yù)測分析表：aA(),#SS—aS—AS—(T)'TT—ST’T—ST’T—ST’T’T’—￡T’—,ST’(1)C^ifEthenSTS⑴(2)C—ifEthen{BACK(E.TC,NXQ);C.chain:=E.FC}S-CS⑴{S.chain:=MERG(C.Chain,S(i).Chain)}(1)FIRSTVT(S)={a, (}FIRSTVT(T)={+,a,(}LASTVT(S)={a,)}LASTVT(T)={+,a,)}(2)aa+()a.>.>+<..><..>(<.<.<.).>.>>.(1)F—fori:=E(i)toE⑵doS—FS⑴(2)F—fori:=E(i)toE⑵do{GEN(:=,E(i).place,_,entry(i));F.place:=entry(i);LIMIT:=Newtemp;GEN(:=,E(2).place,_,LIMIT);Q:=NXQ;F.QUAD:=q;GEN(jW,entry(i),LIMIT,q+2)F.chain:=NXQ;GEN(j,_,_,0)}S—FS⑴{BACKPATCH(S(i).chain,NXQ);GEN(+,F.place,i,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain}5.(i)(j<,a,‘i0’，(3))(2)(j,_,_,(i2))(3)(j>,c,‘0’， (5))(4)(j,_,_,(8))(5)(+,a,T,Ti))(6)(:=,Ti,_,a)(7)(j,_,_,(i))(8)(*,a,‘i3’，T2)

(-,T2, ‘1’，T3)(:二,T3,_,a)(j,_,_, (1))優(yōu)化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+20最左推導(dǎo)S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))短語((T,S),a)(T,S),a(T,S)T,Sa直接短語T,Sa句柄T,S(1)S^doM]S1whileM2EM—8(2){M.quad=nestquad;}{backpatchg.nextlist,M{M.quad=nestquad;}{backpatchg.nextlist,M2.quad);backpatch(E.truelist,M.quad);S.nextlist=E.falelist;}S^doM]S1whileM2E(1)S=〉aAcBe=〉A(chǔ)AbcBe=〉abbcBe=〉abbcde(2)短語:aAbcde,Ab,d素短語：Ab,d(1)S-(L)|aS’S’一S|eL-SL’L'fL’|eFIRST(S')={a,(,e}FIRST(S')={a,(,e}FIRST(L’)={,,e}FOLLOW(S’)={,,),#}FOLLOW(L')={)}(3)()a,#SS-(L)S-aS’S’S’-SS’-eS’-SS’-eS’-eLL-SL’L-SL’L’一,SL’L’L’-eTOC\o"1-5"\h\z(1) (j>,X,0, (5))(j,_,_, (3))(j<,Y,0, (5))(j,_,_, (11))(j>0,X,0, (7))(j,_,_, (7))(*,A,3, T1)(:=,T『_, N)(j, _, _, (5))(j, _, _, (13))(+, B, 3, T2)(:=,T2,_, Y)(1)E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T=>(i+i)*i+F=>(i+i)*i+i(2)短語i,F,E+T,(E+T), (E+T)*i, (E+T)*i+F素短語i,E+T最左素短語E+T(1) FIRSTVT(S)={V, A,i,-}FIRSTVT(T)={八，i,-}FIRSTVT(U)={i,-}LASTVT(S)={V,A,i,-}LASTVT(T)={A,i,-}LASTVT(U)={i,-}(2)iVA-S.>.>V<..><.<.A<..>.><.<..>.><.一、單項(xiàng)選擇題將編譯程序分成若干個(gè)“遍”是為了（B）提高程序的執(zhí)行效率使程序的結(jié)構(gòu)更加清晰利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率不可能是目標(biāo)代碼的是（D）匯編指令代碼 B.可重定位指令代碼C.絕對指令代碼D.中間代碼詞法分析器的輸入是（B）

單詞符號串 B.源程序C.語法單位 。.目標(biāo)程序中間代碼生成時(shí)所遵循的是（C）A.語法規(guī)則 B.詞法規(guī)則C.語義規(guī)則 D.等價(jià)變換規(guī)則編譯程序是對（D）A.匯編程序的翻譯 B.高級語言程序的解釋執(zhí)行C.機(jī)器語言的執(zhí)行 D.高級語言的翻譯詞法分析應(yīng)遵循（C）A.語義規(guī)則 B.語法規(guī)則C.構(gòu)詞規(guī)則 D.等價(jià)變換規(guī)則詞法分析器的輸出結(jié)果是（C）A.單詞的種別編碼 B.單詞在符號表中的位置C.單詞的種別編碼和屬性值D.單詞屬性值8.正規(guī)式M1和M2等價(jià)是指（C）A.M1和M2的狀態(tài)數(shù)相等B.M1和M2的有向弧條數(shù)相等C.M1和M2所識別的語言集相等D.M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡潔、明確，因此，（B）詞法分析器應(yīng)作為獨(dú)立的一遍詞法分析器作為子程序較好詞法分析器分解為多個(gè)過程，由語法分析器選擇使用.詞法分析器并不作為一個(gè)獨(dú)立的階段如果L（M1）=L（M2）,則M1與M2（A）A.等價(jià) B.都是二義的C.都是無二義的D.它們的狀態(tài)數(shù)相等文法G：S-xSx|y所識別的語言是（C）A.xyxB.（xyx）* c.xnyxn（nNO） d.x*yx*文法G描述的語言L（G）是指（A）A.L(G)A.L(G)=ja|S=^a,aeV*B.L(G)=ja|S=^a,ae(VuVn)*C. C. L（G） = ]a | S=^a,a eV*] D. L（G） =]a|S=^a,a e（VuV）*有限狀態(tài)自動(dòng)機(jī)能識別（C）A.上下文無關(guān)文法 B.上下文有關(guān)文法C.正規(guī)文法 D.短語文法如果文法G是無二義的，則它的任何句子（A）最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同最左推導(dǎo)和最右推導(dǎo)必定相同可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是（C）A.短語B.句柄C.句型D.句子文法G：E—E+T|TTT*P|PP-(E)|i則句型P+T+i的句柄為(B)A.P+TB.PC.P+T+iD.i文法G：S-b|A|(T)T-TVS|S則FIRSTVT(T)=(C)A.{b，A，(}B.{b，A，)}C.{b，A，(，V}D.{b，A，），V}18.產(chǎn)生正規(guī)語言的文法為（D)A.0型B.1型C.2型D.3型任何算符優(yōu)先文法（D）優(yōu)先函數(shù)。A.有一個(gè)B.沒有C.有若干個(gè)D.可能有若干個(gè)采用自上而下分析，必須（C）A.消除左遞歸 B.消除右遞歸C.消除回溯 D.提取公共左因子在規(guī)范歸約中，用（B）來刻畫可歸約串。A.直接短語B.句柄C.最左素短語D.素短語有文法G：E-E*T|TT-T+i|i句子1+2*8+6按該文法G歸約，其值為（B）A.23B.42C.30D.17如果文法是無二義的，那么規(guī)范歸約是指（B）A.最左推導(dǎo)的逆過程 B.最右推導(dǎo)的逆過程C.規(guī)范推導(dǎo) D.最左歸約的逆過程文法G:S-S+T|TT-T*P|PP-（S）|i句型P+T+i的短語有（B）A.i,P+TB.P,P+T,i,P+T+iC.P+T+iD.P，P+T，四元式之間的聯(lián)系是通過（B）實(shí)現(xiàn)的。A.指示器B.臨時(shí)變量 C.符號表D.程序變量后綴式ab+cd+/可用表達(dá)式（B）來表示。a+b+c/dA.a+b/c+dB.（a+b）/（c+d）C.a+b/（c+d）D.a+b+c/d使用間接三元式表示法的主要目的（A）A.便于優(yōu)化處理 B.便于表的修改C.節(jié)省存儲(chǔ)空間 D.生成中間代碼更容易表達(dá)式SAVB）A（CVD）的逆波蘭表示為（B）A.nABVACDVB.AnBVCDVAC.ABVnCDVAD.AnBVACDV二、 判斷題TOC\o"1-5"\h\z一個(gè)確定有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 （X）設(shè)R和S分別是字母表工上的正規(guī)式，則有L（R|S）=L（R）UL（S）o（"）自動(dòng)機(jī)M1和M2的狀態(tài)數(shù)不同，則二者必不等價(jià)。 （X）確定有限自動(dòng)機(jī)以及非確定有限自動(dòng)機(jī)都能正確地識別正規(guī)集。 （”）對任意一個(gè)右線性正規(guī)文法G,都存在一個(gè)NFAM,滿足L（G）=L（M）。（”）對任意一個(gè)右線性正規(guī)文法G,都存在一個(gè)DFAM,滿足L（G）=L（M）。（”）對任何正規(guī)式e,都存在一個(gè)NFAM,滿足L（M）=L（e）。（”）對任何正規(guī)式e,都存在一個(gè)DFAM,滿足L（M）=L（e）。（”）從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程是唯一的。（X）詞法分析作為單獨(dú)的一遍來處理較好。 （X）一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。（X）二義文法不是上下文無關(guān)文法。（X）自上而下分析法是一種“移進(jìn)一歸約”法。（X）文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。（”）產(chǎn)生式是定義語法范疇的一種書寫規(guī)則。（”）要構(gòu)造行之有效的自上而下的分析器，則必須消除左遞歸。（X）如果文法G是無二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（”）自下而上的分析法是一種“移進(jìn)一歸約”法。（”）如果文法G是二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（X）三、 填空題解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)代碼）。編譯過程通常可分為5個(gè)階段，分別是（詞法分析）、（語法分析）、語義分析與中間代碼產(chǎn)生、代碼優(yōu)化和目標(biāo)代碼生成。編譯程序工作過程中，第一階段輸入是（源程序），最后階段的輸出為（目標(biāo)代碼）程序。把語法范疇翻譯成中間代碼所依據(jù)的是（語義規(guī)則）。目標(biāo)代碼可以是（匯編）指令代碼或（可重定位）指令代碼或絕對機(jī)器指令代碼。詞法分析的任務(wù)是：輸入源程序，對構(gòu)成源程序的（字符串）進(jìn)行掃描和分解。源程序中的錯(cuò)誤通常分為（語法錯(cuò)誤）和（語義錯(cuò)誤）兩大類。（編譯程序）是將源程序翻譯成目標(biāo)程序的程序。一個(gè)上下文無關(guān)文法G包括四個(gè)部分：（終結(jié)符號）、（非終結(jié)符號）、（開始符號）和一組（產(chǎn)生式）。若氣na2nna〃，則稱這個(gè)序列是從a1到a〃的一個(gè)（推導(dǎo)）。 一*設(shè)文法G的開始符號為S,如果Sna則稱a是l（G）的一個(gè)（句型）。文法G所產(chǎn)生的句子的全體是文法G所定義的（語言）。若一個(gè)文法存在某個(gè)句子對應(yīng)的兩棵不同的語法樹，則稱這個(gè)文法是（二義文法）。程序語言的單詞符號一般可分為五種：（關(guān)鍵字）、（標(biāo)識符）、常數(shù)、（運(yùn)算符）和界符。（確定有限自動(dòng)機(jī)DFA）是非確定有限自動(dòng)機(jī)NFA的一個(gè)特例。對于正規(guī)文法G和有限自動(dòng)機(jī)M,若L（G）=L（M），則稱G和M是（等價(jià)）的。17.若兩個(gè)正規(guī)式所表示的正規(guī)集相等，則認(rèn)為二者是（等價(jià)）的。按照語法分析樹的建立方法，語法分析可分為兩類：（自上而下分析）和（自下而上分析）。18.規(guī)范歸約中的可歸約串是指（句柄）。算符優(yōu)先分析中的可歸約串是指（最左素短語）。（自下而上）語法分析的關(guān)鍵問題是精確定義可歸約串的概念。四、簡答給出上下文無關(guān)文法的定義。一個(gè)上下文無關(guān)文法G是一個(gè)四元式（Vt，Vn，S,P）,其中：vt是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號；V：是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號，vtuvn=①；S、是一個(gè)非終結(jié)符號，稱為開始符號； TNP是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P-a，其中，PGVN，ae（VTUVN）*o開始符號s至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 NTN給出正規(guī)式與正規(guī)集的遞歸定義。（1） 8和①都是工上的正規(guī)式，它們所表示的正規(guī)集分別為3｝和①；（2） 任何a￡E，a是工上的一個(gè)正規(guī)式，它所表示的正規(guī)集為｛a｝；（3） 假定U和V都是工上的正規(guī)式，它們所表示的正規(guī)集分別記為L（U）和L（V），那么，（U|V）、（U?V）和（U）*也都是正規(guī)式，它們所表示的正規(guī)集分別為L（U）UL（V）、L（U）L（V）（連接積）和（L（U））*（閉包）。僅由有限次使用上述三步驟而得到的表達(dá)式才是工上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是工上的正規(guī)集。設(shè)文法G為：S-aAcB|BdSA-BaB|aBc|aB-aScA|cAB|b對于輸入串a(chǎn)acabccb，給出最左推導(dǎo)。S=〉aAcB=〉aaBccB=〉aacABccB=〉aacaBccB=〉aacabccB=〉aacabccb設(shè)文法G為：S-BAA-BS|dB-aA|bS|c對于輸入串a(chǎn)dccd，給出最左推導(dǎo)。S=〉BA=〉aAA=〉adA=〉adBS=〉adcS=〉adcBA=〉adccA=〉adccd證明：文法G：P-PaP|PbP|cP|Pe|f為二義文法。對于文法G定義的句子fbfbf，有兩棵不同的語法樹：所以該文法是二義文法。證明：文法G：P-S+S|S*S|i|(S)為二義文法。對于文法G定義的句子i+i*i,有兩棵不同的語法樹:所以該文法是二義文法。給定正規(guī)文法G:S—aS|bA|bA—aS請構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。給定正規(guī)文法G:S-aAA-bA|aB|bB—aA請構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。對下面給出的NFA確定化。10.11.對下面給出的NFA確定化。對下面給出的DFA最小化。bb13.有如下布爾表達(dá)式:a<band(c<dore<f)假定整個(gè)表達(dá)式的真假出口分別為Ltrue和Lfalse，請翻譯成三地址語句。ifa<bgotoL1gotoLfalseL1:ifc<dgotoLtruegotoL2L2:ife<fgotoLtruegotoLfalse14.有如下語句：ifa<bthenifc<dthenp:=a+1elsep:=b+1elsep:=c+1請翻譯成三地址語句。ifa<bgotoL1gotoL2L1:ifc<dgotoL3gotoL4L3:T1:=a+1p:=T1gotoLnextL4:T2:=b+1p:=T2gotoLnextL2:T3:=c+1p:=T3Lnext:…五、語法分析1.設(shè)有文法G:S-a|b|(A)A-SdA|S⑴完成下列算符優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法(請說明理由)。

ab()d#a?>?>?>b?>?>?>(<?<?<?=<?)?>?>?>d<?<?<??><??>#<?<?<?=由于該文法的任何產(chǎn)生的右部都不含兩個(gè)相繼的非終結(jié)符，故屬于算符文法。從上表可以看出，任何兩個(gè)終結(jié)符之間至少滿足=、＜?、?＞三種關(guān)系之一，故G為算符優(yōu)先文法。⑵給出句型(SdSdS)對應(yīng)的語法樹，指出該句型的短語、句柄△(A)TOC\o"1-5"\h\z短語：(SdSdS)SdSdSSdSS /|\句柄：S SdA/l\2.設(shè)有文法G: SdAS-S*F|FF—FfP|P SP—(S)|i⑴完成下列算符優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法(請說明理由)。*f()i#*?><?<??><??>f?>?><??><??>(<?<?<?=<?)?>?>?>?>i?>?>?>?>#<?<?<?<?=由于該文法的任何產(chǎn)生的右部都不含兩個(gè)相繼的非終結(jié)符，故屬于算符文法。從上表可以看出，任何兩個(gè)終結(jié)符之間至少滿足=、＜?、?＞三種關(guān)系之一，故G為算符優(yōu)先文法。⑵給出句型S*Pf(S)對應(yīng)的語法樹，指出該句型的短語、句柄短語：S*Pf(S)Pf(S)P(S)句柄：P一、單項(xiàng)選擇題（共10小題，每小題2分）（題分20分）1.語言是A.句子的集合C.符號串的集合編譯程序前三個(gè)階段完成的工作是詞法分析、語法分析和代碼優(yōu)化代碼生成、代碼優(yōu)化和詞法分析詞法分析、語法分析、語義分析和中間代碼生成詞法分析、語法分析和代碼優(yōu)化一個(gè)句型中稱為句柄的是該句型的最左A.非終結(jié)符號 B.短語C.句子D.直接短語下推自動(dòng)機(jī)識別的語言是A.0型語言 B.1型語言C.2型語言 D.3型語言掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個(gè)個(gè)具有獨(dú)立含義的最小語法單位即A.字符 B.單詞 C.句子 D.句型對應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是A.L0uL1uL2uL3C.L3=L2uL1uL0.詞法分析的任務(wù)是A.識別單詞C.識別句子.常用的中間代碼形式不含A.三元式 B.四元式代碼優(yōu)化的目的是A.節(jié)省時(shí)間C.節(jié)省時(shí)間和空間代碼生成階段的主要任務(wù)是把高級語言翻譯成匯編語言把高級語言翻譯成機(jī)器語言把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼把匯編語言翻譯成機(jī)器語言B.產(chǎn)生式的集合D?句型的集合B.L3uL2uL]UL0D.L0uL1uL2=L3B.分析句子的含義D.生成目標(biāo)代碼C.逆波蘭式 D.語法樹B.節(jié)省空間D.把編譯程序進(jìn)行等價(jià)交換二、填空題（本大題共5小題，每小題2分）（題分10分）1.編譯程序首先要識別出源程序中每個(gè)（），然后再分析每個(gè)（）并翻譯其意義。2.編譯器常用的語法分析方法有（）和（）兩種。3.通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的（），中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的（ ）。）方案和4.程序設(shè)計(jì)語言的發(fā)展帶來了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類，即： ）方案和）方案。5.對編譯程序而言，輸入數(shù)據(jù)是（5.對編譯程序而言，輸入數(shù)據(jù)是（），輸出結(jié)果是（)o三、名詞解釋題（共5小題，每小題4分）（題分20分）1.詞法分析2.LL（1）文法3.語法樹LR（0）分析器語言和文法四、簡答題（共4小題，每小題5分） （題分20分）1.編譯程序和高級語言有什么區(qū)別？編譯程序的工作分為那幾個(gè)階段？簡述自下而上的分析方法。簡述代碼優(yōu)化的目的和意義。五、 綜合應(yīng)用題（共3小題，每小題10分）（題分30分）證明下述文法G：SraSbSlaSId是二義性文法。對于文法G[S]：Stab，ArAalbB，BralSb求句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五（2）所示。圖五（2）句型baSb的的語法樹3.設(shè)有非確定的有自限動(dòng)機(jī)NFAM=({A,B,C},{0,1},8,{A},{C}),其中：5(A,0)={C}8(A,1)={A,B}8(B,1)={C}8(C,1)={C}。請畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。參考答案一、單項(xiàng)選擇題（共10小題，每小題2分，共20分）1.語言是句子的集合 B.產(chǎn)生式的集合符號串的集合 D?句型的集合編譯程序前三個(gè)階段完成的工作是詞法分析、語法分析和代碼優(yōu)化代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成詞法分析、語法分析和代碼優(yōu)化一個(gè)句型中稱為句柄的是該句型的最左A.非終結(jié)符號 B.短語C.句子D直接短語下推自動(dòng)機(jī)識別的語言是A.0型語言 B.1型語言2型語言 D.3型語言掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個(gè)個(gè)具有獨(dú)立含義的最小語法單位即A.字符 B一單詞 C.句子 D.句型對應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是A.L0UL1UL2UL3C.L3=L2UL]UL0B L3uL2uL1uL0D.L0uL1uL2=L37.詞法分析的任務(wù)是A,識別單詞B分析句子的含義C．識別句子D生成目標(biāo)代碼8.常用的中間代碼形式不含A.三元式 B.四元式C.逆波蘭式 D語法樹9.代碼優(yōu)化的目的是A.節(jié)省時(shí)間B節(jié)省空間-C,節(jié)省時(shí)間和空間D.把編譯程序進(jìn)行等價(jià)交換10.代碼生成階段的主要任務(wù)是把高級語言翻譯成匯編語言把高級語言翻譯成機(jī)器語言把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼把匯編語言翻譯成機(jī)器語言二、 填空題（本大題共5小題，每小題2分，共10分）編譯程序首先要識別出源程序中每個(gè)（單詞），然后再分析每個(gè)（句子）并翻譯其意義。編譯器常用的語法分析方法有（自底向上）和（自頂向下）兩種。通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的（分柝），中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的（綜合）。程序設(shè)計(jì)語言的發(fā)展帶來了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類,映靜態(tài)存儲(chǔ)分配）方案和（動(dòng)態(tài)存儲(chǔ)分配）方案。對編譯程序而言，輸入數(shù)據(jù)是（源程序），輸出結(jié)果是（目標(biāo)程序）。三、 名詞解釋題（共5小題，每小題4分，共20分）1.詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個(gè)個(gè)具有獨(dú)立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token),送給語法分析程序。2.LL(1)文法若文法的任何兩個(gè)產(chǎn)生式ATaiR都滿足下面兩個(gè)條件：FIRST(a)cFIRST(R)=饑若Rn*￡，那么FIRST(a)cFOLLOW(A)=饑我們把滿足這兩個(gè)條件的文法叫做兒(1)文法，其中的第一個(gè)L代表從左向右掃描輸入，第一.個(gè)「表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是一義的，也不含左遞歸。3.語法樹句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法G=(Vn，Vt，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：根節(jié)點(diǎn)的標(biāo)記是開始符號S。每個(gè)節(jié)點(diǎn)的標(biāo)記都是V中的一個(gè)符號。若一棵子樹的根節(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳