編譯原理復習題

一、是非題

1.計算機高級語言翻譯成低級語言只有解釋一種方式。（X）

3.每個文法都能改寫為LL（1）文法。（X）

4.算符優先關系表不一定存在對應的優先函數。（J）

5.LR分析方法是自頂向下語法分析方法。（X）

6.“用高級語言書寫的源程序都必須通過編譯，產生目標代碼后才能投入運行”這種說法。（x）

7.一個句型的句柄一定是文法某產生式的右部。（T）

8.僅考慮一個基本塊，不能確定一個賦值是否真是無用的。（V）

9.在中間代碼優化中循環上的優化主要有不變表達式外提和削減運算強度。（x）

10.對于數據空間的存貯分配，FORTRAN采用動態貯存分配策略。（x）

11.日機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統功能完全相同。（X）

12.遞歸下降分析法是自頂向下分析方法。（V）

13.產生式是用于定義詞法成分的一種書寫規則。（x）

14.在SLR（l）分析法的名稱中，S的含義是簡單的。（4）

15.綜合屬性是用于“自上而下”傳遞信息。（x）

16.符號表中的信息欄中登記了每個名字的屬性和特征等有關信息，如類型、種屬、所占單元大小、地址等等。

（x）

17.程序語言的語言處理程序是一種應用軟件。（X）

18.解釋程序適用于COBOL和FORTRAN語言。（x）

19.一個LL⑴文法一定是無二義的。（J）

20.正規文法產生的語言都可以用.上下文無關文法來描述。（J）

21.一張轉換圖只包含有限個狀態，其中有一個被認為是初態，最多只有一個終態.（X）

22.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。（J）

22.逆波蘭法表示的表達式亦稱后綴式。（4）

23.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。N）

24.數組元素的地址計算與數組的存儲方式有關。（J）

25.算符優先關系表不一定存在對應的優先函數。（x）

26.編譯程序是對高級語言程序的解釋執行。（x）

27.一個有限狀態自動機中，有且僅有一個唯一的終態。（X）

28.一個算符優先文法可能不存在算符優先函數與之對應。（Y）

29.語法分析時必須先消除文法中的左遞歸。（x）

30.LR分析法在自左至右掃描輸入串時就能發現錯誤，但不能準確地指出出錯地點。（4）

31.逆波蘭表示法表示表達式時無須使用括號。（V）

32.靜態數組的存儲空間可以在編譯時確定。（V）

33.進行代碼優化時應著重考慮循環的代碼優化，這對提高目標代碼的效率將起更大作用。（V）

34.兩個正規集相等的必要條件是他們對應的正規式等價。（J）

35.一個語義子程序描述了一個文法所對應的翻譯工作。（x）

36.設r和s分別是正規式,則有L（r|s戶L（r）L（s）。（x）

37.確定的自動機以及不確定的自切機都能正確地識別正規集。（、）

38.詞法分析作為單獨的一遍來處理較好。（x）

39.構造LR分析滯的任務就是產生LR分析表。（Y）

40.規范歸約和規范推導是互逆的兩個過程。（J）

41.同心集的合并有可能產生新的“移進”/“歸約”沖突。（x）

42.LR分析技術無法適用二義文法。（x）

43.樹形表示和四元式不便于優化，而三元式和間接三元式則便于優化。（X）

44.程序中的表達式語句在語義翻譯時不需要回填技術。（力

45.刈?中間代碼的優化依賴于具體的計算機。（x）

46.若一個句型中出現了某產生式的右部，則此右部一定是該句型的句柄。（X）

47.在程序中標識符的出現僅為使用性的。（x）

18.削減運算強度破壞了臨時變量在?基本塊內僅被定義?次的特性。（x）

49.編譯程序與具體的機器有關，與具體的語言無關。（X）

二、選擇題（請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論）

1.一個編譯程序中，不僅包含詞法分析，（A）,中間代碼生成，代碼優化，目標代碼生成等五個部分。

A.語法分析B.文法分析C.語言分析I）.解釋分析

2.語法分析器則可以發現源程序中的（D）。

A.語義錯誤B.語法和語義錯誤C.錯誤并校正D.語法錯誤

3.解釋程序處理語言時，大多數采用的是（B）方法。

A.源程序命令被逐個直接解釋執行

B.先將源程序轉化為中間代碼,再解杼執行

C.先將源程序解釋轉化為目標程序，再執行

1）.以上方法都可以

4.編譯程序是一種（B）。

A.匯編程序B.翻譯程序C.解釋程序D.目標程序

5.文法分為四種類型，即0型、1型、2型、3型。其中3型文法是（B）。

A.短語文法B.正則文法C.上下文有關文法D.上下文無關文法

6.通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優化，目標代碼生成等五個部分,

還應包括（C）。

A.模擬執行^B.解釋希C.表格處理和出錯處理D.符號執行器

7.一個句型中的最左（B）稱為該句型的句柄。

A.短語B.簡單短語C.素短語D.終結符號

8.文法G[E]：

E->T|E+T

JFIT*F

F->a|（E）

該文法句型E+F*（E+T）的簡單短語是下列符號串中的（B）。

①（E+T）②E+T③F④F*（E+T）

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

9.詞法分析器用于識別（C）。

A.句子B.句型C.單詞D.產生式

10.在自底向上的語法分析方法中，分析的關鍵是（A）。

A.尋找句柄B.尋找句型C.消除遞歸D.選擇候選式

11.文法G產生的（D）的全體是該文法描述的語言。

A.句型B.終結符集C.非終結符集D.句子

12.若文法G定義的語言是無限集，則文法必然是（A）。

A.遞歸的B.前后文無關的C.二義性的D.無二義性的

13.四種形式語言文法中，1型文法又稱為（C）文法。

A.短語結構文法B.前后文無關文法C.前后文有關文法D.正規文法

14.一個文法所描述的語言是（A）。

A.唯一的B.不唯一的C.可能唯一，好可能不唯一D.都不對

15.（B）和代碼優化部分不是每個編譯程序都必需的。

A.語法分析B.中間代碼生成C.詞法分析D.目標代碼生成

16.（B）是兩類程序語言處理程序。

A.高級語言程序和低級語言程序B.解彈程序和編譯程序

C.編譯程序和操作系統D.系統程序和應用程序

17.數組的內情向量中肯定不含有數組的（D）的信息。

A.維數B.類型C.維上下界D.各維的界差

18.一個上下文無關文法G包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以

及一組（D）。

A.句子B.句型C.單詞D.產生式

19.文法分為四種類型，即。型、I型、2型、3型。其中2型文法是（D）。

A.短語文法B.正則文法C.上下文有關文法D.上下文無關文法

20.文法G所描述的語言是（C）的集合。

A.文法G的字母表V中所有符號組成的符號串B.文法G的字母表V的閉包V*中的所有符號串

C.由文法的開始符號推出的所有終極符串D.由文法的開始符號推出的所有符號串

21.詞法分析器用于識別（C）。

A.字符串B.語句C.單詞D.標識符

22.文法分為四種類型，即0型、1型、2型、3型。其中。型文法是（A）。

A.短語文法B.正則文法C.上下文有關文法D.上下文無關文法

24.（A）是一種典型的解釋型語言。

A.BASICB.CC.FORTRAND.PASCAL

25.與編譯系統相比，解釋系統（D）。

A.比較簡單，可移植性好，執行速度快B.比較復雜，可移植性好，執行速度快

C.比較簡單，可移植性差，執行速度慢D.比較簡單，可移植性好，執行速度慢

26.月高級語言編寫的程序經編譯后產生的程序叫（B）。

A.源程序B.FI標程序C.連接程序D.解釋程序

27.詞法分析器用于識別（A）。

A.字符串B.語句C.單詞D.標識符

28.編寫一個計算機高級語言的源程序后，到正式上機運行之前，一般要經過（B）這幾步:

⑴編輯⑵編譯⑶連接（4）運行

A.⑴⑵（3）（4）B.⑴⑵⑶C.（1）⑶D.⑴（4）

29.把匯編語言程序翻譯成機器可執行的目標程序的工作是由（B）完成的。

A.編譯器B.匯編器C.解釋器D.預處理器

31.詞法分析器的輸出結果是（C）。

A.單詞的種別編碼B.單詞在符號表中的位置C.單詞的種別編碼和自身值D.單詞自身值

32.正規式M1和M2等價是指（C）。

A.Ml和M2的狀態數相等B.Ml和M2的有向邊條數相等

C.Ml和M2所識別的語言集相等D.Ml和M2狀態數和有向邊條數相等

33.文法G：S-xSx|y所識別的語言是（C）。

A.xyxB.(xyx)*C.xnyxn{n>0)D.x*yx*

34.如果文法G是無二義的，則它的任何句子a（A）o

A.最左推導和最右推導對應的語法樹必定相同B.最左推導和最右推導對應的語法樹可能不同

C.最左推導和最右推導必定相同D.可能存在兩個不同的最左推導，但它們對應的語法樹相同

35.構造編譯程序應掌握（D）。

A.源程序B.目標語言C.編譯方法D.以上三項都是

36.四元式之間的聯系是通過（B）實現的。

A.指示器B.臨時變最C.符號表D.程序變量

37.表達式（1AVB）八（CVD）的逆波蘭表示為（B）。

A.ABVACDVB.A-）BVCDVAC.ABVqCDVAD.AnBVACDV

38.優化可生成（D）的目標代碼。

A.運行時間較短B.占用存儲空間較小

C.運行時間短但占用內存空間大D.運行時間短且占用存儲空間小

39.下列（C）優化方法不是針對循環優化進行的。

A.強度削弱B.刪除歸納變量C.刪除多余運算D.代碼外提

40.編譯程序使用（B）區別標識符的作用域。

A.說明標識符的過程或函數名B.說明標識符的過程或函數的靜態層次

C.說明標識符的過程或函數的動態層次D.標識符的行號

41.編譯程序絕大多數時間花在（D）上。

A.出錯處理B.詞法分析C.目標代碼生成D.表格管理

42.編譯程序是對（D）。

A.匯編程序的翻譯B.高級語言程序的解釋執行C.機器語言的執行D.高級語言的翻譯

43.采用自上而下分析，必須（C）,

A.消除左遞歸B.消除右遞歸C.消除回溯D.提取公共左因子

44.在規范歸約中，用（B）來刻畫可歸約串。

A.直接短語B.句柄C.最左素短語D.素短語

45.若a為終結符，則A->a?ap為（B）項目。

A.歸約B.移進C.接受D.待約

46.間接三元式表示法的優點為（A）。

A.采用間接碼表，便「優化處理B.節省存儲空間，不便于表的修改

C.便于優化處理，節省存儲空間D.節省存儲空間，不便于優化處理

47.基本塊內的優化為（B）。

A.代碼外提，刪除歸納變量B.刪除多余運算，刪除無用賦值

C.強度削弱，代碼外提D.循環展開，循環合并

48.在目標代碼生成階段，符號表用（D）。

A.目標代碼生成B.語義檢查C.語法檢查D.地址分配

49.若項目集Ik含有A->a?,則在狀態k時，僅當面臨的輸入符號a￡FOLLOW（A）時，才采取?”動作的

一定是（D）。

A.LALR文法B.LR（O）文法C.LR⑴文法D.SLR⑴文法

50.堆式動態分配申請和釋放存儲空間遵守（D）原則。

A.先請先放B.先請后放C.后請先放D.任意

三、填空題

1.編許程序的工作過程一般可以劃分為詞法分析，語法分析，語義分析，中間代碼生成，代碼優化等幾個基本階段,

同時還會伴有—表格處理—和—出錯處理

2.編譯方式與解釋方式的根本區別在于—是否牛.成目標代碼

3.產生式是用于定義—語法成分_的一種書寫規則。

4.設G是一個給定的文法，S是文法的開始符號，如果S->x（其中x￡VT*）,則稱x是文法的一個一句子

5.自頂向下的語法分析方法的基本思想是：從文法的一開始符號—開始，根據給定的輸入串并按照文法的產

生式一步一步的向下進行_直接推導—，試圖推導出文法的一句子—，使之與給定的輸入串_匹配

6.常用的參數傳遞方式有一傳地出傳值和傳名。

7.一個句型中的最左簡單短語稱為該句型的一句柄

8.對于文法的每個產生式都配備了一組屬性的計算規則，稱為一語義規則—o

9.一個典型的編譯程序中，不僅包括一詞法分析—、_語法分析—、_中間代碼生成一、代碼優化、目標代

碼生成等五個部分，還應包括表格處理和出錯處理。

10.從功能上說，程序語言的語句大體可分為_執行性一語句和—說明性一語句兩大類。

II.掃描器的任務是從_源程序一中識別出一個個一單詞符號

12.產生式是用于定義一語法范疇—的一種書寫規則。

13.語法分析是依據語言的一語法一規則進行的，中間代碼產生足依據語言的_語義—規進行的。

14.語法分析器的輸入是一單詞符號串其輸出是一語法單位

15.一個名字的屬性包括一類型—和_作用域—o

16.逆波蘭式ab+c+d*e-所表達的表達式為_（a+b+c）*d-e。

17.語法分析最常用的兩類方法是一自上而下—和一自下而.卜.一分析法。

18.計算機執行用高級語言編寫的程序主要有兩種途徑：―解釋_和_編譯

19.掃描器是—詞法分析器一，它接受輸入的一源程序對源程序進行一詞法分析一并識別出一個個單詞

符號，其輸出結果是單詞符號，供語法分析器使用。

20.自上而下分析法采用一移進_、歸約、錯誤處理、一接受—等四種操作。

21.一個LR分析器包括兩部分：一個總控程序和一一張分析表

22.后綴式abc-/所代表的表達式是_a/(b-c)__0

23.局部優化是在_基本塊一范圍內進行的一種優化。

24.詞法分析基于_正則—文法進行，即識別的單詞是該類文法的句子。

25.語法分析基于一上下文無關一文法進行，即識別的是該類文法的句子。語法分析的有效工具是一語法樹一。

26.分析句型時，應用算符優先分析技術時，每步被直接歸約的是—最左素短語而應用LR分析技術時，

每步被直接歸約的是一句柄

27.語義分析階段所生成的與源程序等價的中間表示形式可以有一逆波蘭一、—四無式表示_與一三元式表

示一等。

28.按Chomsky分類法，文法按照—規則定義的形式.進行分類。

29.一個文法能用有窮多個規則描述無窮的符號串集合(語言)是因為文法中存在有一遞歸_定義的規則。

四、簡答題

1.寫文法，使其語言是偶正整數的集告要求：

⑴允許0打頭；

(2)不允許0打頭。

解：⑴G網=({S,P,D,N},{0,1,2,...,9}.P,S)

P:

S->PD|D

P->NP|N

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

N->0|l|2|3|4|5|6|7|8|9

(2)G1S[=({S,P,R,D,N,Q},{0,1,2,...,9心)

P:

S->PD|P0|D

P->NR|N

R->QR|Q

D->2|4|6|8

N->1|2|3|4|5|6|7|8|9

Q->0|l|2|3|4|5|6|7|8|9

2.構造正規式相應的NFA:l(0|l)*101

0

解1(011)*101對應的NFA為1

3.寫出表達式(a+b*c)/(a+b)—d的逆波蘭表示和三元式序列。

逆波蘭表示：abc*+ab+/d—

三元式序列：

①(*.b,c)

②(十,a,①)

③(+,a,b)

④(/,②，③)

⑤(一，④，d)

4.已知文法G[S]為:

S->dAB

A—>aA|a

B->Bb|e

G[S|產生的語言是什么？

nm

答:G[S]產生的語言是L(G[S])={dab|n>\jn>0}o

5.構造正規式相應的DFA:1(1010*11(010)*l)*0o

解：1(1010*|1(010)*1)*0對應的NFA為

6.已知文法G(S)

S->a|A|(T)

T->T,S|S

寫出句子((a,a),a)的規范歸約過程及每一步的句柄。

解：

句型歸約規則句柄

((a,a),a)S—>aa

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

((T,a),a)S—>aa

((T,S),a)T—T,ST,S

((S),a)TTSS

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

(S,aiT—SS

(T,a)S—*aa

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

(T)STD(T)

S

7.寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。

解：文法G(N)：

NTAB|B

ATAC|D

B->1|3|5|7|9

D->B2|4|6|8

C->0|D

8.設文法G(S)：

S—>(L)|aS|a

L->L,S|S

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

(2)計算每個非終結符的FIRST和FOLLOWo

解：⑴

S->(L)|aS'

S」S|￡

L->SL'

LJSU|￡

(2)

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

FIRST(S')={,a,e}FOLLOW(S')={#,,,)}

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

FIRST(L')={,,￡)FOLLOW(L')={)}

9.已知文法G(E)

E->T|E+T

T->F|T*F

F-(E)|i

(1)給出句型(T*F+i)的最右推導；

(2)給出句型(T*F+i)的短語、素短語。

解：(1)最右推導：E=>T>F=>(E)->(E+T)=>(E+F)->(E+i)=>(T4-i)=>(T*F+i)

(2)短語：(T*F+i),T*F+i,T*F,i

素短語:T*F,i

10.Whilea>0Vb<0do

Begin

X：=X+1；

ifa>0thena：=a—1

elseb：=b+l

End；

翻譯成四元式序列。

解：

⑴a,。，5)

(2)(j,一,—,3)

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

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

(5)(+,X,1,Tl)

(6)(：=,Tl,一，X)

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

(8)(j,—,12)

(9)(-,a,I,T2)

(10)(：=,T2,a)

(U)(j，1)

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

(13)(：=,T3,b)

(14)0，一，一，1)

(15)

11.寫出下列表達式的三地址形式的中間表示。

(1)5+6*(a+b);

(2)forj:=lto10doa[j+j]:=0o

答：(1)100:U:=a+b

101:t2:=6*tl

102:6=5+12

(2)100:j:=l

101:ifj>10gotoNEXT

102:i:=j+j

103:a[i]:=0

12.設基本塊p由如下語句構成：

TO:=3.14;

T1:=2*T0;

T2:=R+r;

A:=T1*T2；

B:=A;

T3:=2*T0;

TA：-R+r;

T5:=T3*T4;

T6:=R-r；

B:=T5*T6；

試給出基本塊p的DAGo

13.寫出表達式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。

解：（1）三元式：

①（一,a,b）

②（一，a,b）

③"①，②）

④（*,b,c）

⑤（十，a,④）

⑥（-,③，⑤）

（2）四元式:

①（一,a,b,Tl）

②（一，a,b,T2）

③（/,Tl,T2,T3）

④（*,b,c,T4）

⑤（一,a,T4,T5）

⑥（一，T3,T5,T6）

14.寫一個文法使其語言為偶數集，且每個偶數不以0開頭。

解：文法G（S）：

S->AB|B|A0

A->AD|C

B->2|4|6|8

C->1|3|5|7|9|B

D-0|C

15.設文法G（S）：

S->S+aF|aF|+aF

F—**aF|*a

（1）消除左遞歸和回溯；

（2）構造相應的FIRST和Follow集合。

解：（1）

S->aFS'|+aFS'

S'->+aFSK

F->*aF'

F'->F|￡

(2)

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

FIRST(S')={+,￡}FOLLOW(S')={#}

FIRST(F)={*}FOLLoW(F)=(+,井}

FIRST(F)={*,e}FOLLOW[+,#}

16.簡要說明語義分析的基本功能。

答：語義分析的基本功能包括：確定類型、類型檢查、語義處理和某些靜態語義檢查。

17.考慮文法G[S]:

S—(T)|a+S|a

T->T,S|S

消除文法的左遞歸及提取公共左因子。

解：消除文法G[S]的左遞歸：

S—>(T)|a+S|a

T—ST'

TJ,ST1￡

提取公共左因子：

S->(T)|aS'

S'->+SI￡

T-ST'

TfST|￡

18.試為表達式w+(a+b)*(c+d/(e-10)+8)寫出相應的逆波蘭表示。

解：wab+cde10-/+8+*+

19.按照三種基本控制結構文法將下面的語句翻譯成四元式序列：

while(A<CAB<D)

(

if(A>1)C=C+1;

elsewhile(A<D)

A=A+2;

)。

解：該語句的四元式序列如下(其中El、E2和E3分別對應AVCABVD、A>1A<D,并且關系運算符優先級

高)：

100(j<,A,C,102)

101

102(j<,B.D,104)

1030.113)

104(j=A,1,106)

105(j.___108)

106(+,C,1,C)

107(j-U2)

108(j<,A,D,H0)

109G，___H2)

110(+,A,2,A)

III(j,__108)

112(j._,_,100)

113

20.已知文法GfS］為S->aSb|Sb|b,試證明文法G［S］為二義文法。

證明：

由文法G⑸：S->aSb|Sb|b,對句子aabbbb對應的兩棵語法樹為:

aSb

/K

aSb

bb

因此，文法G[S]為二義文法。

21.文法G[S]為:

S->Ac|aB

A->ah

B->bc

寫出L(G[S])的全部元素。

解：S=>Ac=>abc

或S=>aB=>abc

所以L(G[S]尸{abc}

22.構造正規式1(011)*101相應的DFA。

解：先構造NFA：

確定化:

01

XA

AAAB

ABACAB

ACAABY

ABYACAB

重新命名，令AB為B、AC為C、ABY為D得:

01

XA

AAB

BCB

CAD

DCB

所以，可得DFA為:

S->a|q(T)

T->T,S|S

對(a,(a,a)和(((a,a),A,(a)),a)的最左推導。

解：對(a,(a,a)的最左推導為：

S->(T)=>(T,S)->(S,S)->(a,S)

=>(a,(T))=>(a,(T,S))=>(a,(S,S))

=>(a,(a,S))=>(a,(a,a))

對(((a,a),八,(a)),a)的最左推導為:

S=>(T)=>(T,S)=>(S,S)=>((T),S)

=>((TS),S)=>((T,S,S),S)=>((S,S,S),S)

=>(((T),S,S),S)=>(((T,S),S,S),S)=>(((S,S),S,S),S)

=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),A,S),S)

=>(((a,a)A(T)),S)=>(((a,a),A,(S)),S)=>(((a,a)A(a)),S)

=>(((a,a),A,(a)),a)

24.文法:

S->MH|a

H->LSo|E

K->dML|￡

L->eHf

M->K|bLM

判斷G是否為LL(1)文法，如果是，構造LL(1)分析表。

解：各符號的FIRST集和FOLLOW集為：

FIRSTFOLLOW

s{a4b,c,e)｛機。｝

M{d,e,b){eAo}

H{y}{加}

L母岫島。,#｝

K{d,M{eAo}

預測分析表為:

aodefb

S->a

M->K->K->K->bLM->K

H->s->LSo->S->￡

L->eHf

K->8->dML->￡->2

由于預測分析表中無多重入口，所以可判定文法是LL(1)的。

25.敘述由下列正規式描述的語言

(a)0(0|l)*0

(b)((e10)1*)*

(c)(0|1)*0(011)(0|1)

(d)0*10*10*10*

(e)(0()|11)*((01|10)(00|l1)*(01|10)(00|ll)*)*

解：(a)以0開頭、以。結尾的所有0和1的串。

(b)由。和1組成的串，包括空串.

⑹倒數第3個字符為0,由0和1組成的串。

(d)含有3個1的所有。和1的串。

⑹由偶數個0和偶數個1構成的所有()和I的串。

26.已知文法G［S］：

S-*(L)|a

L-L,S|S

為句子(a,(a,a))構造最左推導和最右推導。

解：句子(a,(a,a))的最左推導為：

S=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=(a,(S,S))=>(a,(a,S))=>(a,(a,a))

句子(a,(a,a))的最右推導為：

S=>(L)=>(L,S)=>(l,(L))=>(L,(L,S))=>(L,(L,a))=>(L,(S,a))=>(L,(a,a))=(S,(a,a))=(a,(a,a))

五.計算題

1.構造下述文法G［S］的自動機：

S->A0

A->A()|S1|O

該自動機是確定的嗎？若不確定，貝］對它確定化。

解：由于該文法的產生式S->A0,A->AO|S1中沒有字符集VT的輸入，所以不是確定的自動機。要將其他確定

化，必須先用代入法得到它對應的正規式。把S?A0代入產生式A?S1有：A=A0|AO110=A(0|01)|0=0(0|01)*o代

入S->A0有該文法的正規式：0(0|01)*0,所以，改寫該文法為確定的自動機為：

由于狀態A有3次輸入0的重復輸入，所以上圖只是NFA,下面將它確定化：

下表由子集法將NFA轉換為

DFA:

IIo-c-closure(MoveIb-e-closure(Move7b(I,i))

A[W]B[X]

B[X]C[X,Y,Z]

C[X,Y,Z]C[X,Y,Z]B[X]

由上表可知DFA為:

2.對下面的文法G：

E->TE'

E'->+E|￡

T->FT'

V->T|e

F->PF'

F->*F'|e

P->(E)|a|b|A

(1)計算這個文法的每個井終結符的FIRST集和FOLLOW集。

(2)證明這個方法是LL(I)的。

(3)構造它的預測分析表。

解：(1)計算這個文法的每個非終結符的FIRST集和FOLLOW集。

FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,A};

FIRST(E尸什同

FIRST(T)=FIRST(F)=F1RST(P)={(,a,b?);

FIRST(T')=FIRST(T)UF}={(,a,b,人間;

FIRST(F)=FIRST(P)={(,a,b,A);

FIRST(F')=FIRST(P)={*,E};

FIRST(P)={(,a,b?!;

FOLLOW集合有：

FOLLOW(E)={),#};

FOLLOW(E')=FOLLOW(E)={),#};

FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}，不包含￡

FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};

FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,A,+,),#);//不包含￡

HOLLOW(E)=FOLLOW(F)=HRSrcr)UHOLLOW(T)={(,a,b,A,+,),#};

FOLLOW(P)=FIRST(F')UFOLLOW(F尸{*,(,a,bj,+,),#};〃不包含￡

(2)證明這個方法是LL(1)的。

各產生式的SELECT集合有：

SELECT(E->TE')=FIRST(T)={(,a,b,A];

SELECT(E'->+E)={+};

SELECT(E'->￡)=FOLLOW(E/)={),#}

SELECT(T->FT')=FIRST(F)={(,a,b,A};

SELECT(T'->T)=FIRST(T)={(,a,b,A};

SELECT(T'->E)=FOLLOW(T/)={+,),#};

SELECT(F->PF')=FIRST(P)={(,a,b,A};

SELECT(F->*F')=<*};

SELECT(F'->￡)=FOLLOW(F')={(,a,b,A,+,),#)；

SELECT(P->(E))={()

SELECT(P->a)={a}

SELECT(P->b)={b)

SELECT(P->A)={A)

可見，相同左部產生式的SELECT集的交集均為空，所以文法G[E]是LL(1)文法。

(3)構造它的預測分析表。

文法G[E]的預測分析表如下：

A

+*()ab#

EITE'TIE'-?TE’->TEr

Ez3+E

T?FT'->FTZ->FT;1FT

Tz->e-?TIT

F3PF’->FF,?PF'-?PF

Ff-^*F,->6￡

P3(E)9a-?b

3.己知NFA=()x,y,z),{0,l)M(x)4z)),其中:

M(x,())={z},M(y,())={x,y},M(z,O)={x,z},M(x,1)={x},M(y,l)=(p,M(zJ)={y},構造相應的DFA并最小化。

下表由子集法將NFA轉換為DFA

IIo-￡-closure(Mov0Ii二e-closure(Move

A[x]B[z]A[x]

B[z]C[x,z]D[y]

C[x,z]C[x,z]E[x,y]

D[y]E[x,y]

E[x,y]F[x,y,z]A[x]

F[x,y,z]F[x,y,z]E[x,y]

下面籽該DFA最小化：

(1)首先將它的狀態集分成兩個子集：P1={A,D,E},P2={B,C,F)

(2)IX分P2:由于F(FJ)=F(C,1)=E,F(F,O)=F并且F(C,O)=C,所以F,C等價。由于F(B.O)=F(C,O)=C,F(B,1)=D,F(C,1)=E,

而D,E不等價(見下步)，從而B與C,F可以區分。有P21={C,F},P22={B}。

(3)區分Pl:由于A,E輸入。到終態，而D輸入0不到終態，所以D與A,E可以區分，有Pl1={A,E},P12={D}。

(4)由于F(A,O)=B,F(E,O)=FjiiB,F不等價，所以A,E可以區分。

(5)綜上所述，DFA可以區分為P={{A},{B},{D},{E},{C,F}}。所以最小化的DFA如下：

4.已知文法為：

S->an(T)

T->T,S|S

構造它的LR(O)分析表。

解：加入非終結符ST方法的增廣文法為:

S'->S

S->a

S->A

S->(T)

T->T,S

T->S下面構造它的LR(O)項目集規范族為:

百天號

A

a)J#sT

Io：I::L：I：II:

S，SS->aaS-X-T)S0S?

T->>T,S

S"T->?S

Sf⑴S-??a

S>(T)

Iiacc

Ic

L

I:I：LIIt：Is：

S-?(*T)s。S^(T9

Tf?T,S—,S

—?S

S->,a

S3」

S+⑴

Is：I；:L：

SIT)S3(TATIT,-S

T—T-，SST?a

S3」

S>(T)

L

IT：

L：I：LIL

T->T,*S—T,s?

S->ba

S3」

s>cr)

I,

從I：表可看出，不存在移進-歸約沖突以及歸約歸約沖突，該文法是LR(O)文法。

從而有下面的LR(O)分析表：

ACTIONGOTO

狀態A

a()#ST

0工s5s1

1acc

2XiXiXiXlXlXl

3r2r：r：工二r2r:

4s：S5S65

5S：So

6r5r5r5Xsr5r?

7Xjr5XjX3r5X3

8s：S5S9

9rrrr▲V■r

5.已知文法

A->aAd|aAb|E

判斷該文法是否是SLR(l)文法,若是構造相應分析表，并對輸入串ab#給出分析過程。

解：增加一個非終結符S/后，產生原文法的增廣文法有：

S'->A

A->aAd|aAb|e

下面構造它的LR(O)項目集規范