编译原理与实践第六七章答案

《编译原理与实践第六七章答案》由会员分享，可在线阅读，更多相关《编译原理与实践第六七章答案（11页珍藏版）》请在装配图网上搜索。

1、The Exercises of Chapter Six 6.2 应该在num→digit产生式中再加一条语义规则：numd.count=1用来进行初始化。 6.4 6.7 Consider the following grammar for simple Pascal-style declarations: delc → var-list : type var-list → var-list, id | id type → integer | real Write an attribute grammar for the type of a vari

2、able. [Solution] Grammar Rule Semantic Rules delc → var-list : type var-list.type = type.type var-list1 → var-list2, id val-list2.type=var-list1.type id.type=var-list1.type var-list → id id.type=var-list.type type → integer type.type= INTERGER type → real

3、 type.type=REAL 6.10 a. Draw dependency graphs corresponding to each grammar rule of Example 6.14 (Page 283) , and for the expression 5/2/2.0. b. Describe the two passes required to compute the attributes on the syntax tree of 5/2/2.0, including a possible order in which the nodes could be vis

4、ited and the attribute values computed at each point. c. Write pseudcode for procedures that would perform the computations described in part(b). [Solution] a. The grammar rules of Example 6.14 S → exp exp → exp/exp | num | num.num The dependency graphs for each grammar rule: S → ex

5、p val S isFloat etype val exp exp → exp / exp isFloat etype val exp isFloat etype val exp / isFloat etype val exp exp → num isFloat etype val exp val num exp → num.num isFloat etype val exp

6、 val num.num The dependency graphs for the expression: 5/2/2.0 val S IsFloat etype val exp isFloat etype val exp / isFloat etype val exp isFloat etype val exp / isFloat etype val exp val num.num (2.0) val

7、 num val num (5) (2) b. The first pass is to compute the etype from isFloat. The second pass is to compute the val from etype. The possible order is as follows: val S12 2IsFloat etype3 val 11 exp 1 isFloat 4 etype val9 exp / isFloat etype val10 e

8、xp isFloat 5etype val6 exp / isFloat 7etype val8 exp val num.num (2.0) val num val num (5) (2) c. The pseudcode procedure for the computation of the isFloat. Function EvalisFloat(T: treenode): Boolean Var temp1, temp2: B

9、oolean Begin Case nodekind of T of exp: temp1= EvalisFloat(left child of T); if right child of T is not nil then temp2=EvalisFloat( right child of T) return temp1 or temp2 else return temp1; num: return false; num.num: return true; end Function

10、Evalval(T: treenode, etype:integer): VALUE Var temp1, temp2: VALUE Begin Case nodekind of T of S: Return(Evalval(left child of T, etype)); Exp: If etype=EMPTY then If EvalisFloat(T) then etype:=FLOAT; Else etype=INT; Temp1=Evalval(left child of T, etype) If rig

11、ht child of T is not nil then Temp2=Evalval(right child of T, etype); If etype=FLOAT then Return temp1/temp2; Else Return temp1 div temp2; Else Return(temp1); Num: If etype=INT Return(T.val); Else Return(T.val); Num.num: Return(T.val).

12、 6.11 Dependency graphs corresponding to the numbered grammar rules in 6.4: Dependency graph for the string ‘3 *(4+5) *6: 6.21 Consider the following extension of the grammar of Figure 6.22(page 329) to include function declarations and calls: program → var-decls;fun-decls;stmts var-dec

13、ls → var-decls;var-decl|var-decl var-decl → id: type-exp type-exp → int|bool|array [num] of type-exp fun-decls → fun id (var-decls):type-exp;body body → exp stmts → stmts;stmt| stmt stmt → if exp then stmt | id:=exp exp → exp + exp| exp or exp | exp[exp]|id(exps) |num|true|false|id

14、 exps→ exps,exp|exp a. Devise a suitable tree structure for the new function type structure, and write a typeEqual function for two function types. b. Write semantic rules for the type checking of function declaration and function calls(represented by the rule exp →id(exps)),similar to rules o

15、f table 6.10(page 330). [Solution] a. One suitable tree structure for the new function type structure: Fun (id) …. Type-exp Type-exp The typeEqual function for two function type: Function typeEqual-Fun(t1,t2 : TypeFun): Boolean Var temp : Boolean; p1,p2:TypeExp

16、 begin p1:=t1.lchild; p2:=t2.lchild; temp:=true; while temp and p1<>nil and p2<>nil do begin temp=typeEqual-Exp(p1,p2); p1=p1.sibling; p2=p2.sibling; end if temp then return(typeEqual-Exp(t1.rchild,t2.rchild)); return(temp); end b. The semantic

17、 rules for type checking of function declaration and function call: fun-decls → fun id (var-decls):type-exp; body id.type.lchild:=var-decls.type; id.type.rchild:=type-exp.type; insert(id.name,id.typefun) exp → id(exps) if isFunctionType(id.type) and ty

18、peEqual-Exp(id.type.lchild,exps.type) then exp.type=id.type.rchild; else type-error(exp) The exercise of chapter seven 7.2 Draw a possible organization for the runtime environment of the following C program, similar to that of Figure 7.4 (Page 354). a. After entry into block

19、A in function f. b. After entry into block B in function g. int a[10]; char *s = “hello” Int f(int i, int b[ ]) { int j=i; A: { int i=j; Char c = b[I]; … } return 0; } void g(char *s) { char c=s[0]; B:{ int a[5]; … } } main { int x=1 x = f(x,a); g(s);

20、 return 0; } [Solution] a. After entry into block A in function f. Activation record of main Global/static area a[9] a[8] a[7] a[6] a[5] a[4] a[3] a[2] a[1] a[0] *(s+4): o *(s+3):l *(s+2):l *(s+1):e *s:h x: 1 fp sp Activation record of f after entering the Block A i:

21、1 b[9] b[8] b[7] b[6] b[5] b[4] b[3] b[2] b[1] b[0] control link return address j:1 i:1 c:b[1] b. After entry into block B in function g. Activation record of main Global/static area a[9] a[8] a[7] a[6] a[5] a[4] a[3] a[2] a[1] a[0] *(s+4): o *(s+3):l *(s+2):l

22、 *(s+1):e *s:h x: 0 sp fp Activation record of g after entering the Block B *(s+4): o *(s+3):l *(s+2):l *(s+1):e *s:h control link return address c: h a[4] a[3] a[2] a[1] a[0] 7.8 In languages that permit variable numbers of arguments in procedure calls, one way t

23、o find the first argument is to compute the arguments in reverse order, as described in section 7.3.1, page 361. a. One alternative to computing the arguments in reverse would be to reorganize the activation record to make the first argument available even in the presence of variable arguments. Des

24、cribe such an activation record organization and the calling sequence it would need. b. Another alternative to computing the arguments in reverse is to use a third point(besides the sp and fp), which is usually called the ap (argument pointer). Describe an activation record structure that uses an a

25、p to find the first argument and the calling sequence it would need. [Solution] a. The reorganized activation record. sp fp Control link Return address Argument 1 … argument n Local-var ….. The calling sequence will be: (1) store the fp as the control link in the new act

26、ivation record; (2) change the fp to point to the beginning of the new activation record; (3) store the return address in the new activation record; (4) compute the arguments and store their in the new activation record in order; (5) perform a jump to the code of procedure to be called. b. Th

27、e reorganized activation record. ap fp Argument 1 … argument n sp Control link Return address Local-var ….. The calling sequence will be: (1) set ap point to the position of the first argument. (2) compute the arguments and store their in the new activation record in order; (

28、3) store the fp as the control link in the new activation record; (4) change the fp to point to the beginning of the new activation record; (5) store the return address in the new activation record; (6) perform a jump to the code of procedure to be called. 7.15 Give the output of the following p

29、rogram(written in C syntax) using the four parameter methods discussed in section 7.5. #include int i=0; void p(int x, int y) { x +=1; i +=1; y +=1; } main { int a[2]={1,1}; p(a[i], a[i]); printf(“%d %d\n”, a[0], a[1]); return 0; } [Solution] pass by value: 1, 1 pass by reference: 3, 1 pass by value-result: 2, 1 pass by name: 2, 2