Problem 1: Is the following grammar LR(0)?

State	Items
0	S &rarr · a S S &rarr · a
1	S &rarr a · S S &rarr a · S &rarr · a S S &rarr · a

State 1 has a shift/reduce conflict, so the grammar is not LR(0).

---

Problem 2: Construct a CFG for the language a(ba)ⁿca(ba)ⁿ. Construct the parse table for your CFG and show a trace of parsing ababacababa.

1) S &rarr a c a
2) S &rarr a b S b a

State	Items
0	S &rarr · a c a S &rarr · a b S b a
1	S &rarr a · c a S &rarr a · b S b a
2	S &rarr a c · a
3	S &rarr a b · S b a S &rarr · a c a S &rarr · a b S b a
4	S &rarr a b S · b a
5	S &rarr a b S b · a

	S	a	b	c
0	accept	s1
1			s3	s2
2		s/r1
3	s4	s1
4			s5
5		s/r2

Stack	Input	Action
0	a	shift, goto 1
0 a 1	b	shift, goto 3
0 a 1 b 3	a	shift, goto 1
0 a 1 b 3 a 1	b	shift, goto 3
0 a 1 b 3 a 1 b 3	a	shift, goto 1
0 a 1 b 3 a 1 b 3 a 1	c	shift, goto 2
0 a 1 b 3 a 1 b 3 a 1 c 2	a	shift, reduce by rule 1
0 a 1 b 3 a 1 b 3	S	shift, goto 4
0 a 1 b 3 a 1 b 3 S 4	b	shift, goto 5
0 a 1 b 3 a 1 b 3 S 4 b 5	a	shift, reduce by rule 2
0 a 1 b 3	S	shift, goto 4
0 a 1 b 3 S 4	b	shift, goto 5
0 a 1 b 3 S 4 b 5	a	shift, reduce by rule 2
0	S	accept!

Problem 3: Given the following attribute grammar, compute the values of the attributes of the nonterminals in the parse tree of pi(ab,i(b,b))a. Assume that p.s is initialized to 0 by the scanner.

Since l is a purely synthesized attribute, compute that first using a bottom-up approach. Next, compute s and then n.

Problem 4: Some languages allow multi-way assignments such as a,b = c,d, which would simulaneously copy the value from c to a and from d to b. Write an attribute grammar for such assignment statements that includes an attribute that can be checked to see if the assignment is balanced (that is, if there are the same number of terms on both sides of the assignment operator). Assume that all of the terms are identifiers.

Problem 5: Show the output of the following code fragment assuming that dynamic binding is used. Assume that execution begins in procedure Z.

procedure A
  print x

procedure B
  int x = 1
  call A

procedure C
  int x = 2
  call B

procedure Z
  int x = 3;
  call A
  call B
  call C
  call A

3 1 1 3

Problem 6: What is the output of the following code fragment if deep binding is used? What is the output if shallow binding is used? In both cases, assume that execution begins in the outermost procedure.

procedure A
  int m

  procedure B(procedure X, int y)
    print X(y)

  procedure C(procedure X)
    m = 10
    B(X, m)

  procedure D(int x) : int
    return x * m

  m = 1
  C(D)

Shallow binding: 100
Deep binding: 10

Problem 7: Consider the following code fragment in a language that allows nested procedures. What is the output, assuming that execution begins in the main body of procedure A? What machine instructions would be generated to perform the call of procedure D from procedure C? What would be generated to perform the call of procedure D from procedure A?

procedure A
  int x

  procedure B
    int y

    procedure C
      int x

      x = 2
      print x, y
      call D

    y = 8
    print x, y
    call C

  procedure D
    int z

    procedure E
      z = 9
      call F

    procedure F
      int y

      y = 5
      print x, y, z


    x++
    z = 4
    call E

  x = 10
  call B
  call D