1999年10月編譯方法試卷(本科)(北京)-自學(xué)考試

1、一、單項(xiàng)選擇題（在每小題的四個(gè)備選答案 中選出一個(gè)正確的答案，并將正確答案的號(hào) 碼填在題干后的括號(hào)內(nèi)，每小題 1分，共5分）1、設(shè) r=(a|b|c)(x|y|z)則 l (r)中元素為個(gè)()a9b6c18d272、正則集合l=an|n呈0相應(yīng)的正則表達(dá)式是。a. a*b . a+c. aa*d . aa+3、一個(gè)右線性文法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/fb . x:=a+(b+c)*d-e/fc . x:+a+b+c*(d-e)/fd .

2、 x:=a+b+c+(c*d)-e/f5、設(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不含生成式，則l (g)一定不含語(yǔ)句。2、設(shè)文法g (e為其開(kāi)始符號(hào))產(chǎn)生式如 下：ef e=t|tt*f|ff-(e) |i,貝u句型e+t+t* (e)的句柄是。3、算符優(yōu)先分析法每次歸約的都是句型的4、若x6l （g）,則一定有（其中g(shù)是文法）。5、ll （1）文法一定不含 遞歸三、判斷題（正確的在題后括號(hào)內(nèi)劃“遮誤的劃“x?！泵啃☆}1分，共5分）1、

3、左線性文法一定是二型（上下文無(wú)半） 文法。（）2、對(duì)任意的lr (1)文法g ,都存在dfam ,滿足 l (m) =l (g)。()3、對(duì)任何一個(gè)正則集合l,都有下正則表達(dá)式r,滿足l (r) =l。()4、任何文法的任何句子的句柄都是唯一的。5、ll (1)文法一定是無(wú)二義性的四、簡(jiǎn)答題(每小題 8分，共24分)1、給定文法g (s為開(kāi)始符號(hào))，其產(chǎn)生式如下：sf bs|aa| af ba|accf bcas|a試問(wèn)下列哪些符號(hào)串是 l (g)中的元素。ba121b100a2b1000aaa800b900a1b100002、構(gòu)造一個(gè)二型文法g,滿足l (g)=ambncndm|m1且n呈1

4、3、給定文法g (s為開(kāi)始符號(hào))其產(chǎn)生式如下s一 s_a|aa- a/b|bb 一 b1|b0|1|0構(gòu)造一個(gè)與 g等價(jià)的ll (1)文法g1,五、計(jì)算題(共56分)1、給定拓廣后的文法 g,其產(chǎn)生式(附有 編號(hào))如下：0.s f s1.s fwes2.sfi =e3.s f 4.s fe5efi(1)構(gòu)造識(shí)別文法g的所有活前綴的dfa (7分)。(2)構(gòu)造s和e的follow集合(4分)。(3)構(gòu)造文法g的slr (1)分析表(7分)2、設(shè)有變量說(shuō)明vara:array-1 2,-3 0,0 5ofinteger;i ,j,k,x,y:integer;假定w=2.試給出下面兩條 pascal

5、語(yǔ)句的三地址代碼語(yǔ)句及s nextlistwhile(x+y) ytheny:=y+5;x:=( i +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）為mr pf p- sf s- ch rft試畫(huà)出此時(shí)棧中的所有活動(dòng)記錄及每個(gè)活 動(dòng)記錄的控制鏈和存取鏈。(12分)4、某pascal程序中三地址代碼語(yǔ)句如下，其中t1是臨時(shí)變量，其它字母表示用戶定義的變量(1)為下面程序劃分基本塊并構(gòu)造流圖(7分)(2)出其相應(yīng)的pascal語(yǔ)句(不彳#含goto語(yǔ)句)(5分)(1) s:=0(2) i :=1