编译原理第3章文法和语言(2)

i

E

E+T

E+T

i

T

F

(E)

i

T

F i

F

问题6：

已知文法G[E]:

E→ET+|T

T→TF*|F

F→F^|a

试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.

答案：

该句型对应的语法树如下：

该句型相对于E的短语有FF^^*

相对于T的短语有FF^^*,F

相对于F的短语有F^;F^^

简单短语有F;F^

句柄为F.

问题7：

适当变换文法，找到下列文法所定义语言的一个无二义的文法：

S→SaS.SbS.ScS.d

答案：

该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。

设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为：

S→SaS.A

A→AbA.C

C→CcC.d

规定结合性为左结合，进一步将文法变换为：

S→SaA.A

A→AbC.C

C→CcF.F

F→d

该文法为非二义的。

问题8：

构造产生如下语言的上下文无关文法：

（1）{anb2ncm|n，m≥0}

（2）{anbmc2m|n，m≥0}

（3）{ambn.m≥n}

（4）{a m b n c p d q.m+n=p+q}

（5）{uawb.u,w∈{a,b}*∧|u|=|w|}

答案：

（1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如anb2n和

形如cm的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是

特别指明，通常可以忽略这一点。

对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：

S→AB

A→ε.aAbb

B→ε.cB

（2）同样，要产生形如anbmc2m的串，可以分别产生形如an和形如bmc2m的串。对于该语

言，存在一个由以下产生式定义的上下文无关文法G[S]：

S→AB

A→ε.aA

B→ε.bBcc

（3）考虑在先产生同样数目的a,b，然后再生成多余的a。以下G[S]是一种解法： S→aSb.aS.ε

（4）以下G[S]是一种解法：

S→aSd.A.D

A→bAd.B

D→aDc.B

B→bBc.ε

注：a不多于d时，b不少于c；反之，a不少于d时，b不多于c。前一种情形通过 对应A，后一种情形对应D。

（5）以下G[S]是一种解法：

S→Ab

A→BAB.a

B→a.b

问题9：

下面的文法G(S)描述由命题变量p、q，联结词∧（合取）、∨（析取）、.（否定）构 成的命题公式集合：

S→S∨T.T

T→T∧F.F

F→.F.p.q

试指出句型.F∨.q∧p的直接短语（全部）以及句柄。

答案：

直接短语：p，q，.F

句柄：.F

问题10：

设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+.

答案：

x0=(aaa)0=ε|x0|=0

xx=aaaaaa|xx|=6

x5=aaaaaaaaaaaaaaa|x5|=15

A+=A1∪A2∪….∪A n∪…={a,aa,aaa,aaaa,aaaaa…}

A*=A0∪A1∪A2∪….∪A n∪…={ε,a,aa,aaa,aaaa,aaaaa…}

问题11：

令Σ={a，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)3|=12

问题12：

已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文

法描述的只含有四个符号的句子。

答案：

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

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

Z=>V1=>Z00=>U000=>1000

Z=>V1=>Z00=>V100=>0100

问题13：

已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。

答案：

A∷=aA︱ε描述的语言:{an|n>=0}

B∷=bBc︱bc描述的语言:{,bncn|n>=1}

L(G[S])={anbmcm|n>=0,m>=1}

问题14：

已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开 始符号、终结符号集合VT、非终结符号集合VN。

答案：

开始符号：E

VT={+,-,*,/,（,）,i}

VN={E,F,T}

问题15：

设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？

答案：

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

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

答案：

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

N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|

N::=0|1|2|3|4|5|6|7|8|9

S

S*S

S+S a

a a

S

S+S

a S*S

a a

第4章词法分析

第1题

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

（１）1(0|1)*101

（２）１(1010*|1(010)*1）*0

（３）a((a|b)*|ab*a)*b

（４）b((ab)*|bb)*ab

答案：

(1)先构造NFA：

用子集法将NFA确定化

.

1

X

.

A

A

A

AB

AB

AC

AB

AC

A

ABY

ABY

AC

AB

除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA 的终态），所以D为终态。

.

1

X

.

A

A

A

B

B

C

B

C

A

D

D

C

B

DFA的状态图：:

(2)先构造NFA：

用子集法将NFA确定化

ε

1

X

X

T0=X

A

A

ABFL

T1=ABFL

Y

CG

Y

Y

CG

CGJ

T2=Y

T3=CGJ

DH

K

DH

DH

K

ABFKL

T4=DH

EI

EI

ABEFIL

T5=ABFKL

Y

CG

T6=ABEFIL

EJY

CG

EJY

ABEFGJLY

T7=ABEFGJLY

EHY

CGK

EHY

ABEFHLY

CGK

ABCFGJKL

T8=ABEFHLY

EY

CGI

EY

ABEFLY

CGI

CGJI

T9=ABCFGJKL

DHY

CGK

DHY

DHY

T10=ABEFLY

EY

CG

T11=CGJI

DHJ

K

DHJ

DHJ

T12=DHY

EI

T13=DHJ

EIK

EIK

ABEFIKL

T14=ABEFIKL

EJY

CG

X 1 A

εB

1 C 0 D 1 E

ε

F 1 G 0 H 1 I 0 J 1 K

L

εε

ε

ε

ε

ε

将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、

1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因为2、7、8、10、12中含有Y，

所以它们都为终态。

1

1

1

2

3

2

3

4

5

4

6

5

2

3

6

7

3

7

8

9

8

10

11

9

12

9

10

10

3

11

13