《编译原理》课后习题答案第三章
答案：
(5) <表达式> =><表达式>＋<项> =><表达式>＋<因子> =><表达式>＋（<表达式>） =><表达式>＋（<表达式>＋<项>） =><表达式>＋（<表达式>＋<因子>）
=><表达式>＋（<表达式>＋i） =><表达式>＋（<项>＋i）
=><表达式>＋（<因子>＋i） =><表达式>＋（i＋i） =><项>＋（i＋i） =><因子>＋（i＋i） =>i＋（i＋i）
表达式> < 项> < 因子 < > i （ + 项> < 因子> < 表达式> < ) 表达式> < 表达式> < 项> < 因子> < i
+ 项> < 因子 < > i
盛威网（www.snwei.com）专业的计算机学习网站
3
《编译原理》课后习题答案第三章
<表 达式>(6) <表达式> =><表达式>＋<项> =><表达式>＋<项>*<因子> <表 达式 > =><表达式>＋<项>*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
盛威网（www.snwei.com）专业的计算机学习网站
+ <项 > <项 > * <因 子> <因 子 > i i 〈表达式〉〈运算
4
《编译原理》课后习题答案第三章
A→ab B→bc
该文法是否为二义的？为什么？ 答案：
对于串 abc
(1)S=>Ac=>abc (2)S=>aB=>abc 即存在两不同的最右推导。所以，该文法是二义的。 或者：
对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。
第 9 题 答案：
第 10 题
S S
a B A c a b c b 考虑下面上下文无关文法：
S→SS*|SS+|a
(1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。
(2)G[S]的语言是什么？
S S S S * S + a (1)此文法生成串 aa+a*的最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。
a a
盛威网（www.snwei.com）专业的计算机学习网站
5
《编译原理》课后习题答案第三章
文法 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)找出该句子的所有短语、直接短语、句 a 答案：
(1)串 abbaa 最左推导:
a S ε B b B A b a A B S S 柄。
盛威网（www.snwei.com）专业的计算机学习网站
6
《编译原理》课后习题答案第三章 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|ε
盛威网（www.snwei.com）专业的计算机学习网站
7
相关推荐：
loading