北方工业大学编译原理习题集VIP免费

编译原理课后习题（修订版）第二章高级语言及其语法描述3、何谓“标识符”，何谓“名字”，两者的区别是什么？解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有其他含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。4、令＋、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值：（1）、优先顺序（从高至低）为＋、*和↑，同级优先采用左结合。（2）、优先顺序为↑、＋、*，同级优先采用右结合。解：（1）、1＋1*2↑*1↑2=2*2↑*1↑2=4↑*1↑2=4↑↑2=（2）、1＋1*2↑*1↑2=6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9（1）、G6的语言L(G6)是什么？（2）、给出句子0127、34和568的最左推导和最右推导。分析：根据产生式N→D∣ND可以看出，N最终可推导出1个或多个（可以是无穷多个）D，根据产生式D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9可以看出，每个D可以推导出0至9中的某一个数字。因此，N最终推导出的是由0到9这10个数字组成的字符串。解：（1）、L(G6)是由0到9这10个数字组成的字符串。（2）、句子0127、34和568的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568句子0127、34和568的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687、写一个文法，使其语言是奇数集，且每个奇数不以0开头。分析：本题要构造一个文法，由它产生的句子是奇数，且不以0开头。也就是说它的每个句子都以1、3、5、7、9中某数结尾。如果数字只有一位，则满足要求；如果有多位，则要求第一位不能是0；而中间有多少位，每位是什么数字则没有要求。因此我们可以把这个文法分3部分完成，分别用3个非终结符来产生句子的第一位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1到9中的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。解：G(S)：A→2∣4∣6∣8∣DB→A∣0C→CB∣AD→1∣3∣5∣7∣9S→CD∣D8、令文法为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）最左推导为：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>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)最右推导为：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>F*F=>F*(E)=>F*(E+T)=>F*(E+F)=>F*(E+i)=>F*(T+i)=>F*(F+i)=>F*(i+i)=>i*(i+i)（2）语法树：9、证明下面的文法是二义的：S→iSeS∣iS∣i分析：根据文法二义性定义，如果要证明该文法是二义的，必须找到一个句子TE+EFi+TFiiE+TEFi*TFiTFiEE-TEFiTFi-FiETF使该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法根据我们对程序语言的了解，不难发现这个文法应该是用来表示if…else…结构的（用“i”表示“if”或语句集，用e代表else）。因此我们就要到if…else…结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。解：考虑句子iiiei，存在如下两个最右推导：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>iiiei由此该文法是二义的。10、把下面文法改为无二义的：S→SS∣(S)∣()分析：本题给出的文法是二义的，关键在于S→SS是产生二义性的根源。我们将该产生式改造成等价的递归结构，消除二义性。解：S→TS∣T，T→(S)∣()11、给出下面语言的相应文法：L1={anbnci∣n≥1，i≥0}，L2={aibncn∣n≥1，i≥0}L3={anbnambm∣n，m≥0}L4={1n0m1m0n∣n，m≥0}分析...