编译原理_课后习题答案_杨明.doc

编译原理习题答案
习题1
1.1翻译程序：把用某种程序设计语言（源语言）编写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。
编译程序：一种翻译程序，将高级语言编写的源程序翻译成等价的机器语言或汇编语言的目标程序。
1.2词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成
1.3词法分析：根据语言的词法规则对构成源程序的符号进行扫描和分解，识别出一个个的单词。
语法分析：根据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析及中间代码生成：对语法分析识别出的语法单位分析其含义，并进 行初步翻译。
代码优化：对中间代码进行加工变换，以产生更高效的目标代码。
目标代码生成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。
以上5个阶段依次执行。

习题2
2.1 （1）有穷非空的符号集合
（2）利用产生是规则A->v将A替换为v时与A的上下文无关。
（3）略
（4）推导是把句型中的非终结符用一个产生是规则的右部开替代的过程；
直接推导是将非终结符的替代结果只用了一次产生式规则。
（5）略
（6）一个句型的最左直接短语
（7）如果一个文法存在某个句子对应两棵不同的语法树或有两个不同的最左（右）推导，则称这个文法是二义的。
2.2（1）VN =｛Z,A,B｝ VT ={a,b,c,d,e}
（2）abbcde,abbbcde是，acde不是。
2.3 （1）L[G]={d|n≥1,m≥0}
（2）
2.4 （1） A=>B=>c=>fAg=>fBg=>fCg=>feg
（2）A=>AaB=>AaC=>Aae=>Bae=>BcCae=>Bceae=>Cceae=>eceae
（3）A=>B=>BcC=>BcfAg=>BcfAaBg=>BcfAaCg=>BcfAaeg=>BcfBaeg
=>BcfCaeg=>Bcfeaeg=>Ccfeaeg=>ecfeaeg
（3）中题目有错应为CfCg|e
2.5 L[G]=｛aⁿbⁿcⁿ|aab,n≥2｝
2.6 (1)Z→AB A→Aa|ε B→Bb|ε
(2)Z→aZb|ab
(3)Z→aAb A→aAb|b
(4)Z→AB A→aAb|ab B→cB|ε
(5)Z→aaAb|ab Z→aaBb|bb A→aaAb|ab B→aaBb|bb

2.7 一位数：Z→2|4|6|8
两位数：Z→AB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8
三位以上：Z→ACB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8 C→CD D→0|1|2|3|4|5|6|7|8|9

2.8证明：E=>E+T=>E+T*F
短语：T*F E+T*F 直接短语：T*F 句柄：T*F
2.9 语法树： E 短语：E*T , (E*T) , F↑(E*T) ，F ,E* F↑(E*T)
E * F 直接短语：E*T , F
T ↑ F 句柄：F
F ( E )
E * T
2.10（1）语法树 （2） 直接短语：a , Z
Z 句柄：Z
( L )
L , Z
Z ( L )
Z
a

2.11最左推导：Z=>ZaB=>BaB=>B+AaB=>A+AaB=>(+)Z*aB=>(+)ZaB*aB
=>(+)+aB*aB=>(+)+aA*aB=>(+)+a(*aB=>(+)+a(*aA
=>(+)+a(*a(
直接短语：（，+
句柄：(

2.12(1) S=>iSeS=>iiSeS=>iiIeS=>iiIeI
S=>iS=>iiSeS=>iiIeS=>iiIeI
(2) S=>SaS=>cSaS=>cfaS=>cfaf
S=>cS=>cSaS=>cfaS=>cfaf
(3) E=>EOE=>EOEOE=>iOEOE=>i+EOE=>i+iOE=>i+i-E=>i+i-i
E=>EOE=>iOE=>i+E=>i+EOE=>i+iOE=>i+i-E=>i+i-i

2.13 Z→aABZ|cCACd
A→bAB|aZA|cCC
B→bAB|Czb
C→cZ|c

习题3
3.1(1)确定的有限自动机
(2)不确定的有限自动机
(3)正规集是一类特殊的单词集合，正规式是正规集的描述工具
3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9)
(2) 11(0|1)*00
3.3 证明：b*(a|b)+=｛a,b,ab,ba,aa,bb…｝
(a|b)+=｛a,b,ab,ba,aa,bb…｝
c
b
a
DSSSss
S0
DSSSss
A
DSSSss
B
DSSSss
C
DSSSss
Z
ε
ε
ε
ε

3.4 (1)

DSSSss
S0
DSSSss
Z
a
DSSSss
A
a
b
b
(2)

b
b
DSSSss
F
b
DSSSss
E
a
b
DSSSss
D
DSSSss
C
DSSSss
B
DSSSss
S0
a
DSSSss
Z
b
DSSSss
A
a
b
a
ε
DSSSss
G
a

(3) (4)
a
DSSSss
B
a
DSSSss
Z
DSSSss
S0
DSSSss
A
b
a
b
b
a
ε
DSSSss
S0

DSSSss
Z
DSSSss
X
0
1
0
DSSSss
U
1
b
a
DSSSss
Y
DSSSss
A
a
DSSSss
Z
b
3.5(1) (2)

(3)

3.6(1) (01|10) *(01|10)
(2) (0(1|00)*)|00

3.7(1) Z→1AB (2)Z→AB
A→(0|1)A A→0A|ε
A→0|1 B→(0|1)B|ε
B→0B
B→ε

3.8 r=a(a|b)*bb

3.9 Z→1B
B→0Z|0
Z→0Z|ε
b
a
DSSSss
3
DSSSss
0
b
a
DSSSss
1
DSSSss
4
b
b
a

a
DSSSss
A
DSSSss
B
a
DSSSss
C
a
DSSSss
D
b
b
3.10 3.11
b

习题4
4.1 (1)若文法G[Z]满足①文法不含左递归②③
(2)

4.2(1) First(S)={a,d} First(B)={a,d,c,ε}
First(A)={a,d,e,c} First(D)={a,d,ε}
Follow(S)={#,a,b,d,e} Follow(B)={a,d}
Follow(A)={b} Follow(D)={e,a,d,b}
(2) 不是

4.3 (1) 证明： First(Z)={a,b,c} Follow(S)={#,a,b,c,d}
First(A)={a,b,c,d} Follow(A)={ #,a,b,c,d }
First(B)={a,d,c} Follow(B)={ a,b,c,d }
是LL(1)文法。
(2)
输入
非终结符
a
b
c
d
#
Z
Z→BA
Z→BA
Z→BA

A
A→BZ
A→BZ
A→BZ
A→d

B
B→aA
B→bZ
B→c

(3)略
4.4 (1) Z→NZ1 Z1→[E]|ε E→ZE1 E1 →*E|ε N→i
(2) First(Z)={i} Follow(Z)={#,*,]}
First(Z1)={[,ε } Follow(Z1)={ #,*,]}
First(E)={i} Follow(E)={ ] }
First(E1 )={*,ε} Follow(E1 )={ ] }
First(N)={i} Follow(N )={#,[,* ] }
(3)

输入
非终结符
[
]
*
i
#
Z

Z→NZ1

Z1
Z1→[E]
Z1→ε

Z1→ε
E

E→ZE1

E1

E1 →ε
E1 →*E

N

N→i

4.5 (1) First(A)={a,ε} Follow(A)={ #,a }
不是LL(1)文法
(2) void A()
{
If(sym==’a’)
{ getsymbol();
A();
If(sym==’a’) getsymbol();
Else error();
}
}

4.6 A→[B
B→X]B’
B’→AB’|ε
X→aX’|bX’
X’→ aX’|bX’|ε

void A() { if(sym==’[’) { getsymbol(); B();}}
void B() { X(); if(sym==’]’) { getsymbol(); B’();}}
void B’(){ if(sym==’[’) { A(); getsymbol(); B’();}}
void X()
{
if(sym==’a’) { getsymbol(); X’();}
else if(sym==’b’) { getsymbol(); X’();}
else error();
}

4.7(1) Z→(L)|aZ|b
L→ZL’
L’→,ZL’|ε
B→dB’
B’→bB’|ε
(2) First(Z)={(,a,b} Follow(Z)={,,),#}
First(L)={ (,a,b } Follow(L)={),}
First(L’)={,,ε} Follow(L’)={ )}
First(B )={d} Follow(B )={# }
First(B’)={b,ε} Follow(B’ )={# }
(3)

4.8(1) Z→aPZ’|*aPZ’
Z’→*aPZ’|ε
P→+aP’
P’→P|ε
(2) First(Z)={a,*} Follow(Z)={ #}
First(Z’)={ *,ε } Follow(Z’)={# }
First(P)={+} Follow(P)={ #,*}
First(P’ )={+,ε} Follow(P’ )={#,* }
(3)
输入
非终结符
a
*
+
#
Z
Z→aPZ’
Z→*aPZ’

Z1

Z’→*aPZ’

Z’→ε
P

P→+aP’

P’

P’→ε
P’→P
P’→ε

习题5
5.1 分析：先求出FirstVT,LastVT集

S
T
FirstVT
a b (
, a b (
LastVT
a b )
, a b )
(1)算符优先关系表如下：

a
b
(
)
,
a

b

(

)

,

(2)因为关系表中无多重定义项，顾是算符优先文法
(3)一种优先函数如下

a
b
(
)
,
f
2
2
0
2
2
g
4
4
4
0
0

5.2
(1)FirstVT,LastVT集如下

S
T
FirstVT
a c d
a c d ,
LastVT
b c d
b c d ,

(2)算符优先关系表

a
b
c
D
,
a

b

c

d

,

(3)是算符优先文法
(4)优先函数

a
b
c
d
,
f
0
3
3
3
2
g
4
0
3
3
1
(5)题目有误
a
A
S
b
b
A
a
b
A
I6:A→SA. ④
S→A.S
S→.AS
S→.b
A→. SA
A→.a
S
I6:S→AS. ②
A→S.A
A→.SA
A→.a
S→.AS
S→.b

A
S
b
b
I3: S→b. ③

a
I0: S’→.S
S→.AS
S→.b
A→.SA
A→.a
A→.
I1: S’→S. acc
A→S.A
A→. SA
A→.a
S→.AS
S→.b
S
S
I5: A→S.A
A→. SA
A→.a
S→.AS
S→.b

I2:A→a. ⑤
I4:S→A.S
S→.AS
S→.b
A→.SA
A→.a

A
S
a
A
b
5.3
(1)文法要拓广
① S’→S
② S→AS
③ S→b
④ A→SA
⑤ A→a

(2) LR(0)分析表
状态
ACTION
GOTO
a
b
#
S
A
0
S2
S3

1
4
1
S2
S3
acc
5
6
2
r5
r5
r5

3
r3
r3
r3

4
S2
S3

7
4
5
S2
S3

5
6
6
S2/r4
S3/r4
r4
7
4
7
S2/r2
S3/r2
r2
5
6
(3)不是LR(0)文法。

5.4
(1)文法要拓广
① S’→S
② S→AS
a
a
a
A
I2: A→AA. ④
S→A.S
A→A.A
S→.AS
S→.b
A→.AA
A→.a
A→. ⑥

S
A
I2: S→A.S
A→A.A
S→.AS
S→.b
A→.AA
A→.a
A→. ⑥
S
I0: S’→.S
S→.AS
S→.b
A→.AA
A→.a
A→. ⑥
S
I1: S’→S. acc

I5: S→AS. ②

A
I4: A→a. ⑤

I3: S→b. ③

b
b
b
③ S→b
④ A→AA
⑤ A→a
⑥ A→ε

(2) SLR(1)分析表
先求Follow(S)={#}
Follow(A)={a,b}

状态
ACTION
GOTO
a
b
#
S
A
0
S4/r6
S3/r6

1
2
1

acc

2
S4/r6
S3/r6

5
6
3

r3

4
r5
r5

5

r2

6
S4/r6/r4
S3/r6/r4

5
6
(3)不是SLR(1)文法。
(4)LR(1)项目集族

a
a
a
A
I2:
[A→AA . b/a] ④
[S→A . S, #]
[A→A . A, b/a]
[S→ . AS , #]
[S→. b , #]
[A→ . AA , b/a]
[A→. a, b/a]
[A→ . ⑥

S
A
I2:
[S→A . S , #]
[A→A . A, b/a]
[S→. AS , #]
[S→. b, #]
[A→. AA , b/a]
[A→. a , b/a]
[A→. , b/a] ⑥
S
I0:
[ S’→. S，#]
[S→. AS，#]
[S→. b，#]
[A→. AA，b/a]
[A→. a, b/a]
[A→. , b/a] ⑥
S
I1: [ S’→S.,#] acc

I5: [S→AS . ,#] ②

A
I4:[A→a. ,b/a] ⑤

I3: [S→b . , #] ③

b
b
b

(5) LR(1)分析表

状态
ACTION
GOTO
a
b
#
S
A
0
S4/r6
S3/r6

1
2
1

acc

2
S4/r6
S3/r6

5
6
3

r3

4
r5
r5

5

r2

6
S4/r6/r4
S3/r6/r4

5
6
(6)不是LR(1)文法。

5.5
(1)拓广文法
① S→A
② A→aAd
③ A→aAb
④ A→ε

I0: S→.A
A→.aAd
A→.aAb
A→. ④

I2: A→a.Ad
A→a.Ab
A→.aAd
A→.aAb
A→. ④

I3: A→aA.d
A→aA.b

I1: S→A . acc

I5: A→aAb. ③

I4:A→aAd. ②
A
A
a
d
b
a

是SLR(1)文法，其SLR(1)表如下：

状态
ACTION
GOTO
a
b
d
#
A
0
S2
r4
r4
r4
1
1

acc

2
S2
r4
r4
r4
3
3

S5
S4

4

r2
r2
r2

5

r3
r3
r3

#ab#分析过程：

2
a
0
#

3
A
2
a
0
#
S2
═>
═>
r4
A→ε归约

S5
═>
S2
═>
═>
r3
A→aAb归约

═>
acc
成功
═

0
#

5
b
3
A
2
a
0
#

3
A
2
a
0
#

2
a
0
#

5.6
LR(0)项目集族：
c
I8:B →aAc.

I9: B→aAb.
A→Ab.

I2: A→b.Ba
B→.aAc
B→.a
B→.aAb
b
B
a
b
a
A
I0: S→.A
A→.Ab
A→.bBa
I1: S→A. acc
A→A.b

A
b
I3: A→Ab.

I4: A→bB.a

I5: A→bBa.

I6: B→a.Ac
B→a.
B→a.Ab
A→.Ab
A→.bBa

I7: B→aA.c
B→aA.b
A→A.b
b

从上述项目集族中，状态集I9是归约-归约冲突。因而不是LR(0)文法。
状态集I6时归约-移进冲突。
但在SLR(1)中，Follow(A)={#,b,c} Follow(B)={a}
因而在SLR(1)中，I9与I6的冲突就消失了，因而是SLR(1)文法。

5.7
(1)文法拓广：
① S’→S
② S→AaAb
③ S→BbBa
④ A→ε
⑤ B→ε
SLR(1)项目集族： Follow(A)={a,b} Follow(B)={a,b}
I0:S’→.S
S→.AaAb
S→.BbBa
A→. ④
B→. ⑤

在I0种有归约-归约冲突。因而不是SLR(1)文法。

I4:
[S→Aa.Ab ,#]
[A→.，b] ④

a
A
B
b
a
b
I1:
[S’→.S，#] acc

I2:
[S→A.aAb ,#]

I3:
[S→B.bBa ,#]

I0:
[S’→.S，#]
[S→.AaAb，#]
[S→.BbBa，#]
[A→.，a] ④
[B→. , b] ⑤

S
A
B
I5:
[S→Bb.Ba ,#]
[B→. , a] ⑤

I6:
[S→AaA.b ,#]
I7:
[S→AaAb. ,#] ②
I8:
[S→BbB.a ,#]
I:
[S→BbBa. ,#] ③
(2)LR(1)项目集族：

从项目集族中可发现，不存在冲突项。因而是LR(1)文法。

习题6

6.1

6.2 改造文法。新文法G’[S]如下:
S→L.R
S→L
L→LB
L→B
R→BR
R→B
B→0
B→1
文法G’[S]的S属性文法如下：
规则
语义规则
S→L.R
S.val=L.val+R.val
S→L
S.val=L.val
L→L1B
L.val= L1.val*2+B.val
L→B
L.val=B.val
R→BR1
R.val=(B.val+ R1.val)*0.5
R→B
R.val=B.val*0.5
B→0
B.val=0
B→1
B.val=1

6.3 题目有误。加上T→num规则。
即文法为 G[E]:E→TR R→+TR/-TR/ε T→num
只用综合属性翻译方案如下：
E→TR
R→+TMR1
R→ -TMR1
R→ ε
M→ ε {print(‘+’)}
N→ ε {print(‘-’)}
T→ num {print(num.lexval)}

6.4
(1)文法改造如下:
G[S’]: S’ → S
S → (L)
S → a
L → L,S
L → S
给S与L配上继承属性S.level L.level
翻译方案如下：（输出每一个a的嵌套深度）
S’→ {S.level=0} S
S → ({L.level=S.level+1}L)
S → a{print(S.level)}
L → {L1.level=L.level}L1,{S.level=L.level}S
L → { S.level=L.level }S

(2) 打印出每个a在句子中是第几个字符的翻译方案。
指派属性如下：
S.pos是继承属性，表示S所代表的字符串的第一个字符的位置
S.len是综合属性，表示S所代表的字符串的长度
L.pos与L.len含义同S
翻译方案如下：
S’ →{S.pos=1}S
S → ({L.pos=S.pos+1}L){S.len=L.len+2}
S → a{print(S.pos)}{S.len=1}
L → {L1.pos=L.pos}L1,{S.pos=L1+L.len+1}S{L.len=L1.len+1+S.len}
L → {S.pos=L.pos}S{L.len=S.len}

6.5
语法分析树方法主要步骤：
(1) 输入串进行语法分析，构造语法分析树
(2) 遍历语法树，确定依赖图
(3) 根据依赖图，确定一种语义计算次序
(4) 属性计算

习题7
7.1
答：进行语法分析时，当发生归约（或推导）时，自动调用该规则所配置的语义规则，自动进行语义的处理。语义处理的时机，调用何种语义规则，由当时所进行的语法分析所决定。
7.2
分析：指派属性E.left表示表达式E是否是左值表达式。若E.left为true，表示是左值。否则是右值表达式。
翻译方案如下：

行号
产生式规则
语义动作
1
E→E1+E2
E.left=false
2
E→(E1)
E.left=E1.left
3
E→E1++
if(E1.left){E.left=false;}
else{
print(“Invalid Value in increment”);
}
4
E→id
E.left=true
5
E→num
E.left=false

7.3
(1)ab-c+*
(2)ab+-cd+*ab+c+-

7.4
(1)
行号
产生式规则
语义动作及含义
1
E→E1?E2:E3
E1.true=newlabel;
E1.false=newlabel;
E1.goto=newlabel;
E.place=newTemp;
E.code=E1.code||gencode(E1.true,’:’)
||E2.code||gencode(E.place,’:=’,E2.place)
||gencode(‘goto’,E1.goto)||gencode(E1.false,’:’)
||E3.code||gencode(E1.place,’:=’,E3.place)
||gencode(E1.goto,’:’)

(2) a:=x>0? x+1:x+2;
翻译如下：（三地址代码）
if x>0 goto L1
goto L2
L1: T1:=x+1
a := T1
goto L3
L2: T2:=x+2
a := T2
L3:

7.5
(1) S→for(i=E1;Mi<E2;Ni++)WS,
M→ε
N→ε
W→ε

(2)
行号
产生式规则
语义动作与含义
1
S→for(i=E1;Mi<E2;Ni++)WS,
M.label=newlabel;
N.label=newlabel;
W.label=newlabel;
S.code=E1.code
||gencode(i,’:=’,E1.place)
||gencode(M.label,’:’)||E2.code
||gencode(‘if’,’i<E2.place’,’goto W.label’)||gencode(‘goto’,S.next)||
Gencode(N.label,’:’)||gencode(‘+’,i,1,i)
||gencode(‘goto’,M.label)||S1.code||
Gencode(‘goto’,N.label)

解释：产生的代码格式如下：
E1.code
i:=E1.place
M.label：
E2.code
if i<E2.place goto W.label
goto S.next
N.label:
i=i+1
goto M.label
W.label:
S1.code
goto N.label
2
M→ε
无
3
N→ε
无
4
W→ε
无

7.6
(1) S→do{MS1} while(E)
(2)
行号
产生式规则
语义动作与含义
1
S→do{MS1} while(E)
M.label=newlabel;
E.true=M.label;
E.false=S.next;
S.code=gencode(M.label,’:’)||S1.code
||E.code
2
M→ε
无

7.7
答：“