4. Consider the following augmented grammar.

S' -> S

S -> V = E ;

-> E ;

V -> * E

-> i

E -> V

a) Construct the DFA of sets of LR( 1) items for this grammar.

b) Construct the canonical LR( 1) parsing table.

c) Trace the actions of the parser on the input

'* i = i ;'.

5. a) Consider the following EBNF grammar for an IF statement

IfStat -> IF Expr THEN Stats [ ELSE Stats] END

Describe the control flow semantics with a diagram.

b) Below, the grammar has been rewritten in a form suitable for an

attributed translation scheme.

IfStat -> IfHead IfTail

IfHead -> IF Expr THEN Stats

IfTail -> ELSE Stats END

-> END

Augment the grammar with action symbols and attributes to handle

the required branch semantics. Give procedural specifications

of all action routines used in the attributed translation grammar.

c) Develop an attributed translation scheme for a REPEAT statement

described by the following grammar.

RepStat -> REPEAT Stats UNTIL Expr

6. Consider the following attribute grammar (partially in implicit

assignment form).

G -> A!0^r

A!x^z -> B!y^z A!x^y

-> c C!x^y { z = 10*y + 3}

B!x^w -> a B!v^z b C!x^y { v = 10*y +2; w = 10*z + 1}

-> b { w = 10*x + 2}

C!x^y -> c { y = 10*x + 3}

a) Draw the parse tree for the input 'abbcbcc'.

b) Draw the dependency graph induced by the implicit assignments and

attribute evaluation rules.

c) Decorate the parse tree with attribute values.

d) Show how the introduction of attributed action symbols realizing

the remaining attribute rules results in an attribute grammar

completely in implicit assignment form

7. Consider the following program in a block-structured language.

The simplest symbol-table organization in such a situation is the

stack symbol table described in class.

program M;

var

a, b, c: integer;

procedure P1( m, n: integer);

var

a, b: integer;

begin (* P1 *)

...

end P1;

procedure P2( n: integer);

procedure P3( p, q: integer);

var

z: integer;

v: boolean;

begin (* P3 *)

...

end P3;

begin (* P2 *)

...

P1( 2*n, 5+n)

...

end P2;

begin (* M *)

...

P2( a+b);

...

end M.

Assume that 'read', 'write', and 'abs', are the only predefined names.

a) Show the contents of the symbol table and the scope table/ display

prior to completing the compilation of procedure P1.

b) Show the contents of the symbol table and display prior to

completing the compilation of procedure P3.

8. Consider the following program skeleton in a statically scoped

language.

program M;

procedure P;

procedure Q;

begin (* Q *)

if ... then

Q

else

P

end;

end Q;

begin (* P *)

if ... then

Q

end;

end P;

begin (* M *)

P

end M.

Consider the following call sequence.

M -> P -> Q -> Q -> Q -> P

a) Draw a snapshot of the runtime stack of activation records

just prior to returning from the second call to P.

b) Show the dynamic chain.

c) Describe how static links are calculated.

d) Show the static chain.