(完整文本版)编译原理课后答案.docVIP

PAGE

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

4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：

优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16

（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=4

6．令文法G6为N→D|ND

D→0|1|2|3|4|5|6|7|8|9

G6的语言L（G6）是什么？

给出句子0127、34和568的最左推导和最右推导。

解：（1）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝

（2）N＝＞ND＝＞NDD＝＞NDDD＝＞DDDD＝＞0DDD＝＞01DD＝＞012D＝＞0127

N＝＞ND＝＞N7＝＞ND7＝＞N27＝＞ND27＝＞N127＝＞D127＝＞0127

N＝＞ND＝＞DD＝＞3D＝＞34

N＝＞ND＝＞N4＝＞D4＝＞34

N＝＞ND＝＞NDD＝＞DDD＝＞5DD＝＞56D＝＞568

N＝＞ND＝＞N8＝＞ND8＝＞N68＝＞D68＝＞568

7．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A→SN,S→+|-|∑,N→D|MD

D→1|3|5|7|9,M→MB|1|2|3|4|5|6|7|8|9B→0|1|2|3|4|5|6|7|8|9

8.文法：

最左推导:

最右推导:

语法树：/********************************

*****************/

9．证明下面的文法是二义的：

S→iSeS|iS|I

解：因为iiiiei有两种最左推导，所以此文法是二义的。

10．把下面文法改写为无二义的：

S→SS|(S)|()

解：S→ST|T,T→(S)|()

11．给出下面语言的相应文法

L1=｛anbnci|n≥1,i≥0｝

L2=｛aibncn|n≥1,i≥0｝

L3=｛anbnambm|n,m≥0｝

L4=｛1n0m1m0n|n,m≥0｝

解：（1）S→AB|A

A→aAb|ab

B→c|cB

(2)S→AB|B

A→a|aA

B→bBc|bc

(3)S→AB|A|B|∑

A→aAb|ab

B→aBb|ab

S→1S0|0A1

A→0A1|01

词法分析

7.构造下列正规式的相应的DFA

1(0|1)*101

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

0*10*10*10*

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

解答：

（1）1(0|1)*101

I I0 I1

{X} Ф {A,B,C}

{A,B,C} {B,C} {B,C,D}

{B,C} {B,C} {B,C,D}

{B,C,D} {B,C,E} {B,C,D}

{B,C,E} {B,C} {B,C,D,y}

{B,C,D,y} {B,C,E} {B,C,D}

S 0 1

A B

B C D

C C D

D E D

E C F

F E D

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

I I0 I1

Ф {A,B,C}

{A,B,C} {y} {D,H,I,L}

{y} Ф Ф

{D,H,I,L} {E,J} {B,C}

{E,J} Ф {B,C,F,G,K}

{B,C} {y} {D,H,I,L}

{B,C,F,G,K} {B,C,G,I,L,y} {D,H,I,L}

{B,C,G,I,L,