《编译原理》课后习题答案第三章 第3章文法和语言 第1题 文法G=(A,B.S,a,bcP,S其中P为 A→ab Bbc 写出L(GS的全部元素。 答案 L(GIS]abc 第2题 文法GN为： N-DND D→01234 答案： GN]的语言是V+。V=0,1,2,3,4,56,7,8,9; N=>ND->NDD.->NDDDD.D->D.D 或者：允许0开头的非负整数？ 第3题 为只包含数字、加号和减号的表达式，例如9-2十5,31,7等构造一个文法。 答案： GIS]: S->S+DIS-DID D->011I23451671819 第4题 已知文法G小： Z-aZbab 写出L(GZ的全部元素。 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 第 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=>D.D 或者：允许 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.com）专业的计算机学习网站 1
《编译原理》课后习恩答案第三章 答案： Z->aZb->aaZbb->aaa.Z.bbb->aaa.ab.bbb L(G[ZD)=fa'b"n>=1; 第3题 写一文法，使其语言是偶正整数的集合。要求： 山)允许0打头： (2不允许0打头 答案： (1)允许0开头的偶正整数集合的文法 E-NTD TNTID N-D359 D-→02441618 (2)不允许0开头的偶正整数集合的文法 ENTID T→FTG N-DI55179 D-→24618 F-N10 G→DI0 第6题 已知文法G: <表达式<项>|<表达式十<项 <项<因子>|<项><因子> <因子>=（表达式）1山 试给出下述表达式的推导及语法树。 (5)i+i+i (6)+ii 盛咸网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 答案： Z=>aZb=>aaZbb=>aaa.Z.bbb=> aaa.ab.bbb L(G[Z])={an b n |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.com）专业的计算机学习网站 2
《编译原理》课后习题答案第三章 答案： ()<表达式 <表达式> 表达式 +<项 =><表达式十<因子> =><表达式+(<表达式>) <表达式 =<表达式+(<表达式>+<项>) <表达式+(<表达式十<因子>) <表达式D+(<表达式+i) =><表达式十(<项>+i) ><表达式+(<因子>+i) =><表达式+(i+i) =><项>+(i+) ><因子>+(i+i) =>i+(i+i) (6)<表达式 <表达式 =<表达式十<项 =<表达式>十<项>*<因子> =之<表达式>十<项>i 表达式 =><表达式十<因子>i ><表达式十南 项+润 因子 =><因子>+ii <因子> =i+街 盛成网(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(表达式)是二义的 (表达式)：=(（表达式）川（表达式）（运算符）（表达式） 〈运算符)：=州 答案 可为句子a+aa构造两个不同的最右推导 最右推导1〈表达式)→〈表达式》〈运算符)〈表达式) →（表达式）（运算符）a 台〈表达式)*a →（表达式）（运算符）（表达式）*a 三《表达式)（运算符）a*a →（表达式）+a*a *a 最右推导2（表达式） 达式 〈运算符)〈表达式 →〈表达式》（运算符）〈表达式)（运算符）（表达式） →〈表达式（运算符〉〈表达式）《运算符〉日 →〈表达式》（运算符）〈表达式)◆a →〈表达式)（运算符）a*a 〈表达式)+a·a =ataa 盛咸网(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题 文法GS为： A-ab B-be 该文法是否为二义的？为什么？ 答案 对于串abc (2)S=>aB=> 即存在两不同的最右推导。所以，该文法是二义的 或者： 对输入字符串abc,能构造两棵不同的语法树，所以它是二义的。 第9题 考虑下面上下文无关文法 ()表明通过此文法如何生成串aa+a*,并为该串构造语法树。 (2)GS1的语言是什么？ 答案： (1)此文法生成串aa+a*的最右推导如下 S=>SS*=>SS*=>S3*=>SSt*=>S4t*=>t* (2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 盛成网(www.snwei.com)专业的计算机学习网站 5
《编译原理》课后习题答案第三章 第 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