编译原理-课后题答案

1、第二章3. 何谓“标志符” ，何谓“名字” ，两者的区别是什么 答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。4. 令+、*和f代表加、乘和乘幕，按如下的非标准优先级和结合性质的约定，计算1 + 1*2 f2*1 f 2的值。(1 )优先顺序(从高到低)为 +、*和f,同级优先采用左结合。(2)优先顺序为f、 +、*，同级优先采用右结合。答：(1) 1+1*2f 2*1 f 2=2*2f 2*1 f 2=4f 2*1 f 2=4f 2f 2=16f 2=256(2) 1+1*2f 2*1f 2=1+1*2f 2*1=1+1*4*1=2*4*1=2*4=86. 令文法 G6 为

2、N- D|NDD-0|1|2|3|4|5|6|7|8|9( 1 ) G6 的语言 L( G6 )是什么(2)给出句子 0127、 34、 568 的最左推导和最右推导。答：(1)由0到9的数字所组成的长度至少为1的字符串。即：L(G)=dn|n仝1,d 0,1,9( 2) 0127 的最左推导： N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>01270127 的最右推导： N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 (

3、其他略)7. 写一个文法,使其语言是奇数集,且每个奇数不以 0 开头。答： G( S)： S->+N|-NN->ABC|CC->1|3|5|7|9A->C|2|4|6|8B->BB|0|A|£注：可以有其他答案。常见的错误 ：N->2N+1原因在于没有理解形式语言的表示法,而使用了数学表达式。8. 令文法为E->T|E+T|E-TT->F|T*F|T/FF->(E)|i(1)给出i+i*i 、i*(i+i)的最左推导和最右推导。给出i+i+i、i+i*i和i-i-i 的语法树，并给出短语，简单短语和句柄。答：i*(i+i) 的最左

4、推导：E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=>i*(i+i)i*(i+i) 的最右推导：E=>T=>T*F=>T*(E) F*(i+i) => i*(i+i)(其他略)注:要牢记每一步都是对(2) i+i+i的语法树：=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>最左(右)的一个非终结符号进行一步推导。短语：i 1,

5、i 2, i 3, i i + i 2, i i+i 2+ i 3简单短语：i 1, i 2, i 3T*(i+i)=>(其他略)9.证明下面的文法是二义的：证明：反例法：对于该文法的句子iiieiS->iSeS|iS|i有两个最右推导如下，所以该文法是二义的:S=>iS=>iiSeS=>iiSei=>iiieiS=>iSeS=>iSei=>iiSei=>iiiei10. 把下面的文法改写成无二义的： S->SS|(S)|()答：假设规定左结合的顺序，可以改造成无二义文法如下：s->s(t)|(s)|()t- >S| £注：大纲不要求掌握，作为参考11. 给出下面语言的相应文法：Li=a nbnci|n 仝 1,i 仝 0L2=aibncn|n 仝 1,i 仝 0n n m mL3=a b a b |m,n = 0n m m nL4=1 0 1 0 |m,n = 0答： (1) S->AB A->aAb|ab B->Bc|(2) S->AB B->bB