搜索
第二章3.何谓“标志符”，何谓“名字”，两者的区别是什么？答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。（1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。（2）优先顺序为↑、+、*，同级优先采用右结合。答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256（2）1+1*2↑2*1↑2=1+1*2↑2*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）G6的语言L（G6）是什么？（2）给出句子0127、34、568的最左推导和最右推导。答：（1）由0到9的数字所组成的长度至少为1的字符串。即：L（G6）={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（其他略）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)的最左推导和最右推导。(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*(i+i)=i*(i+i)（其他略）［注］：要牢记每一步都是对最左（右）的一个非终结符号进行一步推导。(2)i+i+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|n≧1,i≧0}L2={aibncn|n≧1,i≧0}L3={anbnambm|m,n≧0}L4={1n0m1m0n|m,n≧0}答：(1)S-ABA-aAb|abB-Bc|ε(2)S-ABB-bBc|bcA-Aa|ε(3)S-AAA-aAb|ε(4)S-1S0|AA-0A1|ε［注］：可以有其他答案。EE+TE+TTFi１Fi２Fi３短语：i１,i2,i3,i１+i2,i１+i2+i3简单短语：i１,i2,i3句柄：i１