《编译原理》课后习答案第三章 答案： (⑤)<表达式 <表达式> 表达式 +<项 <表达式+<因子> =><表达式>十(<表达式>) <表达式 =><表达式+(<表达式>十<项>) =<表达式+(<表达式>十<因子>) =><表达式+(<表达式+i) =<表达式十(<项>十i) =<表达式>+(<因子>十i) 因子 =><表达式+(i+i) =><顶>+(i+i) 表达式 =2<因子>+(i+i) >i+(i+i) (6)<表达式 <表达式 <表达式十<项*<因子> =)<表达式>十<项>i <表达式 =<表达式十<因子>i =><表达式+i <项 ><项+i <因子 =><因子>十i <因子> =>i+ii 因子 盛威网(www.snwei.com)专业的计算机学习网站 3
《编译原理》课后习题答案第三章 答案： <表达式> <表达式> + <项> <因子> <表达式> <表达式> + <项> <因子> 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.com）专业的计算机学习网站 3
《编译原理》课后习题答案第三章 第7 证明下述文法G表达式)是二义的。 (表达式)：=(（表达式）川（表达式）（运算符）（表达式） 《运算符》：：=+日V 答案： 可为句子a+aa构造两个不同的最右推导： 最右推导1（表达式》→〈表达式》（运算符）〈表达式) →〈表达式)（运算符〉a 台（表达式）幸a 三（表达式》（运算符）（表达式）幸a 一（表达式）（运算符）a幸a （表达式）+a*a a+a*a 最右推导2（表达式）〈表达式)（运算符）（表达式 一（表达式）〈运算符)〈表达式)（运算符〉（表达式） →〈表达式)（运算符）〈表达式)（运算符）a →（表达式》（运算符〉（表达式）·a 台〈表达式)（运算符）a◆a 台（表达式）+a·a ata*a 盛成网(www.snwei.com)专业的计算机学习网站 4
《编译原理》课后习题答案第三章 第 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.com）专业的计算机学习网站 4
《编译原理》课后习答案第三章 第8题 文法G为： A-ab B-D0 该文法是否为二义的？为什么？ 答案： 对于串ahc (DS=>Ac=>abc (2)S=>aB=>abo 即存在两不同的最右推导。所以，该文法是二义的 或者： 对输入字符串abc,能构造两棵不同的语法树，所以它是二义的。 第9题 考虑下面上下文无关文法 ()表明通过此文法如 生成串+，并为该串构造酒法。 2)GS1的语言是什么 答案： (1)此文法生成串aa+a*的最右推导如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* (2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 第 8 题 文法 G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 答案： 对于串 abc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在两不同的最右推导。所以，该文法是二义的。 或者： 对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。 S a B b c S A c a b 第 9 题 考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。 S S S * S S + a a a (2)G[S]的语言是什么？ 答案： (1)此文法生成串 aa+a*的最右推导如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* (2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 盛威网（www.snwei.com）专业的计算机学习网站 5
《编译原理》课后习题答案第三章 第10题 )生成的 言是什么？ 2)该文法是二义的吗？说明理由。 答案： (1)嵌套的括号 (2)是二义的，因为对于()()可以构造两棵不同的语法树。 第山题 令文法G正为 E一→TIE+TE-T T→T*FT/E 证明+T中是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列 E=>E+T=>E+TF,所 以E+TF句型 此句型相对于E的短语有：E+T*F:相对于T的短语 有T 直接短语为：TF 句柄为：T*F 第13题 一个上下文无关文法生成句子abbaa的推导树如下： (I)给出串bbaa最左推导、最右推导。 2)该文法的产生式集合p可能有哪些元素？ 3)找出该句子的所有短语、直接短语、句柄 BB A bb a 盛成网(www.snwei.com)专业的计算机学习网站 6
《编译原理》课后习题答案第三章 第 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 盛威网（www.snwei.com）专业的计算机学习网站 6
《编译原理》课后习恩答案第三章 答案： ()串abbaa最左推导： ABS- >aBS->aSBBS->aBBS->abBS->abbS->abbAa->abbaa 最右推导 S=>ABS=>ABAa=>ABaa=ASBBaa=ASBbaa=>ASbbaa=>Abbaa=abbaa (2)产生式有：S一ABS IAale A→aB→SBBb 可能元素有：e aa ab abbaa aaabbaa (3)该句子的短语有 a是相对A的短语 是相对S的短道 b是相对B的短语 cbb是相对B的短语 aa是相对S的短语 acbbaa是相对S的短语 直接短语有：acb 句柄是：a 第14题 给出生成下述语言的上下文无关文法： (1)1a"b”abmn,m>=0月 (2)(1010,m=0 (3)wawrw属于0a*,r表示w的逆 答案： (1) SAA A-→aAble (2 S-1S0A A-0AllE (3) S→0s01se 盛威网(www.snwei.com)专业的计算机学习网站 7
《编译原理》课后习题答案第三章 答案： (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）{ an bn ambm| n，m>=0} （2）{ 1n 0m 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