------------------------------------------------------------------------- 1 a) Syntax-directed translation can perform actions not specified in the grammar, both for analyzing the input program (type-checking) and generating output (symbol tables, AST). b) Context-sensitive parsing can decide whether to apply a production for a nonterminal based on input surrounding the nonterminal. Context-free parsing applys a production based solely on the nonterminal and the result of the production. c) context-free grammar (least powerful) context-sensitive grammar attribute grammar syntax-directed translation (most powerful) d) Synthesized attributes may be calculated only from attributes of children. Inherited attributes may also be calculated from attributes of parents or siblings. e) E := E PLUS E { E.val = E1.val + E2.val; } // val is synthesized decl := typeSpec id { id.type = typeSpec.type; } // type is inherited typeSpec := INT { typeSpec.type = INT; } ------------------------------------------------------------------------- 2 a) pointer(char) X array(0..3, int) -> int b) array(0..99, (int X int)) c) int X (int X int) -> pointer( (int X int) ) ------------------------------------------------------------------------- 3 a) E := CONST { E.odd = (CONST.val % 2); } // 0 if even, 1 if odd | ID { E.odd = unknown; } | E + E { if ((E1.odd == unknown) || (E2.odd == unknown)) E.odd = unknown; else E.odd = (E1.odd + E2.odd) % 2; } | E - E { if ((E1.odd == unknown) || (E2.odd == unknown)) E.odd = unknown; else E.odd = (E1.odd + E2.odd) % 2; } | E * E { if ((E1.odd == 0) || (E2.odd == 0)) E.odd = 0; // even * X = even for all X else if ((E1.odd == unknown) || (E2.odd == unknown)) E.odd = unknown; else // assert(E1.odd && E2.odd) { both must be odd } E.odd = 1; } | ( E ) { E.odd = E1.odd; } | - E { E.odd = E1.odd; } b) (5 + 2) - (4 * - x) Parse Tree ---> E --> ID / -> ) -> E ---> - / / / / -> E ----> E --> * / \ \ / --> ( --> E --> CONST E --> - \ --> ( -> E --> CONST \ / / -> E ----> E --> + \ \ \ \ -> ) -> E --> CONST Annotated Parse Tree (with values of attributes) ---> E.odd = unknown --> ID.odd == unknown (x) / -> ) -> E.odd = unknown ---> - / / / / -> E.odd = 0 ----> E.odd = 0 --> * / \ \ / --> ( --> E.odd = 0 --> CONST.val = 4 E.odd = 1 --> - \ --> ( -> E.odd = 0 --> CONST.val = 2 \ / / -> E.odd = 1 ----> E.odd = 1 --> + \ \ \ \ -> ) -> E.odd = 1 --> CONST.val = 5 ------------------------------------------------------------------------- 4 a) E := CONST { E.min = CONST.val; E.max = CONST.val; } | ID { E.min = ID.min; E.max = ID.max; } | E + E { E.min = E1.min+E2.min; E.max = E1.max+E2.max; } | E - E { E.min = E1.min-E2.max; E.max = E1.max-E2.min; } | E * E { t1 = E1.min*E2.min; t2 = E1.min*E2.max; t3 = E1.max*E2.min; t4 = E1.max*E2.max; E.min = min(t1,t2,t3,t4); E.max = max(t1,t2,t3,t4); } | ( E ) { E.min = E1.min; E.max = E1.max; } | - E { E.min = -E1.max; E.max = -E1.min; } b) (5 + 2) - (4 * - x) Parse Tree ---> E --> ID / -> ) -> E ---> - / / / / -> E ----> E --> * / \ \ / --> ( --> E --> CONST E --> - \ --> ( -> E --> CONST \ / / -> E ----> E --> + \ \ \ \ -> ) -> E --> CONST Annotated Parse Tree (with values of attributes) ---> E.min=ID.min, E.max=ID.max --> ID / -> ) -> E.min=-ID.max,E.max=-ID.min ---> - / / / / -> E.min=-4*ID.max ----> E.min=-4*ID.max --> * / .max=-4*ID.min .max=-4*ID.min / \ \ / --> ( --> E.min=4,E.max=4 --> CONST.val = 4 / E.min=7+4*ID.min= --> - .max=7+4*ID.max \ \ --> ( -> E.min=2,E.max=2 --> CONST.val = 2 \ / / -> E.min=7,E.max=7 ----> E.min=7,E.max=7 --> + \ \ \ \ -> ) -> E.min=5,E.max=5 --> CONST.val = 5 ------------------------------------------------------------------------- 5 a) E := E + T if ((E'.type == int) && (T.type == int)) E.type = int; else E.type = float; | T E.type = T.type T := num.num T.type = float | num T.type = int b) 5 + 4 + 3.2 + 1 Parse Tree -> T -> num -> num / / E --> + --------------------> T --> . \ / \ -> E --> + -> T -> num -> num \ / -> E --> + \ -> E --> T -> num Annotated Parse Tree -> T.type=int -> num -> num / / / / / / E.type=float-->+ / \ ------------------------> T.type=float --> . \ / \ \ / \ -> E.type=float ---> num \ /---> T.type=int -> num \ / \ / --> E.type=int --> + \ \ ----> E.type=int --> T.type=int -> num ------------------------------------------------------------------------- 6 a) Different scopes may be nested within each other, and each occurrence of a variable refers to the closest lexical declaration, working outwards from where the variable is used. b) Symbol tables can handle nested lexical scoping in many ways. One simple method is to maintain a separate symbol table for each scope, nesting the symbol tables. c) When using nested symbol tables, a variable can find its matching declaration by looking in symbol table for the current scope, then working out to the symbol tables of enclosing scopes until symbol is found. d) Example of nested symbol tables Global Table ---------------- | x : int | | y : int |<--------------\ | bar : func | | | foo : func |<-\ | ---------------- | | | | Tables for foo() ------------- | ------------- Tables for bar() | parent |--/ | parent | ------------- -------------<-------\ | z : int |<---\ | z : int |<--\ | ------------- | ------------- | | | | | ------------- | ------------- | | | parent |----/ | parent |---/ | ------------- ------------- | | y : int |<---\ | x : int | | ------------- | ------------- | | | ------------- | ------------- | | parent |----/ | parent |--------/ ------------- ------------- | x : int | | y : int | ------------- ------------- ^ | | (HERE) Current ----/ ------------------------------------------------------------------------- 7 a) A frame (activation record) stores run-time information needed to maintain the environment of a function during program execution b) parameters - set before invocation return value - set right before procedure return return address - set before invocation pointer to frame of enclosing function (access link) - set before invocation pointer to frame of calling function - set before invocation local variables - set during procedure execution c) local stack (for stack operations) d) when the variable has fixed size and is no longer accessible after procedure return e) entire frame may be freed at together at once when returning from procedure f) most efficient (least wasted memory, memory freed at earliest opportunity), little run-time overhead g) less programmer effort, possibility of premature freeing of memory greatly reduced h) Reference counting keeps track of number of possible references, freeing when count reaches zero. Mark-and-scan looks for accessible memory during program execution and frees inaccessible memory. ------------------------------------------------------------------------- 8 a) x := a + ( b * a ) x := a - (( b + a ) * c ) := := / \ / \ x + x - / \ / \ a * a * / \ / \ b a + c / \ b a b) load R1 a load R1 a load R2 b load R2 b load R3 a load R3 c mult R4 R2 R3 add R4 R2 R1 add R5 R1 R4 mult R5 R4 R3 store x R5 sub R6 R1 R5 store x R6 c) iload index(a) iload index(a) iload index(b) iload index(b) iload index(a) iload index(a) imult iadd iadd iload index(c) istore index(x) imult isub istore index(x) d) Java byte code is most compact because operations can refer to implicit stack instead of actual register numbers/addresses e) ASTs are most easy to manipulate for high-level code, 3-address code is easy to manipulate for low-level code f) Java byte code is hard to manipulate because stack operations are more difficult to reorder g) ASTs are closest to the input program because it maintains the original grammatical structure ------------------------------------------------------------------------- 9 These solutions assume boolean expressions are implemented as numerical values, leaving a 1 or 0 on the stack for true & false. a) stmt := IF (exp) stmtList ; { Handle h1 = genInst( NOP ); stmt.code = append ( exp.code, genInst ( IFEQ( h1 ) ), stmtList.code, h1 } b) stmt := FOR (stmt1 ; exp ; stmt2) stmt3 ; { Handle h1 = genInst( NOP ); Handle h2 = genInst( NOP ); stmt.code = append ( stmt1.code, h1, exp.code, genInst ( IFEQ( h2 ) ), stmt3.code, stmt2.code, genInst ( GOTO( h1 ) ), h2 ); } c) exp := exp1 AND exp2 { Handle h1 = genInst( NOP ); exp.code = append ( exp1.code, dup, genInst ( IFEQ( h1 ) ), pop, exp2.code, h1 ); } d) exp := exp1 NOR exp2 { Handle h1 = genInst( NOP ); Handle h2 = genInst( NOP ); Handle h3 = genInst( NOP ); Handle h4 = genInst( NOP ); exp.code = append ( exp1.code, genInst ( IFEQ( h1 ) ), genInst ( GOTO( h2 ) ), h1, exp2.code, genInst ( IFEQ( h3 ) ), h2, genInst ( LDC_INT( 0 ) ), genInst ( GOTO( h4 ) ), h3, genInst ( LDC_INT( 1 ) ), h4 ); } e) exp := exp1 >= exp2 { Handle h1 = genInst( NOP ); Handle h2 = genInst( NOP ); exp.code = append ( exp1.code, exp2.code, genInst ( IF_ICMPEQ( h1 ) ), exp1.code, exp2.code, genInst ( IF_ICMPGT( h1 ) ), genInst ( LDC_INT( 0 ) ), genInst ( GOTO( h2 ) ), h1, genInst ( LDC_INT( 1 ) ), h2 ); } ------------------------------------------------------------------------- 10 a) Function call could occur in an expression (e.g., 4 + foo()), need to calculate value of function and use return value in expression Function argument could be an expression (e.g., foo(4+x)), need to evaluate expression first and pass as argument b) Could have multidimensional arrays, need to convert indices into memory location by flattening the array in either row or column major order Could have arrays or array elements as arguments (e.g., foo(a[], foo(a[4])), need to decide whether to pass value or address depending on whether call-by-reference or call-by-value c) For a[ i+5 ] = 4, compiler must generate code to calculate i+5, (adjusting by first array index, usually 0 or 1) multiply result by size of elements of array, then add to base address of a to find address of array element d) For x = foo( i+2 ) If foo() is call-by-value, calculate i+2 and use value as argument If foo() is call-by-reference, calculate i+2, store in temporary variable, then pass address of temp var as argument ------------------------------------------------------------------------- 11 a,b,c,e) + labels 2 / \ (# regs) / \ a * 1 2 / \ / \ b c 1 1 Sethi-Ullman: DLS (3 regs): load R1 b load R1 b load R2 c load R2 c ** stall ** load R3 a mult R1 R1 R2 mult R1 R1 R2 load R2 a add R1 R3 R1 ** stall ** add R1 R1 R2 2 stalls total no stalls + labels 3 / \ (# regs) / \ / \ / \ / \ / \ * - 2 2 / \ / \ / \ / \ a b c + 1 1 1 2 / \ / \ d e 1 1 Sethi-Ullman: DLS (3 regs): DLS (4 regs) load R1 a load R1 a load R1 a load R2 b load R2 b load R2 b ** stall ** load R3 d load R3 d mult R1 R1 R2 mult R1 R1 R2 load R4 e load R2 d load R2 e mult R1 R1 R2 load R3 e ** stall ** load R2 c ** stall ** add R2 R3 R2 add R3 R3 R4 add R2 R2 R3 load R3 c sub R2 R2 R3 load R3 c ** stall ** add R1 R1 R2 ** stall ** sub R2 R3 R2 sub R2 R3 R2 add R1 R1 R2 add R1 R1 R2 3 stalls total 2 stalls total no stalls d) DLS always needs 1 more register than Sethi-Ullman to eliminate all stalls, when load instructions have a 1-instruction (cycle) delay ------------------------------------------------------------------------- 12 a) Inheritance occurs when a class can take on all the attributes (fields & methods) of another class, while adding additional attributes. If dynamic methods are allowed descendent classes can override methods in superclasses. b) Inheritance is implemented at run-time by having each object maintain a pointer (tag) to the class record for each class. c) To access the field of an object without prefixing would require following the tag to the class record to determine what class the object belongs to, as well as where a field is stored in an object, then accessing that particular field in that object.. With prefixing, fields are stored at the same offset for all the superclass and all of its descendent classes. The compiler then just needs to generate code to access the field in that object using the offset. d) Multiple inheritance occurs when a class inherits attributes from multiple classes. e) Multiple inheritance increases the complexity of prefixing because offsets must be reserved in the layout of both parent classes, leaving empty space in objects. f) Class Records A: f1() f2() <------- a B: f1*() f2() f3() <------- a b c --> C: f1*() f2() f3() f4() <------- a b c d / D: f1() f2() f4() f5() <------- a d e | \ -------- \----------- | -------- | a | | b | | c | | d | -------- x ------------------------------------------------------------------------- 13 a) Few or no side effects (assignments) Higher order functions Lots of recursion b) Side effects are discouraged or halted in the language specification, compiler can check for violations Higher order functions implemented using closures to preserve environment of function after return, by putting frames on the stack. Recursion is implemented using standard procedure call protocols to reduce overhead through identifying and inlining non-dynamic methods c) No side effects makes programs easier to analyze Higher order functions increases flexibility of language Recursion is simple and elegant way of specifying many algorithms d) No side effects requires a lot of copying & recalculation Higher order functions require frames to be saved longer in order to maintain static lexical nesting. Resursion is inefficient because procedure calls have very large overhead.. e) Compiler and run-time support can try to reduce the amount of copying required. Compiler analysis can determine when frames may be freed earlier Recursion can be converted to tail recursion, and then into loops, if continuations are supported. Compilers can also selectively inline functions to reduce procedure call overhead.