编译原理第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 …… 此处隐藏：2016字，全部文档内容请下载后查看。喜欢就下载吧 ……