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

　　1、設(shè)r=(a|b|c)(x|y|z)則L（r）中元素為 個（ ）
　　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一定是 （ ）
　　A．LL（1）文法 　　B．LR（1）文法　　C．SLR（1）文法　　 D．上述三者都不是

　　4、xab + cde -*f/:=是賦值語句 相應(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為其開始符號）產(chǎn)生式如下：S→aSb|ab|ε 則G是一個（ ）
　　A．LR（1）文法　　 B．SLR（1）文法 　 C．三型文法 　　D．二型文法

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

　　1、若二型文法G不含ε_生成式，則L（G）一定不含語句_____________。

　　2、設(shè)文法G（E為其開始符號）產(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）文法一定不含__________ 遞歸。

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

　　1、左線性文法一定是二型（上下文無半）文法。（ ）

　　2、對任意的LR（1）文法G，都存在DFAM，滿足L（M）=L（G）。（ ）

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

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

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

　　四、簡答題（每小題8分，共24分）

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

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

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

　　五、計算題（共56分）

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

　　2、設(shè)有變量說明
　　Var a:array[-1··2,-3··0,0··5]of integer;
　�、�,j,k,x,y:integer;
　　假定w=2.
　　試給出下面兩條Pascal語句的三地址代碼語句及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è)一個PASCAL程序由主程序M及過程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
　　試畫出此時棧中的所有活動記錄及每個活動記錄的控制鏈和存取鏈。（12分）

　　4、某PASCAL程序中三地址代碼語句如下，其中t1是臨時變量，其它字母表示用戶定義的變量
　　（1） 為下面程序劃分基本塊并構(gòu)造流圖（7分）
　�。�2） 出其相應(yīng)的PASCAL語句（不得含goto語句）（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í)行