成都理工大學(xué)2023

本文格式為Word版，下載可任意編輯——成都理工大學(xué)2023成都理工大學(xué)2023-2023學(xué)年第一學(xué)期《軟件代碼開發(fā)技術(shù)》考試試卷

一，填空題（每題2分，共30分）

1.源程序的動(dòng)態(tài)錯(cuò)誤是源程序中的規(guī)律錯(cuò)誤，它們發(fā)生在程序運(yùn)行的時(shí)候，也被成為動(dòng)態(tài)

語義錯(cuò)誤。

2.設(shè)計(jì)一個(gè)編譯器，除了具有中間代碼生成、代碼生成和出錯(cuò)處理功能之外，還應(yīng)具有哪

些功能：它們分別為_詞法分析、語法分析、語義分析、中間代碼優(yōu)化、符號表管理_3.設(shè)∑=｛0,1｝上的正規(guī)集S由倒數(shù)其次個(gè)字符為0的所有字符串組成，則該正規(guī)集對應(yīng)

的正規(guī)式表示為(0|1)*0(0|1)

4.假設(shè)G是一個(gè)文法，S是文法的開始符號，假使S=>x,則稱x是該文法的一個(gè)句型5.中間代碼生成器對語法樹進(jìn)行遍歷，生成可順序執(zhí)行的中間的代碼序列，最常用的中間

代碼形式是四元式

6.最右推導(dǎo)也成為規(guī)范推導(dǎo)，推導(dǎo)出的句型稱為右句型。

7.LR(k)文法所識別的語言稱為LR(k)語言，其中L表示從左到右掃描輸入序列，R表示逆

序的最右推導(dǎo)，k表示確定下一動(dòng)作向前看的終結(jié)符個(gè)數(shù)

8.將棧頂?shù)姆柡臀姆óa(chǎn)生式的右部符號串進(jìn)行比較，若相等，則用左部符號去替換棧頂

符號串，這種操作稱為規(guī)約

9.自上而下語法分析方法遇到的主要問題是回溯和無限循環(huán)（死循環(huán)）10.正規(guī)文法，正規(guī)表達(dá)式和有限自動(dòng)機(jī)三者在某種意義下是等價(jià)的

11.若為文法G構(gòu)造的預(yù)計(jì)分析表中不含多重定義的條目，則稱G為回溯文法。12.文法符號的屬性有兩種，一種稱為綜合屬性，另一種稱為幾成屬性。13.一個(gè)句型中的最左直接短語稱為該句型的句柄。

14.假使一個(gè)問發(fā)的同一個(gè)句子存在兩棵分析樹，則該文法是二義性的

15.不管任何類型的文法都包括四個(gè)組成部分，它們分別是非終結(jié)符、終結(jié)符、產(chǎn)生式、

開始符號

二、判斷題（每題1分，共10分）

1，確定的和不確定的有限自動(dòng)機(jī)都能識別正規(guī)集。（√）

2，有些語言能被確定的有限自動(dòng)機(jī)識別，但不能用正規(guī)表達(dá)式表示。（×）3，設(shè)L={a,b,c},M={b,c,d},L∪M={b,c}.（×）4，在預(yù)計(jì)分析器的轉(zhuǎn)換圖中，其箭弧上的標(biāo)識必需是終結(jié)符。（×）

5，一個(gè)項(xiàng)目集中既可以有移進(jìn)項(xiàng)目，又有可規(guī)約項(xiàng)目，使得分析無法進(jìn)行，這種沖突稱為移進(jìn)/規(guī)約沖突。（√）

6，在使用自上而下分析法時(shí)，文法應(yīng)當(dāng)沒有左遞歸。（√）

7，正規(guī)集都可以由一個(gè)狀態(tài)數(shù)最少的DFA識別，這個(gè)DFA是唯一的。（√）8，二義文法是SLR(l)文法。（×）

9，正規(guī)表達(dá)式的運(yùn)算操作不具有優(yōu)先級運(yùn)算。（×）10，文法G的產(chǎn)生式為S->（L）|aL->L，S|S是一個(gè)直接左遞歸文法。（√）

三、選擇題（每題1分，共10分）1，文法G所描述的語言是D的集合。

A．文法G的字匯表V中所有符號組成的符號串B．文法G的字匯表V的閉包V*中的所有符號串C．由文法的開始符號推出的所有符號串D．由文法的開始符號推出的所有終結(jié)符號串

2，一個(gè)語言的文法是B。

A．唯一的B.不唯一的C.個(gè)數(shù)有限的

3，若一個(gè)文法是遞歸的，則它所產(chǎn)生的句子個(gè)數(shù)A。A.必定是無窮的B.是有限個(gè)的C.根據(jù)具體狀況而定4，文法的二義性和語言的二義性是兩個(gè)A的概念。A.不同B.一致C.無法判斷D.等價(jià)5，巴克斯范式（BNF）是一種廣泛采用的C的工具。A.描述規(guī)則B.描述語言C.描述文法D.描述句子6，B是兩類程序語言處理程序。A.高級語言程序和低級語言程序B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng)D.系統(tǒng)程序和應(yīng)用程序

7，喬姆斯基把文法分為四種類型：0型、1型、2型和3型，其中2型文法指的是C。A．短語文法B.上下文有關(guān)文法C.上下文無關(guān)文法D.正規(guī)文法8，語法分析常用的方法是A。A.自頂向下、自底向上

B.自頂向下、自底向上、自左向右

C.自頂向下、自底向上、自左向右、自右向左D.自左向右、自右向左

9.編譯程序中的語法分析器接受以C為單位的輸入，并產(chǎn)生以有關(guān)信息供以后各階段使用。

A.表達(dá)式B.產(chǎn)生式C.單詞D.語句10.LR語法分析棧中存放的狀態(tài)是識別B的DFA狀態(tài)。A.前綴B.可規(guī)約前綴C.項(xiàng)目D.句柄四，綜合題（5小題，共50分）1，設(shè)文法G具有以下產(chǎn)生式：

E->EOrT|TT->TandF|F

F->notF|(E)|true|false

請指出文法G的終結(jié)符號、非終結(jié)符號和開始符號。（4分）解答：終結(jié)符：｛or,and,not,(,),true,false｝非終結(jié)符：｛E,T,F｝開始符號：｛E｝

2，根據(jù)1中文法G寫出句子not(trueandfalse)的規(guī)范推導(dǎo)并確定句柄。（6分）解答：規(guī)范推導(dǎo)為：

E=>T=>F=>notF=>not(E)=>not(T)=>not(TandF)=>not(Tandfalse)=>not(Fandfalse)=>not(trueandfalse)

由分析樹：可知句柄為：true

3，有NFA定義如下：

N=（S={0,1}，∑=｛a,b｝,s0=0，F(xiàn)={0}，MOVE={move(0,a)=0，move(0,a)=1，move(1,a)=0}）(1)畫出N的狀態(tài)轉(zhuǎn)換圖（4分）解答：

a0a,ba1

(2)構(gòu)造N的最小DFAD（7分）解答：確定DFAε_閉包（｛0｝）=｛0｝*Aε_閉包（smove(｛0｝,a)）=｛0,1｝*Bε_閉包（smove(｛0｝，b)）=｛1｝*Cε_閉包（smove(｛0，1｝,a)）=｛0,1｝Bε_閉包（smove(｛0，1｝,b)）=｛1｝Cε_閉包（smove(｛1｝,a)）=｛0｝Aε_閉包（smove(｛1｝,b)）=εDFA為：

aAAbaCCΠ=｛｛A，B｝｝,｛C｝｝

Bb

move(A,a)=Bmove(A,b)=｛c｝move(B,a)=Bmove(B,b)=｛c｝

故A,B不可分，將A為｛A,B｝編號0，C編號1,為｛c｝代表最小DFA為

a0ba1

(3)給出串a(chǎn)aba,baa的識別過程（4分）解答：

aaba00010baa0100

識別aaba:識別baa:

4，設(shè)文法G具有以下產(chǎn)生式：

E->E+T|TT->T*F|FF–>id|(E)

(1)消除文法的直接左遞歸：（4分）解答：消除左遞歸后的文法為：E->TE’

E’->+TE’/εT->FT’

T’->*FT’/εF->id/(E)

(2)求消除左遞歸后文法的FIRST和FOLLOW函數(shù)：（6分）解答：

First(F)=｛id,(｝First(T’)=｛*,ε｝First(T)=｛id,(｝

First(E’)=｛+，ε｝

First(E)=First(T)=First(F)=｛id,(｝

Follow(E)=｛#,)｝

Follow(E’)=Follow(E)=｛#,)｝Follow(T)=｛+,#,)｝

Follow(T’)=Follow(T)=｛+,#,)｝

Follow(F)=｛*,+,#｝(3)構(gòu)造其預(yù)計(jì)分析表。（4分）解答：

first(TE’)=｛id，(｝first(+TE’)=｛+,ε｝first(FT’)=｛id，(｝first(*FT’)=｛*,(｝first(id)=id

first((E))=｛（｝E*+）（id#TE’TE’εεE’T+TE’εFT’FT’ε(E)idT’*FT’εF

5，已知文法G3:S`->EE->aA|bBA->cA|dB->cB|d

(1)寫出句型bccB的所有短語、直接短語和句柄。（4分）解答：

S’=>E=>bB=>bcB=>bccB

短語：bccB(S’E)ccB(B1)cB(B2)直接短語：cB(B2)句柄：cB(B2)

(2)列出4個(gè)項(xiàng)目集I1、I2、I3、I4（如下圖），請將這4個(gè)項(xiàng)目集補(bǔ)充完整。（7分）

aI1:S`->.EE->.aAE->.bBI2:E->a.AA->.cAA->dEbI3:E.I4:E->b.BB->.cBB->.d

附加資料：

編譯：高級語言可以直接轉(zhuǎn)換成機(jī)器語言，也可以翻譯成匯編語言，這兩個(gè)過程稱為編譯。解釋器與編譯器的主要區(qū)別：運(yùn)行目標(biāo)程序的控制權(quán)在解釋器而不在目標(biāo)程序。解釋器優(yōu)點(diǎn)：（1）其具有較好的動(dòng)態(tài)特性。（2）具有較好的可移植性。缺點(diǎn)：在時(shí)間和空間上的損失較大，運(yùn)行效率低。文法的分類：

文法產(chǎn)生式語言自動(dòng)機(jī)0型文法（短語）α->β0型語言（短語結(jié)構(gòu)語言，遞歸可枚舉集）圖靈機(jī)1型文法（CSG）限制11型語言（CSL）線性界限自動(dòng)機(jī)2型文法（CFG）限制22型語言（CFL）下推自動(dòng)機(jī)3型文法（正規(guī)）限制33型語言（正規(guī)語言，正規(guī)集）有限自動(dòng)機(jī)

LR(1)與LALR(1)的關(guān)系：LR(1)與LALR(1)對于移進(jìn)/規(guī)約沖突的解決二者是等價(jià)的，而對于規(guī)約/規(guī)約沖突，由于LALR(1)項(xiàng)目中合并了lookaheads可能會減弱它對規(guī)約/規(guī)約沖突的解決能力，具體有下述兩個(gè)結(jié)論：

(1)LR(1)DFA中不發(fā)生的移進(jìn)/規(guī)約沖突，LALR(1)DFA中也一定不會發(fā)生。(2)合并后的lookaheads可能會引起LALR(1)項(xiàng)目集中的規(guī)約/規(guī)約沖突。

aI1:S`->.EE->.aAE->.bBI2:E->a.AA->.cAA->dEbI3:E.I4:E->b.BB->.cBB->.d

附加資料：

編譯：高級語言可以直接轉(zhuǎn)換成機(jī)器語言，也可以翻譯成匯編語言，這兩個(gè)過程稱為編譯。解釋器與編譯器的主要區(qū)別：運(yùn)行目標(biāo)程序的控制權(quán)在解釋器而不在目標(biāo)程序。解釋器優(yōu)點(diǎn)：（1）其具有較好的動(dòng)態(tài)特性。（2）具有較好的可移植性。缺點(diǎn)：在時(shí)間和空間上的損失較大，運(yùn)行效率低。文法的分類：

文法產(chǎn)生式語言自動(dòng)機(jī)0型文法（短語）α->β0型語言（短語結(jié)構(gòu)語言，遞歸可枚舉集）圖靈機(jī)1型文法（CSG）限制11型語言（CSL）線性界限自動(dòng)機(jī)2型文法（CFG）限制22型語言（CFL）下推自動(dòng)