编译原理第二章习题与答案.docx

编译原理第二章习题与答案.docx

《编译原理第二章习题与答案.docx》由会员分享，可在线阅读，更多相关《编译原理第二章习题与答案.docx（10页珍藏版）》请在冰点文库上搜索。

编译原理第二章习题与答案

第2章习题解答

1.文法G[S]为：

S->Ac|aB

A->ab

B->bc

写出L（G[S]）的全部元素。

[答案]

S=>Ac=>abc

或S=>aB=>abc

所以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

===============================================

3.已知文法G[S]：

S→dAB A→aA|a B→ε|bB

问：

相应的正规式是什么？

G[S]能否改写成为等价的正规文法？

[答案]

正规式是daa*b*；

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

G[S]:

S→dAA→a|aBB→aB|a|b|bCC→bC|b

也可为（观察得来）:

G[S]:

S→dAA→a|aA|aBB→bB|ε

===============================================================================

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.给出语言{anbncm|n>=1,m>=0}的上下文无关文法。

[分析]

本题难度不大，主要是考上下文无关文法的基本概念。

上下文无关文法的基本定义是：

A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证anbn的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。

[答案]

构造上下文无关文法如下：

S->AB|A

A->aAb|ab

B->Bc|c

[扩展]

凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。

基本思路是这样的：

要求符合anbncm，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S->AB，其中A推出anbn，B推出cm。

因为m可为0，故上式进一步改写为S->AB|A。

接下来考虑A,凡是要求两个终结符个数相等的问题，都应写为A->aAb|ab形式，对于B就很容易写成B->Bc|c了。

==============================================================================

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

要求：

（1）允许0开头；

（2）不允许0开头。

[答案]

（1）允许0开头的偶正整数集合的文法

E->NT|G|SFM

T->NT|G

N->D|1|3|5|7|9

D->0|G

G->2|4|6|8

S->NS|ε

F->1|3|5|7|9|G

M->M0|0

（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

=============================================================================

7.已知文法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）

8.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。

〈表达式〉->〈表达式〉〈运算符〉〈表达式〉|（〈表达式〉）|i

〈运算符〉->+|-|*|/

[答案]

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

最右推导1

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

=>〈表达式〉〈运算符〉i

=>〈表达式〉*i

=>〈表达式〉〈运算符〉〈表达式〉*i

=>〈表达式〉〈运算符〉i *i

=>〈表达式〉+i*i

=>i+i*i

最右推导2

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

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

=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉i

=>〈表达式〉〈运算符〉〈表达式〉*i

=>〈表达式〉〈运算符〉i *i

=>〈表达式〉+i*i

=>  i+i*i

所以，该文法是二义的。

======================================================================

9.文法G[S]为：

S->Ac|aB

A->ab

B->bc

该文法是否为二义的？

为什么？

[答案]

对于串abc

（1）S=>Ac=>abc

（2）S=>aB=>abc

即存在两不同的最右推导

所以，该文法是二义的。

===========================================================================

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

S->SS*|SS+|a

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

（2）G[S]的语言是什么？

[答案]

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

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

（2）该文法生成的语言是即加法和乘法的逆波兰式,

==============================================================================

11.令文法G[E]为:

E->E+T|E-T

T->T*F|T/F|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

12.已知文法G[E]:

E→ET+|T T→TF*|F F→F^|a

试证：

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

[答案]

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

该句型相对于E的短语有FF^^*；相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F.

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

（1）给出串abbaa最左推导、最右推导。

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

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

（1）串abbaa最左推导:

S=>ABS=>aBS=>aSBBS=>aεBBS=>aεbBS=>aεbbS=>aεbbAa=>aεbbaa

最右推导：

S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aεbbaa=>aεbbaa

（2）产生式有：

S→ABS|Aa|ε

A→a

B→SBB|b

（3）该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2；

直接短语有a1、b1、b2、a2；

句柄是a1。

=====================================================================

14.给出生成下列语言的上下文无关文法。

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

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

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

[答案]

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

S->AA

A->aAb|ε

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

S->1S0|A

A->0A1|ε

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

S->0S0|1S1|ε

===================================================================

15.给出生成下列语言的三型文法。

（1）{an|n>=0}

（2）{anbm|n,m>=1}

（3）{anbmck|n,m,k>=0}

[答案]

（1）{an|n>=0}的三型文法为：

S->aS|ε

（2）{anbm|n,m>=1}的三型文法为：

S->aA    

A->aA|bB

B->bB|ε

（3）{anbmck|n,m,k>=0}的三型文法为:

A->aA|bB|cC|ε

B->bB|cC|ε

C->cC|ε

==========================================================================

16.构造一文法产生任意长的a,b串，使得

|a|<=|b|<=2|a|

其中，“|a|”表示a字符的个数;“|b|”表示b字符的个数。

[分析]

b的个数在a与2a之间，所以应想到形如aSBS和BSaS的形式，B为1到2个b，即可满足条件。

[答案]

如分析中所述，可得文法如下：

S-aSBS|BSaS|ε

B->bb|b

第1个产生式为递归定义，由于在第2个产生式中B被定义为1或2个b，所以第1个产生式可以保证b的个数在|a|与2|a|之间，而a与b的位置可以任意排布，所以此文法即为所求，注意第1个产生式中要包括s。

==============================================================================

17.下面的文法产生a的个数和b的个数相等的非空a,b串

S->aB|bA

B->bS|aBB|b

A->aS|bAA|a 

其中非终结符B推出b比a的个数多1个的串，A则反之。

说明该文法是二义的。

对上述文法略作修改，使之非二义，并产生同样的语言。

（略做修改的含义是：

不增加非终结符。

）

[答案]

句子aabbab有两种不同的推导。

S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbab

S=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab

即它可以产生两棵不同的语法树，故它是二义的。

修改后的无二义文法如下：

S->aBS|bAS|aB|bA

B->aBB|b

A->bAA|a

====================================================================

18.给出0，1，2，3型文法的定义。

[答案]

乔姆斯基（chomsky）把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。

如果它的每个产生式α->β的结构是α∈（VnUVt）*且至少含有一个非终结符,而β∈（VnUVt）*，我们说G=（Vt，VN，S，δ）是一个0型文法。

0型文法也称短语文法。

一个非常重要的理论结果是，0型文法的能力相当于图灵（Tunring）机。

或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。

如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为：

1．G的任何产生式α->β均满足|α|<=|β|；仅仅S->ε例外，但S不得出现在任何产生式的右部。

2．G的任何产生式为A->β，A∈Vn，β∈（VnUVt）*

3．G的任何产生式为A->aB或A->a，其中A，B∈Vn

1型文法也称上下文有关文法。

这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，—般不允许替换成空串。

2型文法对非终结符进行替换时无须考虑上下文，

3型文法也称线性文法。