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

2.1設(shè)字母表A={a},符號(hào)串x=aaa,寫出下列符號(hào)串及其長度：x0,xx,x5以

及A+和A*.

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

xx=aaaaaa|xx|=6

x5=aaaaaaaaaaaaaaa|x5|=15

A+=A,UA2U....UAnU...={a,aa,aaa,aaaa,aaaaa...}

A*=A0UA1UA2U....UAn

U...={e,a,aa,aaa,aaaa,aaaaa...}

2.2令￡=m，b,c},又令x=abc,y=b,z=aab,寫出如下符號(hào)串及它們的長

度：xy,xyz,(xy)3

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

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

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

法樹。

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

2.4已知文法G[Z]：Z：：=UO|VI、U：：=Z1|1、V：：=ZO|0,請(qǐng)寫出

全部由此文法描述的只含有四個(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,寫出該文法描述

的語言。

A：：=aA|￡描述的語言：{an|n>=0}

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

L(G[S])={anbmcm|n>=0,m>=l}

2.6已知文法E：：=TIE+T|E-T、T：：=F|T*F|T/F、F：：=(E)|i,寫

出該文法的開始符號(hào)、終結(jié)符號(hào)集合VT、非終結(jié)符號(hào)集合VN。

開始符號(hào)：E

Vt={+,(,),i)

Vn={E,F,T)

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

2.8設(shè)有文法G[S]：S：：=S*S|S+S|(S)|a,該文法是二義性文法嗎？

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

性文法。

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

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

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

2.10給出語言｛anbm|n,m2l｝的文法。

G[S]:S::=AB

A::=aA|a

B::=bB|b

3.1有正則文法G[Z]：Z::=Ua|Vb,U::=Zb|b,V::=Za|a,畫出該文

法的狀態(tài)圖，并檢查句子abba是否合法。

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

3.2狀態(tài)圖如圖3.35所示，S為開始狀態(tài)，Z為終止?fàn)顟B(tài)。寫出相應(yīng)

的正則文法以及V,Vn和V"

圖3-35狀:態(tài)圖

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

Z::=Ab|bS::=aA|b

A::=Aa|aA::=aA|b

V={Z,A,a,b)V={S,A,a,b)

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

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

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

1(1|0)*|0

1(1010*|1(010)*1)*0

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

0

3、

圖3.36狀態(tài)圖

解:

ab

q0={0}{0,1}{1}

ql={O,l}{0,1}{1}

q2={l}{0}

DFA:

a

3.5將圖3.37的DFA化簡(jiǎn)。

圖3.37DFA狀態(tài)圖

解:

劃分ab

{0,1}{1}{2,4}

{2,3,4,5}{1,0,3,5}{3,5,2,4}

劃分ab

{0,1}{1}{2,4}

{2,4}{0,1}{3,5}

{3,5}{3,5}{2,4}

qO={O,l}ql={2,4}q2={3,5}

化簡(jiǎn)后的DFA：

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

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

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

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

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

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

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

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

解：若采用遞歸下降分析方法，對(duì)此文法來說，在分析過程中不能避免回朔。因?yàn)橐?guī)則A

：：=a|Bb和規(guī)則B：：=Aab構(gòu)成了間接左遞歸，不滿足實(shí)現(xiàn)沒有回溯的遞歸下降分析方法的

條件（1）（書P67）,且規(guī)則A::=a|Bb,FIRST（a）={a},FIRST（Bb）={a},即此規(guī)則候選式

的首符號(hào)集有相交，不滿足實(shí)現(xiàn)沒有回溯的遞歸下降分析方法的條件（2）（書P67）,在分

析過程中，將造成回溯。

改寫文法可避免回溯：

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

溯。

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

〈語句＞fv語句＞＜賦值語句＞|e

〈賦值語句〉f2=〈表達(dá)式〉

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

〈項(xiàng)〉fV因子＞|＜項(xiàng)＞*〈因子＞|〈項(xiàng)〉/V因子〉

〈因子＞fID|NUM|（〈表達(dá)式〉）

解：首先，去掉左遞歸

〈語句〉■*＜語句＞＜賦值語句＞|€改為：＜語句＞T{〈賦值語句〉}

〈表達(dá)式〉—V項(xiàng)）IV表達(dá)式＞+〈項(xiàng)〉IV表達(dá)式＞-＜項(xiàng)＞改為：

〈表達(dá)式＞—礴＞{（+|-）＜項(xiàng)＞}

〈項(xiàng)〉一〈因子〉|〈項(xiàng)〉*〈因子＞|〈項(xiàng)〉/V因子〉改為：

＜項(xiàng)＞-?＜因子＞{（*|/）〈因子〉}

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

〈語句〉—{〈賦值語句〉}

〈賦值語句＞f2=＜表達(dá)式）

〈表達(dá)式〉一＜項(xiàng)＞{（+|-）＜項(xiàng)）}

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

〈因子＞fID|NUM|（〈表達(dá)式〉）

非終結(jié)符號(hào)〈語句〉的分析程序如下:＜語句〉—{〈賦值語句〉}

非終結(jié)符號(hào)〈表達(dá)式〉的分析程序如下:〈表達(dá)式〉一＜項(xiàng)＞{(+1-)V項(xiàng)〉}

非終結(jié)符號(hào)〈因子＞的分析程序如下:〈因子＞-ID|NUM|（〈表達(dá)式〉）

復(fù)值語句的分析程序

4.4有文法G[A]：A::=aABe|&B::=Bb|b

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

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

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

解：

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

FOLLOW(B)={e,b}

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

(3)先消除文法的左遞歸(轉(zhuǎn)成右遞歸)，文法變?yōu)椋篈::=aABe|s,B::=bB',

該文法的LL(1)分析表為:

aeb#

APOP,POPPOP

PUSH(eBAa)

BPOP,

PUSH(B'b)

B，POPPOP,

PUSH(B'b)

aPOP,

NEXTSYM

ePOP,

NEXTSYM

bPOP,

NEXTSYM

#ACCEPT

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

aeb#

AA-*-aABeA-*-EAf￡

BB-bB'

B，B'f￡B'fbB'

4.5若有文法A-*(A)A|e

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

(2)說明該文法是LL(1)的文法。

解：

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

FOLLOW(A)={),#}

(2)

該文法不含左遞歸；

FIRST((A)A)={(},FIRST(e)={e}>FIRST((A)A)nFIRST(e)=0>,

且FOLLOW(A)={),#},FIRST((A)A)ClFOLLOW(A)=<?,

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

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

(1)i+i*i+i

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

解：

(1)i+i*i+i

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

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

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

3#ETFi+i*i+i#POP,PUSH(i)Ff

4#ETii+i*i+i#POP,NEXTSYM

5#ET+i*i+i#POPT'fe

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

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

8#E9Ti*i+i#POP,PUSH(TT)TfFT，

9#ETFi*i+i#POP,PUSH⑴F-*i

10#ETii*i+i#POP,NEXTSYM

11#ET*i+i#POP,PUSH(T9F*)*FT，

12#ETF**i+i#POP,NEXTSYM

13#ETFi+i#POP,PUSH⑴Ffi

14#ETii+i#POP,NEXTSYM

15#ET+i#POPT'-e

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

17#E5T++i#POP,NEXTSYM

18#E'Ti#POP,PUSH(TT)TfFT'

19#ETFi#POP,PUSH⑴F->i

20#ETii#POP,NEXTSYM

21#ET#POPT'fe

22#E，#POPE'fe

23##ACCEPT

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

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

1#Ei*(i+i+i)#POP,PUSH(ET)ETE'

2#E5Ti*(i+l+i)#POP,PUSH(T，F(xiàn))T—FT，

3#ETFi*(i+i+i)#POP,PUSH(i)F->i

4#ETii*(i+i+i)#POP,NEXTSYM

5#ET*(i+i+i)#POP,PUSH(TT*)T，_*FT，

6#ETF**(i+i+i)#POP,NEXTSYM

7#ETF(i+i+i)#POP,PUSH()E()Ff(E)

8#ET)E((i+i+i)#POP,NEXTSYM

9#ET)Ei+i+i)#POP,PUSH(E,T)EfTE，

10#ET)ETi+i+i)#POP,PUSH(TT)T-FT'

11#ET)ETFi+i+i)#POP,PUSH⑴F-i

12#ET)E9T'ii+i+i)#POP,NEXTSYM

13#ET)ET+i+i)#POPT'fe

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

15#ET)E，T++i+i)#POP,NEXTSYM

16#ET)E，Ti+i)#POP,PUSH(TT)TfFT'

17#ET)ETFi+i)#POP,PUSH(i)F-i

18#ET)ETii+i)#POP,NEXTSYM

19#ET)ET+i)#POPT'fe

20#ET)E，+i)#POP,PUSH(E,T+)E'f+TE'

21#ET)E，T++i)#POP,NEXTSYM

22#E'T')E'Ti)#POP,PUSH(TT)T—FT，

23#ET)ETFi)#POP,PUSH(i)Ff

24#ET)E，T，ii)#POP,NEXTSYM

25#E'T')E'T')#POPT'—e

26#ET)E，)#POPE'fe

27#ET))#POP,NEXTSYM

28#ET#POPT'—e

29#E'#POPE'f￡

30##ACCEPT

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

〈聲明語句＞f＜類型＞＜變量表＞；

＜類型〉fint|fk＞at|char

〈變量表〉-HD,＜變量表＞|ID

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

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

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

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

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

解：

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

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

〈變量表,fIDv變量表1＞

＜變量表l＞f,＜變量表＞|e

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

〈聲明語句＞一V類型＞＜變量表＞；

v類型,fint|float|char

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

〈變量表1＞-＞,＜變量表＞|e

(2)FIRST(〈聲明語句＞)=FIRST(＜類型＞)={int,float,char)

FIRST(〈變量表＞)={ID}

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

FOLLOW(〈聲明語句＞)={#}

FOLLOW&類型＞)=FIRSTa變量表＞)={ID}

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

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

FIRST(int)nFIRST(float)DFIRST(char)=0＞

FIRST(,〈變量表〉)nFIRST(e)=O

FIRST(,〈變量表〉)CFOLLOW(〈變量表1＞)=?

因此，所得文法為LL(1)文法。

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

*

9intfloatcharIDf#

V聲明POP,POP,POP,

語句〉PUSH(；＜PUSH(；v變PUSH(；〈變

變量表x量表><類量表＞v類

類型刁型〉)型〉)

＜類POP,POP,POP,

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

〈變量POP,

表〉PUSH(<

變量表

1>ID)

〈變量POPPOP,

表1＞PUSH(<

變量

表〉，)

5POP,

NEXT

SYM

intPOP,

NEXTSY

M

floatPOP,

NEXTSYM

charPOP,

NEXTSYM

IDPOP,

NEXTSY

M

9POP,

NEXTSY

M

#ACC

EPT

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

>intfloatcharID#

〈聲明〈聲明語句〉~*v類〈聲明語句＞一＜類〈聲明語句〉fV類

語句〉型〉〈變量表〉；型＞＜變量表＞；型〉〈變量表》；

＜類v類型〉**int〈類型,ffloat〈類型〉-char

型,

V變量〈變量表,

表〉fIDv變量

表1＞

〈變量〈變量〈變量表

表1＞表1＞1＞f,＜

fe變量表＞

(5)輸入串“charx,y,z；”相對(duì)應(yīng)的LL(1)分析過程如下:

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

1#＜聲明語句〉charx,y,z；#POP,〈聲明語句〉fV

PUSH(；〈變量類型X變量

表x類型〉)表》；

2#!V變量表＞＜類charx,y,z；#POP,v類型,fchar

型〉PUSH(char)

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

charNEXTSYM

4#;〈變量表〉x,y,z；#POP,V變量表＞fIDv

PUSH(<變量表變量表1＞

1>ID)

5#;V變量表1>Xx,y,z；#POP,

NEXTSYM

6#;V變量表1>，y,z：#POP，<變量表l>f,

PUSH（<變量V變量表>

表〉，）

7#;〈變量表〉,，y，z；#POP,

NEXTSYM

8#;〈變量表〉y，z；#POP,<變量表>fID<

PUSH（<變量表變量表1>

1>ID）

9#；<變量表l>yy>z；#POP,

NEXTSYM

10#；<變量表1>，z；#POP,〈變量表1〉-*,

PUSH（<變量〈變量表〉

表〉，）

11#；〈變量表》，，z；#POP,

NEXTSYM

12#；〈變量表）z；#POP,〈變量表>-ID<

PUSH（<變量表變量表

1>ID）

13#?V變量表l>zz；#POP,

NEXTSYM

14#；<變量表1>;#POP〈變量表1>-e

15#；;#POP,

NEXTSYM

16##ACCEPT

5.1考慮以下的文法：

S-S;T|T

T-*a

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

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

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

解：

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

0：S'-S

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'f?SG0[0,S]=l

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

Sf?TG0[0,T]=2

T—?aG0[0,a]=3

1S'fS?ACCEPT

S-S?;TG0[l,;]=4

2S-T?R2

3T-*a?R3

4S-S;?TGO[4,T]=5

A?aGO[4,a]=3

5SfS;T?RI

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

表如下：

ACTIONGOTO

狀態(tài)

?a#ST

0S312

1S4ACCEPT

2R2R2R2

3R3R3R3

4S35

5RIRIRI

(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;a#R35

70145#S;T#RI1

801#S#ACCEPT

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

SfA

A-Ab|bBa

B->aAclalaAb

解：文法G[S]：

0：S-A

1：A—Ab

2：A-*bBa

3：BfaAc

4：B-*a

5：BfaAb

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

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

0Sf?AG0[0,A]=l

A-?AbG0[0,A]=l

A—?bBaG0[0,b]=2

1S—A?ACCEPT

A—A?bG0[l,b]=3

2A-b?BaGO[2,B]=4

Bf?aAcGO[2,a]=5

B—?aGO[2,a]=5

Bf?aAbGO[2,a]=5

3AfAb?RI

4AfbB,aGO[4,a]=6

5B-a?AcGO[5,A]=7

Bfa?R4

B-a?AbGO[5,A]=7

Af?AbGO[5,A]=7

A-*?bBaGO[5,b]=2

6AfbBa?R2

7BfaA?cGO[7,c]=8

BfaA?bGO[7,b]=9

A-A?bGO[7,b]=9

8B—aAc,R3

9BfaAb?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)D=0

狀態(tài)9：

FOLLOW(B)={a},FOLLOW(A)={#,b,c},因此FOLLOW(B)CFOLLOW(A)=①

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

ACTIONGOTO

狀態(tài)

abc#AB

0S21

1S3ACCEPT

2S54

3RIRIRI

4S6

5R4S27

6R2R2R2

7S9S8

8R3

9R5RIRIRI

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

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

S-AaAblBbBa

A-e

Bfe

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

0：S'T

1：S-AaAb

2：S-*,BbBa

3：A7

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

A-?R3

Bf?R4

1S'ACCEPT

2SfA?aAbGO[2,a]=4

3SfB?bBaGO[3,b]=5

4SfAa?AbGO[4,A]=6

Af?R3

5SfBb?BaGO[5,B]=7

B—?R4

6SfAaA?bG0[6,b]=8

7SfBbB?aGO[7,a]=9

8SfAaAb?RI

9SfBbBa?R2

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

HFOLLOW(B)={a,b}W①，所以該文法不是SLR(1)文法。

構(gòu)造LR(1)項(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

Af?,aR3

Bf?,bR4

1S,->s?,#ACCEPT

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

3S-B?bBa,#G0[3,b]=5

4S^Aa?Ab,#GO[4,A]=6

Af?,bR3

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

B—?,aR4

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

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

8SfAaAb?,#RI

9S->BbBa?,#R2

LR⑴分析表:

ACTIONGOTO

狀態(tài)

ab#SAB

0R3R4123

1ACCEPT

2S4

3S5

4R36

5R47

6S8

7S9

8RI

9R2

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

5.4考慮以下的文法：

E-EE+

E-EE*

Efa

(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⑴和LALR(l)分析。

解：

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

0：SfE

1：E-*EE+

2；E—EE*

3：E—a

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

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

0S一?E,#G0[0,E]=l

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

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

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

1S-E,,#ACCEPT

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

EfE?E*,a:#G0[l,E]=3

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

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

Ef?a,*:+GO[1,a]=4

2Efa?,a:#R3

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

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

EfE?E+,*:+GO[3,E]=7

EfE?E*,*:+GO[3,E]=7

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

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

Ef?a,*:+GO[3,a]=4

4Efa?,*:+R3

5EfEE+?,a:#RI

6EfEE*?,a:#R2

7EfEE?+,*:+GO[7,+]=8

EfEE?*,*:+GO[7,*]=9

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

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

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

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

E—?a,*:+GO[7,a]=4

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

9EfEE**,*:+R2

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

ACTIONGOTO

狀態(tài)

+*a#E

0S21

1S4ACCEPT3

2R3R3

3S5S6S47

4R3R3

5RIRI

6R2R2

7S8S9S47

8RIRI

9R2R2

(3)構(gòu)造LALR(l)項(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:ttG0[0,E]=l

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

1S-E?,#ACCEPT

E-E?E+,a:#G0[l,E]=3

EfE?E*,a:#G0[LE]=3

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

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

Ef-a,*:+G0[l,a]=2

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

3EfEE?+,a:8:*:+GO[3,+]=4

EfEE?*,a:#:*：+GO[3,*]=5

EfE-E+,*:+GO[3,E]=3

E-E*E*,*：+GO[3,E]=3

E->?EE+,?：+GO[3,E]=3

E-?EE*,*：+GO[3,E]=3

E->?a,*:+GO[3,a]=2

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

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

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

ACTIONGOTO

狀態(tài)

+*a#E

0S21

1S2ACCEPT3

2R3R3R3R3

3S4S5S23

4RIRIRI