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

The Exercises of Chapter Six6.2应该在numdigit产生式中再加一条语义规则：numd.count=1用来进行初始化。6.46.7 Consider the following grammar for simple Pascal-style declarations:delc var-list : typevar-list var-list, id | idtype integer | real Write an attribute grammar for the type of a variable.Solution Grammar RuleSemantic Rulesdelc var-list : typevar-list.type = type.typevar-list1 var-list2, id val-list2.type=var-list1.typeid.type=var-list1.typevar-list idid.type=var-list.typetype integer type.type= INTERGERtype realtype.type=REAL6.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 visited and the attribute values computed at each point.c. Write pseudcode for procedures that would perform the computations described in part(b).Solutiona.The grammar rules of Example 6.14S expexp exp/exp | num | num.numThe dependency graphs for each grammar rule:S exp valSisFloat etype valexpexp exp / exp isFloat etype valexpisFloat etype valexp/isFloat etype valexpexp numisFloat etype valexp valnumexp num.numisFloat etype valexp valnum.numThe dependency graphs for the expression: 5/2/2.0 valSIsFloat etype val expisFloat etype valexp/isFloat etype valexpisFloat etype valexp /isFloat etype valexpvalnum.num (2.0) val numvalnum(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: valS12 2IsFloat etype3 val 11 exp 1isFloat 4 etype val9exp/isFloat etype val10expisFloat 5etype val6exp /isFloat 7etype val8expvalnum.num (2.0) val numvalnum(5) (2)c. The pseudcode procedure for the computation of the isFloat.Function EvalisFloat(T: treenode): BooleanVar temp1, temp2: BooleanBeginCase nodekind of T ofexp: temp1= EvalisFloat(left child of T);if right child of T is not nil thentemp2=EvalisFloat( right child of T)return temp1 or temp2elsereturn temp1;num:return false;num.num:return true;endFunction Evalval(T: treenode, etype:integer): VALUEVar temp1, temp2: VALUEBeginCase nodekind of T ofS:Return(Evalval(left child of T, etype);Exp: If etype=EMPTY thenIf EvalisFloat(T) then etype:=FLOAT;Elseetype=INT;Temp1=Evalval(left child of T, etype)If right child of T is not nil thenTemp2=Evalval(right child of T, etype);If etype=FLOAT thenReturn temp1/temp2;ElseReturn temp1 div temp2;ElseReturn(temp1);Num:If etype=INTReturn(T.val);ElseReturn(T.val);Num.num:Return(T.val).6.11Dependency 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;stmtsvar-decls var-decls;var-decl|var-declvar-decl id: type-exptype-exp int|bool|array num of type-expfun-decls fun id (var-decls):type-exp;bodybody expstmts stmts;stmt| stmtstmt if exp then stmt | id:=expexp exp + exp| exp or exp | expexp|id(exps)|num|true|false|idexps exps,exp|expa. 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 of table 6.10(page 330).Solutiona. One suitable tree structure for the new function type structure:Fun(id).Type-expType-expThe typeEqual function for two function type:Function typeEqual-Fun(t1,t2 : TypeFun): BooleanVar temp : Boolean;p1,p2:TypeExpbeginp1:=t1.lchild;p2:=t2.lchild;temp:=true;while temp and p1nil and p2nil dobegintemp=typeEqual-Exp(p1,p2);p1=p1.sibling;p2=p2.sibling;endif temp then return(typeEqual-Exp(t1.rchild,t2.rchild);return(temp);endb. The semantic rules for type checking of function declaration and function call:fun-decls fun id (var-decls):type-exp; bodyid.type.lchild:=var-decls.type;id.type.rchild:=type-exp.type;insert(,id.typefun)exp id(exps)if isFunctionType(id.type) andtypeEqual-Exp(id.type.lchild,exps.type) thenexp.type=id.type.rchild;else type-error(exp)The exercise of chapter seven7.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 A in function f.b. After entry into block B in function a10;char *s = “hello”Int f(int i, int b ) int j=i;A: int i=j; Char c = bI;return 0;void g(char *s)char c=s0;B:int a5;mainint x=1x = f(x,a);g(s);return 0;Solutiona. After entry into block A in function f.Activation record of mainGlobal/static areaa9a8a7a6a5a4a3a2a1a0*(s+4): o *(s+3):l*(s+2):l*(s+1):e*s:hx: 1fpspActivation record of f after entering the Block Ai: 1b9b8b7b6b5b4b3b2b1b0 control linkreturn addressj:1i:1c:b1b. After entry into block B in function g.Activation record of mainGlobal/static areaa9a8a7a6a5a4a3a2a1a0*(s+4): o *(s+3):l*(s+2):l*(s+1):e*s:hx: 0spfpActivation record of g after entering the Block B*(s+4): o *(s+3):l*(s+2):l*(s+1):e*s:h control linkreturn addressc: ha4a3a2a1a07.8 In languages that permit variable numbers of arguments in procedure calls, one way to 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. Describe 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 ap to find the first argument and the calling sequence it would need.Solutiona. The reorganized activation record.spfp Control linkReturn addressArgument 1argument nLocal-var.The calling sequence will be:(1) store the fp as the control link in the new activation 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. The reorganized activation record.apfpArgument 1argument n sp Control linkReturn addressLocal-var. The calling sequence wil