編譯原理及實(shí)現(xiàn)課后習(xí)題答案

2.1設(shè)字母表A={a},符號(hào)串x=aaa,寫(xiě)出下列符號(hào)串及其長(zhǎng)度：x。,xx,x5以及A+和A*.

x°=(aaa)°=e|x°|=0

xx=aaaaaa|xx|=6

x5=aaaaaaaaaaaaaaa|xs|=15

A*=A1UA2U….UAnU???={a,aa,aaa,aaaa,aaaaa***}

A*=A0UA1UA2U….UA"U???={e,a,aa,aaa,aaaa,aaaaa***}

2.2令￡=匕，b,c},又令x=abc,y=b,z=aab,寫(xiě)出如下符號(hào)串及它們的長(zhǎng)度：xy,xyz,(xy)3

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12

2.3設(shè)有文法G[S]：S：：=SS*|SS+|a,寫(xiě)出符號(hào)串a(chǎn)a+a*規(guī)范推導(dǎo)，并構(gòu)造語(yǔ)法樹(shù)。

S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

2.4已知文法G[Z]：Z：：=UO|VI、U：：=Z1|1、V：：=ZO|0,請(qǐng)寫(xiě)出全部由此文法描述的只含有四個(gè)符號(hào)

的句子。

Z=>U0=>Z10=>U010=>1010

Z=>U0=>Z10=>V110=>0110

Z=>Vl=>Z01=>U001=>1001

Z=>Vl=>Z01=>V101=>0101

2.5已知文法G[S]：S：：=ABA：：=aA|eB：：=bBc|be,寫(xiě)出該文法描述的語(yǔ)言。

A：：=aA|￡描述的語(yǔ)言：{川11〉=0}

B：：=bBc|be描述的語(yǔ)言：{bncn|n>=l}

L(G[S])={aVc-ln>=0,m>=l}

2.6已知文法E：：=TIE+TIE-T、T：：=FIT*FIT/F、F：：=(E)Ii,寫(xiě)出該文法的開(kāi)始符號(hào)、終結(jié)符號(hào)集合

VT、非終結(jié)符號(hào)集合VN。

開(kāi)始符號(hào)：E

Vt={+,i}

Vn={E,F,T)

2.7對(duì)2.6題的文法，寫(xiě)出句型T+T*F+i的短語(yǔ)、簡(jiǎn)單短語(yǔ)以及句柄。

根據(jù)所給文法推導(dǎo)出句子a+a*a,畫(huà)出了兩棵不同的語(yǔ)法樹(shù)，所以該文法是二義性文法。

2.9寫(xiě)一文法，使其語(yǔ)言是奇正整數(shù)集合。

A::=1|3|5|7|9|NA

N::=0|l|2|3|4|5|6|7|8|9

2.10給出語(yǔ)言｛anbm|n,m^l）的文法。

G[S]:S::=AB

A::=aA|a

B::=bB|b

3.1有正則文法G[Z]：Z::=Ua|Vb,U::=Zb|b,V::=Za|a,畫(huà)出該文法的狀態(tài)圖，并檢查句子abba是否合法。

解：該文法的狀態(tài)圖如下：

句子abba合法。

3.2狀態(tài)圖如圖3.35所示，S為開(kāi)始狀態(tài)，Z為終止?fàn)顟B(tài)。寫(xiě)出相應(yīng)的正則文法以及V,k和X。

解：左線性文法G[Z]:右線性文法

Z::=Ab|b

S::=aA|b

A::=Aa|a

A::=aA|b

V={Z,A,a,b)

V={S,A,a,b)

Vn={Z,A}V?={S,A}

Vt={a,b}Vt={a,b}

3.3構(gòu)造下列正則表達(dá)式相應(yīng)的NFA：

1(1|0)*|0

1(1010*11(010)*1)*0

解：正則表達(dá)式：1(1|0)*|0

{0,1}⑴

ql={0,1}{0,1}{1}

q2={l}{0}①

4.1對(duì)下面文法，設(shè)計(jì)遞歸下降分析程序。

S-*aAS|(A),AfAb|c

解：首先將左遞歸去掉，將規(guī)則A-Able改成A-c

非終結(jié)符號(hào)S的分析程序如下：

非終結(jié)符號(hào)A的分析程序如下:

4.2設(shè)有文法G[Z]：

Z：：=（A）,A：：=a|Bb,B：：=Aab

若采用遞歸下降分析方法，對(duì)此文法來(lái)說(shuō)，在分析過(guò)程中，能否避免回溯？為什么？

解：若采用遞歸下降分析方法，對(duì)此文法來(lái)說(shuō)，在分析過(guò)程中不能避免回朔。因?yàn)橐?guī)則A：：二a|Bb和規(guī)則B：：:Aab

構(gòu)成了間接左遞歸，不滿(mǎn)足實(shí)現(xiàn)沒(méi)有回溯的遞歸下降分析方法的條件（1）（書(shū)P67）,且規(guī)則A::=a|Bb,

FIRST（a）={a},FIRST（Bb）={a）,即此規(guī)則候選式的首符號(hào)集有相交，不滿(mǎn)足實(shí)現(xiàn)沒(méi)有回溯的遞歸下降分析方法的

條件（2）（書(shū)P67）,在分析過(guò)程中，將造成回溯。

改寫(xiě)文法可避免回溯：

將規(guī)則B：：=Aab代入規(guī)則A：：=a|Bb得:A：：=a|Aabb,再轉(zhuǎn)換成：A：：=a{abb）,可避免回溯。

4.3若有文法如下，設(shè)計(jì)遞歸下降分析程序。

＜語(yǔ)句）-*＜語(yǔ)句＞＜賦值語(yǔ)句＞|￡

＜賦值語(yǔ)句＞fID=＜表達(dá)式＞

＜表達(dá)式）一〈項(xiàng)）I＜表達(dá)式〉+＜項(xiàng)＞|〈表達(dá)式〉一＜項(xiàng)＞

＜項(xiàng)〉-＞＜因子〉k項(xiàng)〉*〈因子）|＜項(xiàng)＞/＜因子）

＜因子＞-ID|NUM|（〈表達(dá)式））

解：首先，去掉左遞歸

〈語(yǔ)句〈語(yǔ)句X賦值語(yǔ)句》|￡改為：＜語(yǔ)句＞f{＜賦值語(yǔ)句）}

＜表達(dá)式＞一＜項(xiàng)〉|＜表達(dá)式〉+〈項(xiàng)）|＜表達(dá)式〉-〈項(xiàng)〉改為:

〈表達(dá)式＞~＞＜項(xiàng)＞{（+I-）＜項(xiàng)》

＜項(xiàng)＞一＜因子＞|＜項(xiàng)＞*＜因子）|＜項(xiàng)＞/＜因子）改為：

＜項(xiàng)＞f＜因子＞{（*|/）＜因子）}

則文法變?yōu)椋?/p>

＜語(yǔ)句＞一｛〈賦值語(yǔ)句）｝

＜賦值語(yǔ)句）fIDX表達(dá)式）

〈表達(dá)式〉f〈項(xiàng)乂（+|-）〈項(xiàng)》

＜項(xiàng)＞-＜因子＞｛（*|/）＜因子）｝

＜因子＞-ID|NUM|（＜表達(dá)式））

非終結(jié)符號(hào)＜因子)的分析程序如下:v因子,fID|NUM|(v表達(dá)式〉)

4.4有文法文法:A::=aABe|e,B::=Bb|b

(1)求每個(gè)非終結(jié)符號(hào)的FOLLOW集。

(2)該文法是LL(1)文法嗎？

(3)構(gòu)造LL⑴分析表。

解:

(1)FOLLOW(A)=First(B)U{#}={b,#}

FOLLOW(B)={e,b}

(2)該文法中的規(guī)則B::=Bb|b為左遞歸，因此該文法不是LL(1)文法

(3)先消除文法的左,m母*"心、+口?水4A??一ADjg,B::=bB'B'=bB'|e,該文法的LL⑴

分析表為：復(fù)值語(yǔ)句的分析程序

aeb#

APOP,POPPOP

PUSH(eBAa)

BPOP,

PUSH(B'b)

B，POPPOP,

PUSH?b)

aPOP,

NEXTSYM

ePOP,

NEXTSYM

bPOP,

NEXTSYM

#ACCEPT

更常用且簡(jiǎn)單的LL(1)分析表:

aeb#

AA->aABeAfeA-e

BB—bB，

B，B，-€B'-bB'

4.5若有文法A~(A)A|e

(1)為非終結(jié)符A構(gòu)造FIRST集合和FOLLOW集合。

(2)說(shuō)明該文法是LL⑴的文法。

解：

(1)FIRST(A)={(,e)

FOLLOW(A)={),#}

(2)

該文法不含左遞歸；

FIRST((A)A)={(},FIRST(e)={e},FIRST((A)A)nFIRST(e)=<D,

且FOLLOW(A)={),#},FIRST((A)A)AFOLLOW(A):①，

因此，該文法滿(mǎn)足LL(1)文法的條件，是LL⑴文法。

4.6利用分析表4-L識(shí)別以下算術(shù)表達(dá)式，請(qǐng)寫(xiě)出分析過(guò)程。

(1)i+i*i+i

(2)i*(i+i+i)

解：

(1)i+i*i+i

步驟分析棧余留輸入串分析表元素所用產(chǎn)生式

1#Ei+i*i+i#POP,PUSH(E*T)E-TE'

2#E，Ti+i*i+i#POP,PUSH(T*F)TfFT'

3#E'T,Fi+i*i+i#POP,PUSH(i)F-i

4#E'T'ii+i*i+i#POP,NEXTSYM

5#E'T+i*i+i#POPT，-e

6#E，+i*i+i#POP,PUSH(E'T+)E'f+TE'

7#E'T++i*i+i#POP,NEXTSYM

8阿Ti*i+i#POP,PUSH(T,F)T-FT'

9#E'T'Fi*i+i#POP,PUSH(i)F-i

10#E'T'ii*i+i#POP,NEXTSYM

11阿V?i+i#POP,PUSH(T*F*)『TFT，

12#E'T'F**i+i#POP,NEXTSYM

13#E'T'Fi+i#POP,PUSH(i)F-i

14#E'『ii+i#POP,NEXTSYM

15#E'T'+i#POPT'-*￡

16陽(yáng)+i#POP,PUSH(E,T+)E'—+TE'

17#E'T++i#POP,NEXTSYM

18#E'Ti#POP,PUSH(T*F)TfFT'

19#E'『Fi#POP,PUSH(i)FT

20#E'T'ii#POP,NEXTSYM

21#E'T'#POPT'f￡

22#POPE，-*e

23##ACCEPT

(2)i*(i+i+i)

步驟分析棧余留輸入串分析表元素所用產(chǎn)生式

1#Ei*(i+i+i)#POP,PUSH(E,T)ETE，

2#E,Ti*(i+i+i)#POP,PUSH(T,F)T-FT

3#E'T'Fi*(i+i+i)#POP,PUSH(i)FT

4#E'『ii*(i+i+i)#POP,NEXTSYM

5#EJT'*(i+i+i)#POP,PUSH(T,F*)『TFT，

6#E,T'F**(i+i+i)#POP,NEXTSYM

7#E'『F(i+i+i)#POP,PUSHOEOF-(E)

8#E，『)E((i+i+i)#POP,NEXTSYM

9#E，V)Ei+i+i)#POP,PUSH(E，T)E-TE'

10#E'『)E'Ti+i+i)#POP,PUSH〕'F)TfFT'

11#E，『)E'i+i+i)#POP,PUSH(i)F-i

T'F

12#E'T')E'i+i+i)#POP,NEXTSYM

丁i

13#E'T')E'+i+i)#POPT，-*e

14#E'T')E,+i+i)#POP,PUSH(E*T+)E'f+TE'

15#E'T')+i+i)#POP,NEXTSYM

E'T+

16#E'T')E，Ti+i)#POP,PUSH(T*F)TfFT'

17#E'『)i+i)#POP,PUSH(i)FT

E，rF

18#E'T)i+i)#POP,NEXTSYM

EfT'i

19#E'『)+i)#POPT，-e

E，T‘

20#E'『)E，+i)#POP,PUSH(E*T+)E'—+TE'

21#E'T')E'+i)#POP,NEXTSYM

T+

22#E'『）E，Ti)#POP,PUSH(T*F)TfFT'

23#E'T')E'i)#POP,PUSH(i)F-i

T'F

24#E'T')E'i)#POP,NEXTSYM

T'i

25#E'T')E')#POPT'fe

26#E'T')E')#POPE，-e

27#E，T'))#POP,NEXTSYM

28#E'T'#POPT'fe

29#E'#POPE，-*e

30##ACCEPT

4.7考慮下面簡(jiǎn)化了的C聲明文法：

〈聲明語(yǔ)句＞一＜類(lèi)型X變量表)；

〈類(lèi)型)fint|float|char

〈變量表》-ID,＜變量表＞|ID

(1)在該文法中提取左因子。

(2)為所得的文法的非終結(jié)符構(gòu)造FIRST集合和FOLLOW集合。

(3)說(shuō)明所得的文法是LL(1)文法。

(4)為所得的文法構(gòu)造LL⑴分析表。

(5)假設(shè)有輸入串為“charx,y,z；”，寫(xiě)出相對(duì)應(yīng)的LL⑴分析過(guò)程。

解：

(1)規(guī)則＜變量表＞-ID,＜變量表＞|ID提取公因子如下：〈變量表)一ID(，＜變量表》|￡)

增加新的非終結(jié)符＜變量表1＞,規(guī)則變?yōu)椋?/p>

〈變量表〉fID＜變量表1＞

〈變量表1＞一，＜變量表＞1￡

C聲明文法改變?yōu)椋?/p>

＜聲明語(yǔ)句＞一＜類(lèi)型＞＜變量表)；

＜類(lèi)型〉fint|float|char

＜變量表＞~ID＜變量表1＞

〈變量表l＞f,＜變量表＞1e

(2)FIRST(〈聲明語(yǔ)句＞)=FIRST(＜類(lèi)型＞)={int,float,char)

FIRST《變量表＞)={ID)

FIRST(〈變量表1＞)={,,e}

FOLLOW(＜聲明語(yǔ)句〉)={#}

FOLLOW(＜類(lèi)型＞)=FIRST《變量表＞)={ID}

FOLLOW(＜變量表〉)=FOLLOW(＜變量表1＞)={；}

(3)所得文法無(wú)左遞歸，且

FIRST(int)AFIRST(float)DFIRST(char)=＜D

FIRST(,＜變量表〉)AFIRST(e)=＜D

FIRST(,＜變量表＞)CIFOLLOW(《變量表1＞)=①

因此，所得文法為L(zhǎng)L⑴文法。

(4)所得的文法構(gòu)造LL(1)分析表如下所示:

?intfloatcharID9n

＜聲明POP,POP,POP,

語(yǔ)句》PUSH(；＜變量PUSHG＜變量PUSH(；＜變量

表X類(lèi)型))表X類(lèi)型))表X類(lèi)型》

＜類(lèi)POP,POP,POP,

型)PUSH(int)PUSH(float)PUSH(char)

＜變量POP,

表》PUSH?變量表

1＞ID)

＜變量POPPOP,

表1》PUSH?變量

表)，)

?POP

NEX

TSY

M

intPOP,

NEXTSYM

floatPOP,

NEXTSYM

charPOP,

NEXTSYM

IDPOP,

NEXTSYM

POP,

NEXTSYM

ACCE

PT

更常用且簡(jiǎn)單的LL（1）分析表:

■

9intfloatcharID9#

〈聲明《聲明語(yǔ)句＞f＜〈聲明語(yǔ)句＞f＜〈聲明語(yǔ)句〉-＞＜

語(yǔ)句）類(lèi)型＞＜變量類(lèi)型X變量類(lèi)型X變量

表）；表）；表）；

＜類(lèi)〈類(lèi)型）fint<類(lèi)型)ffloat<類(lèi)型)-char

型〉

＜變量〈變量表》

表）-*ID＜變

量表1＞

《變量<變＜變量

表1＞量表表1＞

1>ff,〈變

e量表》

(5)輸入串"charx,y,z；n；由對(duì)應(yīng)的LL（1）分析過(guò)程如下：

步驟分析棧余留輸入串分析表元素所用產(chǎn)生式

1做聲明語(yǔ)句）charx,y,z；POP,＜聲明語(yǔ)句＞一＜

#PUSH（；＜變量表X類(lèi)型X變量

類(lèi)型》表〉；

2#;＜變量表＞＜類(lèi)charx,y,z；POP,<類(lèi)型)-char

型）nPUSH(char)

3#;〈變量表）charx,y,z；POP,

charnNEXTSYM

4擔(dān)＜變量表》x,y,z；#POP,＜變量表＞fID＜

PUSH?變量表變量表1＞

DID)

5#;＜變量表Dxx,y?z；#POP,

NEXTSYM

6#;＜變量表1＞，y，z；#POP,〈變量表1＞一,＜

PUSH(<變量表>,)變量表》

7#；＜變量表＞，，y，z；#POP,

NEXTSYM

8機(jī)＜變量表）y,z；#POP,〈變量表＞fID＜

PUSH?變量表變量表1＞

1>ID)

9機(jī)＜變量表l＞yy,z；#POP,

NEXTSYM

10#;＜變量表1＞?Z；#POP,＜變量表l＞f,＜

PUSH(<變量表),)變量表》

11#;＜變量表〉，,Z；#POP,

NEXTSYM

12#；＜變量表＞Z；#POP,＜變量表＞-ID＜

PUSH?變量表變量表1＞

1>ID)

13#;＜變量表DzZ；#POP,

NEXTSYM

14#;＜變量表1＞;#POP＜變量表e

15;#POP,

NEXTSYM

16##ACCEPT

5.1考慮以下的文法：

S-*S;T|T

T-*a

＜1)為這個(gè)文/構(gòu)造LR(0)的項(xiàng)目集規(guī)范族。

(2)這個(gè)文法是不是LR(0)文法？如果是，則構(gòu)造LR(0)分析表。

(3)對(duì)輸入串“a;a”進(jìn)行分析。

解：

(1)拓廣文法G[S'G

0：S'fs

1：S-S;T

2：S-T

3：T-a

構(gòu)造LR(0)項(xiàng)目集規(guī)范族

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'--SG0[0,S]=l

Sf?S;TG0[0,S]=l

S-?TG0[0,T]=2

T-**aG0[0,a]=3

1S'fS?ACCEPT

S-S?；TG0[l,1]=4

2S-T?R2

3T—a?R3

4S—S;?TG0[4,T]=5

T—?aG0[4,a]=3

5S-S;T?RI

(2)該文法不存在“歸約一歸約”和“歸約一移進(jìn)”沖突,因此是LR(0)文法。LR(0)分析表如下:

ACTIONGOTO

狀態(tài)

f*a#ST

0S312

1S4ACCEPT

2R2R2R2

3R3R3R3

4S35

飛|―R1―PRIRI

(3)對(duì)輸入串“a;a”進(jìn)行分析如下：

步驟狀態(tài)棧符號(hào)棧輸入符號(hào)棧ACTIONGOTO

00#a:a#S3

103#a;a#R32

302#T;a#R21

401#S;a#S4

5014#S;a#S3

60143#S;aR35

70145#S;TRI1

801#SACCEPT

5.2證明下面文法是SLR(l)文法，但不是LR(O)文法。

S-*A

AfAblbBa

B-?aAc|a|aAb

解:文法G[S]：

0：SfA

1：A-Ab

2：AfbBa

3：B->aAc

4：Bfa

5：B-*aAb

構(gòu)造LR(0)項(xiàng)目集規(guī)范族：

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S-**AG0[0,A]=l

A—?AbG0[0,A]=l

Af?bBaG0[0,b]=2

1S-*A?ACCEPT

AfA?bG0[l,b]=3

2A—b?BaG0[2,B]=4

B—?aAcG0[2,a]=5

Bf?aG0[2,a]=5

B~?aAbG0[2,a]=5

3A-*Ab?RI

4A-*bB?aG0[4,a]=6

5Bfa?AcG0[5,A]=7

B-a?R4

Bfa?AbG0[5,A]=7

A-**AbG0[5,A]=7

Af?bBaG0[5,b]=2

6A-*bBa?R2

7B-*aA?cG0[7,c]=8

BfaA?bG0[7,b]=9

AfA?hG0[7,h]=9

8B—aAc?R3

9B-*aAb-R5

A-Ab-RI

狀態(tài)5存在“歸約一移進(jìn)”沖突，狀態(tài)9存在“歸約一歸約”沖突，因此該文法不是LR(O)文法。

狀態(tài)5：

FOLLOW(B)={a},因此，F(xiàn)OLLOW(B)n=O

狀態(tài)9：

FOLLOW(B)={a},FOLLOW(A)={#,b,c},@jfcFOLLOW(B)nFOLLOW(A)=O

狀態(tài)5和狀態(tài)9的沖突均可用SLR(l)方法解決，構(gòu)造SLR(l)分析表如下：

ACTIONGOTO

狀態(tài)

abcAB

0S21

1S3ACCEPT

2S54

3RIRIRI

4S6

5R4S27

6R2R2R2

7S9S8

8R3

9R5RIRIRI

該SLR(l)分析表無(wú)重定義，因此該文法是SLR(1)文法，不是LR(O)文法。

5.3證明下面文法是LR(1)文法，但不是SLR(l)文法。

S—AaAblBbBa

A—e

Bfe

解：拓廣文法G[S']；

0：S'fs

1：SfAaAb

2：S-BbBa

3：A-e

4：Bfe

構(gòu)造LR(O)項(xiàng)目集規(guī)范族：

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'一?SG0[0,S]=l

Sf?AaAbG0[0,A]=2

S—?BbBaG0[0,B]=3

Af?R3

B~?R4

1S'T?ACCEPT

2SfA?aAbG0[2,a]=4

3S~B?bBaG0[3,b]=5

4S-*Aa?AbG0[4,A]=6

Af?R3

5SfBb?BaG0[5,B]=7

B-*?R4

6SfAaA?bG0[6,b]=8

7SfBbB?aG0[7,a]=9

8S~AaAb?RI

9SfBbBa?R2

狀態(tài)0存在“歸約一歸約”沖突，且FOLLOW(A)={a,b},FOLLOW(B)={a,b},即FOLLOW(A)AFOLLOW(B)={a,b}

K①，所以該文法不是SLR(l)文法。

構(gòu)造LR⑴項(xiàng)目集規(guī)范族：

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S'-?S,#G0[0,S]=l

Sf?AaAb,#G0[0,A]=2

S--BbBa,#G0[0,B]=3

A-*?,aR3

B—?，bR4

1S'~S?，#ACCEPT

2S-*A?aAb,#G0[2,a]=4

3SfB?bBa,#G0[3,b]=5

4S-Aa?Ab,#G0[4,A]=6

Af?,bR3

5S--Bb?Ba,#G0[5,B]=7

B-*?,aR4

6SfAaA?b,#G0[6,b]=8

7S->BbB?a,#G0[7,a]=9

8S->AaAb?,#RI

9S—BbBa?,#R2

LR⑴分析表:

ACTIONGOTO

狀態(tài)

abSAB

0R3R4123

1ACCEPT

2S4

3S5

4R36

5R47

6S8

7S9

8RI

9R2

分析表無(wú)重定義，說(shuō)明該文法是LR(1)文法，不是SLR(l)文法。

5.4考慮以下的文法：

ETE+

E-*EE*

E->a

(1)為這個(gè)文法構(gòu)造LR(1)項(xiàng)目集規(guī)范族。

(2)構(gòu)造LR⑴分析表。

(3)為這個(gè)文法構(gòu)造LALR(l)項(xiàng)目集規(guī)范族。

(4)構(gòu)造LALR(l)分析表。

(5)對(duì)輸入符號(hào)串“aa*a+”進(jìn)行LR(1)和LALR(l)分析。

解：

(1)拓廣文法G[S]：

0：SfE

1：EfEE+

2：E—EE*

3：Efa

構(gòu)造LR⑴項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S-*?E,#G0[0,E]=l

E->?EE+,a:#G0[0,E]=l

Ef,EE*,a:#G0[0,E]=l

Ef?a,a:#G0[0,a]=2

1S—E?，#ACCEPT

EfE?E+,a:#GO[1,E]=3

E-E?E*,a:#GO[LE]=3

E—?EE+,*:+GO[1,E]=3

Ef?EE*,*:+GO[LE]=3

E-?a,*:+GO[La]=4

2Efa??a:#R3

3EfEE?+,a:#G0[3,+]=5

EfEE?*,a:#G0[3,*]=6

E-E-E+,*:+G0[3,E]=7

E—E?E*,*：+G0[3,E]=7

Ef?EE+,*:+G0[3,E]=7

E~?EE*,*:+G0[3,E]=7

Ef-a,*:+G0[3,a]=4

4E-a?,*:+R3

5EfEE+?,a:#RI

6E-EE*?,a:#R2

7E—EE?+,*:+G0[7,+]=8

E-EE?*,*:+G0[7,*]=9

E—E?E+,*:+G0[7,E]=7

EfE?E*,*:+G0[7,E]=7

E-?EE+,*:+G0[7,E]=7

Ef?EE*,*：+G0[7,E]=7

E~?a,*:+G0[7,a]=4

8E-*EE4-*,*:+RI

9E->EE**,*:+R2

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

ACTIONGOTO

狀態(tài)

4-*a#E

0S21

1S4ACCEPT3

2R3R3

3S5S6S47

4R3R3

5RIRI

6R2R2

7S8S9S47

8RIRI

9|R2|R2

(3)構(gòu)造LALR(l)項(xiàng)目集規(guī)范族:

狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)

0S—E,#G0[0,E]=l

E—?EE4-,a:#G0[0,E]=l

Ef?EE*,a:#G0[0,E]=l

E-**a,a:#G0[0,a]=2

1S-*E-,#ACCEPT

EfE?E+,a:#GOU,E]=3

E-*E?E*,a:#GO[1,E]=3

Ef?EE+,*:+G0[l,E]=3

Ef-EE*,*:+GO[1,E]=3

E—?a,*:+G0[l,a]=2

2Efa??a:#:*:+R3

3E—EE?4-,a:#:*:+G0[3,+]=4

E—EE?*,a:#:*:+G0[3,*]=5

E->E?E+,*:+G0[3,E]=3

E-E-E*,*:+G0[3,E]=3

E—?EE+,*:+G0[3,E]=3

E-?EE*,*:+G0[3,E]=3

Ef?a,*:+G0[3,a]=2

4E-EE+?,a:#:*:+RI

5E-EE*?,a:#:*:+R2

(4)構(gòu)造LALR(l)分析表。

ACTIONGOTO

狀態(tài)

4-*a#E

0S21

1S2ACCEPT3

2