青島理工大學(xué)編譯原理（專升本）期末復(fù)習(xí)題及參考答案

一、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)1．一個編譯程序中，不僅包含詞法分析，_____，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分。A．語法分析B．文法分析C．語言分析D．解釋分析2．詞法分析器用于識別_____。

A．字符串

B．語句

C．單詞D．標(biāo)識符3．語法分析器則可以發(fā)現(xiàn)源程序中的_____。A．語義錯誤

B．語法和語義錯誤

C．錯誤并校正

D．語法錯誤4．下面關(guān)于解釋程序的描述正確的是_____。(1)解釋程序的特點是處理程序時不產(chǎn)生目標(biāo)代碼

(2)解釋程序適用于COBOL和FORTRAN語言

(3)解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的

A．(1)(2)B．(1)C．(1)(2)(3)

D．(2)(3)5．解釋程序處理語言時,大多數(shù)采用的是_____方法。A．源程序命令被逐個直接解釋執(zhí)行

B．先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行

C．先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,再執(zhí)行

D．以上方法都可以6．編譯過程中,語法分析器的任務(wù)就是_____。(1)分析單詞是怎樣構(gòu)成的

(2)分析單詞串是如何構(gòu)成語句和說明的

(3)分析語句和說明是如何構(gòu)成程序的

(4)分析程序的結(jié)構(gòu)A．(2)(3)B．(2)(3)(4)

C．(1)(2)(3)D．(1)(2)(3)(4)7．編譯程序是一種_____。A.匯編程序B．翻譯程序

C．解釋程序

D．目標(biāo)程序8．文法G所描述的語言是_____的集合。A.文法G的字母表V中所有符號組成的符號串

B．文法G的字母表V的閉包V*中的所有符號串

C．由文法的開始符號推出的所有終極符串

D.由文法的開始符號推出的所有符號串9．文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_____。A.短語文法

B．正則文法

C．上下文有關(guān)文法D．上下文無關(guān)文法10．一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組_____。A．句子B．句型

C．單詞D．產(chǎn)生式11．通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括_____。A．模擬執(zhí)行器

B．解釋器

C．表格處理和出錯處理D．符號執(zhí)行器12．文法G[N]=（，{N，B}，N，{N→b│bB，B→bN}），該文法所描述的語言是（）。

A．L(G[N])={bi│i≥0}

B．L(G[N])={b2i│i≥0}

C．L(G[N])={b2i+1│i≥0}

D．L(G[N])={b2i+1│i≥1}13．一個句型中的最左_____稱為該句型的句柄。A．短語

B．簡單短語

C．素短語

D．終結(jié)符號14．設(shè)G是一個給定的文法，S是文法的開始符號，如果S->x(其中x∈V*),則稱x是文法G的一個_____。A．候選式

B．句型

C．單詞

D．產(chǎn)生式15．文法G[E]：

E→T∣E＋T

T→F∣T﹡F

F→a∣（E）

該文法句型E＋F﹡(E＋T)的簡單短語是下列符號串中的_____。①（E＋T）

②E＋T

③F

④F﹡(E＋T)A．①和③B．②和③C．③和④D．③16．若一個文法是遞歸的，則它所產(chǎn)生的語言的句子_____。A．是無窮多個

B．是有窮多個

C．是可枚舉的

D．個數(shù)是常量17．詞法分析器用于識別_____。A．句子

B．句型

C．單詞

D．產(chǎn)生式18．在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是_____。A.非終極符集

B．終極符集

C．字母表

D.狀態(tài)集19．在自底向上的語法分析方法中，分析的關(guān)鍵是_____。A.尋找句柄

B.尋找句型

C.消除遞歸

D.選擇候選式20．在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型_____的DFA狀態(tài)。A.句柄

B.前綴

C.活前綴

D.LR(0)項目21．文法G產(chǎn)生的_____的全體是該文法描述的語言。A．句型B．終結(jié)符集C．非終結(jié)符集D．句子22．若文法G定義的語言是無限集，則文法必然是_____。

A．遞歸的

B．前后文無關(guān)的

C．二義性的D．無二義性的23．四種形式語言文法中，1型文法又稱為_____文法。A．短語結(jié)構(gòu)文法

B．前后文無關(guān)文法

C．前后文有關(guān)文法

D．正規(guī)文法24．一個文法所描述的語言是_____。A．唯一的

B．不唯一的

C．可能唯一，好可能不唯一

D．都不對25．_____和代碼優(yōu)化部分不是每個編譯程序都必需的。A．語法分析

B．中間代碼生成

C．詞法分析

D．目標(biāo)代碼生成26．_____是兩類程序語言處理程序。A．高級語言程序和低級語言程序

B．解釋程序和編譯程序

C．編譯程序和操作系統(tǒng)

D．系統(tǒng)程序和應(yīng)用程序27．?dāng)?shù)組的內(nèi)情向量中肯定不含有數(shù)組的_____的信息。A.維數(shù)B．類型

C．維上下界

D．各維的界差28.一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組_____。A．句子B．句型

C．單詞D．產(chǎn)生式29．文法分為四種類型，即0型、1型、2型、3型。其中2型文法是_____。A.短語文法

B．正則文法

C．上下文有關(guān)文法D．上下文無關(guān)文法30．文法G所描述的語言是_____的集合。A.文法G的字母表V中所有符號組成的符號串

B．文法G的字母表V的閉包V*中的所有符號串

C．由文法的開始符號推出的所有終極符串

D.由文法的開始符號推出的所有符號串二、填空題(每空2分)1．編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個基本階段,同時還會伴有_____和___。2．若源程序是用高級語言編寫的,__目標(biāo)程序_是機器語言程序或匯編程序,則其翻譯程序稱為___。3．編譯方式與解釋方式的根本區(qū)別在于_____。4．對編譯程序而言,輸入數(shù)據(jù)是_____,輸出結(jié)果是_____。5．產(chǎn)生式是用于定義_____的一種書寫規(guī)則。6．語法分析最常用的兩類方法是_____和_____分析法。7．設(shè)G是一個給定的文法，S是文法的開始符號，如果S->x(其中x∈VT*),則稱x是文法的一個_____。8．遞歸下降法不允許任一非終極符是直接_____遞歸的。9．自頂向下的語法分析方法的基本思想是：從文法的______開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行______，試圖推導(dǎo)出文法的______，使之與給定的輸入串______。10．自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_____，力求歸約到文法的_____。11．常用的參數(shù)傳遞方式有_____，傳值和傳名。12．在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部_____錯誤和語義部分錯誤。13．一個句型中的最左簡單短語稱為該句型的_____。14．對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為_____。15．一個典型的編譯程序中，不僅包括_____、_____、_____、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。16．從功能上說，程序語言的語句大體可分為_____語句和_____語句兩大類。17．掃描器的任務(wù)是從_____中識別出一個個_____。18．產(chǎn)生式是用于定義_____的一種書寫規(guī)則。三、簡答題1.寫一文法，使其語言是偶正整數(shù)的集合,要求：

(1)允許0打頭；

(2)不允許0打頭。答案：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)

P:

S->PD|D

P->NP|N

D->0|2|4|6|8

N->0|1|2|3|4|5|6|7|8|9

(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)

P:

S->PD|P0|D

P->NR|N

R->QR|Q

D->2|4|6|8

N->1|2|3|4|5|6|7|8|9

Q->0|1|2|3|4|5|6|7|8|92.已知文法G[E]為：

E→T|E+T|E-T

T→F|T*F|T/F

F→（E）|i

①該文法的開始符號（識別符號）是什么？

②請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。

③找出句型T+T*F+i的所有短語、簡單短語和句柄。答案：①該文法的開始符號（識別符號）是E。

②該文法的終結(jié)符號集合VT={+、-、*、/、（、）、i}。非終結(jié)符號集合VN={E、T、F}。

③句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i;簡單短語為i、T*F、第一個T;句柄為第一個T。3.構(gòu)造正規(guī)式相應(yīng)的NFA:1(0|1)*101答案：1(0|1)*101對應(yīng)的NFA為4.寫出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示和三元式序列。答案：逆波蘭表示：abc*＋ab＋/d－

三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)5.寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。答案：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D6.設(shè)文法G(S)：

S→(L)|aS|a

L→L，S|S

(1)消除左遞歸和回溯；

(2)計算每個非終結(jié)符的FIRST和FOLLOW。答案：(1)

S→(L)|aS'

S'→S|ε

L→SL'

L'→SL'|ε

(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(S')＝{，a,ε}FOLLOW(S')＝{#，，，)}

FIRST(L)＝{(，a}FOLLOW(L)＝{)}

FIRST(L')＝{，，ε}FOLLOW(L'〕＝{)}7.已知文法G(E)

E→T|E＋T

T→F|T*F

F→(E)|i

(1)給出句型(T*F＋i)的最右推導(dǎo)；

(2)給出句型(T*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,i8.Whilea＞0∨b＜0do

Begin

X：＝X＋1；

ifa＞0thena：＝a－1

elseb：＝b＋1

End；

翻譯成四元式序列。答案：

(1)(j＞，a，0，5)

(2)(j，－，－，3)

(3)(j＜，b，0，5)

(4)(j，－，－，15)

(5)(＋，×，1，T1)

(6)(：＝，T1，－，×)

(7)(j≥，a，0，9)

(8)(j，－，－，12)

(9)(－，a，1，T2)

(10)(：＝，T2，－，a)

(11)(j，－，－，1)

(12)(＋，b，1，T3)

(13)(：＝，T3，－，b)

(14)(j，－，－，1)9.構(gòu)造正規(guī)式相應(yīng)的DFA:1(1010*|1(010)*1)*0。答案：1(1010*|1(010)*1)*0對應(yīng)的NFA為：10.對下面的文法G：E->TE'E'->+E|εT->FT'T'->T|εF->PF'F'->*F'|εP->(E)|a|b|^(1)計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。(4分)(2)證明這個方法是LL(1)的。(4分)(3)構(gòu)造它的預(yù)測分析表。(2分)答案：（1）計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。

FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};

FIRST(E')={+,ε}

FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};

FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};

FIRST(F)=FIRST(P)={(,a,b,^};

FIRST(F')=FIRST(P)={*,ε};

FIRST(P)={(,a,b,^};

FOLLOW集合有：

FOLLOW(E)={),#};

FOLLOW(E')=FOLLOW(E)={),#};

FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含ε

FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};

FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε

FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};

FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε

(2)證明這個方法是LL(1)的。

各產(chǎn)生式的SELECT集合有：

SELECT(E->TE')=FIRST(T)={(,a,b,^};

SELECT(E'->+E)={+};

SELECT(E'->ε)=FOLLOW(E/)={),#}

SELECT(T->FT')=FIRST(F)={(,a,b,^};

SELECT(T'->T)=FIRST(T)={(,a,b,^};

SELECT(T'->ε)=FOLLOW(T/)={+,),#};

SELECT(F->PF')=FIRST(P)={(,a,b,^};

SELECT(F'->*F')={*};

SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};

SELECT(P->(E))={(}

SELECT(P->a)={a}

SELECT(P->b)=

SELECT(P->^)={^}

可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G[E]是LL(1)文法。

(3)構(gòu)造它的預(yù)測分析表。

文法G[E]的預(yù)測分析表如下：

11.已知文法A->aAd|aAb|ε判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。答案：增加一個非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：

S'->A

A->aAd|aAb|ε

下面構(gòu)造它的LR(0)項目集規(guī)范族為：從上表可看出,狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0狀態(tài)下面臨輸入符號為a時移進(jìn)，為b,d,#時歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是SLR(1)文法。

其SLR(1)分析表為：

對輸入串a(chǎn)b#給出分析過程為：

12.已知文法G[S]為：S->a|^|(T)T->T,S|S(1)計算G[S]的FIRSTVT和LASTVT。(2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說明G[S]是否未算符優(yōu)先文法。(3)計算G[S]的優(yōu)先函數(shù)。(4)給出輸入串(a,a)#的算符優(yōu)先分析過程。答案：（1）各符號的FIRSTVT和LASTVT：

（2）算符優(yōu)先關(guān)系表：

（3）對應(yīng)的算符優(yōu)先函數(shù)為：

（4）句子(a,a)#分析過程如下：

13.設(shè)文法G（S）：S→(T)|aT→T+S|S(1）計算FIRSTVT和LASTVT；（2）構(gòu)造優(yōu)先關(guān)系表。答案：(1)FIRSTVT(S)={a,(}FIRSTVT(T)={+,aa,(}LASTVT(S)={a,)}LASTVT(T)={+,a,)}(2)a+()a.>.>+<..><..>(<.<.<.=.).>.>>.

一、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)ACDBBBCCBDCCBBBACBDCDACABBADDC二、填空題(每空2分)1.表格處理、出錯處理2.編譯程序3．是否生成目標(biāo)代碼4．源程序、目標(biāo)程序5．語法成分6．自上而下、自下而上7．句子8．左9．開始符號、直接推導(dǎo)、句子、匹配10．直接歸約、開始符號11．傳地址12．語法13．句柄14．語義規(guī)則15．詞法分析、語法分析、中間代碼生成、16．執(zhí)行性、說明性17．源程序、單詞符號18．語法范疇三、簡答題1.寫一文法，使其語言是偶正整數(shù)的集合,要求：

(1)允許0打頭；

(2)不允許0打頭。答案：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)

P:

S->PD|D

P->NP|N

D->0|2|4|6|8

N->0|1|2|3|4|5|6|7|8|9

(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)

P:

S->PD|P0|D

P->NR|N

R->QR|Q

D->2|4|6|8

N->1|2|3|4|5|6|7|8|9

Q->0|1|2|3|4|5|6|7|8|92.已知文法G[E]為：

E→T|E+T|E-T

T→F|T*F|T/F

F→（E）|i

①該文法的開始符號（識別符號）是什么？

②請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。

③找出句型T+T*F+i的所有短語、簡單短語和句柄。答案：①該文法的開始符號（識別符號）是E。

②該文法的終結(jié)符號集合VT={+、-、*、/、（、）、i}。非終結(jié)符號集合VN={E、T、F}。

③句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i;簡單短語為i、T*F、第一個T;句柄為第一個T。3.構(gòu)造正規(guī)式相應(yīng)的NFA:1(0|1)*101答案：1(0|1)*101對應(yīng)的NFA為4.寫出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示和三元式序列。答案：逆波蘭表示：abc*＋ab＋/d－

三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)5.寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。答案：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D6.設(shè)文法G(S)：

S→(L)|aS|a

L→L，S|S

(1)消除左遞歸和回溯；

(2)計算每個非終結(jié)符的FIRST和FOLLOW。答案：(1)

S→(L)|aS'

S'→S|ε

L→SL'

L'→SL'|ε

(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(S')＝{，a,ε}FOLLOW(S')＝{#，，，)}

FIRST(L)＝{(，a}FOLLOW(L)＝{)}

FIRST(L')＝{，，ε}FOLLOW(L'〕＝{)}7.已知文法G(E)

E→T|E＋T

T→F|T*F

F→(E)|i

(1)給出句型(T*F＋i)的最右推導(dǎo)；

(2)給出句型(T*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,i8.Whilea＞0∨b＜0do

Begin

X：＝X＋1；

ifa＞0thena：＝a－1

elseb：＝b＋1

End；

翻譯成四元式序列。答案：

(1)(j＞，a，0，5)

(2)(j，－，－，3)

(3)(j＜，b，0，5)

(4)(j，－，－，15)

(5)(＋，×，1，T1)

(6)(：＝，T1，－，×)

(7)(j≥，a，0，9)

(8)(j，－，－，12)

(9)(－，a，1，T2)

(10)(：＝，T2，－，a)

(11)(j，－，－，1)

(12)(＋，b，1，T3)

(13)(：＝，T3，－，b)

(14)(j，－，－，1)9.構(gòu)造正規(guī)式相應(yīng)的DFA:1(1010*|1(010)*1)*0。答案：1(1010*|1(010)*1)*0對應(yīng)的NFA為：10.對下面的文法G：E->TE'E'->+E|εT->FT'T'->T|εF->PF'F'->*F'|εP->(E)|a|b|^(1)計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。(4分)(2)證明這個方法是LL(1)的。(4分)(3)構(gòu)造它的預(yù)測分析表。(2分)答案：（1）計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。

FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};

FIRST(E')={+,ε}

FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};

FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};

FIRST(F)=FIRST(P)={(,a,b,^};

FIRST(F')=FIRST(P)={*,ε};

FIRST(P)={(,a,b,^};

FOLLOW集合有：

FOLLOW(E)={),#};

FOLLOW(E')=FOLLOW(E)={),#};

FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含ε

FOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};

FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε

FOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};

FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε

(2)證明這個方法是LL(1)的。

各產(chǎn)生式的SELECT集合有：

SELECT(E->TE')=FIRST(T)={(,a,b,^};

SELECT(E'->+E)={+};

SELECT(E'->ε)=FOLLOW(