南京信息工程大學(xué)編譯原理期末試卷2021-2022(含答案)

南京信息工程大學(xué)編譯原理試卷

2021—2022學(xué)年第J.學(xué)期編譯原理課程期末試卷（B卷）

本試卷共2,頁；考試時間1延分鐘；任課教師凌妙根：出卷時間2021年12/

計(jì)算機(jī)與軟件學(xué)院_______________專業(yè)____________年級______________班

學(xué)號________________姓名______________得^_____________

一、選擇題：（共5題，共10分）

1.（）不是編譯程序的組成部分。

A.詞法分析程序B.代碼生成程序C.

設(shè)備管理程序D.語法分析程序答

案：C

2.文法STaaS|而c定義的語言是（）。

A.{a"bc|k>0}E.{akbc\k>0}

C.{戶D.{a*a*6c|A:>0）

答案：C

3.在編譯過程中，如果遇到錯誤應(yīng)該（）。

A.把錯誤理解成局部的錯誤

B.對錯誤在局部范圍內(nèi)進(jìn)仃糾止，繼續(xù)向卜分析

C.當(dāng)發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去

D.當(dāng)發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

答案：C

4.在非遞歸的預(yù)測分析過程中進(jìn)行翻譯，以下說法不正確的是（）。

A.要想在非遞歸的預(yù)測分析過程中進(jìn)行翻譯，需要擴(kuò)展語法分析棧B.

非終結(jié)符A的繼承屬性和綜合屬性的計(jì)算時機(jī)不同

C.將非終結(jié)符A的繼承屬性和綜合屬性存放在不同的紀(jì)錄中

D.綜合屬性在A出現(xiàn)之前就可以計(jì)算

答案：D

5.以下說法不正確的是

A.語法制導(dǎo)翻譯方案只限自底向上的分析方法

B.給定一個以LL文法為基礎(chǔ)的L-SDD,可以修改這個文法，并在LR語法分析過程中計(jì)算

這個新文法之上的SDD

C.對于這個內(nèi)嵌的語義動作，向文法中引入一個標(biāo)記非終結(jié)符M來替換它

D.每個標(biāo)記非終結(jié)符M對應(yīng)著一個空產(chǎn)生式該產(chǎn)生式對應(yīng)著段語義子程序，它

的任務(wù)就是完成M所替換的那個語義動作要完成的工作

答案：A

二、畫圖題（共2題，25分）

1.已知文法G（S）

STa|「（T）FTT,S|S

1）給出句子（a,（a,a））的雙左推導(dǎo)，及畫山語法分析樹;

■

渴萬下號S號(丁)今與⑸與

號>(a.s)^(a.tT>>=^>(ouTsy>

S(a,gs/

a，(a,a)D

2）給出句型（（T,S）,a）的短語，直接短語和句柄。（10分）

s

娃論Cr，s〉a

(開)

(Ts>TSQ

他

描

匝Ts

何

柄Fs

2.設(shè)有基本塊

D=A-CE=A*C

F=D*ES=2

T=A-CQ=A*C

G=2*SJ=T*Q

K=G*5L=K+J

M=L

1）畫出DAG圖;

2）假設(shè)所有基本塊出口時只有M還被引用，請寫出優(yōu)化后的三地址指令序列。（15分）

答：

D=AC

E=A*C

F=D*E

M=F+20

三、計(jì)算分析題（共2題，20分）

1、寫一個文法使其語言為〃G）={d產(chǎn)+（5分）

I論

RfodabIab

2、設(shè)文法G[S]：S->*|a|（T）T>T,S\S

【）消除左遞歸；

2構(gòu)造相應(yīng)的FIRST和FOLLOW集合；

3）構(gòu)造預(yù)測分析表。（15分）

ST八IaI

口阡

四、綜合題：（共2題，45分）

1.對于G[E]的一個L屬性文法

E>T{R.in=T.val}R{E.val=R.val}

Kt+7'{,E=R.in+T.val}R\{R,val=Rl.val}

R—e{R.val=R.in}

T->num{T.val=le.xc.val（num）}

使用SLR自動機(jī)進(jìn)行自底向上的分析，構(gòu)造器其SLR項(xiàng)集族和語法分析表。（15分）當(dāng)輸入

字符串為7+5時回出對應(yīng)的語法制導(dǎo)翻譯棧過程。

的超陽EfTMLfE.v叫=bw帥

M今Wf'M」??？舫M”M巧

匕^十［NEifRwm=2.戰(zhàn)，

V今￡fMbi=2，M/VH2二7d

gw他如:￡、行

丁今numf工vM=|必以5M》

卬llDW（￡）-f射

p?gwIM）二f十

FOLL^IAJ（叼二f$y

f3w伊二f十$）

產(chǎn)&仙

1_HT

網(wǎng)qh，泗彳序二H

/EZJ

應(yīng)=7山山平

2.設(shè)定義在｛0,1｝上的正則語言S在倒數(shù)第二個字符為I的所有字符串組成

1）請給出該語言對應(yīng)的正則表達(dá)式；

2）構(gòu)造一個識別該語言的NFA,并構(gòu)造最小化DFA,要求寫出￡一40例犯法的確定化過程。

co「二1（。|,

NF6

^tart

Iztnw口乙°上工（小吵=后萍囹獷吩一廣上

而即如）工一［叫伍如0心（5D>XT加w。（也》（0/2,乃8

鱉國半S3Msk?咦-他<滬根平的c'

心華看小川用此⑻力刈?3何，弘M?23匹.p

m的Lc呼.0ML｛*（c公正“（w（f"）二4-

t>twa（.“C,8S<XQ5吸取力）彳〃2歷a

癡或D亦用U0sMmw口聯(lián)