編譯原理期末考試試卷(A卷)

編譯原理期末考試試卷(A卷）簡(jiǎn)述編譯程序的工作過(guò)程.（10)二、構(gòu)造下列正規(guī)式相應(yīng)的DFA(用狀態(tài)轉(zhuǎn)換圖表示)(15）1(0｜1)＊1000＊10*10*10*1letter（letter｜digit）＊三、給出下面語(yǔ)言的相應(yīng)文法：（15）L1=｛anbn|n≥1}L2={anbm+nam|n≥1，m≥0｝四、對(duì)下面的文法G:S→a|b|(T）T→T,S｜S（1)消去文法的左遞歸，得到等價(jià)的文法G2;(2)判斷文法G2是否LL（1）文法,如果是，給出其預(yù)測(cè)分析表。（15）五、設(shè)有文法G[A]：A→BCc｜gDBB→bCDE|εC→DaB｜c(diǎn)aD→dD｜εE→gAf｜c(diǎn)計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集；試判斷該文法是否為L(zhǎng)L(1）文法。(15）六、對(duì)表達(dá)式文法G:E→E+T｜TT→T*F｜FF→（E)｜I(1）造各非終結(jié)符的FIRSTVT和LASTVT集合；（2)構(gòu)造文法的算符優(yōu)先關(guān)系表。（15）七、有定義二進(jìn)制整數(shù)的文法如下：L→LB｜BB→0|1構(gòu)造一個(gè)翻譯模式，計(jì)算該二進(jìn)制數(shù)的值(十進(jìn)制的值)。（15)簡(jiǎn)述編譯程序的工作過(guò)程。（10）編譯程序的工作過(guò)程，是指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程，是非常復(fù)雜的，就其過(guò)程而言，一般可以劃分為五個(gè)工作階段：①詞法分析，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞；②語(yǔ)法分析，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位;③語(yǔ)義分析與中間代碼產(chǎn)生，即對(duì)各類語(yǔ)法單位，分析其漢一并進(jìn)行初步翻譯；④代碼優(yōu)化，以期產(chǎn)生更高效的代碼；⑤目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言指令形式.二、構(gòu)造下列正規(guī)式相應(yīng)的DFA(用狀態(tài)轉(zhuǎn)換圖表示）（15)1（0|1）*10,10,1letter(letter｜digit）*31031021(1）21000051（2）51104130211104130211letter（3）letter2letter2letter11digitdigit三、給出下面語(yǔ)言的相應(yīng)文法：（15）L1=｛anbn｜n≥1｝L2=｛anbm+nam｜n≥1,m≥0}G1：SG1：S→ABA→aAb|abB→bBa|εG1：A→aAb|ab四、對(duì)下面的文法G：S→a|b｜（T）T→T，S｜S（1)消去文法的左遞歸,得到等價(jià)的文法G2；(2）判斷文法G2是否LL（1）文法，如果是，給出其預(yù)測(cè)分析表。（15)G2：S→a|b｜（T）T→ST’T’→，ST’|εG2是LL(1）文法。ab（），＃SS→aS→bS→（T）TT→ST'T→ST’T→ST’T’T’→εT’→，ST’五、設(shè)有文法G[A]：A→BCc｜gDBB→bCDE|εC→DaB|caD→dD｜εE→gAf|c計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集；試判斷該文法是否為L(zhǎng)L(1）文法。（15）FIRSTFOLLOWABCDEA，b,c，d,gbA,c,dDC，gA,c，dC，d，gA，b,c，g是LL(1）文法。六、對(duì)表達(dá)式文法G：E→E+T|TT→T*F｜FF→（E）｜I（1）造各非終結(jié)符的FIRSTVT和LASTVT集合；（2）構(gòu)造文法的算符優(yōu)先關(guān)系表.（15)FIRSTVTLASTVTETF＊,+,(,i*，（，i（，i*，+，），i*，），i），i算符優(yōu)先關(guān)系表+*I（）＃+*I()＃〉>〉〈><<>><>〈〈<〈〈<〈〈〈>>>=〉>>〉〉=七、有定義二進(jìn)制整數(shù)的文法如下:L→LB｜BB→0|1構(gòu)造一個(gè)翻譯模式，計(jì)算該二進(jìn)制數(shù)的值(十進(jìn)制的值）。（15）引入L、B的綜合屬性val,翻譯模式為：S→L｛print（L.val)｝L→L1B{L.val