第4頁(yè)（共8頁(yè)）南京航空航天大學(xué)第1頁(yè)（共8頁(yè)）二○一八～二○一九學(xué)年第一學(xué)期《編譯原理》考試試題考試日期：2019年1月15日試卷類型：B試卷代號(hào)：班號(hào)學(xué)號(hào)姓名題號(hào)一二三四五六七八九十總分得分本題分?jǐn)?shù)得分本題分?jǐn)?shù)得分簡(jiǎn)述編譯主要包括哪些過(guò)程及每一過(guò)程的主要工作？5分如果去掉C語(yǔ)言中過(guò)程的遞歸調(diào)用特點(diǎn)（即：過(guò)程不允許遞歸調(diào)用），其它特點(diǎn)不變，請(qǐng)說(shuō)明其運(yùn)行時(shí)需要采用何種存儲(chǔ)分配策略。已知文法G（E）：E→EiT|TT→T+F|iF|FF→E*|(請(qǐng)問(wèn)該文法是否是算符優(yōu)先文法，說(shuō)明理由。本題分?jǐn)?shù)得分二．寫(xiě)出一個(gè)文法使其語(yǔ)言為：L(G)={ancm本題分?jǐn)?shù)得分本題分?jǐn)?shù)得分三．已知文法G（E）：（10本題分?jǐn)?shù)得分E→（A）︱bE︱bA→A，E︱E（1）給出句型（E，（b））的最右推導(dǎo)，并給出其語(yǔ)法分析樹(shù)。（2）寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄。本題分?jǐn)?shù)得分四．已知正規(guī)式r=b(b|ab)*a，請(qǐng)給出與之等價(jià)的最小DFA（12分本題分?jǐn)?shù)得分本題分?jǐn)?shù)得分本題分?jǐn)?shù)得分S→BAA→BS|dB→aA|bS|c給出該文法的每一個(gè)非終結(jié)符的First集合與Follow集合給出該文法的預(yù)測(cè)分析表本題分?jǐn)?shù)得分本題分?jǐn)?shù)得分A→aABe|BaB→dB|ε（1）構(gòu)造識(shí)別該文法所以活前綴的項(xiàng)目集規(guī)范簇和DFA（2）構(gòu)造該文法的SLR分析表，并判斷是否為SLR（1）文法。本題分?jǐn)?shù)得分七．已知文法G（P）：本題分?jǐn)?shù)得分P→DD→D；D|id：T|procid；D；S寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義，打印該程序一共聲明了多少個(gè)id。寫(xiě)一個(gè)翻譯方案，打印該程序每個(gè)變量id的嵌套深度。為D設(shè)置一個(gè)綜合屬性i，用于計(jì)算D中含id的個(gè)數(shù)，語(yǔ)法制導(dǎo)定義如下：

產(chǎn)生式

語(yǔ)義規(guī)則

P->D

printf(D.i)

D->D1;D2

D.i:=D1.i+D2.i

D->id:T

D.i:=1

D->procid;D1;S

D.i:=D1.i+1

2：為D設(shè)置一個(gè)繼承屬性h，用以計(jì)算D所在的嵌套深度，翻譯方案如下：

P->{D.h:=1}D

D->{D1.h:=D.h}D1;{D2.h:=D.h}D2

D->id:T{print(，D.h)}

D->procid；{D1.h:=D.h+1}D1；S本題分?jǐn)?shù)得分八．本題分?jǐn)?shù)得分A:=0I:=1T:=5C:=2ifI=1Goto（17）S0:=2S1:=3/S0S2:=1.5S3:=T-CS4:=T+CR:=S0/S3H:=RS5:=S0S6:=T+CS7:=S5/S6H:=S7*S3B:=R+1D:=B+HifD=100Goto6D:=D+1halt1）劃分基本塊，構(gòu)造程序流圖。2）對(duì)含有S3:=T-C的基本塊進(jìn)行優(yōu)化，給出優(yōu)化后的四元式。本題分?jǐn)?shù)得分九．趣味題本題分?jǐn)?shù)得分針對(duì)你了解的網(wǎng)絡(luò)流行用語(yǔ)（比如“山寨”、“