《編譯原理》考試試題及答案.doc
《《編譯原理》考試試題及答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《編譯原理》考試試題及答案.doc（27頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
《編譯原理》考試試題及答案（附錄） 一、判斷題： 1.一個(gè)上下文無(wú)關(guān)文法的開(kāi)始符，可以是終結(jié)符或非終結(jié)符。 ( X ) 2.一個(gè)句型的直接短語(yǔ)是唯一的。 ( X ) 3.已經(jīng)證明文法的二義性是可判定的。 （ X ） 4.每個(gè)基本塊可用一個(gè)DAG表示。 （ √ ） 5.每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （ √ ） 6.2型文法一定是3型文法。 （ x ） 7.一個(gè)句型一定句子。 ( X ) 8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 (應(yīng)是最左素短語(yǔ)) ( X ) 9.采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 （ √ ） 10.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ( x ) 11.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( x ) 12.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( ) 13.遞歸下降分析法是一種自下而上分析法。 ( ) 14.并不是每個(gè)文法都能改寫(xiě)成LL(1)文法。 ( ) 15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 ( ) 16.一個(gè)LL(1)文法一定是無(wú)二義的。 ( ) 17.逆波蘭法表示的表達(dá)試亦稱前綴式。 ( ) 18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( ) 19.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ( ) 20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。 ( ) 二、填空題： 1.( 最右推導(dǎo) )稱為規(guī)范推導(dǎo)。 2.編譯過(guò)程可分為 （ 詞法分析 ） ，（語(yǔ)法分析），（語(yǔ)義分析和中間代碼生成），（代碼優(yōu)化）和（目標(biāo)代碼生成）五個(gè)階段。 3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是（ ）。 4.從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（ ）語(yǔ)句和（ ）語(yǔ)句兩大類。 5.語(yǔ)法分析器的輸入是（ ），其輸出是（ ）。 6.掃描器的任務(wù)是從（ ）中識(shí)別出一個(gè)個(gè)（ ）。 7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（ ）等等。 8.一個(gè)過(guò)程相應(yīng)的DISPLAY表的內(nèi)容為（ ）。 9.一個(gè)句型的最左直接短語(yǔ)稱為句型的（ ）。 10.常用的兩種動(dòng)態(tài)存貯分配辦法是（ ）動(dòng)態(tài)分配和（ ）動(dòng)態(tài)分配。 11.一個(gè)名字的屬性包括( )和( )。 12.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。 13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個(gè)級(jí)別。 14.語(yǔ)法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。 15.預(yù)測(cè)分析程序是使用一張（ ）和一個(gè)（ ）進(jìn)行聯(lián)合控制的。 16.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。 17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為是（ ）態(tài);而且實(shí)際上至少要有一個(gè)（ ）態(tài)。 18.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個(gè)級(jí)別。 19.語(yǔ)法分析是依據(jù)語(yǔ)言的（ ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（ ）規(guī)則進(jìn)行的。 20.一個(gè)句型的最左直接短語(yǔ)稱為句型的（ ）。 21.一個(gè)文法G，若它的預(yù)測(cè)分析表M不含多重定義，則該文法是（ ）文法。 22.對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN采用( )策略， PASCAL采用( )策略。 23.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)， 則稱這個(gè)文法是( )。 24.最右推導(dǎo)亦稱為（ ），由此得到的句型稱為（ ）句型。 25.語(yǔ)法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。 26.對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱為 ( )。 27.所謂自上而下分析法是指（ ）。 28.語(yǔ)法分析器的輸入是（ ），其輸出是（ ）。 29.局限于基本塊范圍的優(yōu)化稱（ ）。 30.預(yù)測(cè)分析程序是使用一張（ ）和一個(gè)（ ）進(jìn)行聯(lián)合控制的。 31.2型文法又稱為（ ）文法；3型文法又稱為（ ）文法。 32.每條指令的執(zhí)行代價(jià)定義為（ ）。 33.算符優(yōu)先分析法每次都是對(duì)（ ）進(jìn)行歸約。 三、名詞解釋題： 1.局部?jī)?yōu)化 2.二義性文法 3.DISPLAY表 4.詞法分析器 5.最左推導(dǎo) 6.語(yǔ)法 7.文法 8.基本塊 9.語(yǔ)法制導(dǎo)翻譯 10.短語(yǔ) 11.待用信息 12.規(guī)范句型 13.掃描器 14.超前搜索 15.句柄 16.語(yǔ)法制導(dǎo)翻譯 17.規(guī)范句型 18.素短語(yǔ) 19.語(yǔ)法 20.待用信息 21.語(yǔ)義 四、簡(jiǎn)答題： 1.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 不以0開(kāi)頭的偶數(shù)集。 2.已知文法G(S)及相應(yīng)翻譯方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 輸入acab, 輸出是什么？ 3. 已知文法G(S) S→bAa A→(B | a B→Aa) 寫(xiě)出句子b(aa)b的規(guī)范歸約過(guò)程。 4. 考慮下面的程序： … procedure p(x, y, z)； begin y:=x+y; z:=z*z; end begin A:=2; B:=A*2; P(A, A, B); Print A, B end. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 A, B的值是什么? 5.文法G(S) S→dAB A→aA| a B→Bb| ε 描述的語(yǔ)言是什么？ 6.證明文法G(S) S→SaS| ε 是二義性的。 7.已知文法G(S) S→BA A→BS| d B→aA| bS | c 的預(yù)測(cè)分析表如下 a b c d # S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c 給出句子 adccd 的分析過(guò)程。 8.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)={albmclanbn| l>=0, m>=1, n>=2} 9.已知文法G(S): S→a| (T) T→T,S|S 的優(yōu)先關(guān)系表如下： 關(guān)系 a ( ) , a - - .> .> ( <. <. =. <. ) - - .> .> , <. <. .> .> 請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。 10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？ 11.目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？ 12.一字母表Σ={a, b}，試寫(xiě)出Σ上所有以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。 13.基本的優(yōu)化方法有哪幾種？ 14.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)={abncn| n≥0} 15.考慮下面的程序： … procedure p(x, y, z); begin y:=y+z; z:=y*z+x end; begin a:=2; b:=3; p(a+b, b, a); print a end. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a的值是什么? 16.寫(xiě)出表達(dá)式a＋b*(c-d)/e的逆波蘭式和三元序列。 17.證明文法G(A) A→AA | (A)| ε 是二義性的。 18.令Σ={a,b}，則正規(guī)式a*b|b*a 表示的正規(guī)集是什么？ 19.何謂DISPLAY表？其作用是什么？ 20.考慮下面的程序： … procedure p(x, y, z)； begin y:=y+2; z:=z+x; end begin a:=5; b:=2; p(a+b, a-b, a); print a end. 試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a的值是什么? 21.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)={anbncm| n>0為奇數(shù)， m>0為偶數(shù)} 22.寫(xiě)出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。 23.一個(gè)文法G別是LL(1)文法的充要條件是什么？ 24.已知文法G[S] S→S*aF | aF | *aF F→+aF | +a 消除文法左遞歸和提公共左因子。 25.符號(hào)表的作用是什么？符號(hào)表查找和整理技術(shù)有哪幾種？ 五、計(jì)算題： 1.設(shè)文法G(S): S→^ | a | (T) T→T,S | S ⑴ 消除左遞歸； ⑵ 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； ⑶ 構(gòu)造預(yù)測(cè)分析表 2.語(yǔ)句 if E then S (1) 改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯； (2) 寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。 3.設(shè)文法G（S）： S→(T) | a T→T+S | S (1）計(jì)算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 4.設(shè)某語(yǔ)言的for語(yǔ)句的形式為 for i:＝E(1) to E(2) do S 其語(yǔ)義解釋為 i:＝E(1) LIMIT:＝E(2) again: if i＜＝LIMIT then Begin S; i:＝i＋1 goto again End; （1）寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式； （2）寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。 5.把語(yǔ)句 while a<10 do if c>0 then a:=a+1 else a:=a*3-1; 翻譯成四元式序列。 6.設(shè)有基本塊 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q K:=G*5 L:=K+J M:=L 假設(shè)基本塊出口時(shí)只有M還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S (1) 給出句子(a,(a,a))的最左推導(dǎo)； (2) 給出句型((T,S),a)的短語(yǔ), 直接短語(yǔ)，句柄。 8.對(duì)于 C 語(yǔ)言do S while E語(yǔ)句 (1)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯； (2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d (1)給出句子abbcde的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； (2)給出句型aAbcde的短語(yǔ)、素短語(yǔ)。 10.設(shè)文法G(S): S→(T) | aS | a T→T,S | S ⑴消除左遞歸和提公共左因子； ⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合； ⑶構(gòu)造預(yù)測(cè)分析表。 11.把語(yǔ)句 if X>0 ∨ Y<0 then while X>0 do X:=A*3 else Y:=B+3; 翻譯成四元式序列。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 給出句型 (i+i)*i+i的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； (2) 給出句型 (E+T)*i+F 的短語(yǔ)，素短語(yǔ)和最左素短語(yǔ)。 13.設(shè)文法G（S）： S→T | S∨T T→U |T∧U U→i |-U （1）計(jì)算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 第6頁(yè)共6頁(yè) 參考答案 一、是非題： 1. 2. 3. 4.√ 5.√ 6. 7. 8. 9.√ 10. 11. 12.√ 13. 14.√ 15.√ 16.√ 17. 18.√ 19.√ 20. 21.√ 22.√ 二、填空題： 1.(最右推導(dǎo)） 2.(詞法分析），（語(yǔ)法分析），（中間代碼生成），（代碼優(yōu)化），（目標(biāo)代碼生成） 3.(二義性的） 4.(執(zhí)行性），（說(shuō)明性） 5.(單詞符號(hào)），（語(yǔ)法單位）。 6.(源程序），（單詞符號(hào)） 7.(類型、種屬、所占單元大小、地址） 8.(現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址) 9.(句柄） 10.(棧式)，（堆式） 11.(類型)，（作用域） 12.(傳地址），（傳值），（傳名） 13.(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化） 14.(自上而下），（自下而上） 15.(分析表），（符號(hào)棧） 16.(傳地址），（傳值），（傳名） 17.(初），（終） 18.(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化） 19.(語(yǔ)法），（語(yǔ)義） 20.(句柄） 21.(LL(1) 文法） 22.(靜態(tài)），（動(dòng)態(tài)） 23.(二義性文法） 24.(規(guī)范推導(dǎo)），（規(guī)范） 25.(自上而下），（自下而上） 26.(句子) 27.(從開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子） 28.(單詞符號(hào)），（語(yǔ)法單位） 29.(局部?jī)?yōu)化） 30.(分析表），（符號(hào)棧） 31.(上下文無(wú)關(guān)文法），（正規(guī)） 32.(指令訪問(wèn)主存次數(shù)加1） 33.(最左素短語(yǔ)） 三、名詞解釋題： 1.局部?jī)?yōu)化-------局限于基本塊范圍的優(yōu)化稱。 2.二義性文法------如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義性文法。 3.DISPLAY表----過(guò)程的嵌套層次顯示表，記錄該過(guò)程的各外層過(guò)程的最新活動(dòng)記錄的起始地址。 4.詞法分析器-----執(zhí)行詞法分析的程序。 5.最左推導(dǎo)------任何一步α=>β都是對(duì)α中的最右非終結(jié)符替換。 6.語(yǔ)法------一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。 7.文法------描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。 8.基本塊------指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語(yǔ)句，出口就是其中的最后一個(gè)語(yǔ)句。 9.語(yǔ)法制導(dǎo)翻譯------在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的辦法叫做語(yǔ)法制導(dǎo)翻譯。 10.短語(yǔ)------令G是一個(gè)文法，S劃文法的開(kāi)始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有SαAδ且Aβ，則稱β是句型αβδ相對(duì)非終結(jié)符A的短語(yǔ)。 11.待用信息------如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)有A的其它定值，則稱j是四元式i的變量A的待用信息。 12.規(guī)范句型------由規(guī)范推導(dǎo)所得到的句型。 13.掃描器------執(zhí)行詞法分析的程序。 14.超前搜索------在詞法分析過(guò)程中，有時(shí)為了確定詞性，需超前掃描若干個(gè)字符。 15.句柄------一個(gè)句型的最左直接短語(yǔ)。 16.語(yǔ)法制導(dǎo)翻譯------在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義程序進(jìn)行翻譯的方法 叫做語(yǔ)法制導(dǎo)翻譯。 17.規(guī)范句型------由規(guī)范推導(dǎo)所得到的句型。 18.素短語(yǔ)------素短語(yǔ)是指這樣一個(gè)短語(yǔ)，至少含有一個(gè)終結(jié)符，并且，除它自身外不再含任何更小的素短語(yǔ)。 19.語(yǔ)法------是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。 20.待用信息------如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)有A的其它定值，則稱j是四元式i的變量A的待用信息。 21.語(yǔ)義------定義程序的意義的一組規(guī)則。 四、簡(jiǎn)答題： 1.所求文法是G[S]: S→AB |B A0 A→AD |C B→2 |4 |6 |8 C→1 |3 |5 |7 |9 |B D→0 |C 2.輸出是4231 3.句子b(aa)b的規(guī)范歸約過(guò)程： 步驟 符號(hào)棧 輸入串 動(dòng)作 0 # b(aa)b# 預(yù)備 1 #b (aa)b# 移進(jìn) 2 #b( aa)b# 移進(jìn) 3 #b(a a)b# 移進(jìn) 4 #b(A a)b# 歸約 5 #b(Ma )b# 移進(jìn) 6 #b(Ma) b# 移進(jìn) 7 #b(B b# 歸約 8 #bA b# 歸約 9 #bAb # 移進(jìn) 10 #S # 接受 4.傳地址 A=6, B=16 傳值 A=2, B=4 5.L(G)={danbm |n>0, m≥0} 6.證明： 因?yàn)槲姆℅[S]存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。 S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa 7.句子 adccd 的分析過(guò)程： 步驟 符號(hào)棧 輸入串 產(chǎn)生式 0 #S adccd# 1 #AB adccd# S→BA 2 #AAa adccd# B→aA 3 #AA dccd# 4 #Ad dccd# A→d 5 #A ccd# 6 #SB ccd# A→BS 7 #Sc ccd# B→c 8 #S cd# 9 #AB cd# B→c 10 #Ac d# 11 #A d# 12 #d d# A→d 13 # # 8.所求文法是G[S]: S→AB A→aAc | D D→bD | b B→aBb | aabb 9. 函數(shù) a ( ) , f 4 2 4 4 g 5 5 2 3 10.優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化 11.目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。 應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)； (3)如何充分利用指令系統(tǒng)的特點(diǎn)。 12.正規(guī)式 a ( a | b )*。 13.刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫(xiě)傳播和刪除無(wú)用賦值。 14.文法G[S]: S→aB | a B→bc |bBc 15.傳值 a=2 傳地址 a=15 16.逆波蘭式: abcd-*e/+ 三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 17.證明： 因?yàn)槲姆℅[S]存在句子 () 有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。 A=>AA=>(A)A=>()A=>() A=>AA=>A=>(A)=>() 18.(a*b|b*a)={a,b,ab,ba,aab,bba……} 19.Display表: 嵌套層次顯示表 由于過(guò)程嵌套允許內(nèi)層過(guò)程引用外層過(guò)程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過(guò)程運(yùn)行時(shí)必須跟蹤它的所有外層過(guò)程的最新活動(dòng)記錄起始地址， display表就是用于登記每個(gè)外層過(guò)程的最新活動(dòng)記錄起始地址。 20.傳地址 a=12 傳值 a=5 21.所求文法是G[S]: S→AC A→aaAbb | ab C→ccC | cc 22.逆波蘭式 abc+e*bc+f/+:= 三元序列 op arg1 arg2 (1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5) 23.一個(gè)文法G別是LL(1)文法的充要條件是: (1) FIRST(α) ∩FIRST(β)=Ф (2) 如果 β=*>ε, FIRST(α) ∩FOLLOW(A)= Ф 24.消除左遞歸 S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a 提公共左因子,文法 G’(S) S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF’ F’→F |ε 25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。 主要技術(shù)：線性表，對(duì)折查找，雜奏技術(shù)。 五、計(jì)算題： 1. (1)消除左遞，文法變?yōu)镚’[S]： S→^ | a | (T) T→ST’ | S T’→,ST’ |ε 此文法無(wú)左公共左因子。 (2)構(gòu)造相應(yīng)的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}， FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，F(xiàn)OLLOW(T)={}} FIRST(T’)={,, ε} ，F(xiàn)OLLOW(F)={)} (3)構(gòu)造預(yù)測(cè)分析表： a ^ ( ) , # S S→a S→^ S→(T) T T→ST’ T→ST’ T→ST’ T’ T’→ε T’→,ST’ 2. (1) C→if E then S→CS(1) (2) C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC} S→CS(1) {S.chain:=MERG(C.Chain, S(1). Chain)} 3. (1) FIRSTVT(S)={a, ( } FIRSTVT(T)={+, aa, (} LASTVT(S)={a, ) } LASTVT(T)={+, a, )} (2) a + ( ) a .> .> + <. .> <. .> ( <. <. <. =. ) .> .> >. 4. (1) F→for i:=E(1) to E(2) do S→FS(1) (2) F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp; GEN(:=, E(2).place, _, LIMIT); Q:=NXQ; F.QUAD:=q; GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)} S→FS(1) {BACKPATCH(S(1).chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain } 5. (1) (j<, a, ‘10’, (3)) (2) (j, _, _, (12)) (3) (j>, c, ‘0’, (5)) (4) (j, _, _, (8)) (5) (+, a, ‘1’, T1)) (6) (:=, T1, _, a) (7) (j, _, _, (1)) (8) (*, a, ‘13’, T2) (9) (-, T2, ‘1’, T3) (10) (:=, T3, _, a) (11) (j, _, _, (1)) 6.優(yōu)化后的四元序列 D:=A-C E:=A*C F:=D*E M:=F+20 7. 最左推導(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ǔ) ((T,S),a) (T,S),a (T,S) T,S a 直接短語(yǔ) T,S a 句柄 T,S 8.(1) S→do M1 S1 while M2 E M→ε (2) M→ε {M.quad=nestquad;} S→do M1 S1 while M2 E {backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; } 9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde (2) 短語(yǔ): aAbcde, Ab, d 素短語(yǔ): Ab, d 10.(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 , # S S →(L) S → aS’ S’ S’→S S’→ε S’→S S’→ε S’→ε L L→SL’ L→SL’ L’→,SL’ L’ L’→ε 11.(1) (j>, X, 0, (5)) (2) (j, _, _, (3)) (3) (j<, Y, 0, (5)) (4) (j, _, _, (11)) (5) (j>0, X, 0, (7)) (6) (j, _, _, (7)) (7) (*, A, 3, T1) (8) (:=, T1, _, N) (9) (j, _, _, (5)) (10) (j, _, _, (13)) (11) (+, B, 3, T2) (12) (:=, T2, _, Y) 12.(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) 短語(yǔ) i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語(yǔ) i, E+T 最左素短語(yǔ) E+T 13.(1) FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -} LASTVT(S)={∨, ∧, i, - } LASTVT(T)={∧, i, -} LASTVT(U)={i, -} (2) i ∨ ∧ - S .> .> ∨ <. .> <. <. ∧ <. .> .> <. - <. .> .> <. 一、單項(xiàng)選擇題 1．將編譯程序分成若干個(gè)“遍”是為了( B ) A．提高程序的執(zhí)行效率 B. 使程序的結(jié)構(gòu)更加清晰 C．利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率 D．利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率 2．不可能是目標(biāo)代碼的是( D ) A．匯編指令代碼 B．可重定位指令代碼 C．絕對(duì)指令代碼 D．中間代碼 3．詞法分析器的輸入是( B ) A．單詞符號(hào)串 B．源程序 C．語(yǔ)法單位 D．目標(biāo)程序 4．中間代碼生成時(shí)所遵循的是( C ) A．語(yǔ)法規(guī)則 B．詞法規(guī)則 C．語(yǔ)義規(guī)則 D．等價(jià)變換規(guī)則 5．編譯程序是對(duì)( D ) A．匯編程序的翻譯 B．高級(jí)語(yǔ)言程序的解釋執(zhí)行 C．機(jī)器語(yǔ)言的執(zhí)行 D．高級(jí)語(yǔ)言的翻譯 6．詞法分析應(yīng)遵循( C ) A．語(yǔ)義規(guī)則 B．語(yǔ)法規(guī)則 C．構(gòu)詞規(guī)則 D．等價(jià)變換規(guī)則 7．詞法分析器的輸出結(jié)果是( C ) A．單詞的種別編碼 B．單詞在符號(hào)表中的位置 C．單詞的種別編碼和屬性值 D．單詞屬性值 8．正規(guī)式M1和M2等價(jià)是指( C ) A．M1和M2的狀態(tài)數(shù)相等 B．M1和M2的有向弧條數(shù)相等 C．M1和M2所識(shí)別的語(yǔ)言集相等 D．M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等 9．詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此，( B ) A．詞法分析器應(yīng)作為獨(dú)立的一遍 B．詞法分析器作為子程序較好 C．詞法分析器分解為多個(gè)過(guò)程，由語(yǔ)法分析器選擇使用 ． D．詞法分析器并不作為一個(gè)獨(dú)立的階段 10．如果L(M1)=L(M2)，則M1與M2( A ) A．等價(jià) B．都是二義的 C．都是無(wú)二義的 D．它們的狀態(tài)數(shù)相等 11．文法G：S→xSx|y所識(shí)別的語(yǔ)言是( C ) A．xyx B．(xyx)* c．xnyxn(n≥0) d．x*yx* 12．文法G描述的語(yǔ)言L(G)是指( A ) A． B． C． D． 13．有限狀態(tài)自動(dòng)機(jī)能識(shí)別( C ) A．上下文無(wú)關(guān)文法 B．上下文有關(guān)文法 C．正規(guī)文法 D．短語(yǔ)文法 14．如果文法G是無(wú)二義的，則它的任何句子( A ) A．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同 B．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同 C．最左推導(dǎo)和最右推導(dǎo)必定相同 D．可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同 15．由文法的開(kāi)始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是( C ) A．短語(yǔ) B．句柄 C．句型 D．句子 16．文法G：E→E+T|T T→T*P|P P→(E)|i 則句型P+T+i的句柄為( B ) A．P+T B．P C．P+T+i D．i 17．文法G：S→b|∧|(T) T→T∨S|S 則FIRSTVT(T)=( C ) A．{ b，∧，( } B．{ b，∧，) } C．{ b，∧，(，∨ } D．{ b，∧，），∨ } 18．產(chǎn)生正規(guī)語(yǔ)言的文法為( D ) A．0型 B．1型 C．2型 D．3型 19．任何算符優(yōu)先文法( D )優(yōu)先函數(shù)。 A．有一個(gè) B．沒(méi)有 C．有若干個(gè) D．可能有若干個(gè) 20．采用自上而下分析，必須( C ) A．消除左遞歸 B．消除右遞歸 C．消除回溯 D．提取公共左因子 21．在規(guī)范歸約中，用( B )來(lái)刻畫(huà)可歸約串。 A．直接短語(yǔ) B．句柄 C．最左素短語(yǔ) D．素短語(yǔ) 22．有文法G：E→E*T|T T→T+i|i 句子1+2*8+6按該文法G歸約，其值為( B ) A．23 B．42 C．30 D．17 23．如果文法是無(wú)二義的，那么規(guī)范歸約是指( B ) A．最左推導(dǎo)的逆過(guò)程 B．最右推導(dǎo)的逆過(guò)程 C．規(guī)范推導(dǎo) D．最左歸約的逆過(guò)程 24．文法G:S→S+T|T T→T*P|P P→(S)|i 句型P+T+i的短語(yǔ)有( B ) A．i,P+T B．P,P+T,i,P+T+i C．P+T+i D．P，P+T，i 25．四元式之間的聯(lián)系是通過(guò)( B )實(shí)現(xiàn)的。 A．指示器 B．臨時(shí)變量 C．符號(hào)表 D．程序變量 26．后綴式ab+cd+／可用表達(dá)式( B )來(lái)表示。 A．a(chǎn)+b／c+d B．(a+b)／(c+d) C．a(chǎn)+b／(c+d) D．a(chǎn)+b+c／d 27．使用間接三元式表示法的主要目的( A ) A．便于優(yōu)化處理 B．便于表的修改 C．節(jié)省存儲(chǔ)空間 D．生成中間代碼更容易 28．表達(dá)式(┐A∨B)∧(C∨D)的逆波蘭表示為( B ) A．┐AB∨∧CD∨ B．A┐B∨CD∨∧ C．AB∨┐CD∨∧ D．A┐B∨∧CD∨ 二、判斷題 1．一個(gè)確定有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 (╳) 2．設(shè)R和S分別是字母表∑上的正規(guī)式，則有L(R|S)=L(R)∪L(S)。 (√) 3．自動(dòng)機(jī)M1和M2的狀態(tài)數(shù)不同，則二者必不等價(jià)。 (╳) 4．確定有限自動(dòng)機(jī)以及非確定有限自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 (√) 5．對(duì)任意一個(gè)右線性正規(guī)文法G，都存在一個(gè)NFA M，滿足L(G)=L(M)。 (√) 6．對(duì)任意一個(gè)右線性正規(guī)文法G，都存在一個(gè)DFA M，滿足L(G)= L(M)。(√) 7．對(duì)任何正規(guī)式e，都存在一個(gè)NFA M，滿足L(M)=L(e)。(√) 8．對(duì)任何正規(guī)式e，都存在一個(gè)DFA M，滿足L(M)=L(e)。(√) 9．從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程是唯一的。(╳) 10．詞法分析作為單獨(dú)的一遍來(lái)處理較好。 (╳) 11．一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。(╳) 12．二義文法不是上下文無(wú)關(guān)文法。（╳） 13．自上而下分析法是一種“移進(jìn)—?dú)w約”法。（╳） 14．文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。(√) 15．產(chǎn)生式是定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。(√) 16．要構(gòu)造行之有效的自上而下的分析器，則必須消除左遞歸。（╳） 17．如果文法G是無(wú)二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。(√) 18．自下而上的分析法是一種“移進(jìn)—?dú)w約”法。(√) 19．如果文法G是二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。（╳） 三、填空題 1．解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)代碼）。 2．編譯過(guò)程通常可分為5個(gè)階段，分別是（詞法分析）、（語(yǔ)法分析）、語(yǔ)義分析與中間代碼產(chǎn)生、代碼優(yōu)化和目標(biāo)代碼生成。 3．編譯程序工作過(guò)程中，第一階段輸入是（源程序），最后階段的輸出為（目標(biāo)代碼）程序。 4．把語(yǔ)法范疇翻譯成中間代碼所依據(jù)的是（語(yǔ)義規(guī)則）。 5．目標(biāo)代碼可以是（匯編）指令代碼或（可重定位）指令代碼或絕對(duì)機(jī)器指令代碼。 6．詞法分析的任務(wù)是：輸入源程序，對(duì)構(gòu)成源程序的（字符串）進(jìn)行掃描和分解。 7．源程序中的錯(cuò)誤通常分為（語(yǔ)法錯(cuò)誤）和（語(yǔ)義錯(cuò)誤）兩大類。 8．（編譯程序）是將源程序翻譯成目標(biāo)程序的程序。 9．一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)部分：（終結(jié)符號(hào)）、（非終結(jié)符號(hào)）、（開(kāi)始符號(hào)）和一組（產(chǎn)生式）。 10．若，則稱這個(gè)序列是從到的一個(gè)（推導(dǎo)）。 11．設(shè)文法G的開(kāi)始符號(hào)為S，如果則稱是L(G)的一個(gè)（句型）。 12．文法G所產(chǎn)生的句子的全體是文法G所定義的（語(yǔ)言）。 13．若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)的兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是（二義文法）。 14．程序語(yǔ)言的單詞符號(hào)一般可分為五種：（關(guān)鍵字）、（標(biāo)識(shí)符）、常數(shù)、（運(yùn)算符）和界符。 15．（確定有限自動(dòng)機(jī)DFA）是非確定有限自動(dòng)機(jī)NFA的一個(gè)特例。 16．對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，若L(G)=L(M)，則稱G和M是（等價(jià)）的。 17．若兩個(gè)正規(guī)式所表示的正規(guī)集相等，則認(rèn)為二者是（等價(jià)）的。 18．按照語(yǔ)法分析樹(shù)的建立方法，語(yǔ)法分析可分為兩類：（自上而下分析）和（自下而上分析）。 18．規(guī)范歸約中的可歸約串是指（句柄）。 19．算符優(yōu)先分析中的可歸約串是指（最左素短語(yǔ)）。 20．（自下而上）語(yǔ)法分析的關(guān)鍵問(wèn)題是精確定義可歸約串的概念。 四、簡(jiǎn)答 1．給出上下文無(wú)關(guān)文法的定義。 一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式(VT，VN，S，P)，其中： VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)； VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VT∪VN=Φ； S是一個(gè)非終結(jié)符號(hào)，稱為開(kāi)始符號(hào)； P是一個(gè)產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式的形式是P→α，其中，P∈VN，α∈(VT∪VN)*。 開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 2．給出正規(guī)式與正規(guī)集的遞歸定義。 (1)ε和Φ都是∑上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Φ； (2)任何a∈∑，a是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}； (3)假定U和V都是∑上的正規(guī)式，它們所表示的正規(guī)集分別記為L(zhǎng)(U)和L(V)，那么，(U|V)、(UV)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U)∪L(V)、L(U)L(V)(連接積)和(L(U))*(閉包)。 僅由有限次使用上述三步驟而得到的表達(dá)式才是∑上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是∑上的正規(guī)集。 3．設(shè)文法G為： S→aAcB|BdS A→BaB|aBc|a B→aScA|cAB|b 對(duì)于輸入串a(chǎn)acabccb，給出最左推導(dǎo)。 S=>aAcB=>aaBccB=>aacABccB=>aacaBccB=>aacabccB=>aacabccb 4．設(shè)文法G為： S→BA A→BS|d B→aA|bS|c 對(duì)于輸入串a(chǎn)dccd，給出最左推導(dǎo)。 S=>BA=>aAA=>adA=>adBS=>adcS=>adcBA=>adccA=>adccd 5．證明：文法G： P→PaP|PbP|cP|Pe|f 為二義文法。 對(duì)于文法G定義的句子fbfbf，有兩棵不同的語(yǔ)法樹(shù)： P P P b P P b f f f P P P b P P f f f b 所以該文法是二義文法。 6．證明：文法G： P→S+S|S*S|i|(S) 為二義文法。 對(duì)于文法G定義的句子i+i*i，有兩棵不同的語(yǔ)法樹(shù)： S S S * S S + i i i S S S + S S i i i * 所以該文法是二義文法。 S FD A a b a b 7．給定正規(guī)文法G: S→aS|bA|b A→aS 請(qǐng)構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。 8．給定正規(guī)文法G: S→aA A→bA|aB|b B→aA 請(qǐng)構(gòu)造與之等價(jià)的有限自動(dòng)機(jī)。 A BD F b b a a S a 9．對(duì)下面給出的NFA確定化。 S FD A a b a b a 2 4D 3 a b a a 1 b a a 2 4D 3 a a a 1 b b 10．對(duì)下面給出的NFA確定化。 S BD A a a a a b 11．對(duì)下面給出的DFA最小化。 1 3D 2 a b a a b a A DD B a b a S a b C b b a b A DD B b a a S a C b a b a b 12．對(duì)下面給出的DFA最小化。 b 2 4D 3 b a a 1 a b b a 13．有如下布爾表達(dá)式： a下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
5 積分
| 下載 |
還剩頁(yè)未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 編譯原理 編譯 原理 考試 試題 答案
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書(shū)面授權(quán)，請(qǐng)勿作他用。
鏈接地址：http://m.appdesigncorp.com/p-12812247.html