成都理工大學(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)

語(yǔ)義錯(cuò)誤。

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

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

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

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

代碼形式是四元式

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

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

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

8.將棧頂?shù)姆?hào)和文法產(chǎn)生式的右部符號(hào)串進(jìn)行比較，若相等，則用左部符號(hào)去替換棧頂

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

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

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

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

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

開始符號(hào)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.表達(dá)式B.產(chǎn)生式C.單詞D.語(yǔ)句10.LR語(yǔ)法分析棧中存放的狀態(tài)是識(shí)別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

請(qǐng)指出文法G的終結(jié)符號(hào)、非終結(jié)符號(hào)和開始符號(hào)。（4分）解答：終結(jié)符：｛or,and,not,(,),true,false｝非終結(jié)符：｛E,T,F｝開始符號(hào)：｛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ε_(tái)閉包（｛0｝）=｛0｝*Aε_(tái)閉包（smove(｛0｝,a)）=｛0,1｝*Bε_(tái)閉包（smove(｛0｝，b)）=｛1｝*Cε_(tái)閉包（smove(｛0，1｝,a)）=｛0,1｝Bε_(tái)閉包（smove(｛0，1｝,b)）=｛1｝Cε_(tái)閉包（smove(｛1｝,a)）=｛0｝Aε_(tái)閉包（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｝編號(hào)0，C編號(hào)1,為｛c｝代表最小DFA為

a0ba1

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

aaba00010baa0100

識(shí)別aaba:識(shí)別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的所有短語(yǔ)、直接短語(yǔ)和句柄。（4分）解答：

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

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

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

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

附加資料：

編譯：高級(jí)語(yǔ)言可以直接轉(zhuǎn)換成機(jī)器語(yǔ)言，也可以翻譯成匯編語(yǔ)言，這兩個(gè)過(guò)程稱為編譯。解釋器與編譯器的主要區(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)生式語(yǔ)言自動(dòng)機(jī)0型文法（短語(yǔ)）α->β0型語(yǔ)言（短語(yǔ)結(jié)構(gòu)語(yǔ)言，遞歸可枚舉集）圖靈機(jī)1型文法（CSG）限制11型語(yǔ)言（CSL）線性界限自動(dòng)機(jī)2型文法（CFG）限制22型語(yǔ)言（CFL）下推自動(dòng)機(jī)3型文法（正規(guī)）限制33型語(yǔ)言（正規(guī)語(yǔ)言，正規(guī)集）有限自動(dòng)機(jī)

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

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

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

附加資料：

編譯：高級(jí)語(yǔ)言可以直接轉(zhuǎn)換成機(jī)器語(yǔ)言，也可以翻譯成匯編語(yǔ)言，這兩個(gè)過(guò)程稱為編譯。解釋器與編譯器的主要區(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)生式語(yǔ)言自動(dòng)機(jī)0型文法（短語(yǔ)）α->β0型語(yǔ)言（短語(yǔ)結(jié)構(gòu)語(yǔ)言，遞歸可枚舉集）圖靈機(jī)1型文法（CSG）限制11型語(yǔ)言（CSL）線性界限自動(dòng)機(jī)2型文法（CFG）限制22型語(yǔ)言（CFL）下推自動(dòng)