|
一九九九年下半年北京市高等教育自學考試
一、單項選擇題（在每小題的四個備選答案中選出一個正確的答案，並將正確答案的號碼填在題幹後的括號內，每小題1分，共5分）
1、設r=(a|b|c)(x|y|z)則L（r）中元素爲 個（ ） A．9 B．6 C．18 D．27
2、正則集合L={an|n≧0}相應的正則表達式是（ ） A．a* B．a+ C．aa* D．aa+
3、一個右線性文法G一定是 （ ） A．LL（1）文法 C．SLR（1）文法 B．LR（1）文法 D．上述三者都不是
4、xab + cde -*f/:=是賦值語句 相應的後綴式 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、設文法G（S爲其開始符號）產生式如下： S→aSb|ab|ε 則G是一個（ ） A．LR（1）文法 B．SLR（1）文法 C．三型文法 D．二型文法
二、填空題（每空2分，共10分）
1、若二型文法G不含ε_生成式，則L（G）一定不含語句 。
2、設文法G（E爲其開始符號）產生式如下： E→E=T|T T→T*F|F F→（E）|I 則句型E+T+T*（E）的句柄是 。
3、算符優先分析法每次歸約的都是句型的 。
4、若x∈L（G），則一定有 （其中G是文法）。
5、LL（1）文法一定不含 遞歸。
三、判斷題（正確的在題後括號內劃“√”錯誤的劃“×”。每小題1分，共5分）
1、左線性文法一定是二型（上下文無半）文法。（ ）
2、對任意的LR（1）文法G，都存在DFAM，滿足L（M）=L（G）。（ ）
3、對任何一個正則集合L，都有下正則表達式r，滿足L（r）=L。（ ）
4、任何文法的任何句子的句柄都是唯一的。（ ）
5、LL（1）文法一定是無二義性的。（ ）
四、簡答題（每小題8分，共24分）
1、給定文法G（S爲開始符號），其產生式如下： S→bS|aA|ε A→bA|Ac C→bCaS|a 試問下列哪些符號串是L（G）中的元素。 ba121b100a2 b1000aa a800b900a1 b10000
2、構造一個二型文法G，滿足L（G）={ambncndm|m≧1且n≧1}
3、給定文法G（S爲開始符號）其產生式如下 S→S_A|A A→A/B|B B→B1|B0|1|0 構造一個與G等價的LL（1）文法G1。
五、計算題（共56分）
1、給定拓廣後的文法G，其產生式（附有編號）如下： 0.S’→S 1.S→Wes 2.S→ⅰ=E 3.S→ε 4.S→E+ⅰ 5.E→ⅰ (1) 構造識別文法G的所有活前綴的DFA（7分）。 (2) 構造S和E的follow集合（4分）。 (3) 構造文法G的SLR（1）分析表（7分）
2、設有變量說明 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、設一個PASCAL程序由主程序M及過程P，Q，R，S，T構成，它們之間的句含關係如下圖所示 (圖缺失） 現在正在執行的調用（用X→Y表示X調用Y）爲 M→P→P→S→S→Q→R→T 試畫出此時棧中的所有活動記錄及每個活動記錄的控制鏈和存取鏈。（12分）
4、某PASCAL程序中三地址代碼語句如下，其中t1是臨時變量，其它字母表示用戶定義的變量 （1） 爲下面程序劃分基本塊並構造流圖（7分） （2） 出其相應的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表示程序停止執行
|
