《編譯原理》期末復(fù)習(xí)資料

［題1)

1.(a|b)*(aa|bb)(a|b)*畫出狀態(tài)轉(zhuǎn)換圖。

（此題中第

一個空輸入

可以省略，

即①可以省

略。）

lalb

①1,2,32,3,42,3,5

②2,3,4234,6,7,82,3,5

③2,3,52,3,42,35,6,7,8

④2,3,4,6782,3,4,678235,7,8

⑤2,3,5,678234,7,82,3,567,8

⑥2,357,82,347,82,3,567,8

⑦2,347,82,3,467,82,3,578

lalb

123

243

325

446

575

675

746

新的狀態(tài)轉(zhuǎn)換圖如下:

a

（判斷終結(jié)，含有最

后一個數(shù)字，含有8

的）

b

(I)A={1.2.3).B={}Aa={2,4}X

(2)A={1,3(,B={2),C={4,5,6,7|Aa={2}B,Ab={3,5}X

(3)A={1},B={2,C={3},D=45,6,7}(單元素可以不用看,必有，古先看D)

b

Da={4,7

}D,

Db={5,6

}D,

Aa={2}

B,

Ab={3}

C

Ba={4}a

D,

Bb:{3}

c,

Ca={2}

B,

Cb-{5}

C,則

有

ABC

BDC

CBD

DDD

2.(a*|b*)b(ba)*的狀態(tài)轉(zhuǎn)換圖。

lalb

①123.42.434568

②2.42.45.6.8

(3)3,456,8—34567,8

④5,6.8—7

?3,4,5,6786,83,4,5,6,7,8

⑥76,8—

⑦6,8—7

la1b

123

224

3—5

4—6

575

67—

7—6

新的狀態(tài)轉(zhuǎn)換圖如下:

化笥：(用終結(jié)狀態(tài)與非終結(jié)狀態(tài)，然后輸出狀態(tài)一致分一類)。

(I)A={1,2,6},B={3,4,5,7}Aa={2}X

(2)A={1,2(,B={6},C={3,4,7),D={5}Cb={5,6}X(只要有一個不屬于任何一個集合,就不行)

(3)A={1,2},B={6},C={3},D=[4,7},E={5}Ab={3,4}X

(4)A={1},B={2},C={6},D={3},E={4,7},F={5}Aa={2}B,Ab={3}D,Ba={2}B,Bb={4}E,

Ca={7}E,Db={5}F,Eb={6}C,Fa={7}E,Fb={5}F

ab

ABD

BBE

CE—

D—F

E—C

FEF

［注意事項(xiàng)］:

1.

只有唯一選擇時，才

2.可以省B3空輸入

不能省略空輸入

?［知識要點(diǎn)］:

正則表達(dá)式：

ao{sya,aa,aaa,o…4}；a\伙a或b）o{?,/?}；ab（a^b）o{ab}；

（a。）“<=>{E,ab,abab,ababab,...）

(aIb)o(aIb\a\b).......(a\b)?{f,a,b,aab,aabb,baba,.......}

是最左邊，個字母?定是，其余字母為的任意組合，不包括。

a|ah<=>［a,/?,ab.aab,aaab,aaaab,??-}<=>{a和若干個a(包括0的情形)后跟一個b構(gòu)成的符號串集

合）

aIal）<=>{〃（￡I/?"）}<=>{a（e|。）"}<=>ab'<=>{a,ab,abb,abbb,abbbb,???}<=>{a和a后跟若干個（包括0

的情形)b構(gòu)成的符號串集合}

狀態(tài)轉(zhuǎn)換圖(有窮狀態(tài)自動機(jī))：

終結(jié)

aab

a

a\h

[題2]

1.求如下簡單算術(shù)表達(dá)式文法G”,中語法變量的FOLLOW集。

ETTE

E->^TE\S

TTFT

7.*F7|￡

Ff(E)|id

［解答］:(1)求表達(dá)式文法的語法符號的FIRST集：

FIRST(F)=((,id}

FIRST(T)=FIRST(F)=((,id)

FIRST(E)=FIRST(T)={(,id}

FIRST(E，)={+,e}

FIRST(r)={*,e}

FIRST(+)={+},FIRST(*)={*}

FIRST(()={(}

FIRST0)={)}

FIRST(id)={id}

(2)求表達(dá)式文法的語法變最的FOLLOW集：

FOLLOW(E)={#,)}

FOLLOW(E*)=FOLLOW(E)={#,)}

FOLLOW(T)={FIRST(E*)-{e}}UFOLLOW(E)UFOLLOW(E')={+,),#}

FOLLOW(T)=FOLLOW(T)={+,),#}

FOLLOW(F):FIRST(T')UFOLLOW(T)UFOLLOW(T*)={*,+,),#}6

［知識點(diǎn)］

First集合的求法：

First集合最終是對產(chǎn)生式右部的字符串而言的，但其關(guān)鍵是求出非終結(jié)符的First集合，由于終結(jié)

符的First集合就是它自己，所以求出非終結(jié)符的First集合后，就訶很直觀地得到每個字符串的First

集合

1.直接收取：對形如U->a…的產(chǎn)生式(其中a是終結(jié)符)，把a(bǔ)收入到First(U)中

2.反復(fù)傳送:對形入U->P1P2P3…Pn的產(chǎn)生式(其中P是非終結(jié)符)，應(yīng)先把First(P1)中的全部內(nèi)容傳

送到First(U)中,如果P1中有￡,把First(P2)中的內(nèi)容傳送到First(U)中,類推直到Pi中無￡。

Follow集合的求法：

Follow集合是針對非終結(jié)符而言的，F(xiàn)ollow(U)所表達(dá)的是句型中非終結(jié)符U所有可能的后隨終結(jié)符

號的集合，特別地，“$”是識別符號的后隨符,先直接加入到S中。

1.直接收取：注意產(chǎn)生式右部的每一個形如''…Ua…”的組合，把a(bǔ)直接收入到Follow(U)中。

2.直接收?。簩π稳纭啊璘P…”［P是非終結(jié)符)的組合,把First(P)中非e收入到Follow(U)中。

3.反復(fù)傳送：對形如U->aP的產(chǎn)生式(其中P是非終結(jié)符)或U->aPQ(P,Q為非終結(jié)符且Q中含￡),應(yīng)

把Follow(U)中的全部內(nèi)容傳送到Follow⑻中。

［例］文法：S-ABcA-*a|￡B-b|￡

First集合求法:能由非終結(jié)符號推出的所有的開頭符號或可能的*但要求這個開頭符號是終結(jié)符號。

如此題A可以推導(dǎo)出a和￡,所以FIRST(A)={a,￡}；同理FIRST(B)={b,e};S可以推導(dǎo)出aBc,還

可以推導(dǎo)出be,還可以推導(dǎo)出c,所以FIRST(S)={a,b,c)

Follow集合的求法:緊跟隨其后面的終結(jié)符號或#。但文法的識別符號包含#,在求的時候還要考慮到￡。

具體做法是把所有包含你要求的符號的產(chǎn)生式都找出來，再看哪個有用。Follow(§)={#}如求A的，產(chǎn)

生式：S-*ABcA-*a|￡,但只有S-*ABc有用.跟隨在A后面的終結(jié)符號是FIRST(B)={b,e),當(dāng)

FIRST(B)的元素為e時，跟隨在A后的符號就是c,所以Follow(A)={b,c}同理Follow(B)={c}

2.對下面的文法G:

ETTE

E^+E\￡(1)計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。

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

(3)構(gòu)造它的預(yù)測分析表。

T^T\s

FTPF

F-*尸|￡

P^(E)\a\b\^

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

FIRST集合有：

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

FIRST但尸{+同

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

FIRST(T')=FIRST(T)U{&={(,a,bf同；

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

FIRST(F>FIRST(P)={*,￡};

FIRST(P)={Ga,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);{;〃不包含￡

FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b「,+,j,#};

FOLLOW(P)=FIRST(F')UFOLLOW(F)={*,(,a,b?,+,),#);〃不包含e

(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?};

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

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

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

SELECT(F->e)=FOLLOW(F)={(,a,b,A,+,),#);

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

SELECT(P->a)={a}

SELECT(P->b)=

SELECT(P->A)={A}

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

(3)構(gòu)造它的預(yù)測分析表。

文法G[E]的預(yù)測分析表如下：

A

+*()ab#

E3TE'-?TE'-?TEy->TEZ

E，->+E->6

TTFT，->FT/->FTf

T3T-?T->T-?T

F-^PFZ3PF’?PF'->PFy

Fz今￡->*FZT￡->￡->8->￡)￡

P1(E)-^a-?b一

[題3]

考慮下面的文法：

⑴

ETT(1)求出所有語法變量的FIRSTOP集合和LASTOP集合。

(2)E-￡+7

(2)構(gòu)造文法G,的算符優(yōu)先關(guān)系表，并判斷G,是否為算符優(yōu)先文法。

⑶EfE-T

F

(4)T—(3)計算文法G,的算符優(yōu)先函數(shù)。

⑸rfr*/

(6)Tf7VF(4)給出表達(dá)式，&和id*(id+id)的第符優(yōu)先分析過程。

⑺尸f出)

(8)尸一>/

(I)[解答]:

所有語法變量的FIRSTOP集合和LASTOP集合如下:

FIRSTORE)={+「*,/,(〃]

FIRSTORT)={",id)

FIRSTORF)={(,id)

LASTOP(E)={+-^,/,)Jd]

LASTORT)={*,/,),沮}

LASTOI\F)={\id}

(2)文法G,的算符優(yōu)先關(guān)系表

算的

關(guān)系

*

算符+-/()id

+⑤⑤@?@

-⑤?

*??⑤0?

/⑤⑤⑤?

(???

)⑤⑤⑤

id⑤⑤⑤⑤

（3）因?yàn)槲姆ㄖ腥我鈨蓚€終結(jié)符之間只存在一種關(guān)系，因此該文法為算符優(yōu)先文法。

（4）文法G,的算符優(yōu)先函數(shù)

優(yōu)先函數(shù)

-/()id#

算符+

f（棧內(nèi)優(yōu)先函數(shù)）22440440

g（棧外優(yōu)先函數(shù)）11335050

（5）表達(dá)式a的算符優(yōu)先分析過程

步驟棧輸入串優(yōu)先關(guān)系動作

1#id}+id2#

2+id2##?a移進(jìn)a

3#F+id1##0id、?#用尸—沮歸約

4#F+id2#@移進(jìn)+

5#F+i4#@移進(jìn)以2

+用尸—/歸約

6#F+F?id2?#

7而##0+0#用E-＞石+丁歸約

表達(dá)式id*（id+id）的算符優(yōu)先分析過程

步驟棧S優(yōu)先關(guān)系當(dāng)前輸入字符R輸入字符串

0*?id*(id+id)#

1#id?*(id+id)#

2#N?*(id+id)#

3二\*?(id+id)#

4#N*(?id+id)#

5#N*(id?+id)#

6#N*(N?+id)#

7#N*(N+id)#

8#N*(N+id?)#

9#N*(N+N?)

10#N*(N)

11#N*(N)?#

12#N*N#

13#N停止#

2.已知文法G[S]為：

S->a|A|(T)

T->T,S|S

(1)計算G[S]的FIRSTVT和LASTVT。

(2)構(gòu)造G[S1的算符優(yōu)先關(guān)系表并說明G[S]是否為算符優(yōu)先文法。

(3)計算G[S1的優(yōu)先函數(shù)。

(4)給出輸入串(a,a)#的算符優(yōu)先分析過程。

解：(1)各符號的FIRSTVT和LASTVT:

FIRSTVTLASTVT

Sa、八、(a、八、)

9\八、(

T,、a、八、)

(2)算符優(yōu)先關(guān)系表:

a()A#

a>>>

(<=<

>>

)>

<<>><

A>>>

#<<<

因?yàn)槲姆ㄖ腥我鈨蓚€終結(jié)符之間只存在一種關(guān)系，因此該文法為算符優(yōu)先文法。

(3)對應(yīng)的算符優(yōu)先函數(shù)為：

A

a()9#

s212221

T331131

（4）句子（a,a）#分析過程如下:

步驟棧優(yōu)先關(guān)系當(dāng)前符號剩余輸入串移進(jìn)或歸約

1##<((a,a)#移進(jìn)

2抵(<aa,a)#移進(jìn)

3抵aa>,9a)#歸約

4和F崖，9a)#移進(jìn)

5即，A)#移進(jìn)

6<F,aA>))#歸約

7敵F,F，》）)#歸約

8#(F(三))#移進(jìn)

9笊F))>##歸約

10悔Q##接受

［知識點(diǎn)］

FIRSTVT及LASTVT求法

構(gòu)造集合FIRSTVT(P)的兩條規(guī)則。

(i)若有產(chǎn)生式P-?a-,或P-*Qa…，則a￡FIRSTVT(P

(ii)若a￡FIRSTVT(P),且有產(chǎn)生式P-Q…，則a￡FIRSTVT(P)<,

構(gòu)造集合FIRSTVT(P)的兩條規(guī)則

(i)有產(chǎn)生式P-…a,或P-…aQ,則a-LASTVT(P)。

(ii)若a￡LASTVT(Q),且有產(chǎn)生式P-Q…，則a￡FIRSTVT(P)。

［題4］

令文法G:SfBBB-aBB-b判斷該文法是否LR(1)文法，若是構(gòu)造LR(1)分析表，

解1)將文法G拓廣為G':(0)S'-*S(1)S-*BB(2)B-*Ab(3)B-*b

2)求出G'的非終結(jié)符的FOLLOW和FIRST集

AbOLLUW(A)KIKST(A)

S'#a,b

S#a,b

Ba,b,#a,b

3）構(gòu)造個G'的LR⑴的項(xiàng)目集族及GO函數(shù)

3）判斷文法是否為LR（1）文法。

該文法構(gòu)出的C={10,II,12,13,14,15,16,17,18,19}中，每個狀態(tài)集均無沖突.所以該文

法是LR(1)文法。

4)構(gòu)造LR(1)分析表

狀態(tài)ACTIONGOTO

ab#sB

0S3S412

1acc

2S6S75

3S3S48

4r3r3

5rl

6S6S7

7r3

8r2r2

9r2

填空題

［消除左遞歸(P124)

?文法左遞歸問題:一個文法是含有左遞歸的，如果存在非終結(jié)符P。

直接消除見諸于產(chǎn)生式中的左遞歸：

假定關(guān)于非終結(jié)符P的規(guī)則為P~P(I(洪中(不以P開頭。那么，我們可以把P的規(guī)則等價地改寫為如

下的非直接左遞歸形式：

P-*pPf

P'faP'le

一般而言，假定關(guān)于P的全部產(chǎn)生式是P-P(l|P(2|…|P(m|(l|(2|…|(n,其中，每個(都不等于(,而

每個(都不以P開頭,那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：

PfBlPIB2P'|…IBnP'

P,-*alP,|a2P'I-IamP11e

［例］文法

E-*E+T|T

TfT*F|F

F-(E)|i

經(jīng)消去直接左遞歸后變成：

E-TE'

E」+TE」￡

TfFT

■*FT|￡

F-(E)|i

例如文法

S-*Qc|c

QfRb|b

R-*Sa|a

?雖沒有直接左遞歸，但S、Q、R都是左遞歸的S(Qc(Rbc(Sabc

I)一個文法消除左遞歸的條件：

2)不含以匕為右部的產(chǎn)生式(無空產(chǎn)生式)；

3）不含回路。PnP

消除左遞歸的算法：

1.把文法G的所有非終結(jié)符按任一種順序排列成P1,P2,…,Pn；按此順序執(zhí)行；

2.F0.i:=T..DO

BEGIN

FORj:=lTOi-1DO

把形如Pi-Pjy的規(guī)則改寫成

P16122丫|…|西；

（其中Pi-*81|82|-|8k是關(guān)于Pj的所有規(guī)則）

消除關(guān)于Pi規(guī)則的直接左遞歸性

END

3.化簡由2所得的文法。即去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。

［例］考慮文法G（S）

S-*Qc|c

QfRb|b

R->Sa|a

令它的非終結(jié)符的排序?yàn)镽、Q、S。對于R,不存在直接左遞歸。

把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)镼-Sab|ab|b,現(xiàn)在的Q不含直接左遞歸。

把Q代入到S的有關(guān)候選后,S變成S-Sabc|abc|bc|c,由于S~Sabc|abc|be|c存在直接左遞歸，消除S

的直接左遞歸后：

S~abcS'|bcS'|cS'

S'fabeS'|E

QfSab|ab|b

RfSa|a

關(guān)于Q和R的規(guī)則已是多余的，化簡為：

S-abeS'|beS'|cS'

S'-abeS'|E

注意：由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的.

同樣：［例］考慮文法G（S）

S-*Qc|c

QfRb|b

RfSa|a

非終結(jié)符排序選為S、Q、R,那么，

R-*Qca|ca|a

R-*Rbca|bca|ca|a

最后所得的無左遞歸文法是：

S-*Qc|c

QfRb|b

RfbcaR'|caR'|aR'

R'-bcaR'|￡

不司排序所得的文法的等價性是顯然的。

2.文法的分類（Chomsky體系）（P41）

（I）短語結(jié)構(gòu)文法（PSG）

如果G滿足文法定義的要求，則G是0型文法（短語結(jié)構(gòu)文法PSG:PhraseStructureGrammar）0

L(G)為PSL。

(1)上下文有關(guān)文法(CSG)

(2)如果對于，均有|B121a成立($一￡除外)，則稱G為1型文法。即：上下文有關(guān)文法(CSG)

(3)L(G)為1型/上下文有關(guān)/敏感語言(CSL)。其他定義方法：設(shè)文法G[S],若P中任一產(chǎn)生式a-B的

形式為一，其中，B,￡(VUT)《V。

(4)上下文無關(guān)文法(CFG)

如果對于,均有并且a￡V成立，則稱G為2型文法。即：上下文無關(guān)文法(CFG:)

L(G)為2型/上下文無關(guān)語言(CFL),CFG能描述程序設(shè)計語言的多數(shù)語法成分。

(3)正規(guī)(則)文法(RG)

設(shè)A,R￡V,w￡T+或?yàn)?，加果對于，均具有如下形式?/p>

右線性(RightLinear)文法：或

左線性(LeftLinear)文法:或

都是3型文法(正規(guī)文法RG),L(G)為3型/正規(guī)集/正則集/正則語言(RL),能描述程序設(shè)計語言的多數(shù)單

詞，左、右線性文法不可混用。

[例]正規(guī)文法(RG):

G1:S0|1|00|11

G3：S()|1|()A|IB,A0,B1

G5:S0|OS

G8;AaS|bS|cS|a|b|c

上下文無關(guān)文法(CFG):

G2:SA|B|AA|BB,A0,B1

G4：SA|B|BB,A0,BI

G14:S0|1|2|3|0S0|1S1|2S2|3S3

上下文有關(guān)文法(CSG):

G：

S-CD

C-*aCA

CA-*Ca

CaD-*daD

dAc-dec

G=(V,T,P,S)是一個文法,c-*BGP

*G是0型文法,L(