------------------------------------------------------------------------- 1 a) In attribute grammars, values of attributes can only be computed from attributes of other terminals & nonterminals in the production. In syntax-directed translations, any actions may be performed, and attributes may be computed in any way. b) Attribute grammars are easier to analyze and prove properties. Syntax-directed translations are more efficient and general. c) E := ID { E.type = getType(ID.name); } ------------------------------------------------------------------------- 2 a) pointer(int) -> char b) array(0..3, char) -> ------------------------------------------------------------------------- 3 a) E := CONST { E.type = INT; } | ID { E.type = getType(ID.name); } | E + E { if ((E1.type == INT) && (E2.type == INT)) E.TYPE = INT; else E.TYPE = INT; // error } | E < E { if ((E1.type == INT) && (E2.type == INT)) E.TYPE = BOOL; else E.TYPE = INT; // error } | E == E { if (E1.type == E2.type) E.TYPE = BOOL; else E.TYPE = INT; // error } | ( E ) { E.type = E1.type; } b) (5 < 2) == (4 + x) Parse Tree -> ) -> E ---> ID / / / / -> E ----> E --> + / \ \ / --> ( --> E --> CONST E --> == \ --> ( -> E --> CONST \ / / -> E ----> E --> < \ \ \ \ -> ) -> E --> CONST Annotated Parse Tree (with values of attributes) -> ) -> E.type = getType(ID.name) ---> ID.name = x / / / / -> E.type = INT ----> E.type = INT --> + / \ \ / --> ( --> E.type = INT --> CONST.val = 4 E.type = INT (error) --> == \ --> ( -> E.type = INT --> CONST.val = 2 \ / / -> E.type = BOOL ----> E.type = BOOL --> < \ \ \ \ -> ) -> E.type = INT --> CONST.val = 5 ------------------------------------------------------------------------- 4 a) Nested lexical scoping allows the scope of each variable reference to be completely determined at compile-time. In dynamic scoping languages such as LISP it is not possible to always determine where a variable is declared until run time. For instance, with nested lexical scoping the assignment to "x" always refers to the "x" declared in bar(). With dynamic scoping, it could also refer to the "x" declared in foo() if foo() is invoked more recently than bar() before invoking num(). foo() { int x; bar() { int x; num() { x = ... } } } b) Compilers can use a single symbol table per scope, and nest them according to the rules for nested lexical scoping. Symbol lookup then start from the current symbol table and repeat in enclosing symbol tables until found. c) Example of nested symbol tables Table for main() ------------- | parent |----\ ------------- | | y : int | | ------------- | | Global Table ---------------- | | x : int |<---/ | main : func |<--------------\ | bar : func | | | foo : func |<-\ | ---------------- | | | | Tables for bar() ------------- | ------------- Tables for foo() | parent |--/ | parent | ------------- -------------<-------\ (HERE) Current ----> | z : int |<---\ | z : int |<--\ | ------------- | ------------- | | | | | ------------- | ------------- | | | parent |----/ | parent |---/ | ------------- ------------- | | y : int | | x : int | | ------------- ------------- | | ------------- | | parent |--------/ ------------- | y : int | ------------- ------------------------------------------------------------------------- 5 a) A frame (activation record) stores run-time information needed to maintain the environment of a function during program execution b) Stack, global data, heap. Stack when the variable has fixed size and is no longer accessible after procedure return, global data for fixed sized global variables, heap for everything else. c) garbage collection is when the run-time system attempts to automatically free inactive memory. d) virtual machine is a software machine architecture where instructions are interpreted and executed in software, affecting software implementations of registers, memory, condition codes, and/or stack. ------------------------------------------------------------------------- 6 a) x := ( a - b) * ( c + d ) := / \ x * / \ - + / \ / \ a b c d b) load R1 a load R2 b sub R3 R1 R2 load R4 c load R5 d add R6 R4 R5 mult R7 R3 R6 store x R7 c) iload index(a) iload index(b) isub iload index(c) iload index(d) iadd imult istore index(x) d) ASTs are closest to the input program because it maintains the original grammatical structure e) 3-address code is closes to the hardware because it is closest to the actual assembly instructions executed by the processor (for general microprocessors) f) compilers may use multiple intermediate representations to be able to perform both high and low-level program transformations ------------------------------------------------------------------------- 7 These solutions assume boolean expressions are implemented as numerical values, leaving a 1 or 0 on the stack for true & false. a) stmt := DO stmtList WHILE ( exp ) ; { Handle h1 = genInst( NOP ); Handle h2 = genInst( NOP ); stmt.code = append ( h1, stmtList.code, exp.code, genInst ( IFEQ( h2 ) ), genInst ( GOTO( h1 ) ), h2 } b) exp := exp1 XOR exp2 { Handle h1 = genInst( NOP ); Handle h2 = genInst( NOP ); exp.code = append ( exp1.code, exp2.code, genInst ( IF_ICMPEQ( h1 ) ), genInst ( LDC_INT( 1 ) ), genInst ( GOTO( h2 ) ), h1, genInst ( LDC_INT( 0 ) ), h2 ); } ------------------------------------------------------------------------- 8 For a[ 5 ], compiler must add (5 * arrayElementSize) to the base address of "a" to find the address of a[5] a) If foo() is call-by-value, get value at a[5] and use value as argument b) If foo() is call-by-reference, pass address of a[5] as argument ------------------------------------------------------------------------- 9 a) (a * (b+c)) - d - labels 2 / \ (# regs) / \ * d 2 1 / \ / \ a + 1 2 / \ / \ b c 1 1 b,c,e) Sethi-Ullman: DLS: load R1 b load R1 b load R2 c load R2 c load R3 a add R1 R1 R2 add R1 R1 R2 load R2 a load R2 d mult R1 R3 R1 mult R1 R1 R2 sub R1 R1 R2 load R2 d sub R1 R1 R2 3 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 ------------------------------------------------------------------------- 10 a) Prefixing is a technique where fields & methods are stored at the same offset for the superclass and all of its descendent classes, so the compiler can use the offset directly without identifying whether the object is a subclass. b) To access the method 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 method is stored in the class method table, then accessing that method. With prefixing methods are stored at the same offset in the method table for all descendent classes, so the compiler only needs to generate code to look up the object tag to the desired index in the method table.. c) Class Records Method Table Field Layout A: f1() f2() <------- a B: f1*() f2() f3() <------- a b c C: f1() f2() f4() <------- a c --> D: f1() f2() f4*() f5() <------- a c d e / \ -------- \----------- | -------- | a | | c | | d | | e | -------- x ------------------------------------------------------------------------- 11 a) Few or no side effects (assignments) in a functional language b) Causes lots of recursion and the use of higher order functions. c) A closure is a function and a saved copy of its environment (frames of lexical enclosing scopes). Closures are needed with higher-order functions because a function may need to access variables declared in enclosing nested scopes later. d) Closures are implemented in the run-time environment by saving function frames (even after function return) on the heap, if variables may be accessed later through higher-order functions.