江南大學(xué)《編譯原理》試卷參考 答案(2010A)

1、 江南大學(xué)考20092010第二學(xué)期編譯原理期末考試試卷 （A）使用專業(yè)、班級(jí) 學(xué)號(hào) 姓名 題數(shù)一二三四五六七總分得分 一、選擇填空每空1分，共計(jì)20分1編譯程序?qū)⒃闯绦蚣庸こ赡繕?biāo)程序是 C 之間的轉(zhuǎn)換。A詞法 B語(yǔ)法 C語(yǔ)義 D規(guī)則2開發(fā)一個(gè)編譯程序應(yīng)掌握 D 。A源語(yǔ)言 B目標(biāo)語(yǔ)言 C編譯技術(shù) D以上三項(xiàng)都是 3詞法分析器的輸出結(jié)果是 B 。A單詞自身 B單詞的機(jī)內(nèi)符C單詞的詞義信息 D單詞的詞法信息 4稱有限自動(dòng)機(jī)A1和A2等價(jià)是指 D 。AA1和A2都是定義在一個(gè)字母表上的有限自動(dòng)機(jī)BA1和A2狀態(tài)數(shù)和有向邊數(shù)相等CA1和A2狀態(tài)數(shù)或有向邊數(shù)相等DA1和A2所能識(shí)別的字符串集合相同5同

2、正則表達(dá)式(a | b)+等價(jià)的正則表達(dá)式是 B 。 A(a | b) * B(a | b) (a | b) *C(a b)* (a b) D(a | b)| (a | b)*6前后文無(wú)關(guān)文法G：S S | 所產(chǎn)生的語(yǔ)言是 D 。 A m n （m，n0） B m n （m，n1）C m m （m0） D n n（n1） 7由文法的開始符出發(fā)通過(guò)若干步（包括0步）推導(dǎo)產(chǎn)生的文法符號(hào)序列是 B 。A語(yǔ)言 B句型 C句子 D句柄8最左簡(jiǎn)單子樹的葉結(jié)點(diǎn)，自左至右排列組成句型的 C 。A短語(yǔ) B簡(jiǎn)單短語(yǔ) C句柄 D素短語(yǔ)9簡(jiǎn)單優(yōu)先分析法每次都是對(duì) D 進(jìn)行歸約。A短語(yǔ) B簡(jiǎn)單短語(yǔ)C素短語(yǔ) D句柄考試形

3、式開卷（ ）、閉卷（），在選項(xiàng)上打（）（1）開課教研室 命題教師 命題時(shí)間 試卷專用紙 10一個(gè)文法G是LL(1)文法的充要條件是對(duì)每一個(gè)非終結(jié)符A的任意兩個(gè)不同產(chǎn)生式A | ，有 C 。AFIRST()FIRST()=BFIRST()FOLLOW(A)=CSELECT(A)SELECT(A)=DSELECT(A)SELECT(A)11一個(gè)文法G，若 C ，則稱它是LL(1)文法。AG中不含左遞歸BG無(wú)二義性CG的LL(1)分析表不含多重定義DG中產(chǎn)生式不含左公因子 12若a為終結(jié)符，則A a為 A 項(xiàng)目。A移入 B待約 C歸約 D接受13設(shè)有文法G=(S，a， SSaS | ，S)，該文法是

4、 D 。ALL(1)文法 BLR(0)文法C簡(jiǎn)單優(yōu)先文法 D二義性文法14LR分析器核心部分是一張分析表，該表由 D 組成。AACTION表 BGOTO表 CLL(1)分析表 DACTION表和GOTO表15可歸前綴是指 C 。 A規(guī)范句型的前綴 B活前綴 C含有句柄的活前綴 D句柄16編譯程序的語(yǔ)法分析器必須輸出的信息是 A 。A語(yǔ)法錯(cuò)誤信息 B語(yǔ)法規(guī)則信息 C語(yǔ)法分析過(guò)程 D語(yǔ)句序列 17下列錯(cuò)誤屬于靜態(tài)語(yǔ)義錯(cuò)誤的是 C 。A括弧不配對(duì) B出現(xiàn)非法字符C類型不相容 D溢出 18在語(yǔ)法制導(dǎo)翻譯中不采用拉鏈回填技術(shù)的語(yǔ)句是 B 。A轉(zhuǎn)向語(yǔ)句 B賦值語(yǔ)句C條件語(yǔ)句 D循環(huán)語(yǔ)句 19下面逆波蘭式（

5、后綴式）中，能正確表示算術(shù)表達(dá)式a+b+c+d的是 D 。Aabcd+ Babc+d+Cab+cd+ Dab+c+d+ 20屬于標(biāo)識(shí)符“種屬”屬性信息的描述是 B 。A整型 B變量 C地址 D指針使用學(xué)期 總張數(shù) 教研室主任審核簽字 江南大學(xué)考 二、文法和語(yǔ)言類型題1小題10分，2小題5分，共計(jì)15分1設(shè)有文法GS：E E+T | E-T | TT T*F | T/F | FF x | y | z | (E) (1) 給出對(duì)于句子x+y*x-z的最右推導(dǎo)過(guò)程E = E-T= E -F= E -z= E+T -z= E+ T*F -z = E+T*x -z= E+F*x -z= E+y*x -z

6、= T+y*x -z= F+y*x -z= x+y*x -z (2) 試構(gòu)造句型(E+T)-(T+F)的語(yǔ)法樹xFTyxFT * FEE TFzE + T (3) 基于上述語(yǔ)法樹給出該句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。短語(yǔ)：x+y*x-z、x+y*x、y*x、x（1）、y、x（2）、z簡(jiǎn)單短語(yǔ)：x（1）、y、x（2）、z句柄：x（1）試卷 專用紙2試構(gòu)造文法G，L(G)=a2m b2n+1 | m1，n0。 G： S A BA aaA | aaB bbB | b 三、詞法分析類題每小題5分，共計(jì)15分1令：L = A | B | | Z | a | b | | zD = 0 | 1 | 2 | 3

7、| | 9試構(gòu)造描述C語(yǔ)言標(biāo)識(shí)符集的正則表達(dá)式。 (L | _ ) (L | D | _ )*S1BCA00D11102設(shè)有如下DFA試構(gòu)造與之等價(jià)的3型文法。 G：S 1A A 0B | B 1B | 0C C 0D D 1B | 0C | 江南大學(xué)考 a,bX3設(shè)有如下NFA：試完成下列（右側(cè)）NFA到DFA狀態(tài)表的構(gòu)造，將該NFA確定化為DFAIaIb-SASASASXZ+XZXZXYZ+XYZXZXYZbYbbaASaZba,b 四、自上而下語(yǔ)法分析類型題每題5分，共計(jì)15分；1對(duì)文法GS：S BA A abB | B Acd | dc | eb（1）求如下每條產(chǎn)生式的SELECT集合

8、。SELECT( S BA ) = a , c , d ,e SELECT( A abB ) = a SELECT( A ) = c , # SELECT( B Acd ) = a , c SELECT( B dc ) = d SELECT( B eb ) = e （2）證明這個(gè)文法是否為L(zhǎng)L(1)文法。 由于SELECT( A abB ) SELECT( A )= a c , # =SELECT(BAcd)SELECT( B dc)SELECT( B eb)= a , c d e = 滿足LL（1）文法條件，所以該文法是LL（1）文法。 = 試卷專用紙（3）無(wú)論GS是否LL(1)文法，試完成

9、下列LL(1)分析表的構(gòu)造。 VTVN a b cd e #SSBASBASBASBA AAabBAA BBAcdBdcBeb #acc 五、自下而上語(yǔ)法分析類型題每題10分，共計(jì)20分；1設(shè)有文法GS：S Aa | bAA cd | cAd (1) 完成下列優(yōu)先關(guān)系矩陣的構(gòu)造 SA a bcd#S A a b c d# (2) 基于上述優(yōu)先關(guān)系矩陣，按下面要求回答上述文法GS是否為簡(jiǎn)單優(yōu)先文法并說(shuō)明其原因 該文法GS（ 是 ）簡(jiǎn)單優(yōu)先文法； 原因是：優(yōu)先關(guān)系矩陣不存在兩個(gè)以上關(guān)系的元素。江南大學(xué)考2. 設(shè)有如下文法GS:SEFEaE | ab FFb | ba (1) 完成下列LR(0)項(xiàng)目

10、集規(guī)范族(可歸前綴圖)的構(gòu)造I8:EabbaI0:SEFEaEEabI1:EaEEabEaEEabaI2:EaEEEI3:SEFFFbFbaI4: FbabaI5: FbaFI7:FFbI6:SEFFFbb(2) 基于該LR(0)可歸前綴圖，按下面要求回答上述文法GS是否為L(zhǎng)R(0)文法并說(shuō)明其原因。 該文法GS( 不是 )LR(0)文法 原因是：項(xiàng)目集規(guī)范族(可歸前綴圖)中項(xiàng)目集I6存在“移入歸約”項(xiàng)目沖突。試卷專用紙六、代碼生成類題每題5分，共計(jì)15分；1設(shè)有一語(yǔ)法制導(dǎo)翻譯算法如下：SE print “E” EE+T print “+” ET print “T” TT*F print “*

11、” TF print “F” Fid print “id”若輸入序列為a+b*c，且采用自底向上的分析方法，則給出輸出序列。輸出序列：aFTbF*+E2試給出表達(dá)式w=x+y-z*(a+b)*c規(guī)范和簡(jiǎn)易的四元式序列。規(guī)范的四元式序列 簡(jiǎn)易的四元式序列1（+, x, y, T1） T1:= x+y2（+, a, b, T2） T2:= a+b3（*, z, T2, T3） T3:= z*T24（*, T3, c, T4） T4:= T3* c5（-, T1, T4, T5） T5:= T1-T4 6（:=, T5 , _ , w） w:= T53是給出布爾表達(dá)式ab and cd or ef or gh的四元式序列，且求其真、假鏈 四