文档库

最新最全的文档下载
当前位置:文档库 > 编译原理第二版作业答案_第2章

编译原理第二版作业答案_第2章

第二章 文法和语言

p48 4、6(6)、11、 12(2)(6)、18(2)

4 证明文法G=({E,O},{(,),+,*,v ,d},P ,E )是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明:

因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v

=〉EOv+v =〉E*v+v =〉v*v+v , 句子v*v+v 有两棵不同的语法树

编译原理第二版作业答案_第2章

编译原理第二版作业答案_第2章

编译原理第二版作业答案_第2章

所以文法G 是二义的。

问题:1)只有文字说明,比如v*v+v 有两棵语法树,但没有画出语法树或者最左(最右)推导过程

2)给出的是不同句子(v*v+d v+v*d )的语法树 6、已知文法G :

E

E

E

E O

O v

*

v

+ v

E E

E E O O v

+

v

* v

〈表达式〉∷=〈项〉|〈表达式〉+〈项〉

〈项〉∷=〈因子〉|〈项〉*〈因子〉

〈因子〉∷=(〈表达式〉)| i

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

(6)i+i*i

推导过程:

〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F

=〉〈表达式〉+〈项〉* i =〉E+ T*i

=〉〈表达式〉+ 〈因子〉* i =〉E+F*i

=〉〈表达式〉+ i* i =〉E+i*i

=〉〈项〉+ i* i =〉T +i*i

=〉〈因子〉+ i* i =〉F +i*i

=〉i +i*i =〉i +i*i 共8步推导

语法树:

〈表达式〉

+

〈因子〉〈项〉

i 〈因子〉

i

〈项〉

〈项〉

编译原理第二版作业答案_第2章

〈因子〉

编译原理第二版作业答案_第2章

i

*

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

编译原理第二版作业答案_第2章

(1)给出该句子相应的最左推导和最右推导

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

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

(1)最左推导:

S=〉ABS=〉aBS=〉aSBBS=〉aBBS

=〉abBS=〉abbS =〉abbAa=〉abbaa

最右推导:

S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa

=〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa

(2)该文法的产生式集合P可能有下列元素:

S→ABS | Aa|εA→a B→SBB|b

(3)因为字符串中的各字符有相对的位置关系,为了能相互区别,给相同的字符标上不同的数字。

短语:a1b1b2a2a3、b1b2、a2a3、a1、ε、b1、b2、a2简单短语:a1、ε、b1、b2、a2

句柄:a1

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

(2){a m b n | m≥n≥0}

解:

a m

b n 等价于a m-n a n b n

令k=m-n, k≥0,

则{a m b n | m≥n≥0} 即{a k a n b n | k≥0,n≥0},

G[S]:S→AB| ε

A→aA | ε

B→aBb | ε

(6){ww R | w∈{a,b}*}其中w R表示w的反向串,其含义是将w中的字母依次反转,首尾字母交换位置。

G[S]:S→aSa | bSb |ε

18、给出生成下述语言的3.型.文法

(2){a n b m|n,m≥1}

A→aA|aB B→bB|b