编译原理(清华大学-第2版)课后习题答案.doc

第三章
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题

第9题
语法树

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

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

短语：<T><F><MOP> <E><T><F><MOP><POP>
直接短语：<T><F><MOP>
句柄： <T><F><MOP>
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

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

(3)NFA

(4)NFA

2、解：构造DFA矩阵表示

0
1
{X}0
{Z}
{X}
{Z }*
{X,Z}
{Y}
{X,Z} *
{X,Z}
{X,Y}
{Y}
{X,Y}

{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状态图为：

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）解
构造状态转换矩阵：

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} 此时
G=( {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如下

确定化，构造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状态转换图如下；

8．代入得
S = 0(1S|1)| 1(0S|0)
= 01(S|ε) | 10(S|ε)
= (01|10)(S|ε)
= (01|10)S | (01|10)
= (01|10)*(01|10)
构造NFA

由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为

正规式:b*a(da|c)*bb*
第五章
1、
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 ) = { ） }
构造预测分析表

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

T
-> S T’
-> S T’
-> S T’

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’ ->ξ
# ) ) # )匹配
# # 接受
2、
E->TE’ E’->+E E’->ξ T->FT’ T’->T T’->ξ F->PF’ F’->*F’ F’->ξ
P->(E) P->a P->b P->∧
非终结符名
就是否＝>ε
FIRST集
FOLLOW集
E
否
{（，a，b，^}
{#，）}
E’
就是
{+,ε}
{#，）}
T
否
{（，a，b，^}
{＋，#，）}
T’
就是
{ε, （，a，b，^}
{＋，#，）}
F
否
{（，a，b，^}
{（，a，b，^，＋，#，）}
F’
就是
{*,ε}
{（，a，b，^，＋，#，）}
P
否
{（，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 }
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 ) 分析表

a
b
e
d
f
o
#

S
-> a
-> M H
-> M H
-> M H

-> M H
-> M H

H

->L S o

->ξ
->ξ
->ξ

K

->ξ
-> d M L

->ξ
->ξ

L

-> e H f

M

-> b L M
->K
->K

->K
->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－否
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 ;

if
then
else
begin
end
a
b
;
#
S

->begin A end

A
-> B A’

-> B A’

A’

->ξ

-> ; B A’

B
-> D

-> C

C

-> a

D
-> E D’

D’

-> else B D’

->ξ

->ξ

E
->FC

F
->if b then

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’
(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)
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）左公因子
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|ξ
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)# 移进
＃( <· 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）
栈
优先关系
当前符号
剩余输入串
移进或规约
＃
＃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＋a）＃
（a＋a）＃
（a＋a）＃
a＋a）＃
＋a）＃
a）＃
a）＃
）＃
＃
＃
＃
移进
规约
移进
移进
移进
规约
移进
移进
规约
规约
移进
规约
规约
接受
分析a；（a＋a）
栈
优先关系
当前符号
剩余输入串
移进或规约
＃
＃（
＃（a
＃（T
＃（T＋
＃（T＋a
＃（T＋T
＃（T
＃（T）
＃T
<·
<·
·>
<·
<·
·>
·>
＝·
·>
＝·
(
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：
a
I0：
A’ →·A
A →·aAd
A →·aAb
A →·

由上图可知该文法就是SLR（1）文法。
构造SLR（1）得分析表：
状态
ACTION
GOTO
a
d
b
#
A
0
S2
R3
R3
R3
1
1

acc

2
S2
R3
R3
R3
3
3

S4
S5

4

R1
R1
R1

5

R2
R2
R2

输入串ab#得分析过程：
步骤
状态栈
符号栈
输入串
ACTION
GOTO
1
0
#
ab#
S2

2
02
#a
b#
R3
3
3
023
#aA
b#
S5

4
0235
#aAb
#
R2
1
5
01
#A
#
acc

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：
I0：
S’→·S
S →·AS
S →·b
A →·SA
A →·a
I1：
S’→ S·
A →S·A
A →·SA
A