《编译原理第二章-课后题答案(3页).doc》由会员分享，可在线阅读，更多相关《编译原理第二章-课后题答案(3页).doc（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-编译原理第二章-课后题答案-第 3 页第二章3.何谓“标志符”，何谓“名字”，两者的区别是什么？答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。4.令+、*和代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*22*12的值。（1）优先顺序（从高到低）为+、*和，同级优先采用左结合。（2）优先顺序为、+、*，同级优先采用右结合。答：（1）1+1*22*12=2*22*12=42*12=422=162=256（2）1+1*22*12=1+1*22*1=1+1*4*1=2*4*1=2*4=86.令文法G6为N-D|NDD-0|1|2|3|4|5|6|7|8|9（1
2、）G6的语言L（G6）是什么？（2）给出句子0127、34、568的最左推导和最右推导。答：（1）由0到9的数字所组成的长度至少为1的字符串。即：L（G6）=dn|n1,d0,1,9 （2）0127的最左推导：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127 0127的最右推导：N=ND=N7=ND7=N27=ND27=N127=D127=0127 （其他略）7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。答：G（S）：S-+N|-NN-ABC|C C-1|3|5|7|9 A-C|2|4|6|8 B-BB|0|A|注：可以有其他答案。常见的错误：N-2N+1
3、原因在于没有理解形式语言的表示法，而使用了数学表达式。8.令文法为E-T|E+T|E-TT-F|T*F|T/FF-(E)|i(1)给出i+i*i、i*(i+i)的最左推导和最右推导。(2)给出i+i+i、i+i*i和i-i-i的语法树，并给出短语，简单短语和句柄。答：(1) i*(i+i)的最左推导：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) =T*(E+T)=T*(E+F)=T*(E+i)=T*(T+i)=T*(F+i)= T*(i+i)= F
4、*(i+i) = i*(i+i)（其他略）注：要牢记每一步都是对最左（右）的一个非终结符号进行一步推导。(2) i+i+i的语法树：EE+TE+TTFiFiFi短语：i, i2, i3, i+ i2, i+i2+ i3简单短语：i, i2, i3句柄：i（其他略）.证明下面的文法是二义的：S-iSeS|iS|i证明：反例法：对于该文法的句子iiiei有两个最右推导如下，所以该文法是二义的：S=iS=iiSeS=iiSei=iiieiS=iSeS=iSei=iiSei=iiiei10.把下面的文法改写成无二义的：S-SS|(S)|()答：假设规定左结合的顺序，可以改造成无二义文法如下：s-s(t)|(s)|()t-s|注：大纲不要求掌握，作为参考11.给出下面语言的相应文法：L1=anbnci|n1,i0L2=aibncn|n1,i0L3=anbnambm|m,n0L4=1n0m1m 0n|m,n0答：(1) S-AB A-aAb|ab B-Bc| (2) S-AB B-bBc|bc A-Aa|(3) S-AA A- aAb|(4) S-1S0|A A- 0A1|注：可以有其他答案。