1999年10月編譯方法試卷(本科)(北京)

　　1、設(shè)r=(a|b|c)(x|y|z)則L（r）中元素為 個(gè)（ ）
　　A．9 B．6 C．18 D．27

　　2、正則集合L={an|n≧0}相應(yīng)的正則表達(dá)式是（ ）
　　A．a(chǎn)* B．a(chǎn)+ C．a(chǎn)a* D．a(chǎn)a+

　　3、一個(gè)右線(xiàn)性文法G一定是 （ ）
　　A．LL（1）文法 　　B．LR（1）文法　　C．SLR（1）文法　　 D．上述三者都不是

　　4、xab + cde -*f/:=是賦值語(yǔ)句 相應(yīng)的后綴式
　　A．x:=a+b+c*d-e/f　　 B．x:=a+(b+c)*d-e/f　　　C．x:+a+b+c*(d-e)/f 　　D．x:=a+b+c+(c*d)-e/f

　　5、設(shè)文法G（S為其開(kāi)始符號(hào)）產(chǎn)生式如下：S→aSb|ab|ε 則G是一個(gè)（ ）
　　A．LR（1）文法　　 B．SLR（1）文法 　 C．三型文法 　　D．二型文法

　　二、填空題（每空2分，共10分）

　　1、若二型文法G不含ε_(tái)生成式，則L（G）一定不含語(yǔ)句_____________。

　　2、設(shè)文法G（E為其開(kāi)始符號(hào)）產(chǎn)生式如下： E→E=T|T T→T*F|F F→（E）|I　，則句型E+T+T*（E）的句柄是____________。

　　3、算符優(yōu)先分析法每次歸約的都是句型的__________。

　　4、若x∈L（G），則一定有______________ （其中G是文法）。

　　5、LL（1）文法一定不含__________ 遞歸。

　　三、判斷題（正確的在題后括號(hào)內(nèi)劃“√”錯(cuò)誤的劃“×”。每小題1分，共5分）

　　1、左線(xiàn)性文法一定是二型（上下文無(wú)半）文法。（ ）

　　2、對(duì)任意的LR（1）文法G，都存在DFAM，滿(mǎn)足L（M）=L（G）。（ ）

　　3、對(duì)任何一個(gè)正則集合L，都有下正則表達(dá)式r，滿(mǎn)足L（r）=L。（ ）

　　4、任何文法的任何句子的句柄都是唯一的。（ ）

　　5、LL（1）文法一定是無(wú)二義性的。（ ）

　　四、簡(jiǎn)答題（每小題8分，共24分）

　　1、給定文法G（S為開(kāi)始符號(hào)），其產(chǎn)生式如下：
　　S→bS|aA|ε
　　A→bA|Ac
　　C→bCaS|a
　　試問(wèn)下列哪些符號(hào)串是L（G）中的元素。
　　ba121b100a2 b1000aa a800b900a1 b10000

　　2、構(gòu)造一個(gè)二型文法G，滿(mǎn)足L（G）={ambncndm|m≧1且n≧1}

　　3、給定文法G（S為開(kāi)始符號(hào)）其產(chǎn)生式如下
　　S→S_A|A A→A/B|B B→B1|B0|1|0
　　構(gòu)造一個(gè)與G等價(jià)的LL（1）文法G1。

　　五、計(jì)算題（共56分）

　　1、給定拓廣后的文法G，其產(chǎn)生式（附有編號(hào)）如下：
　　0.S’→S 1.S→Wes 2.S→ⅰ=E
　　3.S→ε 4.S→E+ⅰ 5.E→ⅰ
　　(1) 構(gòu)造識(shí)別文法G的所有活前綴的DFA（7分）。
　　(2) 構(gòu)造S和E的follow集合（4分）。
　　(3) 構(gòu)造文法G的SLR（1）分析表（7分）

　　2、設(shè)有變量說(shuō)明
　　Var a:array[-1··2,-3··0,0··5]of integer;
　�、�,j,k,x,y:integer;
　　假定w=2.
　　試給出下面兩條Pascal語(yǔ)句的三地址代碼語(yǔ)句及S·nextlist
　　while(x+y)﹤a[ⅰ*j+2,j*3,k+5]do
　　if x﹥y then y:= y+5;
　　x:=(ⅰ+j)*k+y;(14分)

　　3、設(shè)一個(gè)PASCAL程序由主程序M及過(guò)程P，Q，R，S，T構(gòu)成，它們之間的句含關(guān)系如下圖所示
　　(圖缺失）
　　現(xiàn)在正在執(zhí)行的調(diào)用（用X→Y表示X調(diào)用Y）為
　　M→P→P→S→S→Q→R→T
　　試畫(huà)出此時(shí)棧中的所有活動(dòng)記錄及每個(gè)活動(dòng)記錄的控制鏈和存取鏈。（12分）

　　4、某PASCAL程序中三地址代碼語(yǔ)句如下，其中t1是臨時(shí)變量，其它字母表示用戶(hù)定義的變量
　�。�1） 為下面程序劃分基本塊并構(gòu)造流圖（7分）
　�。�2） 出其相應(yīng)的PASCAL語(yǔ)句（不得含goto語(yǔ)句）（5分）
　�。�1） s:=0
　�。�2） ⅰ:=1
　　（3） t1:= ⅰ+s
　�。�4） s:=t1
　　（5） ifⅰ﹤5goto (7)
　�。�6） goto(10)
　�。�7） t2:=ⅰ+1
　　（8） ⅰ:=t2
　�。�9） goto(12)
　　（10） t3: =ⅰ+2
　�。�11） ⅰ:=t3
　�。�12） ifⅰ﹥20goto(14)
　�。�13） goto(3)
　�。�14） halt
　　注：halt表示程序停止執(zhí)行