编译原理作业参考答案

作业参考答案

第二章 高级语言及其语法描述

+

6、（1）L（G6）={0,1,2,......,9}（2）最左推导：

N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34

N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：

N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34

N=>ND=>N8=>ND8=>N68=>D68=>568 7、Ｇ：S→ABC | AC | C

A→1|2|3|4|5|6|7|8|9

B→BB|0|1|2|3|4|5|6|7|8|9 C→1|3|5|7|9

8、（1）最左推导：

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i) 最右推导：

E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i

E=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i) (2)

i

i i i

i

9、证明：该文法存在一个句子iiiei有两棵不同语法分析树，如下所示，因此该文法是二义的。

i

11、 G1: G2: G3: G4:

S→AB S→AB S→AA S→1S0|A A→aAb|ab A→aA|ε A→aAb|ε A→0A1|ε

B→cB|ε B→bBc|bc

第3章 词法分析

7、构造下列正规式相应的DFA：1(0|1)*

101 解：

（1）构造NFA：

（2）确定化：

重命名：

（注：已是最简）

8、（1）（0|1）*

01

（2）（0|1|2|3|4|5|6|7|8|9）(1|2|3|4|5|6|7|8|9)*

(0|5)|0|5

（3）（10*1|0）*10*|（01*0|1）*01

*

（4）a*b*c*......z*

9、（1）

正规式（0|1）*（010）（0|1）*

NFA:

构造状态转换矩阵： 重命名：

画出DFA：

最少化后：

1

重命名：

重命名：

画出确定化后的有限自动机：

（b）最少化：首先分为终态集和非终态集： {0，1}{2，3，4，5} {0，1}a={1} {0，1}b={2，4}

{2，3，4，5}a={1，3，0，5} 可分为{2，4}和{3，5} {2，4}b={3，5} {3，5}b={2，4}

形成划分：{0，1}{2，4}{3，5} 最少化后的DFA：

b

14、每个1都有0直接跟在右边： （10|0）*

15、画出NFA：

等价的左线性正规文法： F→A1|B0|C0|C1 S→0|1|S0|S1 A→1|S1 B→0|S0

C→A1|B0|C0|C1

第4章 语法分析——自上而下分析 1、S→a|^|(T) T→T,S|S (1)消除左递归

S→a|^|(T) T→ST’

T’ →,ST’|ε 递归下降子程序：

void S() {

if (sym==’a’) advanced();

else if (sym==’^’) advanced(); else if (sym==’(‘) {advanced();

T();

if (sym==’)’) advanced(); else error(); }

else error(); }

void T() {

S(); T’(); }

void T’() {

if (sym==’,’)

{advanced(); S(); T’();}

else if (sym in follow(T’)) else error(); }

该文法是LL(1)的： 方法一（利用概念）：

a. 不含左递归；

b. 候选终结首符集没有交集；

c. ε∈first(T’),follow(T’)∩first(T’)={} 方法二（指出预测分析表没有多重入口） 2、文法：

E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’

F’→*F’|ε P→(E)|a|b|^

(2)略

4、文法：

Expr→-Expr|(Expr)|Var ExprTail ExprTail→-Expr|ε Var→id VarTail VarTail→(Expr)|ε (1)构造LL(1)分析表：

第5章 语法分析——自下而上分析 1、文法：

E→E+T|T T→T*F|F F→(E)|i

证明E+T*F是它的一个句型，并指出该句型所有短语、直接短语和句柄。 解：E+T*F是它的一个句型，因为存在下面语法树： E E + T * F

短语：T*F, E+T*F 直接短语：T*F 句柄：T*F 2、文法： S→a|^|(T) T→T,S|S

(1)给出(a,(a,a))和(((a,a),^,(a)),a)的最左和最右推导；

(2)指出(((a,a),^,(a)),a)的规范归约以及每一步的句柄，根据这个规范归约，给出“移进-归约”过程，并给出它的语法树自下而上构造过程。 解： (1)略

(2)①规范句型及每一步的句柄（用下划线标示）：

②“移进-规约”过程：

步骤 分析栈 输入串 动作 （1） # (((a,a),^,(a)),a)# 预备 （2） #( ((a,a),^,(a)),a)# 移进 （3） #(( (a,a),^,(a)),a)# 移进 （4） #((( a,a),^,(a)),a)# 移进 （5） #(((a ,a),^,(a)),a)# 移进 （6） #(((S ,a),^,(a)),a)# 归约 （7） #(((T ,a),^,(a)),a)# 归约

（8） #(((T, a),^,(a)),a)# 移进 （9） #(((T,a ),^,(a)),a)# 移进 （10） #(((T,S ),^,(a)),a)# 归约 （11） #(((T ),^,(a)),a)# 归约 （12） #(((T) ,^,(a)),a)# 移进 （13） #((S ,^,(a)),a)# 归约 （14） #((T ,^,(a)),a)# 归约 （15） #((T, ^,(a)),a)# 移进 （16） #((T,^ ,(a)),a)# 移进 （17） #((T,S （18） #((T （19） #((T, （20） #((T,( （21） #((T,(a （22） #((T,(S （23） #((T,(T （24） #((T,(T) （25） #((T,S （26） #((T （27） #((T) （28） #(S （29） #(T （30） #(T, （31） #(T,a （32） #(T,S （33） #(T （34） #(T) （35） #S （36） #S ③语法树的自下而上的构造过程：

,(a)),a)# 归约 ,(a)),a)# 归约 (a)),a)# 移进 a)),a)# 移进 )),a)# 移进 )),a)# 归约 )),a)# 归约 ),a)# 移进 ),a)# 归约 ),a)# 归约 ,a)# 移进 ,a)# 归约 ,a)# 归约 a)# 移进 )# 移进 )# 归约 )# 归约 # 移进 # 归约 # 接受

3、（1）计算练习2文法G2的FIRSTVT和LASTVT； （2）计算G2的优先关系，G2是一个算符优先文法吗？ （3）给出输入串(a,(a,a))的算符优先分析过程。 解：

因为：1）该文法不含ε产生式； 2）该文法是算符文法；

3）由优先关系表可以看出，任何终结符之间的优先关系之多满足一种优先关系； 所以该文法是算符优先文法。 （3）

步骤 分析栈 输入串 动作 原因 0 # (a,(a,a))# 预备

1 #( a,(a,a))# 移进 #, 5 #(S,( a,a))# 移进 ,) 12 #(S,(T) )# 移进 (=) 13 #(S,S )# 归约 )>) 14 #(T )# 归约 ,>) 15 #(T) # 移进 (=) 16 #S # 归约 )># 17 #S# 分析成功 5、考虑文法：

S→AS|b A→SA|a

（1）列出这个文法所有的LR(0)项目；

（2）构造这个文法的LR(0)项目集规范族以及识别活前缀的DFA； （3）这个文法是SLR的吗？若是，构造分析表； （4）这个文法是LALR或LR(1)的吗？ 解：拓广文法如下：

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

（1）所有LR(0)项目如下：

1）S’→.S 2）S’→S. 3）S→.AS 4）S→A.S 5）S→AS. 6）S→.b

7）S→b. 8）A→.SA 9） A→S.A 10）A→SA. 11）A→.a 12）A→a. （2）该文法的LR(0)项目集规范族如下：

I0: S’→.S I2: S→A.S I6: A→S.A

S→.AS S→.AS A→.SA

S→.b S→.b A→.a

A→.SA A→.SA S→.AS

A→.a A→.a S→.b

I1: S’→S. I3: S→b. I7: S→AS.

A→S.A I4: A→a. A→S.A

A→.SA I5: A→SA. A→.SA

A→.a S→A.S A→.a

S→.AS S→.AS S→.AS

S→.b S→.b S→.b

A→.SA

A→.a

DFA略。

（3）FOLLOW(S)={#,a,b} FOLLOW(A)={a,b}

在LR(0)项目集规范族中，同时存在“移进-归约”和“归约-归约”项目的项目集有I1，I5和I7；其中I1中“归约”项目是“接受”项目，面临#时接受，移进项目要求面临a和b时移进，不存在冲突；I5中归约项目面临FOLLOW(A)中元素a,b时归约，“移进”项目面临a,b时移进，存在冲突；同理，I7也存在冲突。所以该文法不是SLR的。 （或者：构造出SLR分析表，指出存在多重入口） （4）构造LR(1)项目集规范族：

I2: S→A.S, #/a/b I6: A→S.A , a/b

I0: S’→.S ，# S→.AS, #/a/b A→.SA, a/b S→.AS，#/a/b S→.b, #/a/b A→.a, a/b S→.b，#/a/b A→.SA, a/b S→.AS, a/b A→.SA，a/b A→.a, a/b S→.b, a/b A→.a，a/b I3: S→b. , #/a/b I7: S→b. , a/b I1: S’→S. ,# I4: A→a. , a/b I8: S→AS. , #/a/b A→S.A, a/b I5: A→SA. , a/b A→S.A, a/b A→.SA, a/b S→A.S, a/b A→.SA, a/b A→.a, a/b S→.AS, a/b A→.a, a/b S→.AS, a/b S→.b, a/b S→.AS, a/b S→.b, a/b A→.SA, a/b

S→.b, a/b

A→.a, a/b

I9: S→AS. , a/b I10: S→A.S, a/b A→S.A, a/b S→.AS, a/b A→.SA, a/b S→.b, a/b A→.a, a/b A→.SA, a/b S→.AS, a/b A→.a, a/b S→.b, a/b 因为：

I5,I8,I9中存在“移进-归约”冲突，所以该文法不是LR(1)的，更不是LALR的。 （!此题另解：该文法是二义文法，故不是任何LR文法。）

本章补充作业：

1、文法G[S]，构造LR(1)分析表：

S→aAd|bAc|aec|bed A→e 解：（1）拓广文法如下：

0）S’→S 1）S→aAd 2）S→bAc 3）S→aec 4）S→bed 5）A→e

(2)LR(1)项目集规范族构造如下：

I0: S ’→.S, # I2: S→a.Ad, # I5: S→ae.c, # S→.aAd, # S→a.ec, # A→e., d S→.bAc, # A→.e, d I6: S→bA.c, # S→.aec, # I3: S→b.Ac, # I7: S→be.d, # S→.bed, # S→b.ed, # A→e., c I1: S ’→ S., # A→.e, c I8: S→aAd., # I4: S→aA.d, # I9: S→aec., # I10: S→bAc., # I11: S→bed., # （3）LR(1)分析表如下：

2、文法G[S]：S→AB

A→aBa|ε B→bAb|ε

（1）该文法是SLR的吗？

（2）若是，请构造它的分析表； （3）给出输入串baab#的分析过程。 解：对文法拓广：

(0)S’→S (1)S→AB (2)A→aBa (3)A→ε (4)B→bAb (5)B→ε

（1）构造LR(0)项目集规范族如下： I6: A→aB.a I0: S’→.S I3: A→a.Ba I7: B→bA.b S→.AB B→.bAb I8: A→aBa. A→.aBa B→. I9: B→

bAb. A→. I4: S→AB. I1: S’→ S. I5: B→b.Ab I2: S→A.B A→.aBa B→.bAb A→. B→.

因为：FOLLOW(S)={#}

FOLLOW(A)={b,#} FOLLOW(B)={a,#}

I0面临FOLLOW(A)中元素时归约，面临a时移进，不存在冲突；同理，I2,I3,I5中的冲突也可以用SLR方法解决，所以该文法是SLR的。 （2）SLR分析表如下：

（3）

步骤 状态栈 符号栈 输入串 0 0 # baab# 1 02 #A baab# 2 025 #Ab aab# 3 0253 #Aba ab#

4 02536 #AbaB ab# 5 025368 #AbaBa b# 6 0257 #AbA b# 7 02579 #AbAb # 8 024 #AB # 9 01 #S #

3、若有文法G[S]:

S→S;M|M M→MbD|D D→D(S)|ε

（1）证明G[S]是SLR文法，并构造它的分析表；（2）给出G[S]的LR(1)项目集规范族中的I0。 解：（1）拓广文法为：

0)S’→S 1)S→S;M 2)S→M 3)M→MbD 4)M→D 5)D→D(S) 6)D→ε

LR(0)项目集规范族如下：

I0: S’→.S I3: M→D.

S→.S;M D→D.(S)

S→.M I4: S→S; .M

M→.MbD M→.MbD

M→.D M→.D

D→.D(S) D→.D(S)

D→. D→.

I1: S’→ S. I5: M→Mb.D

S→S.;M D→.D(S)

I2: S→M. D→.

M→M.bD

FOLLOW(S)={#,;,)}

FOLLOW(M)={#,;,),b} FOLLOW(D)={#,;,),b,c} SLR分析表如下：

I6: D→D(.S) S→.S;M S→.M M→.MbD M→.D D→.D(S) D→. I7: S→S;M. M→M.Bd I8: M→MbD. D→D.(S) I9: D→D(S.) S→S.;M I10: D→D(S).

分析表入口唯一，所以是SLR的。 （2）LR(1)项目集规范族中的I0:

S’→.S, # S→.S;M, #/; S→.M, #/; M→.MbD, #/;/b M→.D, #/;/b

D→.D(S), #/;/b/( D→. , #/;/b/(