当前位置:文档之家› 编译原理第二版作业答案_第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 有两棵不同的语法树
所以文法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
〈项〉
〈项〉
〈因子〉
i
*
11、一个上下文无关文法生成句子abbaa的推导树如下:
(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。

相关主题