***Problem*** 1.

A --> BdA'
     |CBA'
A'--> ffA'
     |epsilon
B --> dfB'
B'--> dB'
     |fB'
     |epsilon
C --> h 
     |g 


***Problem*** 2.

First(D) = {p,r} 
First(C) = {k, epsilon}
First(B) = {p, r, epsilon}
First(A) = {p, r, k, m, epsilon}

Follow(A) = {$}
Follow(B) = First(C)-epsilon V {m} = {k, m}
Follow(C) = {$, m}
Follow(D) = First(B)-epsilon V Follow(B) = {p, r, k, m}


***Problem*** 3.

the correct statements about bison are:
2, 5, 7, 8, 10


***Problem*** 4.

For a string "aab", there can be two parse trees:

	     S                        S
            /|\                      / \
           a S b                    S   S
             |                     / \   \
             a                    S   S   b
				  |   |
				  a   a


***Problem*** 5.

Part A.
Lexical Analysis

Part B.
DFA

Part C.
Regular expressions are a language for denoting regular sets.


***Problem*** 6.

e-closure(1) = 1
m(1, a) = 2
e-closure(2) = [2,3]
m(1, b) = []
m([2,3], a) = 4
e-closure(4) = [3,4]
m([2,3], b) = 2
m([3,4], a) = [4,5]
e-closure([4,5]) = [3,4,5]
m([3,4], b) = 4
m([3,4,5], a) = [4,5]
m([3,4,5], b) = 4


            a          b 
---------------------------
[1]       [2,3]        []
[2,3]     [3,4]       [2,3]
[3,4]     [3,4,5]     [3,4]
[3,4,5]*  [3,4,5]     [3,4]

Note: * denotes final state


***Problem*** 7.

There is no left recursion in this grammar, but there is left factor,
So the grammar can be rewritten as:

S --> aSa
S --> bSb
S --> L
L --> cR
R --> L
     |epsilon

First(L) = {c}
Follow(R) = Follow(L) = Follow(S) = {a, b, $}

The parsing table is as follows:

      a      b     c     $
----------------------------
S    aSa    bSb    L
L                  cR
R    eps    eps    L     eps

Note: eps = epsilon

  
***Problem*** 8.

Part A.
one or more a's followed by one or more b's followed by d's and 
# of d's = # of a's  + # of b's

Part B.
S0:
S'--> .S
S --> .aSd
S --> .aLd

S0 -- a --> S1:
S --> a.Sd
S --> a.Ld
S --> .aSd
S --> .aLd
L --> .bLd
L --> .bd

S0 -- S --> S2
S' --> S.

Part C.
Follow(S) = {d, $}
Follow(L) = {d}

State   input    reduce by production rule
------------------------------------------
6	d	r1
6	$	r1
7	d	r2
7	$	r2
9	d	r4
10	d	r3
 

***Problem*** 9.
 
E ==> T 
  ==> T*F
  ==> F*F
  ==> (E)*F
  ==> (T)*F
  ==> (F)*F
  ==> (id)*F
  ==> (id) * id


***Problem*** 10.

Part A.
E.val = E1.val + T.val
E.val = T.val
T.val = T1.val + F.val + 1
T.val = F.val
F.val = E.val
F.val = 0

Part B.

                            E(2)
			    |
                            T(2)
			   /|\
                       (1)T * F(0)
                         /     \
                        F(1)   id(0)
                       /|   \
                      ( E(1) )
                       / | \
                   (1)E  +  T(0)
                     /       \
                    T(1)      F(0)
                   / | \       \
               (0)T  *  F(0)    id(0)
                 /       \ 
                F(0)      id(0)
               /
              id(0)