编译原理（清华大学 第2版）课后习题答案

第三章

N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD

L={a |a(0|1|3..|9)n

且 n>=1}

(0|1|3..|9)n

且 n>=1

{ab,}

anbn

n>=1

第6题.

(1) <表达式> => <项> => <因子> => i

(2) <表达式> => <项> => <因子> => (<表达式>) => (<项>)

=> (<因子>)=>(i)

(3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i

(4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项>

=> <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i

(5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>)

=> i+(<因子>+<因子>)

=> i+(i+i)

(6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

<表达式><表达式><运算符><表达式><表达式><运算符><表达式>*ii+i 1

<表达式><表达式><运算符><表达式>i+<表达式><运算符><表达式>i*

第9题 语法树

sss*ss+a

aa

推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树:

EE+TT*F

短语: T*F E+T*F 直接短语: T*F 句柄: T*F

12．

i2

短语： 直接短语： 句柄：

13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS

=> abBS => abbS => abbAa => abbaa

最右推导：S => ABS => ABAa => ABaa => ASBBaa

=> ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3

(2) 文法：S ? ABS

S ? Aa S ? ε A ? a

B ? b

(3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa,

直接短语： a1 , b1 , b2, a2 , , 句柄：a1

14 (1)

S ? AB

A ? aAb | ε B ? aBb | ε (2)

S ? 1S0 S ? A

A ? 0A1 |ε

第四章

1. 1. 构造下列正规式相应的DFA (1) 1(0|1)*101

NFA

0111203140,1

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

3

00111010ε00014001020

(3)NFA

b (4)NFA

a2a0a1b42b0b1ε3εba5b6ε3εa,bab4

2.解：构造DFA矩阵表示 {X} {Z } {X,Z} {Y}

**00 {Z} {X,Z} {X,Z} {X,Y} 1 {X} {Y} {X,Y} 4

{X,Y} {X,Y,Z} {X} {X,Y,Z} * {X,Y,Z} {X,Y} 其中0 表示初态，*表示终态

用0，1，2，3，4，5分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z} 得DFA状态图为：

11130000005012411

3．解：构造DFA矩阵表示 构造DFA的矩阵表示 0 1 {S}0 {V,Q} {Q,U} {V,Q} {Z,V} {Q,U} {Q,U} {V} {Q,U,Z} {Z,V}* {Z} {Z} {V} {Z} {Q,U,Z}* {V,Z} {Q,U,Z} {Z} {Z} {Z} 其中0 表示初态，*表示终态

替换后的矩阵 0 1 00 1 2 1 3 2 2 4 5 3* 6 6 4 6 5* 3 5 6 6 6 构造DFA状态转换图（略） 4．（1）解

构造状态转换矩阵：

5

a b {0}0* {0,1} {1} {0,1}* {0,1} {1} {1} {0}

转换为 a b 0* 1 2 1* 1 2 2 0

{2，3} {0，1}

{2，3}a={0,3} {2},{3},{0,1}

{0,1}a={1,1} {0,1}b={2,2} （2）解：首先把M的状态分为两组：终态组{0}，和非终态组{1，2，3，4,5} {1,2,3,4,5}a={1,3,0,5} {1,2,3,4,5}b={4,3,2,5}

由于{4}a={0} {1,2,3,5}a={1,3,5}

因此应将{1,2,3,4,5}划分为{4},{1,2,3,5} G=({0}{4}{1,2,3,5}) {1,2,3,5}a={1,3,5} {1,2,3,5}b={4,3,2}

因为{1,5}b={4} {23}b={2,3}

所以应将{1,2,3,5}划分为{1,5}{2,3} G=({0}{1,5}{2,3}{4})

{1,5}a={1,5} {1,5}b={4} 所以{1,5} 不用再划分 {2,3}a={1,3} {2,3}b={3,2}

因为 {2}a={1} {3}a={3} 所以{2,3}应划分为{2}{3} 所以化简后为G＝（ {0},{2},{3},{4},{1,5}）

7.去除多余产生式后，构造NFA如下

aADabbbSZbbbbBQaa

此时G=( {0},{1,2,3,4,5} ) 6

确定化，构造DFA矩阵 a b S A Q A A B,Z B,Z Q D Q Q D,Z D A B D,Z A D B Q D 变换为 a b 00 1 3 1 1 2 2* 3 4 3 3 5 4 1 6 5* 1 4 6 3 4 化简： G={(0,1,3,4,6),(2,5)} {0,1,3,4,6}a={1,3}

{0,1,3,4,6}b={2,3,4,5,6}

所以将{0,1,3,4,6}划分为 {0,4,6}{1,3} G={(0,4,6),(1,3),(2,5)}

{0,4,6}b={3,6,4} 所以 划分为{0},{4,6} G={(0),(4,6),(1,3),(2,5)}

不能再划分，分别用 0，4，1，2代表各状态，构造DFA状态转换图如下；

a0a,b1a4bbab2

8．代入得

S = 0(1S|1)| 1(0S|0) = 01(S|ε) | 10(S|ε) = (01|10)(S|ε)

= (01|10)S | (01|10)

7

= (01|10)*

(01|10)

构造NFA

0A11SZ01B0

由NFA可得正规式为(01|10)*

(01|10)=(01|10)+

9.状态转换函数不是全函数,增加死状态8, G={(1,2,3,4,5,8),(6,7)}

(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出 (1,2,3,4,5,8)b=(2,6,7,8) (1,2,3,4,5,8)c=(3,8) (1,2,3,4,5,8)d=(3,8)

所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4) G={(1,2,5,8),(3,4),(6,7)}

(1,2,5,8)a=(3,4,8) 8应分出 (1,2,5,8)b=(2,8) (1,2,5,8)c=(8) (1,2,5,8)d=(8)

G={(1,2,5),(8),(3,4),(6,7)} (1,2,5)a=(3,4,8) 5应分出

G={(1,2), (3,4),5, (6,7) ,(8) } 去掉死状态8,

最终结果为 (1,2) (3,4) 5,(6,7) 以1,3,5,6代替,最简DFA为bc1a3b6bda5

正规式:b*a(da|c)*bb*

第五章

1.

8

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

S => ( T ) => ( T , S ) => ( S , S ) => ( a , S) => ( a, ( T )) =>(a , ( T , S ) ) => (a , ( S , S )) => (a , ( a , a ) ) S=>(T) => (T,S) => (S,S) => ( ( T ) , S ) => ( ( T , S ) , 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 ) , ^ , S ) , S ) => ( ( ( a , a ) , ^ , ( T ) ) , S )

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

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

消除直接左递归： S->a | ^ |( T ) T -> S T’

T’ -> , S T’ | ξ

SELECT ( S->a) = {a} SELECT ( S->^) = {^}

SELECT ( S->( T ) ) = { ( }

SELECT ( T -> S T’) = { a , ^ , ( } SELECT ( T’ -> , S T’ ) = { , }

SELECT ( T’ ->ξ) = FOLLOW ( T’ ) = FOLLOW ( T ) = { ） }

构造预测分析表 S T T’

a -> a -> S T’ ^ -> ^ -> S T’ ( -> ( T ) -> S T’ ) ->ξ , -> , S T’ # 分析符号串 （ a , a ）#

分析栈 剩余输入串 所用产生式 #S ( a , a) # S -> ( T ) # ) T ( ( a , a) # ( 匹配 # ) T a , a ) # T -> S T’ # ) T’ S a , a ) # S -> a # ) T’ a a , a ) # a 匹配 # ) T’ ，a) # T’ -> , S T’ # ) T’ S , , a ) # , 匹配 # ) T’ S a ) # S->a # ) T’ a a ) # a匹配 # ) T’ ) # T’ ->ξ # ) ) # )匹配 # # 接受

9

2.

E->TE’ E’->+E E’->ξ T->FT’ T’->T T’->ξ F->PF’ F’->*F’ F’->ξ P->(E) P->a P->b P->∧ 非终结符名 E E’ T T’ F F’ P 是否＝>ε 否 是 否 是 否 是 否 FIRST集 {（，a，b，^} {+,ε} {（，a，b，^} {ε, （，a，b，^} {（，a，b，^} {*,ε} {（，a，b，^} FOLLOW集 {#，）} {#，）} {＋，#，）} {＋，#，）} {（，a，b，^，＋，#，）} {（，a，b，^，＋，#，）} {*，（，a，b，^，#，）} SELECT（E－>TE’）=FIRST(TE’)=FIRST(T)= {（，a，b，^）

SELECT（E’－>+E）={+}

SELECT（E’－>ε）=FOLLOW(E’)= {#，)}

SELECT（T－>FT’）=FIRST（F）= {（，a，b，^} SELECT（T’ —>T）=FIRST（T）= {（，a，b，^） SELECT(T’－>ε)=FOLLOW(T’)= {＋，#，)} SELECT(F －>PF’)=FIRST(F)= {（，a，b，^} SELECT(F’－>*F’)={*}

SELECT(F’－>ε)=FOLLOW(F’)= {（，a，b，^，＋，#，）}

3. S->MH S->a H->Lso H->ξ K->dML K->ξ L->eHf M->K M->bLM FIRST ( S ) =FIRST(MH)= FIRST ( M ) ∪ FIRST ( H ) ∪ {ξ} ∪ {a}= {a, d , b , e ,ξ} FIRST( H ) = FIRST ( L ) ∪ {ξ}= { e , ξ} FIRST( K ) = { d , ξ}

FIRST( M ) = FIRST ( K ) ∪ { b } = { d , b ,ξ}

FOLLOW ( S ) = { # , o }

FOLLOW ( H ) = FOLLOW ( S ) ∪ { f } = { f , # , o } FOLLOW ( K ) = FOLLOW ( M ) = { e , # , o }

FOLLOW ( L ) ={ FIRST ( S ) –{ξ} } ∪{o} ∪ FOLLOW ( K ) ∪ { FIRST ( M ) –{ξ} } ∪ FOLLOW ( M ) = {a, d , b , e , # , o }

FOLLOW ( M ) ={ FIRST ( H ) –{ξ} } ∪ FOLLOW ( S )

∪{ FIRST ( L ) –{ξ} } = { e , # , o }

SELECT ( S-> M H) = ( FIRST ( M H) –{ξ} ) ∪ FOLLOW ( S )

= ( FIRST( M ) ∪ FIRST ( H ) –{ξ} ) ∪ FOLLOW ( S ) = { d , b , e , # , o } SELECT ( S-> a ) = { a }

SELECT ( H->L S o ) = FIRST(L S o) = { e }

10

SELECT ( H ->ξ ) = FOLLOW ( H ) = { f , # , o } SELECT ( K-> d M L ) = { d }

SELECT ( K->ξ ) = FOLLOW ( K ) = { e , # , o } SELECT ( L-> e H f ) = { e }

SELECT ( M->K ) = ( FIRST( K ) –{ξ} ) ∪ FOLLOW ( M ) = {d， e , # , o } SELECT ( M -> b L M )= { b } 构造LL( 1 ) 分析表 S H K L M a -> a b -> M H -> b L M e -> M H ->L S o ->ξ -> e H f ->K d -> M H -> d M L ->K f ->ξ o -> M H ->ξ ->ξ ->K # -> M H ->ξ ->ξ ->K

4 . 文法含有左公因式，变为

S->C $ { b, a } C-> b A { b } C-> a B { a }

A -> b A A { b } A-> a A’ { a }

A’-> ξ { $ , a, b }

A’-> C { a , b } B->a B B { a } B -> b B’ { b }

B’->ξ { $ , a , b }

B’-> C { a, b }

5. <程序> --- S <语句表>――A <语句>――B <无条件语句>――C <条件语句>――D <如果语句>――E <如果子句> --F

S->begin A end S->begin A end { begin } A-> B A-> B A’ { a , if } A-> A ; B A’-> ; B A’ { ; } A’->ξ { end } B-> C B-> C { a } B-> D B-> D { if } C-> a C-> a { a } D-> E D-> E D’ { if } D-> E else B D’-> else B { else }

D’->ξ {; , end }

E-> FC E-> FC { if }

F-> if b then F-> if b then { if } 非终结符是否为空

S－否 A－否 A’－是 B－否 C－否 D－否 D’－是 E－否 F－否

11

FIRST(S) = { begin }

FIRST(A) = FIRST(B) ∪ FIRST(A’) ∪ {ξ} = {a , if , ; , ξ} FIRST(A’) ={ ; , ξ}

FIRST(B) = FIRST(C) ∪ FIRST(D) ={ a , if } FIRST(C) = {a}

FIRST(D) = FIRST（E）= { if } FIRSR(D’) = {else , ξ}

FIRST(E) = FIRST(F) = { if } FIRST(F) = { if }

FOLLOW(S) = {# } FOLLOW(A) = {end} FOLLOW(A’) = { end } FOLLOW(B) = {; , end }

FOLLOW (C) = {; , end , else } FOLLOW(D) = {; , end } FOLLOW( D’ ) = { ; , end } FOLLOW(E) = { else , ; end } FOLLOW(F) = { a }

S A A’ B C D D’ E F if then else begin end a b ; S A A’ B C D D’ E F if -> B A’ -> D -> E D’ ->FC ->if b then then else begin end ->ξ ->ξ a -> B A’ -> C -> a b ; # ->begin A end -> ; B A’ ->ξ -> else B D’ 6. 1.

(1) S -> A | B (2) A -> aA|a (3)B -> bB |b 提取 （2），（3）左公因子 (1) S -> A | B (2) A -> aA’ (3) A’-> A|ξ (4) B -> bB’

12

(5) B’-> B |ξ 2.

(1) S->AB (2) A->Ba|ξ (3) B->Db|D (4) D-> d|ξ

提取（3）左公因子 (1) S->AB (2) A->Ba|ξ (3) B->DB’ (4) B’->b|ξ (5) D-> d|ξ 3.

(1) S->aAaB | bAbB (2) A-> S| db (3) B->bB|a 4

(1) S->i|(E)

(2) E->E+S|E-S|S 提取（2）左公因子 (1) S->i|(E) (2) E->SE’

(3) E’->+SE’|-SE’ |ξ 5

(1) S->SaA | bB (2) A->aB|c (3) B->Bb|d

消除（1）(3)直接左递归 (1) S->bBS’ (2) S’->aAS’|ξ (3) A->aB | c (4) B -> dB’ (5) B’->bB’|ξ 6.

(1) M->MaH | H (2) H->b(M) | (M) |b

消除（1）直接左递归，提取（2）左公因子 (1) M-> HM’

(2) M’-> aHM’ |ξ (3) H->bH’ | ( M ) (4) H’->(M) |ξ

7. (1)

13

1) A->baB 2) A->ξ 3) B->Abb 4) B->a 将1）、2)式代入3）式 1) A->baB 2) A->ξ 3) B->baBbb 4) B->bb 5) B->a 提取3）、4）式左公因子 1) A->baB 2) A->ξ 3) B->bB’

4) B’->aBbb | b 5) B->a (3)

1) S->Aa 2) S->b 3) A->SB 4) B->ab

将3）式代入1）式 1) S->SBa 2) S->b 3) A->SB 4) B->ab

消除1）式直接左递归 1) S->bS’

2) S’->BaS’ |ξ 3) S->b 4) A->SB 5) B->ab

删除多余产生式4） 1) S->bS’

2) S’->BaS’ |ξ 3) S->b 4) B->ab

（5）

1) S->Ab 2) S->Ba 3) A->aA 4) A->a 5) B->a

提取3） 4）左公因子

14

1) S->Ab 2) S->Ba 3) A->aA’ 4) A’-> A |ξ 5) B->a

将3）代入1） 5）代入2 1) S->aA’b 2) S->aa 3) A->aA’ 4) A’-> A |ξ 5) B->a

提取1） 2） 左公因子 1) S-> aS’ 2) S’->A’b | a 3) A->aA’ 4) A’-> A |ξ 5) B->a

删除多余产生式5） 1) S-> aS’ 2) S’->A’b | a 3) A->aA’ 4) A’-> A |ξ A A’ S’ S 将3）代入4） 1) S-> aS’ 2) S’->A’b | a 3) A->aA ’ 4) A’-> aA’ |ξ 将4）代入2） 1) S-> aS’ 2) S’->aA’b 3) S’->a 4) S’->b 5) A->aA ’ 6) A’-> aA’ |ξ

对2）3)提取左公因子 1) S->aS’ 2) S’->aS’’ 3) S’’->A’b|ξ 4) S’->b 5) A->aA ’ 6) A’-> aA’ |ξ 删除多余产生式5） 1) S->aS’ 2) S’->aS’’ 3) S’’->A’b|ξ

15

4) S’->b

5) A’-> aA’ |ξ

第六章

1

S ? a | ∧ | ( T ) T ? T , S | S

解：(1) 增加辅助产生式 S’?＃S＃ 求 FIRSTVT集 FIRSTVT（S’）＝ {#}

FIRSTVT（S）＝ {a ∧ ( }＝ { a ∧ ( }

FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( } 求 LASTVT集 LASTVT（S’）＝ { # } LASTVT（S）＝ { a ∧ )} LASTVT (T) ＝ { , a ∧ )} (2)

算符优先关系表 a ∧ ( ) , # a ·> ·> ·> ∧ ·> ·> ·> ( <· <· <· =· <· ) ·> ·> ·> , <· <· <· ·> ·> # <· <· <· =· 因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法 (3)

a ∧ ( ) , F 1 1 1 1 1 1 g 1 1 1 1 1 1

f 2 2 1 3 2 1

g 2 2 2 1 2 1 f 3 3 1 3 3 1

g 4 4 4 1 2 1 f 3 3 1 3 3 1

g 4 4 4 1 2 1

(4)

栈 优先关系 当前符号 剩余输入串 移进或规约 ＃ <· ( a,a)# 移进

16

#

＃( <· a ,a)# 移进 # (a ·> , a)# 规约 ＃(T <· , a)# 移进 ＃(T， <· a )# 移进 ＃(T,a ·> ) # 规约 ＃(T,T ·> ) # 规约 ＃(T =· ) # 移进 ＃(T) ·> ＃ 规约 ＃T =· ＃ 接受 4. 扩展后的文法

S’?#S# S?S;G S?G G?G(T) G?H H?a H?(S) T?T+S T?S （1）

FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( } FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( } FIRSTCT(H)={a , ( }

FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }

LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )} LASTVT(G) = { )} ∪ LASTVT(H) = { a , )} LASTVT(H) = {a, )}

LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) }

构造算符优先关系表

； ( ) a + # ; ·> <· ·> ·> <· <· ( <· <· ·> ·> <· <· ) ·> ＝· ·> ·> ·> a <· <· <· <· + ·> <· ·> ·> ·> # ·> ·> ·> ＝· 因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法 （2）

句型a(T+S);H;(S)的

短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H 直接短语有: a T+S H (S) 句柄： a

素短语：a T+S (S) 最左素短语：a (3)

分析a；（a＋a）

栈

优先关系 当前符号 剩余输入串 移进或规约 17

＃ ＃a ＃T ＃T； ＃T；（ ＃T；（a ＃T；（T ＃T；（T＋ ＃T；（T＋a ＃T；（T＋T ＃T；（T ＃T；（T） ＃T；T ＃T

分析a；（a＋a） 栈 ＃ ＃（ ＃（a ＃（T ＃（T＋ ＃（T＋a ＃（T＋T ＃（T ＃（T） ＃T <· ·> <· <· <· ·> <· <· ·> ·> ＝· ·> ·> ＝· a ； ； （ a ＋ ＋ a ） ） ） ＃ ＃ ＃ ；（a＋a）＃ （a＋a）＃ （a＋a）＃ a＋a）＃ ＋a）＃ a）＃ a）＃ ）＃ ＃ ＃ ＃ 移进 规约 移进 移进 移进 规约 移进 移进 规约 规约 移进 规约 规约 接受 优先关系 <· <· ·> <· <· ·> ·> ＝· ·> ＝· 当前符号 ( a ＋ ＋ a ） ） ） ＃ ＃ 剩余输入串 a＋a）＃ ＋a）＃ a）＃ a）＃ ）＃ ＃ ＃ ＃ 移进或规约 移进 移进 规约 移进 移进 规约 规约 移进 规约 接受 （4）

不能用最右推导推导出上面的两个句子。

第七章

1、已知文法：

A → aAd|aAb|ξ

判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。 解：(0) A’→ A

(1) A → aAd (2) A → aAb (3) A → ξ

构造该文法的活前缀DFA：

18

I0： A’ →·A a I2： A I3： A →aA·d A →·aAd A →·aAb A →· A I1：A’ →A· A →a·Ad A →a·Ab A →·aAd A →·aAb a A →· Follow(A)∩{a}=∮ d I4： A →aAd· A →aA·b b I5：A →aAb·

由上图可知该文法是SLR（1）文法。 构造SLR（1）的分析表： 状态 a 0 1 2 3 4 5 步骤 1 2 3 4 5 S2 S2 状态栈 0 02 023 0235 01 # #a #aA #aAb #A d R3 R3 S4 R1 R2 符号栈 ACTION b R3 R3 S5 R1 R2 输入串 ab# b# b# # # # R3 acc R3 R1 R2 ACTION S2 R3 S5 R2 acc GOTO A 1 3 GOTO 3 1 输入串ab#的分析过程：

3、考虑文法：

S →AS|b A→SA|a (1) 列出这个文法的所有LR（0）项目 (2) 按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA

的所有状态全体构成这个文法的LR（0）规范族。

(3) 这个文法是SLR的吗？若是，构造出它的SLR分析表。 (4) 这个文法是LALR或LR（1）的吗？ 解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a (1)列出所有LR（0）项目：

S’→·S S→·b A→·a S’→ S· S→b· A→a· S →·AS A→·SA S →A·S A→S·A S →AS· A→SA·

(3)构造该文法的活前缀NFA：

19

b b b b I6： I7： a S →b· A →a· a a a a b I0： S I1： A I3： I5： S’→·S S’→ S· A →SA· S S →AS· S →·AS A →S·A S →A·S A →S·A S →·b A →·SA S →·AS A →·SA A →·SA A →·a S →·b A A →·a A →·a A S →·AS S A →·SA S →·AS S →·b A →·a S →·b A A I2： IS S 4： a S →A·S A →S·A S →·AS A A →·SA S b S →·b A →·a A →·SA S →·AS A →·a S →·b 由上可知：I1 I3 I5 中存在着移进和归约冲突

在I1中含项目：S’→ S· 归约项 Follow(S’)={#}

A →·a 移进项 Follow(S’)∩{a}=∮ S →·b 移进项 Follow(S’)∩{b}=∮

在I3中含项目：A →SA· 归约项 Follow(A)={a,b}

S →·b 移进项 Follow(A) ∩ {b}≠∮ A →·a 移进项 Follow(A) ∩ {a}≠∮

在I5中含项目：S →AS· 归约项 Follow(S)={#,a,b}

A →·a 移进项 Follow(S) ∩ {a}≠∮ S →·b 移进项 Follow(S) ∩ {b}≠∮

由此可知，I3、I5的移进与归约冲突不能解决，所以这个文法不是SLR（1）文法。 （4）做LR（1）项目集规范族

I0： I1： I2：

S’→·S ，# S’→ S· ,# S →A·S ,a/b/#

S →·AS ，a/b/# A →S·A ,a/b S →·AS ,a/b/#

S →·b ,a/b/# A →·SA ,a/b S →·b ,a/b/#

A →·SA ,a/b A →·a ,a/b A →·SA ,a/b A →·a ,a/b S →·AS ,a/b A →·a ,a/b

S →·b ,a/b

20

本文来源：https://www.bwwdw.com/article/5jbg.html