编译原理及实现课后习题答案docx.docx

编译原理及实现课后习题答案docx.docx

《编译原理及实现课后习题答案docx.docx》由会员分享，可在线阅读，更多相关《编译原理及实现课后习题答案docx.docx（43页珍藏版）》请在冰点文库上搜索。

编译原理及实现课后习题答案docx

2.1设字母表A={a},符号串x=aaa,写出下列符号串及其长度：

x0,xx,x5以及A+和A*.

x°=（aaa）°=e|x°|=0

xx=aaaaaa|xx|=6

x'=aaaaaaaaaaaaaaa|x5|=15

A+=AXUA2U....UA11U...=（a,aa,aaa,aaaa,aaaaa..

A*=A0UA1UA2U....UAnU...=（e,a,aa,aaa,aaaa,aaaaa...}

2.2令£=位，b,c）,又令x=abc,y=b,z=aab,写出如下符号串及它们的长度：

xy,xyz,（xy）3

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

（xy）3=（abcb）3=abcbabcbabcb|（xy）31=12

2.3设有文法G[S]：

S：

：

=SS*|SS+|a,写出符号串aa+a*规范推导，并构造语法树。

S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

2.4已知文法G[Z]：

Z：

：

=UOIVI、U：

：

=Z1|1、V：

：

=ZOI0,请写出

全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010

Z=>U0=>Z10=>V110=>0110

Z=>Vl=>Z01=>U001=>1001

Z=>Vl=>Z01=>V101=>0101

2.5已知文法G[S]：

S：

：

=ABA：

：

=aA|eB：

：

=bBcIbe,写出该文法描述的语言。

A：

：

=aA|£描述的语言：

{an|n>=0}

B：

：

=bBc|be描述的语言：

{bncn|n>=l}

L（G[S]）={anbmcm|n>=0,rn>=l}

2.6已知文法E：

：

=T|E+T|E-T>T：

：

=F|T*F|T/F、F：

：

=（E）|i,写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。

开始符号：

E

Vt={+,（,）,i}

Vn={E,F,T}

2.7对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。

根据所给文法推导出句子a+a*a,画出了两棵不同的语法树，所以该文法是二义性文法。

2.9写一文法，使其语言是奇正整数集合。

A:

:

=1|3|5|7|9|NA

N:

:

=0|l|2|3|4|5|6|7|8|9

2.10给出语言｛anbm|n,mNl｝的文法。

G[S]:

S:

:

=AB

A:

:

=aA|a

B:

:

=bB|b

3.1有正则文法G[Z]：

Z:

:

=Ua|Vb,U:

:

=Zb|b,V:

:

=Za|a,画出该文

法的状态图，并检查句子abba是否合法。

解：

该文法的状态图如下：

句子abba合法。

3.2状态图如图3.35所示，S为开始状态，Z为终止状态。

写出相应

的正则文法以及V,Vn和Vt。

解：

左线性文法G[Z]:

Z:

:

=Ab|b

A:

:

=Aa|a

V=（Z,A,a,b}

Vn={Z,A}

右线性文法G，[S]:

S:

:

=aA|b

A:

:

=aA|b

V={S,A,a,b}

Vn={S,A}

Vt={a,b}

Vt={a,b}3.3构造下列正则表达式相应的NFA：

1（1|0）*|0

1（1010*|1（010）*1）*0

解：

正则表达式：

1（1|0）*|0

1、

©

正则表达式：

1（1010*11（010）*1）*0

3.4将图3.36的NFAM确定化

a

b

q0={0}

{0,1}

{1}

ql=（O,l}

{0,1}

{1}

q2={l}

{0}

3.5将图3.37的DFA化简。

DFA:

划分

a

b

{0,1}

{1}

{2,4}

{234,5}

{1,305}

{3,5,2,4}

划分

a

b

{0,1}

{1}

{2,4}

{2,4}

（0,1}

{3,5}

{3,5}

{3,5}

{2,4}

qO={O,l}ql={2,4}q2={3,5}

化简后的DFA：

4.1对下面文法，设计递归下降分析程序。

S—aAS|（A）,A—Ab|c

解：

首先将左递归去掉，将规则A-Ab|c改成A-c{b}非终结符号S的分析程序如下：

非终结符号A的分析程序如下:

4.2设有文法G[Z]：

Z：

：

=（A）,A：

：

=a|Bb,B：

：

=Aab

若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？

为什么？

解：

若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。

因为规则A

:

：

=a|Bb和规则B：

：

=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件

（1）（书P67）,且规则A:

:

=a|Bb,FIRST（a）={a},FIRST（Bb）={a},即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件

（2）（书P67）,在分析过程中，将造成回溯。

改写文法可避免回溯：

将规则B：

：

=Aab代入规则A：

：

=a|Bb得:

A：

：

=a|Aabb,再转换成：

A：

：

=a{abb},可避免回溯。

4.3若有文法如下，设计递归下降分析程序。

＜语句＞一＜语句＞＜赋值语句＞|e

〈赋值语句＞-ID=＜表达式〉

〈表达式〉一〈项＞|〈表达式〉+〈项＞|〈表达式〉一v项〉

〈项＞—＜因子＞|〈项＞*＜因子＞|〈项〉/＜因子〉

〈因子＞—ID|NUM|（〈表达式〉）

解：

首先，去掉左递归

〈语句＞—＜语句＞＜赋值语句＞|e改为：

〈语句＞—{V赋值语句〉}

〈表达式＞—＜项〉|〈表达式〉+〈项〉|〈表达式〉-＜项＞改为：

v表达式＞一＜项〉{（+|-）＜项〉}

＜项＞—v因子＞|＜项＞*＜因子＞|v项〉/v因子〉改为：

〈项＞一＜因子＞{（*|/）〈因子〉}则文法变为：

〈语句＞_{＜赋值语句〉}

〈赋值语句＞-ID=＜表达式〉

〈表达式＞-＞＜项〉{（+|-）v项〉}

＜项＞一〈因子＞{（*|/）〈因子〉}

〈因子＞一ID|NUM|（〈表达式〉）

复值语句的分析程序

4.4有文法G[A]：

A:

:

=aABe|£,B:

:

=Bb|b

（1）求每个非终结符号的FOLLOW集。

（2）该文法是LL

（1）文法吗？

（3）构造LL

（1）分析表。

解：

（1）FOLLOW（A）=First（B）U{#}={b,#}

FOLLOW（B）={e,b}

（2）该文法中的规则B:

:

=Bb|b为左递归，因此该文法不是LL

（1）文法

（3）先消除文法的左递归（转成右递归），文法变为：

A:

:

=aABe|w,B:

:

=bB,,B，:

:

=bB，|&

该文法的LL

（1）分析表为:

a

e

b

#

A

POP,PUSH（eBAa）

POP

POP

B

POP,PUSH（B'b）

B9

POP

POP,

PUSH（B'b）

a

POP,

NEXTSYM

e

POP,

NEXTSYM

b

POP,

NEXTSYM

#

ACCEPT

更常用且简单的LL

（1）分析表:

a

e

b

#

A

A—aABe

A—£

A—£

B

B—bB，

B，

B'-£

B'fbB‘

4.5若有文法A-（A）A|e

（1）为非终结符A构造FIRST集合和FOLLOW集合。

（2）说明该文法是LL

（1）的文法。

解：

（1）FIRST（A）={（,e）

FOLLOW（A）=（）,#}

（2）

该文法不含左递归；

FIRST（（A）A）=（（},FIRST（e）={e},FIRST（（A）A）nFIRST（e）=①,且FOLLOW（A）=（）,#},FIRST（（A）A）AFOLLOW（A）=①，因此，该文法满足LL

（1）文法的条件，是LL

（1）文法。

4.6利用分析表4-1,识别以下算术表达式，请写出分析过程。

（1）i+i*i+i

（2）i*（i+i+i）

解：

（1）i+i*i+i

步骤

分析栈

余留输入串

分析表元素

所用产生式

1

#E

i+i*i+i#

POP,PUSH（E,T）

E—TE'

2

#E，T

i+i*i+i#

POP,PUSH（T，F）

T—FT'

3

#E，TF'

i+i*i+i#

POP,PUSH（i）

F—i

4

#ETi

i+i*i+i#

POP,NEXTSYM

5

#E，T，

+i*i+i#

POP

T'_8

6

#E5

+i*i+i#

POP,PUSH（E,T+）

E—+TE'

7

#E，T+

+i*i+i#

POP,NEXTSYM

8

#E9T

i*i+i#

POP,PUSH（T9F）

T—FT，

9

#ETF

i*i+i#

POP,PUSH（i）

F-*i

10

#ETi

i*i+i#

POP,NEXTSYM

11

#E,T,

*i+i#

POP,PUSHfTF*）

12

#ETF*

*i+i#

POP,NEXTSYM

13

#E，T，F

i+i#

POP,PUSH（i）

F—i

14

#ETi

i+i#

POP,NEXTSYM

15

#ET

+i#

POP

T'_e

16

#E9

+i#

POP,PUSH（E,T+）

E5-*+TE5

17

#E5T+

+i#

POP,NEXTSYM

18

#E，T

i#

POP,PUSH（T5F）

T—FT，

19

#ETF

i#

POP,PUSH（i）

F—i

20

#ETi

i#

POP,NEXTSYM

21

#E，r

#

POP

T'—e

22

#E，

#

POP

E'—e

23

#

#

ACCEPT

（2）i*（i+i+i）

步骤

分析栈

余留输入串

分析表元素

所用产生式

1

#E

i*（i+i+i）#

POP,PUSH（E,T）

E—TE，

2

#E，T

i*（i+i+i）#

POP,PUSH（T，F）

T—FT'

3

#E，T，F

i*（i+i+i）#

POP,PUSH（i）

F—i

4

#E'T'i

i*（i+i+i）#

POP,NEXTSYM

5

#E，T，

*（i+i+i）#

POP,PUSH（T，F*）

*FT，

6

#e，t，f*

*（i+i+i）#

POP,NEXTSYM

7

#E，T，F

（i+i+i）#

POP,PUSH（）E（）

F-（E）

8

#E5T5）E（

（i+i+i）#

POP,NEXTSYM

9

#ET）E

i+i+i）#

POP,PUSH（E,T）

E->TE9

10

#E，t，）E'T

i+i+i）#

POP,PUSH（TT）

T—FT，

11

#E，t，）E'T'F

i+i+i）#

POP,PUSH（i）

F—i

12

#E,T,）E,T,i

i+i+i）#

POP,NEXTSYM

13

#E'T'）E'T'

+i+i）#

POP

e

14

#E,T,）E,

+i+i）#

POP,PUSH（E,T+）

E—+TE，

15

#E'T'）E'T+

+i+i）#

POP,NEXTSYM

16

#E，t，）E'T

i+i）#

POP,PUSH（TT）

T—FT，

17

#E'T'）E'T'F

i+i）#

POP,PUSH（i）

F—i

18

#E'T'）E'T'i

i+i）#

POP,NEXTSYM

19

#E'T'）E'T‘

+i）#

POP

T'fe

20

#E'T'）E'

+i）#

POP,PUSH（E,T+）

E—+TE，

21

#E'T'）E'T+

+i）#

POP,NEXTSYM

22

#E，t，）E'T

i）#

POP,PUSH（TT）

T—FT，

23

#E'T'）E'T'F

i）#

POP,PUSH（i）

F—i

24

#E'T'）E'T'i

i）#

POP,NEXTSYM

25

#E'T'）E'T‘

）#

POP

T'_e

26

#E'T'）E'

）#

POP

E'—£

27

#ET）

）#

POP,NEXTSYM

28

#E,T,

#

POP

T'_8

29

#E5

#

POP

E'—£

30

#

#

ACCEPT

4.7考虑下面简化了的C声明文法:

〈声明语句>-<类型x变量表〉；〈类型〉—int|float|char

〈变量表>TD,v变量表>|ID

（1）在该文法中提取左因子。

（2）为所得的文法的非终结符构造FIRST集合和FOLLOW集合。

（3）说明所得的文法是LL

（1）文法。

（4）为所得的文法构造LL

（1）分析表。

（5）假设有输入串为“charx,y,z；”,写出相对应的LL

（1）分析过程。

解：

（1）规则〈变量表〉一ID,〈变量表>|ID提取公因子如下：

〈变量表〉一1。

（,<变量表>|8）增加新的非终结符〈变量表1>,规则变为：

〈变量表>—IDV变量表1>

V变量表1>—,V变量表>16

C声明文法改变为：

〈声明语句>—<类型><变量表〉；

〈类型〉—int|float|char

〈变量表>-ID<变量表1>

〈变量表1>_,〈变量表>|e

（2）FIRST（<声明语句>）=FIRST（〈类型>）=（int,float,char）

FIRST（<变量表>）={ID）

FIRST（〈变量表1>）={,,e）

FOLLOW（<声明语句>）={#）

FOLLOW（〈类型>）=FIRST（v变量表>）=（ID）

FOLLOW（〈变量表>）=FOLLOW（<变量表1>）=（:

}

（3）所得文法无左递归，且

FIRST（int）AFIRST（float）nFIRST（char）=®

FIRST（,〈变量表〉）AFIRST（e）=0>

FIRST（,〈变量表〉）flFOLLOW（〈变量表1>）=0

因此，所得文法为LL

（1）文法。

（4）所得的文法构造LL

（1）分析表如下所示:

int

float

char

ID

9

#

V声明语句〉

POP,

PUSH（；<变量表>v类型〉）

POP,

PUSH（；v变

量表><类

型〉）

POP,

PUSH（；〈变

量表><类型〉）

<类型〉

POP,PUSH（int）

POP,PUSH（float）

POP,PUSH（char）

V变量表〉

POP,PUSH（<变量表1>ID）

〈变量

POP

POP,

表1>

PUSH（<

变量

表〉，）

POP,

NEXT

SYM

int

POP,

NEXTSY

M

float

POP,

NEXTSYM

char

POP,

NEXTSYM

ID

POP,

NEXTSY

M

POP,

NEXTSY

M

#

ACC

EPT

更常用且简单的LL

（1）分析表:

int

float

char

ID

#

v声明语句〉

V声明语句〉一V类型〉V变量表〉；

V声明语句〉一V类型〉V变量表〉；

v声明语句〉一v类型><变量表〉；

<类型〉

V类型>-*int

v类型>-*float

v类型>—char

V变量表〉

V变量表〉

—IDV变量

表1>

〈变量表1>

V变量表1>

—e

〈变量表1>-,<变量表〉

（5）输入串"charx,y,z；"柞

对应的LL

（1）分析过程如下：

步骤

分析栈

余留输入串

分析表元素

所用产生式

1

#<声明语句〉

charx,y,z；#

POP,

PUSH（；〈变量表><类型〉）

〈声明语句〉一V类型><变量表〉；

2

#;〈变量表><类型〉

charx,y,z；#

POP,PUSH（char）

v类型>fchar

3

#；V变量表〉char

charx,y,z；#

POP,

NEXTSYM

4

#;〈变量表〉

x,y,z；#

POP,

v变量表〉一ID<

PUSH（<变量表

1>ID）

变量表1>

5

#；〈变量表1>X

x,y,z；#

POP,

NEXTSYM

6

#;〈变量表1>

，y，z；#

POP,

PUSH（<变量表〉，）

〈变量表1>—,

〈变量表〉

7

#；V变量表〉，

y,z；#

POP,

NEXTSYM

8

#；V变量表〉

y,z；#

POP,

PUSH（<变量表

1>ID）

〈变量表>—ID<变量表1>

9

#；〈变量表l>y

y,z；#

POP,

NEXTSYM

10

#；〈变量表1>

，z；#

POP,

PUSH（<变量表〉，）

V变量表1>一，

V变量表〉

11

#；V变量表〉，

，z；#

POP,

NEXTSYM

12

#；V变量表〉

z；#

POP,

PUSH（<变量表

1>ID）

v变量表>—IDv变量表1>

13

#；〈变量表1>Z

z；#

POP,

NEXTSYM

14

#;〈变量表1>

;#

POP

〈变量表1>—e

15

#;

;#

POP,

NEXTSYM

16

#

#

ACCEPT

5.1考虑以下的文法：

S-S;T|T

T—a

（1）为这个文法构造LR（O）的项目集规范族。

（2）这个文法是不是LR（O）文法？

如果是，则构造LR（O）分析表。

（3）对输入串“a;a”进行分析。

解：

（1）拓广文法G[S,]：

0：

S'-S

1：

S-S;T

2：

S-T

3：

T—a

构造LR（0）项目集规范族

状态

项目集

转换函数

0

S'—•SS—•S;TS—•TT—.a

G0[0,S]=lG0[0,S]=lG0[0,T]=2G0[0,a]=3

1

S'—S・

S—S•;T

ACCEPT

GO[1,;]=4

2

S—T・

R2

3

T—a•

R3

4

S—S;•T

T—•a

GO[4,T]=5

GO[4,a]=3

5

S-S;T•

R1

（2）该文法不存在“归约一归约”和“归约一移进”冲突，因此是LR（0）文法。

LR（0）分析

表如下:

状态

ACTION

GOTO

a

#

S

T

0

S3

1

2

1

S4

ACCEPT

2

R2

R2

R2

3

R3

R3

R3

4

S3

5

5

R1

R1

R1

（3）对输入串“a;a”进行分析如下:

步骤

状态栈

符号栈

输入符号栈

ACTION

GOTO

0

0

#

a;a#

S3

1

03

#a

;a#

R3

2

3

02

#T

;a#

R2

1

4

01

#S

;a#

S4

5

014

#S;

a#

S3

6

0143

#S;a

#

R3

5

7

0145

#S;T

#

R1

1

8

01

#S

#

ACCEPT

5.2证明下面文法是SLR

（1）文法，但不是LR（O）文法。

S—A

A—Ab|bBa

B—aAc|a|aAb

解：

文法G[S]：

0：

S—A

1：

A—Ab

2：

A—bBa

3：

B—aAc

4：

B—a

5：

B—aAb

构造LR（0）项目集规范族:

状态

项目集

转换函数

0

S—-A

A—•Ab

A-*•bBa

G0[0,A]=lG0[0,A]=lG0[0,b]=2

1

S—A・

A-A・b

ACCEPT

G0[l,b]=3

2

A—b•Ba

B—•aAc

B—•a

B—•aAb

GO[2,B]=4

GO[2,a]=5

GO[2,a]=5

GO[2,a]=5

3

A-Ab•

R1

4

A—bB•a

GO[4,a]=6

5

B—a•Ac

GO[5,A]=7

B—a•

B—a•Ab

A—-Ab

A—•bBa

R4

GO[5,A]=7

GO[5,A]=7

GO[5,b]=2

6

A—bBa•

R2

7

B—aA•cB—aA•bA—A・b

GO[7,c]=8

G0[7,b]=9

GO[7,b]=9

8

B—aAc•

R3

9

B—aAb•

A—Ab•

R5

R1

状态5存在“归约一移进”冲突，状态9存在“归约一归约”冲突，因此该文法不是LR（O）文法。

状态5：

FOLLOW（B）={a},因此，FOLLOW（B）n{b}=O

状态9：

FOLLOW（B）={a},FOLLOW（A）=（#,b,c},因此FOLLOW（B）nFOLLOW（A）=O

状态5和状态9的冲突均可用SLR

（1）