上面的文法还有另一个移进-归约冲突【精品-doc】

上面的文法还有另一个移进-归约冲突【精品-doc】 勘 误 表 2003年7月 2.13(答案 . . . 上面的文法还有另一个移进,归约冲突，在bd进栈后，面临a的情况，其冲突的原因和上面的类似。该冲突在LR(1)情况下也不存在。这样，该文法是LR(1)文法。 显然该文法的规范LR(1)项目集的集合中没有同心项目集，因此该文法也是LALR(1)文法。 4.17 答案 首先需要说明一点，历史上，C语言中有参函数定义的一般形式是: 类型标识符 函数名(形式参数列表) 形式参数声明 对于这种形式的声明，C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的， 现在ANSI新允许使用另一种方法声明形式参数，即在函数名后的括号中列出形式参数的同时，声明形式参数的类型。本题中的函数就是用这种方式声明的。现在的C编译器对于这种形式的函数声明是要进行实在参数和形式参数的个数和类型是否一致的检查的。本题就是因为这种检查才出现这个警告错误的。 我们提供两种修改方式。第一种是修改函数HypoCompare的类型。 . . . 8.1(. . . 答案 所用到的优化有复写传播、常量合并、代码外提、删除无用赋值，另外，优化使得对i，j和k的赋值都成为无用赋值而被删除，因此对i，j和k分配内存单元也成为多余，从而被取消。优化后的目标程序对应下面的C程序。 main() { register int j, k; j=1; k=6; while(j99){ j=j+k; } } 2003年1月 1.6(由/*开始，由*/结束的串构成注释，注解中间没有*/。画出接受这种注解的DFA的状态 转换图。 3.13(象习题3.4那样，用语法制导定义决定S.val。在该定义中，B的唯一综合属性是c，它给出由B产生的位对最终值的贡献。例如，101.101的最前位和最后位对值的贡献分别是4和0.125。 S , L . L | L L , L B | B B , 0 | 1 答案 先将文法改写成 S , L . R | L L , B L | B R , R B | B B , 0 | 1 所求语法制导定义如下，其中i是B的继承属性，val和c是综合属性。 S , L . R S. val := L. val + R. val S , L S. val := L. val L , B L B. i := L. c ， 2; L. c := L. c ， 2; L. val := L. val + B. c 1111 L , B B. i := 1; L. c := 1; L.val := B. c R , R B B. i := R. c / 2; R. c := R. c / 2; R. val := R. val + B. c 1111 R , B B. i := 0.5; R. c := 0.5; R. val := B. c B , 0 B. c := 0 B , 1 B. c := B. i 分析 首先，从B推出的串是不可能知道这个B在串中的具体位置的，因此也不可能计算它的贡献。这样B必须有继承属性，它被用来计算B的贡献。对于一个二进制数，如101.101，对于小数点前的1，我们需要知道它处在从右向左数的第几位上;而对于小数点后的1，我们需要知道它处在从左向右数的第几位上。考察原来的文法，从下面图3.5的分析树可以看出，不管是小数点前还是后，它都是一种自左向右的归约，适合于自左向右地计数。这样，小数点左边就需要用继承属性来计数，这就增加了难度。而且，由于小数点左右都是用非终结符L，那么，L就即要有综合属性来用于从自左向右地计数，又要有继承属性来用于自右向左地计数，显然语法制导定义的难度会大大增加。所以我们采用改写文法的办法，让分析树是图3.6的形式。这样，小数点两边的归约方式不一样，适合于不同方向的计数，使我们的语法制导定义能简洁得多。 S S L . L L . R L B L B B L R B L B L B R L B B B B B B 图3.6 不同归约方式的分析树 图3.5 都是自左向右归约的分析树 由于在分析树中一个B对应一个L(小数点左边)或一个R(小数点右边)，那么我们用L和R的c属性来表示每一位的贡献，然后传给B的继承属性i。如果B是1，那么B的c属性就等于它的i属性，否则就等于0。 如果不限制B的综合属性的个数及其含义，那么可以写出更简单的语法制导定义，无 需继承属性。另外，为了使语义规则简明，我们在本题使用了非L属性的语法制导定义。 从本习题，我们再次看到，掌握修改文法的技巧对设计语法制导定义是很有用的。 5.6 一个C语言程序如下: func(i1,i2,i3) long i1,i2,i3; { long j1,j2,j3; printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3); printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3); } main() { long i1,i2,i3; func(i1,i2,i3); } 该程序在X86/Linux机器上的运行结果如下: Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434 从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。 答案 图5.1给出了栈式分配的活动的一般情况，通返回值 常临时数据区在活动记录栈中靠近栈顶的地方。由于C参数 语言对实在参数表达式的计算是采用自右向左的方式，栈 可能有的控制链 因此在main函数中，实在参数进栈的次序是i3,i2和i1。增如果栈是向低地址方向增长，那么i1,i2和i3的地址是长可能有的访问链 逐渐增大。 方保存的机器状态 向 对于局部变量j1,j2和j3来说，它们在局部数据区 局部数据 的分配是按照它们在变量声明中出现的次序。如果栈是 临时数据 向低地址方向增长，那么j1,j2和j3的地址是逐渐减小。 因此出现这种不一致的情况。 图5.1 一般活动记录 2002年12月 1.12题 在图1.13、1.14和1.15中，状态2到状态4的边上的标记应该改成b，见下面: start a a 0 1 2 b b b a 3 4 b b 图1.13 一个DFA start a a 0 1 2 b b b 4 b 图1.14 最简DFA start a a 0 1 2 a b b b a a 5 3 4 b a, b b 图1.15 加入死状态后的DFA 2.23题 在图2.9中，项目集I中的S,应该改成S，见下面: 2 S, , . S, $ b S , .a A c, $ A , b . A b, c A , b . A b, b I 0A , b. , c A , b. , b a A , . b A b, b A , . b A b, b b b A , . b, b A , . b, b S , a . A c, $ I I 46A , . b A b, c A , . b, c I2 图2.9 部分LR(1)项目集 2.27题 答案中的非二义且非LR(1)的文法有误，应该按如下修改。同时需修改相应的分 析。 答案 该语言的一个LR(1)文法是 S , A B A , a a A b | a b | , B , B b | , 该语言的一个二义文法是 S , A A S b | , A , a | , 该语言的一个非二义且非LR(1)的文法是 S , a a S b | A A , a B b | B B , B b | , 分析 先看LR(1)文法。和2.25题相比，A , a a A b用来将两个a和一个b同时归约，以保证a的个数不会超过b的个数的两倍。因为a的个数可能是奇数，所以有产生式A , a b，并且a的个数可能是奇数时，第一步就是将ab归约成A。 再看二义文法。用类似于2.25题的思想来写一个类似的文法是可能的。那就是 S , a a S b | S b | a b | , 但是我们这儿用了完全不同的方法。 S , A A S b | ,使得S推出的A的个数是b的两倍。由于A可以用a或,来重写，因此最终a的个数不会超过b个数的两倍。由于产生式没有限制一定是哪些A重写成a，哪些A重写成,，因此该文法是二义的。 最后看非二义且非LR(1)的文法。该文法的特点是，在空归约后，先做若干次一个b的归约，然后可能做一次一个a和一个b的归约，最后做若干次两个a和一个b的归约。问题是，向前看一个符号无法确定究竟先做多少次一个b的归约才是合适的。 3.8题 题目中的2 2 2应该改成1 2 2，见下面: (a) 写一个翻译，它输出每个a的嵌套深度。例如，对于句子( a , ( a , a) )，输出的结果是1 2 2。 3.10题 答案中的翻译方案应该增加一个语句，修改如下: S , {E. val := any}E E , { if E. val = left then print ( “error”); E. val := left}E := {E. val := any}E 1122 E , { if E. val = left then print ( “error”); E. val := any}E + {E. val := any} E 1122 E , { E. val := E. val } ( E ) 11 E , id 3.17题 函数function T遗漏了T , id {T. nptr := mkleaf ( id, id. entry )}的情况，需要加上，修改如下: function T : , syntax_tree_node; var nptr, nptr1: , syntax_tree_node; val : integer; entry : , symbol_table_entry; begin if lookahead = ‘(‘ then /, 产生式T , ( E ) ,/ begin match ( ‘(‘ ); nptr1 := E; match ( ‘)’ ); nptr := nptr1 end else if lookahead = num then /, 产生式T , num ,/ begin val := lexval; match (num); nptr := mkleaf (num, val ) end else if lookahead = id then /, 产生式T , id ,/ begin entry := lexval; match (id); nptr := mkleaf (id, entry ) end else error; return nptr end; 5.13题 图5.7的修改如下: ret a b addm 图5.7 活动树 5.16题 答案的修改如下: 程序运行时陷入死循环的原因是由于p指向分配给i的存储单元引起的。循环体执行一 次便停止是由于p指向分配给i的低位字节引起的。 6.9题 该题对于第一种定义的解答改成下面的形式更合理一些。 t := E11 t := E 22 t := E 33 if t> tgoto L1 1 3 v := t 1 L2: S if v = t goto L13 v := v + t 2 if v , t goto L2 3 L1: