编译原理作业20150515(答案).doc

第3章作业【编辑人：陈芳芳】
1. 写一文法，使其语言是偶正整数的集合。要求：
（1）允许0打头；
（2）不允许0打头。
【解】：
(1) 允许0打头且含0的偶正整数集合的文法为：
N—>(0|D|E)N|(E|0)
D—>1|3|5|7|9
E—>2|4|6|8

(2) 不允许0打头的偶正整数集合的文法为：
R—>(D|E)N|E
N—>(0|D|E)N|(E|0)
D—>1|3|5|7|9
E—>2|4|6|8

(3) 允许0打头的偶正整数集合的文法为：
S—>0S|R
R—>(D|E)N|E
N—>(0|D|E)N|(E|0)
D—>1|3|5|7|9
E—>2|4|6|8

2.一个上下文无关文法生成句子abbaa的推导树如下：
S

A B S

a S B B A a

Ɛ b b a
（1）给出该句子的相应的最左推导，最右推导。
（2）该文法的产生式集合P可能有哪些元素？
（3）找出该句子的所有短语，简单短语，句柄。

【解】：
（1）最左推导：
S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa
最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa
(2) 产生式集合P：
S—>ABS | Aa| Ɛ
A—>a
B—>SBB | b
(3) 短语：a , Ɛ , b , bb , aa , abbaa
直接短语：a , Ɛ , b
句柄：a

3、给出生成下述语言的上下文无关文法：
(1){anbnambm | n, m >= 0}
(2){1n0m1m0n | n, m >= 0}
【解】：
（1）S—>AA
A—>aAb | Ɛ
（2）S—>1S0 | A
A—>0A1 | Ɛ

第4章课后作业
1. 构造一个状态数最小的DFA，它接受∑={0,1}上所有倒数第二个字符为1的字符串。（编辑：张超）
解：
① 构造正规式：（0│1）* 1（0│1）
② 由正规式构造NFA：

③ NFA转化为DFA ：
T0=ε－closure（{0}）={0}
用子集构造法求DFA状态，T0为初态，T2，T3为终态
状态
ε－closure（move（Ti，0））
ε－closure（move（Ti，1））
T0={0}
{0}
{0,1}
T1={0,1}
{0,2}
{0,1,2}
T2={0,2}
{0}
{0,1}
T3={0,1,2}
{0,2}
{0,1,2}
用0,1,2,3代表T0，T1，T2，T3，得到如下DFA ：

④最小化DFA ：
P0=（{0,1}，{2,3}）
P1=（{0}，{1}，{2}，{3}）
∴无等价状态。
∵ 没有找到多余状态，∴ 无多余状态。
∴ 上图为最小化的DFA。

2、将下图的NFA确定化为DFA，并最小化。（编辑：张超）

解：用子集构造法求DFA状态，T0为初态，T3为终态。
状态
ε－closure（move（Ti，a））
ε－closure（move（Ti，b））
T0={X，1，2}
{1，2}
{1，2，3}
T1={1，2}
{1，2}
{1，2，3}
T2={1，2，3}
{1，2，Y}
{1，2，3}
T3={1，2，Y}
{1，2}
{1，2，3}
用0,1,2,3代表T0，T1，T2，T3，得到如下DFA ：
最小化：
①{0，1，2} {3}
②{0，1} {2} {3}
③{0，1} {2} {3}
0和1是等价的∴ 得到最小化的DFA 如下 ：

第5-7章课后作业（含答案）

1、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]： S→bSAe|bA A→Abd | dc | a
【解】：
G[S]：S→bS’ S’→SAe|A
A→(dc|a)A’ A’ →bd A’ |ε

2、有文法G[S]：S→ABf A→BbS|e B→dAg|ε
证明文法G是LL(1)文法，并构造预测分析表
【解】：
①计算FIRST、FOLLOW、SELECT集
产生式
FIRST
FOLLOW

SELECT
左部
右部
S
ABf
d b e
# g d f
d b e
A
BbS
d b
g d f
d b
e
e
e
B
dAg
d
b f
d
ε
ε
b f

由上表可知：该文法中，所有相同左部不同右部的产生式SELECT集两两相交均为空集，所以该文法为LL(1)文法。

②构造预测分析表

f
b
e
d
g
#
S

ABf
ABf
ABf

A

BbS
e
BbS

B
ε
ε

dAg

3、已知文法G[S]：S→(A)│a│b A→AcS│S 构造文法的算符优先矩阵，并判断该文法是否是算符优先文法。
【解】：
①拓展该文法：S’→#S# S→(A)│a│b A→AcS│S

②计算FIRSTVT与LASTVT:

FIRSTVT
LASTVT
S’
#
#
S
( a b
) a b
A
c ( a b
c ) a b

③计算算符优先关系：
# = # ( = )
# < FIRSTVT(S) ( < FIRSTVT(A) c< FIRSTVT(A)
LASTVT(S) > # LASTVT(A) > ) LASTVT(A) > c

④构造算符优先矩阵（注：按终结符出现顺序列表）:

(
)
a
b
c
#
(
<
=
<
<
<

)

>

>
>
a

>

>
>
b

>

>
>
c
<
>
<
<
>

#
<

<
<

=

⑤ 因为该文法G为2型文法，且不含空产生式，没有形如 U®…VW…的产生式，其中V,W∈VN，所以 G 为算符文法；又因为G 中任意两个终结符间至多有一种算符优先关系存在(算符优先矩阵无冲突，见上表)，所以G 为算符优先文法。

4、课后习题 P122：4(2)
已知文法：S→ S;G|G G→ G(T)|H H→ a|(S) T→ T+S|S
求句型a(T+S);H;(S) 的短语、直接短语、句柄、素短语与最左素短语。

【解】：
①该句型的对应的语法树如下：

②短语： a T+S H (S) a(T+S) a(T+S);H a(T+S);H;(S)
直接短语： a T+S H (S)
句柄： a
素短语： a T+S (S)
最左素短语：a

5. 给定文法G[A]：A→(A)│a，构造出该文法的LR(1)分析表。

【解】
①对该文法拓广，得其拓广文法G[S’]：
(0) S’→A (1) A→(A) (2) A→a

②计算其LR(1)项目集规范族如下：
I0 = { [S’→.A,#]， [A→.(A),#]， [A→.a,#] }
I1 = GOTO(I0，A) = { [S’→A.,#] }
I2 = GOTO(I0，() = { [A→(.A),#]，[A→.(A),)]，[A→.a,)] }
I3 = GOTO(I0，a) = { [A→a.,#] }
I4 = GOTO(I2，A) = { [A→(A.),#] }
I5 = GOTO(I2，() = { [A→(.A),)]，[A→.(A),)]，[A→.a,)] }
I6 = GOTO(I2，a) = { [A→a.,)] }
I7 = GOTO(I4，)) = { [A→(A).,#] }
I8 = GOTO(I5，A) = { [A→(A.),)] }
GOTO(I5，() = I5 ; GOTO(I5，a) = I6
I9 = GOTO(I8，)) = { [A→(A).,)] }

③构造LR(1)分析表
状
态
Action表
Goto表
（
）
a
#
A
0
S2

S3

1
1

acc

2
S5

S6

4
3

r2

4

S7

5
S5

S6

8
6

r2

7

r1

8

S9

9

r1

6、证明文法 S ® bB B® B*a B ® a
不是LR(0)文法，而是 SLR(1)文法。
【解】
①对该文法拓广，得其拓广文法G[S’]：
(0) S’→S (1) S ® bB (2) B® B*a (3) B ® a

②计算其LR(0)项目集规范族如下：
I0 = closure{ S’→.S } ={ S’→.S , S→. bB }
I1 = GOTO(I0，S) = { S’→S.}
I2 = GOTO(I0，b) = { S→b.B，B® .B*a，B ® .a }
I3 = GOTO(I2，B) = { S→bB.，B® B.*a }
I4 = GOTO(I2，a) = { B ® a. }
I5 = GOTO(I3，*) = { B® B*.a }
I6 = GOTO(I5，a) = { B® B*a. }

③ 因为该文法的LR(0)项目集规范族中有一个项目集I3同时存在移进项目与归约项目，即“移进-归约”冲突，所以不是LR(0)文法。
I3 = { S→bB.，B® B.*a }
而，FOLLOW（S）={ # }
Follow(S) ∩ { * } = φ
即可采用Follow集能解决其冲突，所以该文法是SLR(1)文法。
7. 给出下面赋值语句的逆波兰式： x := a*(b+c)-d/e

【解】 x a b c + * d e / – :=

8. 把下列语句翻译成四元式(四元式的编号从100开始）。
while A∨B∧～C∨D do
if a > b then x := m - k
else y := m + k;

【解】 对应的四元式序列为：
100（Jnz， A， ， 108 ）
101（J ， ， ， 102 ）
102（Jnz， B， ， 104 ）
103（J ， ， ， 106 ）
104（Jnz， C， ， 106 ）
105（J ， ， ， 108 ）
106（Jnz， D， ， 108 ）
107（J ， ， ， 116 ）
108（J>，a ，b ， 110 ）
109（J ， ， ， 113 ）
110（-， m，k ， T1 ）
111（:= ，T1 ， ，x ）
112（J ， ， ， 100）
113（+， m，k ， T2 ）
114（:= ，T2 ， ，y ）
115（J ， ， ，100 ）
116

11