CS 4410/6415

CS 4410/6415

Final Exam

December 7, 1998

1. (20 points)
Show the symbol table, attributes and type descriptor structures that would exist in a Macro compiler after it had processed the following declarations. Label all objects to indicate their types. Include values for the Size attributes of all types and for the Offsets associated with all variables and record field names, with the first variable located at offset 8. type AAA is
array (1..20) of record M, N : Integer;
Z : Float; end record

Stack :     record
                        Top : Integer;
                        Data : AAA;
                end record;

ArrayVar : array (1..5) of AAA;

2. (15 points)
Assume that the variables declared in question 1 are allocated in a procedure activation record at level 2 and that I is an integer variable with address level 1, offset 8. Give SPIM code sequences to do the following: (a) Load the value of Stack.Top into register t2

(b) Compute the address of Stack.Data(Stack.Top).Z in the register of your choice

(d) Assume X is an parameter implemented using the pass by-reference technique. The address of X is level 3, offset 10 and its size is 4. Load the value of X into register t7.

3. Assume we add a new operator, the swap operator, <->, to Macro. Given two variables, v1 and v2, the expression v1<->v2 assigns v2’s value to v1 and assigns v1’s original value to v2, and then returns v1’s new value. (a) (5 points)
What checking must be done by the Semantics operation of the corresponding AST node?

(b) (5 points)
Define a CodeGen operation that correctly implements the swap operator.

4. (10 points)
In C and C++ the expression exp1,exp2 means evaluate exp1, then exp2 and return the value of exp2. If exp1 has no side effects (assignments, I/O, system calls or calls to functions with side effects) it need not be evaluated at all. How can we test exp1’s AST, prior to code generation, to see if we can suppress its evaluation?

5. Briefly answer each of the following:

(a) (3 points)
A number of language features introduce name scopes. Explain what a "name scope" means and describe how name scopes and symbol tables are related.

(b) (12 points)
A name scope can have one of three effects: it can hide all of its name, it can allow some of its names to be visible external to itself, or it can have only a selected subset of its names externally visible. Name language features that match each of these three cases and explain the key symbol table techniques used to implement each alternative.

(c) (3 points)
In order to compile procedure calls, parameter descriptors must be accessed to match actuals with formals to check types and generate appropriate code. Explain how the formal parameter attribute records are located, since no names are available to look them up in the?symbol table.

6. (10 points)
Use an example to demonstrate clearly how an LR parser is able to handle left-recursive grammars while an LL(1) parser cannot do so. 7. The earliest control statement commonly found in programming languages is the GoTo statement. Its semantics are simple: control is unconditionally transferred to the statement whose label matches that name in the GoTo statement.
(a) (3 points)
Explain how you would extend your AST to incorporate an optional label on every statement.

(b) (5 points)
What must the Semantics operation on a GoTo statement node look like? Can it do all of the checking necessary to implement the simple definition of the statement given above?

(c) (4 points)
The design of Pascal includes the requirement that all labels must appear in the declaration section. Why do you think that Wirth included this in the language? [Hint: see you answer to part (b)!]

(d) (5 points)
What additional checking mechanisms are necessary if GoTos into structure statements are disallowed (as they are in all languages more restrictive than C)?