《编译原理》课后习题答案第三章 第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
《编译原理》课后习题答案第三章 答案： () 表达式 + =>) +) ) +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
《编译原理》课后习恩答案第三章 第10题 文法S*SSS ()生成的语言是什么？ 2该文法是二义的吗？说明理由 答案： (1)嵌套的括号 (2)是二义的，因为对于()()可以构造两棵不同的语法树。 第11题 令文法GE为： E◆TE+TE-1 T一→TFT/F F(Ei 证明E+TF是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列 E=>E+T=>E+TF,所 以E+T*F句型 此句型相对于E的短语有E+TF:相对于T的短语 有 直接短语为：TF 句柄为：T*F ]· 第13题 一个上下文无关文法生成句子abbaa的推导树如下： (山)给出串abbaa最左推导、最右推导。 2)该文法的产生式集合P可能有哪些元素？ 3)找出该句子的所有短语、直接短语、句柄。 A B a bb a 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 第 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最左推导 AB >aBS->aSBBS->aBBS->abBS->abbS-abbAa->abbaa 最石推导： S=>ABS=>ABAa=→ABaa=→ASBBaa=>ASBbaa=>ASbbaa=→Abbaa=>abbaa (2)产生式有：S→ABS1AaeA→aB→SBBb 可能元素有：￡aaab abbaa aaabbaa (3)该句子的短语有 a是相对A的短语 ε是相对S的短请 b是相对B的短语 cbb是相对B的短语 aa是相对S的短语 acbbaa是相对S的短语 直接短语有：aeb 句柄是：a 第14题 给出生成下述语言的上下文无关文法。 (1){aba"b"1n,m>=0 2)1r1a,m>-0 (3)WaWW属于0，Wr表示W的逆 答案： (1) S-AA A→aA ble (2) S1SOIA A→0A13 (3) S→0s01S川 盛成网(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
《编译原理》课后习题答案第三章 第16 给出生成下述语言的三型文法 ()an>0} (2){abn,m>=1} 3)ab"cn,m,k>-d】 答案： (1)s→asle 2 S-aA A-aAB BbBb (3) A→aAB B→bBIC C→cCe 第17题 习题7和习题1山中的文法等价吗？ 答案： 等价。 第18题 解释下列术语和概念： (1)字母表 (2)串、字和句子 (3)语言、语法和语义 答案： (1)字母表：是一个非空有穷集合。 (2)串：符号的有穷序列。 句子，如果2X,xVT则称是文法G的一个句子 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 第 16 题 给出生成下述语言的三型文法： (1){an|n >=0 } (2) { an bm|n,m>=1 } (3){an bmc k |n,m,k>=0 } 答案： (1) S→aS|ε (2) S→aA A→aA|B B→bB|b (3) A→aA|B B→bB|C C→cC|ε 第 17 题 习题７和习题 11 中的文法等价吗？ 答案： 等价。 第 18 题 解释下列术语和概念： （１） 字母表 （２） 串、字和句子 （３） 语言、语法和语义 答案： （１）字母表：是一个非空有穷集合。 （２）串：符号的有穷序列。 字：字母表中的元素。 句子：如果 Z x , x ∈V * + T 则称 x 是文法 G 的一个句子。 盛威网（www.snwei.com）专业的计算机学习网站 8
《编译原理》课后习思答案第三章 (3)语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的 切 本符号串组成的集合 语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 盛成网(www.snwei.com)专业的计算机学习网站 9
《编译原理》课后习题答案第三章 （３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。 语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 盛威网（www.snwei.com）专业的计算机学习网站 9
《编译原理》课后习答案第三章 附加题 问题1： 给出下述文法所对应的正规式： S-0AJIB B-0S0 答案： R=(01110)(01110)广 问题2： 已知文法G,写出它定义的语言描述 GAA→0B1C C一00W1CC 答案 GA]定义的语言由0、1符号串组成，串中0和1的个数相同 问题3： 给出语言描述，构造文法 构造一文法其定义的语言是由算符+，)和运算对象a构成的算术表达式的集合 答案一 GEE一E+TT T→T'FF F→(Ea 答案二： GEE→E+EEE(E湘 问题4 己知文法GS S-dAB 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 附加题 问题 1： 给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 答案： R = (01 | 10) ( 01 | 10 )* 问题 2： 已知文法 G[A]，写出它定义的语言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案: G[A]定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同. 问题 3： 给出语言描述，构造文法. 构造一文法,其定义的语言是由算符+, *, (,)和运算对象 a 构成的算术表达式的集合. 答案一： G[E] E→E+T|T T→T* F|F F→(E)|a 答案二： G[E] E→E+E|E* E|(E)|a 问题 4： 已知文法 G[S]: S→dAB 盛威网（www.snwei.com）专业的计算机学习网站 10