编译原理第三章答案

第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。答案：L(G[S])={abc}第2题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[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|DD-0|1|2|3|4|5|6|7|8|9第4题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。答案：Z=aZb=aaZbb=aaa..Z...bbb=aaa..ab...bbbL(G[Z])={anbn|n=1}第5题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答案：(1)允许0开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6题已知文法G：表达式::=项｜表达式＋项项::=因子｜项*因子因子::=（表达式）｜i试给出下述表达式的推导及语法树。（５）i+(i+i)（６）i+i*i第8题文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=Ac=abc(2)S=aB=abc即存在两不同的最右推导。所以，该文法是二义的。或者：第10题文法S→S(S)S|ε(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。第14题给出生成下述语言的上下文无关文法：（1）{anbnambm|n，m=0}（2）{1n0m1m0n|n，m=0}（3）{WaWr|W属于{0|a}*，Wr表示W的逆}答案：（１）S→AAA→aAb|ε（２）S→1S0|AA→0A1|ε（３）S→0S0|1S1|ε第16题给出生成下述语言的三型文法：(1){an|n=0}(2){anbm|n,m=1}(3){anbmck|n,m,k=0}答案：(1)S→aS|ε(2)S→aAA→aA|BB→bB|b(3)A→aA|BB→bB|CC→cC|ε第18题解释下列术语和概念：（１）字母表（２）串、字和句子（３）语言、语法和语义答案：（１）字母表：是一个非空有穷集合。（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。附加题问题1：给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：R=(01|10)(01|10)*问题2：已知文法G[A]，写出它定义的语言描述G[A]:A→0B|1CB→1|1A|0BBC→0|0A|1CC答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.问题3：给出语言描述，构造文法.构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案一：G[E]E→E+T|TT→T*F|FF→(E)|a答案二：G[E]E→E+E|E*E|(E)|a问题4：已知文法G[S]:S→dABA→aA|aB→ε|bB相应的正规式是什么？G[S]能否改写成为等价的正规文法？答案：正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dAA→a|aBB→aB|a|b|bCC→bC|b也可为(观察得来):G[S]:S→dAA→a|aA|aBB→bB|ε问题5：已知文法G：E→E+T|E-T|TT→T*F|T/F|FF→(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)