《編譯原理》練習測試題庫

壹、填空

1.若源程序是用高級^言編寫的，目的程序是，則其翻譯程序稱卷編譯程序。

2.同法分析和^法分析本質(zhì)上都是射源程序的逸行分析。

3.假如源^言（編寫源程序的^言）是高級^言，而目的^言是某計算機的匯編^言或機器^

言，則追種翻譯程序稱卷o

4.封編譯程序而言，輸入數(shù)據(jù)是，輸出成果是0

5.____,是構(gòu)成^言文法的覃同，是言吾法成分的最小罩位。

6.由PL/0的EBNF可知，PL/0^言可常作是PASCAL^言的子集，它的編譯程序是壹種

O

7.由于PL/0編譯程序采用,因此^法分析通程BLOCK是整（I同編譯遇程的關(guān)鍵。

8.用韓去圖描述^法規(guī)則為畏處是、o

9.每他非終止符是壹種^法成分，在耆寫^言程序畤并不出現(xiàn)，它是由和

、或終止符串定義的。

10.PL/0的目的程序卷假想棧式計算機的匯編者吾言，與詳細計算機____o

11.PL/0的編譯程存和目的程序的解釋執(zhí)行程序都足用古寫的，因此PL/0^言可

在配置________的任何機器上實垣。

12.PL/0編譯程序是用PASCAL^言善寫的，整倜編譯程序（包括主程序）是由____他嵌套

及并列的遇程或函數(shù)構(gòu)成

13.富源程序編譯封的畤，PL/O編譯程序自助調(diào)用,封目的代碼暹行解釋執(zhí)行,

并按顧客程序規(guī)定輸入數(shù)據(jù)和輸出運行成果。

14.由于封某些非終止符可以遞歸定義，道就使得可用有窮的文法描述。

15.的任務(wù)是識別由施）法分析余臺出的軍同符號序列在構(gòu)造上與否符合給定的文法規(guī)

則。

16.PL/0編譯程序的^法分析采用了。

17.^法分析程序除纏控外重要有兩大部分的功能，即________和__________.

18.PL/0的弱J法分析程序GETSYM,是壹種獨立的謾程,其功能是卷提供罩前J用的,

是的基礎(chǔ)，它把輸入的字符串形式的源程序分割成壹種他單同符號。

19.每他謾程應(yīng)有遇程首哲以定義局部于它自己謾程的常量、變晟和謾程內(nèi)票識符，也稱。

20.同法分析程序GETSYM將完畢的任務(wù)有:識別保留字；，拼數(shù)，拼復(fù)合前I,

輸出源程序.

21.假如壹種PL/0^言的罩前I序列在整他|言吾法分析中，都能逐壹得到匹配,直到,

造疇就^所輸入的程序是封的的。

22.若要構(gòu)造程序設(shè)計^言的編譯程序，則首先要封程序設(shè)計許吾言自身有較卷精確的描述。

而有關(guān)程序設(shè)計^言的描述，將波及、^義和______三他方面。

23.但凡具有某種特殊性質(zhì)的客體的聚合，都可稱卷。

24.假如集合中元素他數(shù)卷零，即集合中不具有任何元素，道樣的集合稱卷，記^小。

25.設(shè)有集合A和B,假如A和B有相似的元素，則稱道兩他集合是_____.

26.設(shè)A、B卷任意兩他集合，由所有屬于集合A或?qū)儆诩螧的元素構(gòu)成的集合，叫做集合

A與B的_______.

27.設(shè)A、任意兩（周集合，由所有用于集合A且屬于集合B的元素構(gòu)成的集合，稱卷集

合A與B的_______.

28.假如壹種集合，它能包括我ffl所要考慮目的之內(nèi)的所有元素，則稱此集合卷,記

Eo

29.設(shè)A卷壹集合，由A的所有子集(包括空集及A自身)所構(gòu)成的集合，稱卷A的.

30.由兩他按壹定次序排列的客體構(gòu)成的序列，稱卷.

31.設(shè)A和B卷任意兩值I集合，若序偶的第壹種組員是英合A的壹種元素，第二他組員是集

合B的壹種元素，則所有it樣的序偶構(gòu)成的集合稱卷集合A和B的.

32.在集合X上的關(guān)系R,如封任意x￡X,均有(x,x)ER,則稱關(guān)系R是____o

33.在集合X上的關(guān)系R,假如合(x,y)￡R,便必有(y,x)GR,則稱關(guān)系R是。

34.在集合X上的關(guān)系R,假如合(x,y)OR且(y,z)OR,必有(x,z)OR,則稱關(guān)系R

是o

35.例設(shè)P={(1,2),(3,4),(2,2)}Q={(4,7),(2,9),(3,1)}

則P-Q=

36.符號串與符號構(gòu)成次序,如符號串a(chǎn)bba,符號申001也____010。

37.假設(shè)G是壹種文法，S是文法的I剁始符號，假如S=>*x,則稱x是_______。

38.文法G產(chǎn)生的的全體是該文法描述的言吾言。

39.壹種文法G[Z]若存在推導(dǎo)序列Z=>+???Z???,

則稱G(z)是______文法，此類文法所產(chǎn)生的句子有他I。

40.喬姆斯基把文法提成一類型.

41.四體1文法類的定義是逐漸增晨限制的，因此每壹種正規(guī)文法都是

42.最右推導(dǎo)常被稱懸。

43.由規(guī)范推導(dǎo)所得的句型稱卷。

44.文法的二義性和^言的二義性是兩他的概念。

45.封于上下文輾關(guān)文法，是句型推導(dǎo)遇程的幾何表達。

46.直接短言吾也稱.

47.每棵^法樹的葉子構(gòu)成壹種.

48.每棵子樹的葉子構(gòu)成壹種____.

49.每棵簡樸子樹的葉子構(gòu)成宜種.

50.最左邊簡樸子樹的葉子構(gòu)成.

51.壹種句型的最左直接短^稱卷該句型的o

52.有關(guān)句型或句子的直接推導(dǎo)〃=>〃和推導(dǎo)〃二〉+〃，實際上均可視懸符號串之間關(guān)系，并且推

導(dǎo)”=>+〃卷直接推導(dǎo)〃=>”的。

53.是^言文法的等價表達，可用它來替代BNF規(guī)則集合。

54.某條規(guī)則U-u中的左部符號U(U不是識別符號)，不在所屬文法的任何其他規(guī)則右部出

垣，那么道條規(guī)則在推導(dǎo)中不起作用，即所有句子的推導(dǎo)宜直不畬用到此規(guī)則，顯然造種規(guī)

則是多出的。也稱迨種非終止符卷________.

55.彳龍文法的某倜非終止符號U推不出終止符號串，顯然，所有具有U的規(guī)則是多出的。也

稱適種非終止符懸o

56.若L是上下文有關(guān)^言、上下文瓢關(guān)^言或正規(guī)^言，則LU")和L-屋)分別是上

下文有關(guān)^言、和正規(guī)^言。

57.設(shè)有文法G,封于其中某壹非終止符號U也^作出某些不壹樣推導(dǎo)U=>+Sx,其中S叫

豆真符號，由于推導(dǎo)不壹樣，由U產(chǎn)生的^符號S也也^不壹樣，道些^符號S構(gòu)成的集合，

稱卷U的推導(dǎo)的__________.

58.壹種上下文輾關(guān)文法C包括四倜構(gòu)成部分依次是：.11

59.文法所描述的^言是_____的集合。

60.^1法分析器工作的第壹步是輸入源程序文本。輸入串壹般是放在壹種緩沖區(qū)中，造倜緩

沖區(qū)稱________o

二、選擇

I.編譯程序是壹種常用的軟件。

A.應(yīng)用B.系統(tǒng)C.工具D.測試

2.在使用高級言編程畤，首先可通遇編譯程序發(fā)現(xiàn)源程序的所有籍誤和部分

^誤。

法義用D.運行

3.編譯程序生成的目的程序是機器^言的程序。

A.壹定B.不壹定C某種狀況下壹定D.某種狀況下不壹定

4.編譯程序生成的目的程序是可執(zhí)行的程序。

A.壹定B.不壹定C.某種狀況下壹定D.某種狀況下不壹定

5.壹種言的文法是.

A.惟壹的B.不惟壹的C.他數(shù)有限的D.簸限的

6.巴科斯-諾爾范式(即BNF)是壹種廣泛采用的的工具。

A.描述規(guī)則B.描述言吾言C.描述文法D.描述句子

7.設(shè)r=(a|b|c)(x|y|z)則L(r)中元素卷(0()

A.9B.6C.18D.27

8^正則集合L={an|n工()}封應(yīng)的正則體土兄式是()

A.a*B.a+C.aa*D.aa+

9.編譯謾程中掃描器的任務(wù)包括。

①組織源程序的輸入

②按同法規(guī)則分割出軍*司，識別出其屬性，并轉(zhuǎn)換成屬性字的形式輸出

⑧刪除注解

④刪除空格及輾用字符

⑤行計數(shù)、列計數(shù)

⑥發(fā)現(xiàn)并定位同法拿昔誤

⑦建立符號表

A.⑦B.②③④⑥⑦C.①②③④?0D.①?@?⑤⑥⑦

10、編譯謾程中，言吾法分析器的任務(wù)是______。

a.分析單同是怎樣構(gòu)成的

b.分析罩前］串是怎樣構(gòu)成言吾句和闡明的

c.分析^句和闡明是怎樣構(gòu)成程序的

d.分析程序的構(gòu)造

A.bcBdC.bedD.abed

11、法分析的常用措施是O

a.自頂向下b.自底向上c.自左向右d.自右向左

A.abedB.abC.cdD.abc

12、編譯程序中的言吾法分析器接受以卷電位的輸入，并產(chǎn)生有關(guān)信息供彼來各階

段使用。

A.體現(xiàn)式B.產(chǎn)生式C.D.^句

13、LL(1)文法的條件是______°

A.封形如U->XI|X2卜??|Xn的規(guī)則，規(guī)定FIRST(Xi)CFIRST(Xj尸①，(iWj)

C.a和bD.都不是

23.代碼優(yōu)化的重要目的是()12

①怎樣提高目的程序的運行速度

②怎樣減少目的程序運行所需的空間

③怎樣協(xié)調(diào)①和②

④怎樣使生成的目的代碼盡量短

A①②B①②③C①②④D①②③④

24、設(shè)文法G(S卷其^始符號)產(chǎn)生式如下：

S-*aSb|ab|E則G是壹種()

A.LR(1)文法B.SLR(1)文法

C.三型文法D.二型文法

25在編譯程序采用的優(yōu)化措施中，是在循環(huán)^句范圍內(nèi)迤行的。12

①合并己知常量②刪除多出運算，

③刪除歸納變量④強度減弱

⑤代碼外提

A①④B①⑤C⑤D③④⑤

26合并體現(xiàn)式中常量運算的目的是o12

①合并常量，使體現(xiàn)式中的常量盡量少

②合并常量，使體現(xiàn)式盡量簡短

③將可在編譯畤刻計算的常量運算在編譯畤刻計算出來，然彳爰用所計算出來的值替代體

現(xiàn)式中出現(xiàn)的所有適種常量運算，使得生成的代碼指令盡量少

A①B②C③D①②③

27下面的程序段可以暹行哪些優(yōu)化。12

i：=1

j：=10

readk

L：x：=x*i

y：=j*i

z：=x*y

writej

i：=i+l

ifi<100gotoL

halt

①合并i2知常量②刪除多出運算

③刪除歸納變量④強度減弱

⑤代碼外提

可選項有：

A.??B①⑤C,①④⑤D.③④⑤

28.屬于低級^言的是()

AFortranB.PascalC.LispDMasm

29.設(shè)oci是字母表｛0,1,…，7｝中的任何壹種元素,表達CIS言的八暹制輾符號整規(guī)體瑰

式是()。

A.(ocl)8B.(oct)*C.(oct)+D.(ocl)#

30.采用()實垣三地址代碼疇，不利于封中間代碼暹行優(yōu)化。

A.四元式B.間接三元式C.三元式D.有向輾循環(huán)圖

31.壹種正規(guī)^言只能封應(yīng)()?

A壹種正規(guī)文法；

B壹種最小有限狀態(tài)臼勛機；

C.壹種下推自勤機

D.壹種確定的有限自勤機

32.文法G[A]：A->￡A->aBB->AbB^a)：

A正規(guī)文法B二型文法

C.上下輾關(guān)文法D.不確定

33.下面^法封的的是()：

A壹種SLR(1)文法壹定也是LALR(1)文法

B壹種LR(1)文法壹定也是LALR(1)文法

34.壹種上下文輾關(guān)文法消除了左遞歸，提取了左公共因子彼是滿足LL(1)文法的()：

A.必要條件

B.充足必要條件

C.充足條件

D.輾法確定

35.PL/O^言的日的程序解程執(zhí)行畤用到的數(shù)據(jù)封象有()：

A目的代碼CODE

B符號表TABLE

C關(guān)鍵字表WORD

D數(shù)據(jù)棧S

36.PL/O言編譯畤產(chǎn)生或使用的數(shù)據(jù)封象不包括()：

A目的代碼CODE

B符號表TABLE

C數(shù)據(jù)棧S

D關(guān)鍵字表WORD

37、編譯程序是壹種常用的軟件。

A.應(yīng)用B.系統(tǒng)C支撐D.自勃化

38、在使用高級^言編程畤，首先可通謾編譯程序發(fā)現(xiàn)源程序的所有拿普誤和部分^義

拿背誤。

人信吾法B^義C,^用D.運行

39.壹種LR(1)文法合并同心集彳菱若不是LALR(1)文法：

A則也^存在移迭/歸約沖突

B則也^存在歸約/歸約沖突

C則也言午存在移選/歸約沖突和歸約/歸約沖突

D不存在沖突

40、運算符與運算射象類型不符”屬于。

人信吾法^誤B.^義皓?誤C,^用金音誤D.規(guī)則

三、簡答題

1.“具有優(yōu)化部分的編譯程序的執(zhí)行效率高”，道種^法封的嗎？

2.有人認卷編譯程序的五(I司構(gòu)成部分卻壹不可，道種見解封的嗎？

3.解釋程序定義哪些寄存器？

4.PL/O編譯程序笠於吾法籍誤的處理采用哪兩種措施？

5.解釋闡明指令LIT?LOD?STO?CAL?INT?JMP?JPC?0PR?5

6.已知文法G(S)

S-a|A|(T)

T-T,S|S

寫出句子((a,a),a)的規(guī)范歸約遇程及每壹步的句柄。

7.何謂優(yōu)化？按所波及的程序范圍可分懸哪幾級優(yōu)化？

8.目的代碼有哪幾種形式？生成目的代碼畤壹般應(yīng)考慮哪幾種冏題？

9.寫出體現(xiàn)式(a+b*c)/(a+b)—d的逆波蘭表達及三元式序列。

10.寫壹種文法，使其^言是奇數(shù)集，且每低1奇數(shù)不以()IR^。

11.編譯程序的構(gòu)造是什么？

12.關(guān)系有哪些基本性質(zhì)？

13.解釋字母表，符號，符號串，符號串的展:度,符號串聯(lián)結(jié)？

14.自下而上分析算法的基本思想是什么？

15.設(shè)有文法G：

s::=Qc|c

Q::=Rb|b

R::=Sa|a

試求HARD(S),HARD(Q),HARD(R).

16.用擴充的BNF范式表達下述文法以消去￡規(guī)則：

S::=aABb|ab

A::=Aab|￡

B::=Aa|a

17.考慮下面程序

Vara：integer；

ProcedureS(X)；

VarX：integer；

Begin

a：=a+1；

X：=a+X

End；

Begin

a：=5；

S(a)：

Print(a)

End.

試冏：若參數(shù)傳遞方式分別采用傳名和傳值畤，程序執(zhí)行彳麥輸出a的值是什么？

18.設(shè)有文法G[I]:8

l->Il/I0/Ia/lc/a/b/c

判斷下面符號串中哪些是該文法的句子.

(l)abO

(2)a0c01

(3)aaa

(4)bcl0

(5)aabc

(6)bbca

19?卷了封的地封源程序造行編譯，不容^文法有二義性，那么怎樣才能排除文法的二義性

呢?9

20.什么是簡樸子樹？

21.什么是子樹？

22.什么是句型的分析？

23.自下而上分析算法的基木思想是什么？

24.設(shè)有文法G：

s::=Qc|c

Q::=Rb|b

R::=Sa|a

試求HARD(S),HARD(Q),HARD(R).

四、綜合題

1.Whilea>0Vb<0do

Begin

X：=X+1；

ifa>0thena：=a—1

elseb：=b+l

End；

翻譯成四元式序列。

2.設(shè)布爾體現(xiàn)式的文法卷

E一E⑴VE⑵

E-E⑴AE⑵

E—i

假定它儼將用于條件控制^句中，m

(1)改寫文法，使之適合迤行^法制導(dǎo)翻譯和實垣回填；

(2)寫出改寫彳發(fā)的短[固產(chǎn)生式的^義勤作。

3設(shè)文法G(S)：

S—*(L)|aS|a

L-L,S|S

(1)消除左遞歸和回溯；

(2)計算每值I非終止符的FIRST和FOLLOW；

4.封下列文法G:26

S'->#s#

S->D(R)

R->R;P|p

P->S|i

D->i

計算文法中每佃非終止符的FIRSTVT集和LASTVT集。

5.將下列賦值^句譯成三地址代碼。A[i,j]:=B[i,j]+C[A[k,1]]+D[i+j]

6、設(shè)布爾體現(xiàn)式的文法懸

E-*E(1)VE(2)

E-*E(1)AE(2)

E—i

假定它儼J將用于條色控制^句中，M

(1)改寫文法，使之適合暹行者普法制導(dǎo)翻譯和實現(xiàn)回填；

(2)寫出改寫彳灸的短低產(chǎn)生式的^義勒作。

7、(8分)給定PASCAL程序句

whilea>bdoifa>0thena:=a-lelsea:=a+l;

1.將該^句翻譯成逆波蘭式；

2.給出編譯程序掃描到then處及分號處畤所得的四元式序列。

8.怎樣計算FIRST集？

《編譯原理》練習測試題庫參照答案

壹、填空

1.機器^言程序或匯編程序

2.構(gòu)造

3.編譯程序

4.源程序，H的程序。

5.終止符

6.編譯解釋執(zhí)行系統(tǒng)

7.壹趟掃描措施

8.直觀、易^

9.終止符和非終止符串

10.輾關(guān)

11.PASCALW

12.18

13.解釋執(zhí)行程序

14.融窮的句子集

15JM法分析

16.自頂向下的遞歸子程序法

17.闡明部分的處理，程序體部分的處理

18.言吾法分析法分析

19局部量

20濾空格，識別襟識符，輸出源程序

21程序結(jié)束符

22京吾法W吾用

23.集合

24.空集

25.相等的

26.并集

27.交集

28.全集

29.靠集

30.序偶

31.笛卡爾乘積

32.自反的

33第稱的

34.傳遞的

35.{(I,9),(3,7),(2,5))

36.有關(guān)，不壹樣于，不壹樣于

37.句型

38.句子

39.(1)遞歸(2讖數(shù)

40.四種

41.上下文輾關(guān)的

42.規(guī)范推導(dǎo)

43.規(guī)范句型

44.不壹樣

45京吾法樹

46.簡樸短^

47.句型

48.短i借

49.簡樸短^

50.句柄

5L句柄

52.傳遞閉包

53.言吾法圖

54.不可到達的

55.不可終止的

56.上下文趣關(guān)^言

57.HH符號集合

58.終止符號，非終止符號，^始符號，產(chǎn)生式

59.由文法的識別符推出的所有終止符號串

60.輸入緩沖區(qū)

二、選擇

1.B2.A3.B4.B5.B6.B7.B8.A9.D1O.C

II.B12.C13.C14.A15.A16.DI7.B18.D19.A20.D

21.C22.B23.B24.D25.D26.D27.C28.D29.D30.C

31.B32.B33.A34.A35.A36.C37.B38.A39.B40.A

三、簡答題

1.答：具有優(yōu)化功能的編譯程序，其優(yōu)化是指封生成的目的代碼暹行優(yōu)化，而不是編譯程序

自身得到優(yōu)化，它提高目的代碼的效率，而不是編譯程序的效率。因此，上述萩:法不引。

2.答：不封的。編譯程序的五值I構(gòu)成部分中，同法分析，^法分析，義分析和代碼生成是

必須完畢的，而代碼優(yōu)化是卷了提高目的程序的質(zhì)量，它不是必需的，沒有優(yōu)化部分的編譯

程序也能生成目的代碼。

3.指令寄存器,程序地址寄存器,棧頂寄存器,基址寄存器

4.(1)封十某些易十校止的金昔誤，如丟了逗號、分號等，則指出出^位置，并加以校止。校

正的方式就是補上逗號或分號。

(2)封某些^誤，編譯程序難于確定校正的措施，懸了使目前的誤不致影響整他程序

的瓦解，把金昔誤盡量局限在壹種局部的吉普法覃位中。il樣就需跳謾某些背面輸入的單前］符號,

直到^入壹種能使編譯程序恢復(fù)正常言吾法分析工作的軍同卷止。

5.LIT：將常量值取到運行棧頂。L0D：將變量放到棧頂，ST0：將棧頂?shù)膬?nèi)容送入某變量^

元中。CAL：調(diào)用謾程的指令。1NT：卷被調(diào)用的遇程(或主程序)在運行棧中^辟數(shù)據(jù)區(qū)。JMP：

趣條件轉(zhuǎn)移指令。JPC：條件轉(zhuǎn)移指令。0PR：關(guān)系運算和算術(shù)運算指令。將棧頂和次棧頂?shù)?/p>

內(nèi)容逛行運算，成果寄存在次棧頂，此外遢可以是SS寫等特殊功能的指令

6.句型歸約規(guī)則句柄

((a,a),a)S-*aa

((S,a),a)T-*SS

((T,a),a)S-*aa

((T,S),a)T-T,ST,S

((S),a)T—SS

((T),a)S-S(T)(T)

(S,a)T-*SS

(T,a)S-*aa

(T,S)T-T,ST,S

(T)S~(D(T)

S

7.優(yōu)化：射程序謹行多種等價變換,使得優(yōu)變換彳爰的程序出

發(fā)，能產(chǎn)生更有效的目的代碼。

三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。

8.目的代碼壹般采用三種形式：機器^言，匯編^言，待裝配

機器^言模塊。

應(yīng)著重考慮的冏題：

(1)怎樣使生成的目的代碼較短；

(2)怎樣充足運用寄存器，以減少訪冏內(nèi)存次數(shù)：

(3)怎樣充足運用指僅系統(tǒng)的的特玷。

9.逆波蘭表達：

abc*+ab+/d—

三元式序列：

①(*,b,c)

②（+,a,①）

③（+,a,b）

④（/,②，③）

⑤（一,④,d）

10.文法G(N)：

N—AB|B

A—AC|D

BT|3|5|7|9

D->B|2|4|6|8

C->0|D

H編譯謾程的六值I階段的任務(wù)，再加上表格管理和出余音處理的工作可分別由幾種模塊或程

序完畢，它儼j分別稱作同法分析程序、言吾法分析程序、言吾義分析程序、中間代碼生成程

序、代碼優(yōu)化程序、目的代碼生成程序、表格管理程序和出^處理程序。

12自反的在集合X上的關(guān)系R,如封任意x￡X,均有(x,x)ER,則稱關(guān)系R是自

反的。

非自反的在集合X上的關(guān)系R,如封任意x￡X,均有(x,x)?R,則稱關(guān)系R是非自

反。

封稱的在集合X上的關(guān)系R,假如合(X,y)eR,便必有(y,x)￡R,則稱關(guān)系R是封

稱的。

非封稱的在集合X上的關(guān)系R,假如有(x,y)￡R從xWy,便必有(y,x)^lR,則稱

關(guān)系R是非封稱的。

傳遞的在集合X上的關(guān)系R,假如合(x,y)￡R且(y,z)WR,必有(x,z)￡R,則

稱關(guān)系R是傳遞的。

13.元素的非空有窮集合。字母表中的元素。由字母表中的符號構(gòu)成的任何有窮序列，常用

小寫字母I、U、v、x、y…表達符號串。畏度是符號串所含符號的他1數(shù)。設(shè)有符號串x

和y,把y的符號寫在x的符號之彳爰所得的符號串，叫做x與y的聯(lián)記卷xy。

14答：優(yōu)所給符號串始，在其中尋找與文法的某條規(guī)則右部相匹配的子串，并用該規(guī)

則的左部取代此子串(即歸約)，反復(fù)此遇程，步步向上歸約，最終試圖將符號串x歸約到文

法的識別符號Z。如歸約成功，則符號申x是文法的句子。

15HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q.R,a,b,c}

HARD(R)={S,Q,R,a,b,c}

16S::=aABb|ab

A::={ab}

B::=Aa|a

17傳名：a=12傳值：a=6

18.⑴鰭誤

(2)封的

(3)封的

(4)封的

(5)籍誤

(6通誤

(7涕誤

19.(1)在^義上加些限制，或者^加某些^法的非形式規(guī)定。道樣做不必變化文法中原有的

言吾法規(guī)則。

(2)把排除二義性的規(guī)則合并到原有文法中，即構(gòu)造壹種等價的輾二義性的文法G，。道

樣做，需要改造原有文法。

20.只有軍層分支的子樹稱懸簡樸子樹。

21.由某壹結(jié)黠及其所有分支構(gòu)成的部分，成懸原法樹的壹棵子?樹。

22.句型的分析就是識別壹種符號串與否■^某文法的句型，是某他推導(dǎo)的構(gòu)造遇程。

23.優(yōu)所符號串x^始，在其中尋找與文法的某條規(guī)則右部相匹配的子串，并用該規(guī)則的

左部取代此子串(即歸約)，反復(fù)此謾程，步步向上歸約，最終試圖將符號串x歸約到文

法的識別符號Z。如歸約成功，則符號串x是文法的句子。

24.HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q,R,a,b,c)

HARD(R)={S,Q,R,a.b,c}

四、綜合題

每題10分，3題共30分

1.解：

(l)(j>?a,0,5)

(2)(j，一，一，3)

(3)(j<?b,0,5=

(4)(j,一，—,15)

(5)(+,x,1,Ti)

(6)(：=?T|,一,x)

(7)(j>,a,0,9)

(8)(j,—,—,12)

(9)(-,a,1,T2)

(10)(：=,Tz?—,a)

(11)0，一，I)

(12)(+,b,1,T3)

(13)(：=，T3,一,b)

(14)。，一，1)

2.解：(DE—E⑴

E—E°E⑵

EA->E(,)

E—EAE?

E->i

(2)E—E⑴

{BACKPATCH(Ed)FC,NXQ)；

E°TC：=E(,)TC}

E-EOE⑵

{EFC：=R2)FC；

ETC：=MERG(E°TC,E⑵TC)}

EA->E(1)

{BACKPATCH(E(,)TC,NXQ)：

E°FC：=E(,)FC}

E->EAE2)

{ETC：=E(2)T3C；

ETC：=MERG(EATC,E⑵FC)

E—i

{ETC：=NXQ；EFC：=NXQ+1；

GEN(jn2,entry(i),—0)；

GEN。，0)

3解：⑴

S-*(L)|aS,

S*一S|￡

L-*SL'

17-SU|￡

(2)

FIRST)S)=((,a)FOLLOW(S)={#,,,))

FIRSTS)={,a,￡}FOLLOWS)={#,,,)}

FIRST(L)={(,a)FOLLOW(L)={)}

FIRST(L*)={,,￡}FOLLOW(LfJ={)}

(3)

a)#

sS-*aS，S-(L)

s，S'-SS'7S'~SS'f￡S'fe

LL-SL'L-SL'

L，L'一￡L'一￡

4.(1)文法G中每倜非終止符的FIRSTVT集和LASTVT集卷:

FIRSTVT(s，)={4}FIRSTVT(P)={i,0

FIRSTVT(s)={(?i)FIRSTVT(D)={i}

FIRSTVT(R)={;f(,i)

(2)文法G中每他非終止符的LASTVT集卷：

LASTVT(S')二{鉗LASTVT(P)={i,}(

LASTVT(S)={)}LASTVT(D)={i}

LASTVT(R)={;,(,i)

5.til:=i*20

tl2=tll+j

tl3=A-84;

tl4=4*tl2

t15=t13[tl4]//A[i,j]

t21=i*20

t22=t21+j

t23=B-84;

t24=4*t22

t25=t.23[t24]//B[i,j]

t31=k*20

t32=t31+l

t33=A-84

t34=4*132

t35=t33[t34]//A[k,1]

t36=4*t35

t37=C-4

t38=t37[t36]//C[A[k,l]]

t41=i+j

t42:=4*t41

t43:=D-4

t44:=t43[t42]//D[i+j]

tl:=t25+t38

t2:=tl+t44

t