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

第3章文法和语言

第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为：

S→Ac|aB

A→ab

B→bc

写出L(G[S])的全部元素。

答案：

L(G[S])={abc}

第2题

文法G[N]为：

N→D|ND

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

G[N]的语言是什么？

答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}

N=>ND=>NDD....=>NDDDD...D=>D......D

或者：允许0开头的非负整数？

第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：

G[S]:

S->S+D|S-D|D

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

第4题

已知文法G[Z]：

Z→aZb|ab

写出L(G[Z])的全部元素。

答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb

L(G[Z])={anbn|n>=1}

第5题

写一文法，使其语言是偶正整数的集合。要求：

(1)允许0打头；

(2)不允许0打头。

答案：

(1)允许0开头的偶正整数集合的文法

E→NT|D

T→NT|D

N→D|1|3|5|7|9

D→0|2|4|6|8

(2)不允许0开头的偶正整数集合的文法

E→NT|D

T→FT|G

N→D|1|3|5|7|9

D→2|4|6|8

F→N|0

G→D|0

第6题

已知文法G：

<表达式>::=<项>｜<表达式>＋<项>

<项>::=<因子>｜<项>*<因子>

<因子>::=（<表达式>）｜i

试给出下述表达式的推导及语法树。

（５）i+(i+i)

（６）i+i*i

答案：

(5)<表达式>

=><表达式>＋<项>

=><表达式>＋<因子>

=><表达式>＋（<表达式>）

=><表达式>＋（<表达式>＋<项>）

=><表达式>＋（<表达式>＋<因子>）

=><表达式>＋（<表达式>＋i）

=><表达式>＋（<项>＋i）

=><表达式>＋（<因子>＋i）

=><表达式>＋（i＋i）

=><项>＋（i＋i）

=><因子>＋（i＋i）

=>i＋（i＋i）

(6)<表达式>

=><表达式>＋<项>

=><表达式>＋<项>*<因子>

=><表达式>＋<项>*i

=><表达式>＋<因子>*i

=><表达式>＋i*i

=><项>＋i*i

=><因子>＋i*i

=>i＋i*i

<表达式>

<表达式>+<项>

<因子>

<表达式>

<表达式>+<项>

<因子>

i

<项>

<因子>

i

<项>

<因子>

i

（)

<表达式>

<表达式>+<项>

<项>*<因子>

<因子>i

<项>

<因子>

i

i

第7题

证明下述文法G[〈表达式〉]是二义的。

〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉

〈运算符〉∷=+|-|*|/

答案：

可为句子a+a*a构造两个不同的最右推导:

最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉a

〈表达式〉*a

〈表达式〉〈运算符〉〈表达式〉*a

〈表达式〉〈运算符〉a*a

〈表达式〉+a*a

a+a*a

最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉〈表达式〉〈运算符〉a

〈表达式〉〈运算符〉〈表达式〉*a

〈表达式〉〈运算符〉a*a

〈表达式〉+a*a

a+a*a

第8题

文法G[S]为：

S→Ac|aB

A→ab

B→bc

该文法是否为二义的？为什么？

答案：

对于串abc

(1)S=>Ac=>abc(2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。

或者：

对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。

第9题

考虑下面上下文无关文法：

S→SS*|SS+|a

(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？

答案：

(1)此文法生成串aa+a*的最右推导如下

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

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

S

A c

a b

S

a B

b c

S

S S*

S S+a

a a

第10题

文法S→S(S)S|ε

(1)生成的语言是什么？

(2)该文法是二义的吗？说明理由。

答案：

（１）嵌套的括号

（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。

第11题

令文法G[E]为：

E→T|E+T|E-T

T→F|T*F|T/F

F→(E)|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

答案：

此句型对应语法树如右，故为此文法一个句型。

或者：因为存在推导序列:E=>E+T=>E+T*F，所

以E+T*F句型

此句型相对于E的短语有:E+T*F；相对于T的短语

有T*F

直接短语为：T*F

句柄为：T*F

第13题

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

(1)给出串abbaa最左推导、最右推导。

(2)该文法的产生式集合P可能有哪些元素？

(3)找出该句子的所有短语、直接短语、句柄。

B

a

S

A B S

a

S B A

εb b a

答案：

(1)串abbaa最左推导:

S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa

最右推导：

S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa

(2)产生式有：S→ABS|Aa|εA→a B→SBB|b

可能元素有：εaa ab abbaa aaabbaa……

(3)该句子的短语有：

a是相对A的短语

ε是相对S的短语

b是相对B的短语

εbb是相对B的短语

aa是相对S的短语

aεbbaa是相对S的短语

直接短语有：aεb

句柄是：a

第14题

给出生成下述语言的上下文无关文法：

（1）{anbnambm|n，m>=0}

（2）{1n0m 1m0n|n，m>=0}

（3）{WaWr|W属于{0|a}*，Wr表示W的逆}

答案：

（１）

S→AA

A→aAb|ε

（２）

S→1S0|A

A→0A1|ε

（３）

S→0S0|1S1|ε

第16题

给出生成下述语言的三型文法：

(1){an|n>=0}

(2){anbm|n,m>=1}

(3){anbmck|n,m,k>=0}

答案：

(1)S→aS|ε

(2)

S→aA

A→aA|B

B→bB|b

(3)

A→aA|B

B→bB|C

C→cC|ε

第17题

习题７和习题11中的文法等价吗？

答案：

等价。

第18题

解释下列术语和概念：

（１）字母表

（２）串、字和句子

（３）语言、语法和语义

答案：

（１）字母表：是一个非空有穷集合。

（２）串：符号的有穷序列。

字：字母表中的元素。

句子：如果Z x,x∈V*T则称x是文法G的一个句子。+

（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规

则构成的一切基本符号串组成的集合。

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。

语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 附加题

问题1：

给出下述文法所对应的正规式：

S→0A|1B

A→1S|1

B→0S|0

答案：

R=(01|10)(01|10)*

问题2：

已知文法G[A]，写出它定义的语言描述

G[A]:A→0B|1C

B→1|1A|0BB

C→0|0A|1CC

答案:

G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.

问题3：

给出语言描述，构造文法.

构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合. 答案一：

G[E]E→E+T|T

T→T*F|F

F→(E)|a

答案二：

G[E]E→E+E|E*E|(E)|a

问题4：

已知文法G[S]:

S→dAB

A→aA|a

B→ε|bB

相应的正规式是什么？G[S]能否改写成为等价的正规文法？

答案：

正规式是daa*b*；

相应的正规文法为(由自动机化简来)：

G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b

也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε

问题5：

已知文法G：

E→E+T|E-T|T

T→T*F|T/F|F

F→(E)|i

试给出下述表达式的推导及语法树

(1)i;

(2)i*i+i

(3)i+i*i

(4)i+(i+i)

答案：

(1)E=>T=>F=>i

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

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

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)

=>i+(i+T)=>i+(i+F)=>i+(i+i)

(2)

(3)

(4)

E+T

i

T

F

i

F

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

5

6

13

14

14

7

3

0 1 0

12

1 2

7

10 8

3

4

5

6

9

11 13 14

1

1

1

1

1

1

1

1

1

1

0 1

1

1

(3)先构造NFA：

先构造NFA：

用子集法将NFA确定化

ε

a

b

X

X

T0=X

A

A

ABCD

T1=ABCD

BE

BY

BE

ABCDE

BY

ABCDY

T2=ABCDE

BEF

BEY

BEF

ABCDEF

BEY

ABCDEY

T3=ABCDY

BE

BY

T4=ABCDEF

BEF

BEY

T5=ABCDEY

BEF

BEY

将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y，

所以它们都为终态。

a

b

1

1

3

2

4

5

3

2

3

4

4

5

5

4

5

X a A

εB

a,b

ε

D a E a F

C

ε

Y

ε

ε

b

ε

b

0 a 1 b 3

2

a

5

a 4

b

a

b

a

b

a

b

本文来源：https://www.bwwdw.com/article/uz2i.html