第三章
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
I3: I4: I5:(I1-A->) S →b· ,a/b/# A →a· ,a/b/# A →SA· ,a/b
S →A·S ,a/b I:(I-S->) IS →·AS ,a/b 617:(I2-S->) A →S·A ,a/b S →AS· ,a/b/# S →·b ,a/b A →·SA ,a/b A →S·A ,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 S →·AS ,a/b S →·b ,a/b
由上可知该文法不是LR(1)文法,也不是LALR(1)文法。
5、一个类ALGOL的文法如下:
< Program >→
< Compound Tail >→S; < Compound Tail >
解:设
A→B A→C B→D;E D→begin d D→D;d E→s end E→s;E C→begin E (0)A’ →A (1) A→B (2)A→C (3)B→D;E (4) D→begin d (5) D→D;d (6) E→s end (7) E→s;E (8) C→begin E 构造该文法的活前缀DFA:
21
I7: I6: S E→S·end B→D;·E IIE 1: 10: D→D;·d E→S·;E end A’→ A· B→D; E· A ; E→·S end E→·S;E ; S I112: I0: D IE→S end· 4: d I13: A’→·A B→D·;E E→SA→·B D→D·;d I11: ;·E A→·C D→D; d· E→·Send B→·D;E begin E→·S;E C→·begin E IS 5: E D→·begin d C→begin· E D→·D;d D→begin· d I14: E→·S end E→S;E· B C E→·S;E I2: I3: E d A→B· A→C· I8: I9: C→begin E· D→begin d· 构造LR(0)分析表: 状 ACTION GOTO 态 begin ; d S end # A B C D E 0 S5 1 2 3 4 1 acc 2 R1 R1 R1 R1 R1 R1 3 R2 R2 R2 R2 R2 R2 4 S6 5 S9 S7 8 6 S11 S7 10 7 S13 S12 8 R8 R8 R8 R8 R8 R8 9 R4 R4 R4 R4 R4 R4 10 R3 R3 R3 R3 R3 R3 11 R5 R5 R5 R5 R5 R5
22
12 R6 R6 R6 R6 R6 R6 13 S7 14 14 R7 R7 R7 R7 R7r R7 6、文法G=({U,T,S},{a,b,c,d,e},P,S)其中P为: S→UTa|Tb T→S|Sc|d U→US|e
(1) 判断G是LR(0),SLR(1),LALR(1)还是LR(1),说明理由。 (2) 构造相应的分析表。
解:(0)S’→S (1)S→UTa (2)S→Tb (3)T→S (4) T→Sc (5)T→d
(6)U→US (7)U→e 首先做LR(0)分析:
I0:S’?·S S?·UTa S?·Tb U?·US U?·e T?·S T?·Sc T?·d I1:S’?S· T?S·c
(I1产生移进-规约冲突,但Follow(S’) ∩{c}=∮ 可以用SLR(1)解决)
I2: S?U·Ta U?U·S S?·UTa S?·Tb U?·US U?·e T?·S T?·Sc T?·d I3: S?T.b I4: U?e· I5:T?d· I6:T?Sc·
I7:S?UT·a S?T·b I8:U?US· T?S· T?S·c
产生移进—规约喝规约-规约冲突 Follow(U)={d,e} Follow(T)={a,b} 可以用SLR(1)的方法解决 I9: S?UTa· I10: S?Tb·
所以该文法是SLR(1)文法,也是LALR(1)文法,LR(1)文法。
构造SLR(1)分析表: 状态 ACTION GOTO
23
a b c d e # S U T 0 S12 S11 1 2 3 1 S6 acc 2 S5 S4 8 2 7 3 S10 4 R7 R7 5 R5 R5 6 R4 R4 7 S9 S10 8 R3 R3 S6 R6 R6 9 R1 R1 R1 R1 10 R2 R2 R2 R2 7
证明下面文法不是LR(0)但是SLR(1)。 S→A A→Ab|bBa B→aAc|a|aAb
证明:(0)S’→ S (1)S→A (2)A→Ab (3)A→bBa (4)B→aAc (5) B→a (6)B→aAb 构造该文法的活前缀DFA:
24
I1: S’→ S· S I0: S’→·S S→·A A→·Ab A→·bBa A I2: S→A· A→A·b I3: A→b·Ba B→·aAc B→·a B→·aAb b I7: A→Ab· B I5: A→bB·a a I8: A→bBa· b a b I4: B→a·Ac B→a· B→a·Ab A→·Ab A→·bBa A I6: B→aA·c B→aA·b A→A·b b I9: B→aAb· A→Ab· c I10: B→aAc·
在I2项目集中含有:S→A· 归约项 Follow(S)={#}
A→A·b 移进项 Follow(S)∩{b}=∮
在I4项目集中含有:B→a· 归约项 Follow(B)={a}
A→·bBa 移进项 Follow(B)∩{b}=∮
在I9项目集中有 B?aAb· 规约项 Follow(B)={a}
A?Ab· 规约项 Follow(A)={b,c,#} Follow(B) ∩ Follow(A)= ∮
文法的冲突项可以用SLR(1)文法来解决,所以该文法是SLR(1)文法,不是LR(0)文法。
11、设文法G[S]为:
S→AS|ξ A→aA|b
(1) 证明G[S]是LR(1)文法; (2) 构造它的LR(1)分析表;
(3) 给出输入符号串abab#的分析过程。 解:
(0)S’→S (1)S→AS (2) S→ξ (3)A→aA (4)A→b 证明:
构造该文法的活前缀DFA:
S
25
I0: S’→·S ,# S→·AS ,# S→· ,# A→·aA ,a/b/# A→·b , a/b/# I1: S’→ S· ,# a a A I2: S→A·S ,# S→·AS ,# S→· ,# A A→·aA ,a/b/# A→·b , a/b/# I3: A→a· A ,a/b/# A→·aA ,a/b/# A→·b , a/b/# a A I6: A→a A· ,a/b/# b I4: A→b · , a/b/# b S I5: S→AS· ,# b
在该文法I0 ,I2 中出现了归约——移进冲突,由于归约项目的搜索符集合与移进项目的待移进符号不相交,所以在I0 ,I2中当面临输入符为#时归约,为a或b 时移进。 所以该文法是LR(1)文法。
构造它的LR(1)分析表: 状态 a 0 1 2 3 4 5 6 步骤 1 2 3 4 5 6 7 8 9 10 11
ACTION b S4 S4 S4 R4 R3 符号栈 # #a #ab #aA #A #Aa #Aab #AaA #AA #AAS #AS R2 acc R2 R4 R1 R3 输入串 abab# bab# ab# ab# ab# b# # # # # # # 1 5 ACTION S3 S4 R4 R3 S3 S4 R4 R3 R2 R1 R1 S S3 S3 S3 R4 R3 状态栈 0 03 034 036 02 023 0234 0236 022 0225 025 GOTO A 2 2 6 GOTO 6 2 6 2 5 5 1 26
构造输入符号串abab#的分析过程:
12 01 #S # acc
16、给定文法:
S→do S or S|do S|S;S|act (1) 构造识别该文法活前缀的DFA。 (2) 该文法是LR(0)吗?是SLR(1)吗?说明理由。 (3) 若对一些终结符的优先级以及算符的结合规则规定如下: a) or优先性大于do; b) ;服从左结合; c) ;优先性大于do; d) ;优先性大于or;
请构造该文法的LR分析表。
解:(0)S’→S (1)S→do S or S (2)S→do S (3)S→S;S (4)S→act 构造该文法的活前缀DFA:
; I3: I1: S→S; ·S S I5: S S’→ S· S→·do S or S S→S; S· I0: S→S·;S S→·do S S→S·;S S’→·S S→·S;S ; S→·do S or S I2: do S→·act S→·do S do S→do· S or S S→·S;S S→do· S ; S→·act S→·do S or S S I4: I6: S→·do S S→do S ·or S S→do S or act act S→·S;S do S→do S· or ·S S→·do S or S S→·act S→S·;S S→·do S I8: act SS→act· act do →·S;S S→·act S I7: S→do S or S· S→S·;S 由上可知:在I1中含有项目:S’→ S· 归约项目 Follow(S’)={#}
S→S·;S 移进项目 Follow(S’)∩{;}=∮
在I4中含有项目:S→do S· 归约项目 Follow(s)={#,or,;}
S→do S ·or S 移进项目 Follow(s)∩{or}≠∮ S→S·;S 移进项目 Follow(s)∩{;}≠∮
在I5中含有项目:S→S; S· 归约项目 Follow(s)={#,or,;}
S→S·;S 移进项目 Follow(s)∩{;}≠∮
在I7中含有项目:S→do S or S· 归约项目Follow(s)={#,or,;}
S→S·;S 移进项目Follow(s)∩{;}≠∮
所以该文法不是LR(0),也不是SLR(1)文法。 根据算符优先关系构造该文法的LR分析表:
27
状态 ACTION GOTO Do or ; act # S 0 S2 S8 1 1 S3 acc 2 S2 S8 4 3 S2 S8 5 4 S6 S3 R2 5 R3 R3 R3 6 S2 S8 7 7 R1 S3 R1
18、对算术表达式文法G[E];
E→E+T|T T→T*F|F F→(E)|i
(1) 构造算符优先关系表和LR分析表,并对G[E]进行适合的改写后构造预测分析表。 (2) 分别使用三种表对句子i+i*i#进行分析。
(3) 对于错误的输入串:(i+(*i)#和*+i)+(i*#分别查看错误的发现时刻和输入串出错的位置。解:(1) 构造算符优先关系表,文法扩展后为
E’→#E# E→E+T E→T T→T*F T→F F→(E) F→i FirstVT(E’)={#} LastVT(E’)={#}
FirstVT(E)={+,*, (,i} LastVT(E)={ +,*, ),i } FirstVT(T)={ *, (,i } LastVT(T)={ *, ),i } FirstVT(F)={ (,i } LastVT(F)={ ),i } 构造算符优先关系表: + * ( ) i # + ·> <· <· ·> <· ·> * ·> ·> <· ·> <· ·> ( <· <· <· =· <· ) ·> ·> ·> ·> i ·> ·> ·> ·> # <· <· <· <· =·
做LR(0)分析,扩展后的文法为:
(0)E’?E (1)E?E+T (2)E?T (3) T?T*F (4)T?F (5)F?(E) (6)F?i I0:E’?·E E?·E+T E?·T T?·T*F T?·F F?·(E) F?·i I1: E’?E· E?E·+T
(I1产生移进-规约冲突,但Follow(E’) ∩{+}=∮ 可以用SLR(1)解决) I2:E?T· T?T·*F
(I2产生移进-规约冲突,但Follow(E) ∩{*}=∮ 可以用SLR(1)解决) I3: T?F·
I4: F?(·E) E?·E+T E?·T T?·T*F T?·F F?·(E) F?·i I5: F?i·
I6: E?E+·T T?·T*F T?·F F?·(E) F?·i I7: T?T*·F F?·(E) F?·i
28
I8: F?(E·) E?E·+T I9: E?E+T· T?T·*F
(I2产生移进-规约冲突,但Follow(E) ∩{*}=∮ 可以用SLR(1)解决) I10: T?T*F· I11: F?(E) ·
构造SLR(1)分析表 状态 ACTION GOTO + * ( ) i # E T F 0 S4 S5 1 2 3 1 S6 acc 2 R2 S7 R2 R2 3 R4 R4 4 S4 S5 8 2 3 5 R6 R6 R6 R6 6 S4 S5 9 3 7 S4 S5 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5
做LL(1)分析:
消除左递归,文法为: E?TE’ E’?+TE’ E’?ε T?FT’ T’?*FT’ T’?ε F?(E) F?i
求select集
select (E?TE’)=first(TE’)=first(T)=first(FT’)=first(F)={(,i) select(E’?+TE’)={+}
SELECT(E’?ε)=Follow(E’)=Follow(E)={#,)} SELECT(T?FT’)= first(F)={(,i} Select(T’?*FT’)={*}
Select(T’?ε)=follow(T’)={+,),#} Select(F?(E))={(} Select(F?i)={i}
29
构造预测分析表 + * ( ) i # E ?TE’ ?TE’ E’ ?+TE’ ?ε ?ε T ?FT’ ?FT’ T’ ?ε ?*FT’ ?ε ?ε F ?(E) ?i
第八章
while a
100:if a
102: if c 104: if e 106: if x if A>B then while A>C do A:=A-B else if D and F then A:=A+100 100: if A>B goto 102 101 goto 107 102 if A>C goto 104 103 goto 114 104 t1:=A-B 105 A:=t1 106 goto 102 107 goto 114 108 if D goto 110 109 goto 114 110 if F 112 111 goto 114 112 t2:=A+100 30 113 A:=t2 114 补充习题 1.对下列各语言写出它们的正规表达式和有限自动机 (a) 字母表{a,b,c}上的串,其中第一个a先于第一个b 解:我们关心的状态是什么时候出现了第一个a,可以设出现第一个a后的状态为1,出现第一个a之前的状态为0。必须保证在状态1之前不能出现b: c a,b,c ? 0 a 1 转换为正规式:c*a(a|b|c)* (b) 其中有偶数个a的字母表{a,b,c}上的串 解:我们关心的状态是a的个数的奇偶性,可以设定偶数个a时的状态是0,奇数个a的状态是1,我们要偶数个a,因此0状态是终结状态: b|c a b|c ? 0 1 a 转换为正规表达式: (b|c)*(a(b|c)*a)* (c) {0,1}上的串,该串看成二进制是4的倍数 解:A=(0|1)*00 (d) {0,1}上不含子串011的串 解:我们关心的状态是出现01时,这时只要保证01后不能是1即可: 1 0 0 0 0 1 1 2 1*0(0|10)* (e) {0,1}上的串有偶数个0和奇数个1 解:我们关心的状态是0和1的奇偶性,组合情况有4个: 0:偶数个0,偶数个1 1:偶数个0,奇数个1 ――终结状态 2: 奇数个0,偶数个1 3:奇数个0,奇数个1 1 ? 0 1 1 0 0 0 0 2 1 3 1 正规表达式: (0(11)*0)*( 1 | 0(11)*10 )( 00 | 01(11)*10 | ( 1 | 01( 11 )* 0) (0 (11)* 0)* ( 1 | 0 (11)* 10) )* 31 2.试从文法G[s] S?(L)|a L?L,S | S 中消除左递归,并为之构造一个递归预测分析器和LL(1)分析表. 请说明句子(a,(a,a))在LL(1)分析器中的动作. 解: 改写为 S?(L) | a L?SL’ L’?ε| ,SL’ 非终结符 是否*?ε FIRST集 FOLLOW集 S 否 {( , a} {# , } L 否 {( , a) { )} L’ 是 { , ε} {) } SELECT(S?(L))={( } SELECT(S?a)={a} SELECT(L?SL’)={(,a} SELECT(L’?ε)={ )} SELECT(L’?,SL’)={,} 预测分析表: ( a , ) S ?(L) ?a L ?SL’ ?SL’ L’ ?,SL’ ?ε 对符号串(a,(a,a))#的分析过程 步骤 分析栈 剩余输入串 所用产生式 1 #S (a,(a,a))# S?(L) 2 #)L( (a,(a,a))# ( 匹配 3 #)L a,(a,a))# L?SL’ 4 #)L’S a,(a,a))# S?a 5 #)L’a a,(a,a))# a 匹配 6 #)L’ ,(a,a))# L’?,SL’ 7 #)L’S , ,(a,a))# ,匹配 8 #)L’S (a,a))# S?(L) 9 #)L’)L( (a,a))# ( 匹配 10 #)L’)L a,a))# L?SL’ 11 #)L’)L’S a,a))# S?a 12 #)L’)L’a a,a))# a匹配 13 #)L’)L’ ,a))# L’?,SL’ 14 #)L’)L’S, ,a))# , 匹配 15 #)L’)L’S a))# S?a 16 #)L’)L’a a))# a匹配 32 17 #)L’)L’ ))# L’?ε 18 #)L’) ))# )匹配 19 #)L’ )# L’?ε 20 #) )# )匹配 21 # # 接受 步骤 分析栈 剩余输入串 所用产生式 1 #S (a,(a,a))# S?(L) 2 #)L( (a,(a,a))# ( 匹配 3 #)L a,(a,a))# L?SL’ 4 #)L’S a,(a,a))# S?a 5 #)L,a a,(a,a))# a , 匹配 6 #)L (a,a))# L?SL’ 7 #)L’S (a,a))# S?(L) 8 #)L’)L( (a,a))# ( 匹配 9 #)L’)L a,a))# L?SL’ 10 #)L’)L’S a,a))# S?a 11 #)L’)L’a a,a))# a匹配 12 #)L’)L’ ,a))# L’?,SL’ 13 #)L’)L’S, ,a))# , 匹配 14 #)L’)L’S a))# S?a 15 #)L’)L’a a))# a匹配 16 #)L’)L’ ))# L’?ε 17 #)L’) ))# )匹配 18 #)L’ )# L’?ε 19 #) )# )匹配 20 # # 接受 3. 对于文法G[bexpr] bexpr?bexpr or bterm | bterm bterm?bterm and bfactor | bfactor bfactor?not bfactor | (bfactor) | true | false 构造一个预测分析器 解: bexpr:S bterm: A bfactor: B 原文法变为: S?S or A | A A?A and B | B B?not B | (B) | true | false 改写为: S?AS’ 33 S’?ε| or AS’ A?BA’ A’?ε| and BA’ B?not B | (B) | true | false 非终结符 是否*?ε FIRST集 FOLLOW集 S 否 { not , ( , true , {#} false } S’ 是 { or ε} {#} A 否 { not , ( , true , {# , or} false } A’ 是 { and ε} {# , or} B 否 {not , ( , true , {# , ) , and} false} SELECT(S?AS’)={ not , ( , true , false } SELECT(S’?ε)={#} SELECT(S’?or AS’)={or} SELECT(A?BA’)={ not , ( , true , false } SELECT(A’?ε)={ # , or } SELECT(A’? and BA’)={and} SELECT(B?not B)={not} SELECT(B?(B))={(} SELECT(B?true)={true} SELECT(B?false)={false} 预测分析表: Not ( true false # or and S ?AS’ ?AS’ ?AS’ ?AS’ S’ ?ε ?or AS’ A ?BA’ ?BA’ ?BA’ ?BA’ A’ ?ε ?ε B ?not B ?(B) ?true ?false ? and BA’ 4. (1)计算下面文法G[s]的FIRST和FOLLOW集 S?uBDz B?Bv | w D?EF E?y |ε F?x |ε (2)构造这个文法的LL(1)分析表 (3)给出这个文法不是LL(1)的证据 (4)尽可能少的修改这个文法,使之成为能产生与原文法相同语言的LL(1)文法 解:(1) 34 非终结符 是否*?ε FIRST集 FOLLOW集 S 否 {u} {#} B 否 {w} {v, x, y, z} D 是 { x ,y, ε} {z} E 是 { y, ε} {z , x} F 是 { x, ε} {z} (2)这个文法的LL(1)分析表 SELECT(S?uBDz)={u} SELECT(B?By)={w} SELECT(B?w)={w} SELECT(D?EF)={x , y , z} SELECT(E?y)={y} SELECT(E?ε)={z , x} SELECT(F?x)={x} SELECT(F?ε)={z} u w x y z S ?uBDz B ?By ?w D ?EF ?EF ?EF E ?ε ?y ?ε F ?ε (3)给出这个文法不是LL(1)的证据 由以上计算结果可得相同左部产生的SELECT交集为不为空,该文法不是LL(1)文法 (4)修改为 S?uBDz B?wB’ B’?ε| vB’ D?EF E?y |ε F?x |ε Select(B’?ε) ={ x, y, z} Select(B’?vB’) = {v} 所以Select(B’?ε) ∩ Select(B’?vB’) =Φ 又:select(E ? y) ∩ select(E ?ε)= { y } ∩ { x, z} = Φ select(F ? x) ∩ select(F ?ε)= { x } ∩ { z} = Φ 应此是LL(1)文法 将下列文法提取左公因子并消除左递归 (1) S?aA|aD|B (2) B?Bb|e|C 35 (3) C?S 解:提取(1)式左公因子,消除(2)式直接左递归,文法为 (1) S?aS’|B (2) S’?A|D (3) B?eB’|CB’ (4) B’?bB’|ε (5) C?S 将(1)式代入(5)式 (1) S?aS’|B (2) S’?A|D (3) B?eB’|CB’ (4) B’?bB’|ε (5) C?aS’|B 将(5)式代入(3)式 (1) S?aS’|B (2) S’?A|D (3) B?eB’|aS’B’|BB’ (4) B’?bB’|ε (5) C?aS’|B 消除(3)式直接左递归 (1) S?aS’|B (2) S’?A|D (3) B?eB’B’’|aS’B’B’’ (4) B’’?B’B’’|ε (5) B’?bB’|ε (6) C?aS’|B 消除多余产生式(6) (1) S?aS’|B (2) S’?A|D (3) B?eB’B’’|aS’B’B’’ (4) B’’?B’B’’|ε (5) B’?bB’|ε (6) 36