《编译原理》课后习题答案第三章 第16 给出生成下述语言的三型文法 (1)fan>=01 2{abn,m>=1) 3)ab"cm.m,k>=0】 答案 (1)S-aS] 2 S-aA A-aA/B B→bBb (3) AAIB 第17题 习题7和习题山中的文法等价吗？ 答案： 等价。 第18题 解释下列术语和授念： (1)字母表 (2)串、字和句子 (3)语言、语法和语义 答案： (1)字母表：是一个非空有穷集合。 (2)串：符号的有穷序列。 高索生莲xev中男新思文法0的一个子。 字：字 盛成网(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)专业的计算机学习网站
《编译原理》课后习题答案第三章 （３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。 语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 盛威网（www.snwei.com）专业的计算机学习网站 9
《编译原理》课后习题答案第三章 附加题 问愿1： 给出下述文法所对应的正规式： -0A1B A-1S1 B-→0S0 答案： R=(01110)(01110) 问题2： 已知文法GA,写出它定义的语言描述 GAA→0B1 B→11A0BB C→00A1CC 答案 GA]定义的语言由0、1符号串组成，串中0和1的个数相同 问题3： 给出语言描述，构造文法 构造一文法其定义的语言是由算符+，气，和运算对象构成的算术表达式的集合 答案一： GEE→E+TT T→TF F→(E 答案二： GEE-→E+EE'E(Ea 问题： 己知文法GS啡 S-dAB 盛成网(www.snwei.com)专业的计算机学习网站 6
《编译原理》课后习题答案第三章 附加题 问题 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
《编译原理》课后习恩答案第三章 A-aAla B→ebB 相应的正规式是什么？GS能否改写成为等价的正规文法？ 答案 正规式是daa*b*: 相应的正规文法为（由自动机化简来）： GS:s→dAA→aaBB-aBlalbbC C-bCb 也可为（观察得来）GSS→dAA→ajaAlaB B→bBE 问题5： 已知文法G: -E+TE-TT T-T-FT/FF F→(Ei 试给出下述表达式的推导及语法树 (山G (2)i*+i ③)+i1 ()++i 答案 (I)E->T->F->i (2)E=>E+T->T+T->T*F+T->F*F+T->i*F+T->i*i+T->ii+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>HT=>i+T*F=>i+F+F=>i+i+F=>itii (4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>iHiti) 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 A→aA|a B→ε|bB 相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 答案： 正规式是 daa*b*； 相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 问题 5： 已知文法 G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i 试给出下述表达式的推导及语法树 (1) i; (2) i*i+i (3) i+i*i (4) i+(i+i) 答案： (1)E=>T=>F=>i (2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i (4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) E E E + T T T * F F i i E + T i T F i F i E E + T E + T i T F F ( E ) i T F i F T F i F i (1) (2) (3) (4) 盛威网（www.snwei.com）专业的计算机学习网站 11
《编译原理》课后习题答案第三章 问题6： 已知文法GE E-ET+1 T-TF+F F-Fa 试证：FA是文法的句型，指出该句型的短语、简单短语和句柄 答案 该句型对应的语法树如下： 该句型相对于E的复语有FF 相对于T的短语有FF幸， 相对于F的短语有FF 简单短语有F,F 句柄为F F 问题7： 适当变换文法，找到下列文法所定义语言的一个无二义的文法： s→Sas|ShS|ses|d 答案 该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。 设α、b和c的优先级别依次增高，根据优先级联规则将文法变换为： S→SaS|A A→AbAC c→ccc|d 规定结合性为左结合，进一步将文法变换为： s→saA A→AbC IC C-CCFF F-d 该文法为非二义的。 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 问题 6： 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 答案： 该句型对应的语法树如下： 该句型相对于 E 的短语有 FF^^* 相对于 T 的短语有 FF^^*,F 相对于 F 的短语有 F^;F^^ 简单短语有 F;F^ 句柄为 F. 问题 7： 适当变换文法，找到下列文法所定义语言的一个无二义的文法： S → SaS ⏐ SbS ⏐ ScS ⏐ d 答案： 该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。 设 a、b 和 c 的优先级别依次增高，根据优先级联规则将文法变换为： S → SaS ⏐ A A → AbA ⏐ C C → CcC ⏐ d 规定结合性为左结合，进一步将文法变换为： S → SaA⏐ A A → AbC ⏐C C → CcF ⏐ F F → d 该文法为非二义的。 盛威网（www.snwei.com）专业的计算机学习网站 12