《编译原理》课后习题答案第三章第3章文法和语言第1.pdfVIP

《编译原理》课后习题答案第三章

第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=DD

或者：允许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])的全部元素。

盛威网（www.snwei.co）专业的计算机学习网站1

《编译原理》课后习题答案第三章

答案：

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

盛威网（www.snwei.co）专业的计算机学习网站2

《编译原理》课后习题答案第三章

答案：

表达式

表达式+项

因子

表达式

表达式+项

因子

i

项

因子

i

项

因子

i

（)

(5)表达式

=表达式＋项

=表达式＋因子

=表达式＋（表达式）

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

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

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

=表达式＋（项＋i）

=表达式＋（因子＋i）

=表达式＋（i＋i）

=项＋（i＋i）

=因子＋（i＋i）

=i＋（i＋i）

表达式

表达式+项

项*因子

因子i

项

因子

i

i

(6)表达式

=表达式＋项

=表达式＋项*因子

=表达式＋项*i

=表达式＋因子*i

=表达式＋i*i

=项＋i*i

=因子＋i*i

=i＋i*i

盛威网（www.snwei.co）专业的计算机学习网站3

《编译原理》课后习题答案第三章

第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

盛威网（www.snwei.co）专业的计算机学习网站4

《编译原理》课后习题答案第三章

第8题

文法G[S]为：

S→Ac|aB

A→ab

B→bc

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

答案：

对于串abc

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

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

或者：

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

S

aB

bc

S

Ac

ab

第9题

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

S→SS*|SS+|a

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