《编译原理与实践第六七章.doc》由会员分享，可在线阅读，更多相关《编译原理与实践第六七章.doc（11页珍藏版）》请在三一文库上搜索。
1、The Exercises of Chapter Six6.2应该在 num digit 产生式中再加一条语义规则：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 | realWrite an attribute grammar for the type of a variable.SolutionGrammar RuleSemanti
2、c Rulesdelc var-list : typevar-list.type = type.typevar-list1 var-list2, idval-list2.type=var-list1.typeid.type=var-list1.typevar-list idid.type=var-list.typetype integertype.type= INTERGERtype realtype.type=REAL6.10 a. Draw dependency graphs corresponding to each grammar rule of Example 6.14 (Page2
3、83) , 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 com
4、putations described in part(b).Solutiona. The grammar rules of Example 6.14 S expexp exp/exp | num | num.numThe dependency graphs for each grammar rule:S expvalSisFloatetypevalexpexpexp / expisFloatetypevalexpisFloatetypevalexp/isFloatetypevalexpexp numisFloatetypevalexpvalnumexp num.numisFloatetype
5、valexpvalnum.numThe dependency graphs for the expression: 5/2/2.0valSIsFloatetypevalexpisFloatetypevalexp/isFloatetypevalexpisFloatetypevalexp/isFloatetypevalexpvalnum.num(2.0)valnum(5)valnum(2)b. The first pass is to compute theetype from isFloat .The second pass is to compute the val from etype.Th
6、e possible order is as follows:valS122IsFloatetype3 val11exp1isFloat 4 etypeval9exp/isFloatetypeval10expisFloat5etypeval6exp/isFloat7etypeval8expvalnum.num(2.0)valnumvalnum(5)(2)c. The pseudcode procedure for the computation of the isFloat. Function EvalisFloat(T: treenode): BooleanVar temp1, temp2:
7、 Boolean BeginCase nodekind of T of exp: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): V ALUEVar temp1, temp2: VALUE
8、BeginCase nodekind of T ofS:Return(Evalval(left child of T, etype);Exp:If etype=EMPTY thenIf EvalisFloat(T) then etype:=FLOAT;Else etype=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
9、 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)
10、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 ex
11、p | 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
12、(exps),similar to rules of table 6.10(page330).Solutiona. One suitable tree structure for the new function type structure:Fun(id)Type-exp .Type-expThe typeEqual function for two function type:Function typeEqual-Fun(t1,t2 : TypeFun): BooleanVar temp : Boolean;p1,p2:TypeExpbeginp1:=t1.lchild;p2:=t2.lc
13、hild;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-ex
14、p; bodyid.type.lchild:=var-decls.type;id.type.rchild:=type-exp.type;insert(id.name,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 runtim
15、e 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 g.int a10;void g(char *s)mainchar *s =“ hello ”char c=s0;int x=1B: int a5;x = f(x,a);Int f(int i, int b )g(s);int j=i;return 0;A: int i
16、=j;Char c = bI;return 0;Solutiona. After entry into block A in function f.a9a8a7Global/static areaa6a5a4a3a2a1a0*(s+4): o*(s+3):l*(s+2):l*(s+1):e*s:hx: 1Activation record of maini: 1b9b8b7b6b5b4Activationrecord of f afterb3entering the Block Ab2b1b0fpcontrol linkreturn addressj:1i:1c:b1spfpspb. Afte
17、r entry into block B in function g.a9a8a7a6a5a4a3a2a1a0*(s+4): o*(s+3):l*(s+2):l*(s+1):e*s:hx: 0*(s+4): o*(s+3):l*(s+2):l*(s+1):e*s:hcontrol linkreturn addressc: ha4a3a2a1a0Global/static areaActivation record of mainActivationrecordofg afterentering the Block B7.8 In languages that permit variable n
18、umbers 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
19、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
20、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.Control linkfpReturn addressArgument 1argument nLocal-varsp.The calling sequence will be:(1) store the fp as the control link in the new activ
21、ation 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
22、 activation record.apArgument 1argument nfpControl linkReturn addressspLocal-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;(3) store the fp as the control link in the new activat
23、ion 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 program(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;mainint a2=1,1; p(ai, ai);printf(“ %d n%d” , a0, a1);return 0;Solutionpass by value:1,1pass by reference:3,1pass by value-result:2,1pass by name:2,2