  We solve an open problem related to an optimal encoding of a straight line
program (SLP), a canonical form of grammar compression deriving a single string
deterministically. We show that an information-theoretic lower bound for
representing an SLP with n symbols requires at least 2n+logn!+o(n) bits. We
then present a succinct representation of an SLP; this representation is
asymptotically equivalent to the lower bound. The space is at most 2n log
{rho}(1 + o(1)) bits for rho leq 2sqrt{n}, while supporting random access to
any production rule of an SLP in O(log log n) time. In addition, we present a
novel dynamic data structure associating a digram with a unique symbol. Such a
data structure is called a naming function and has been implemented using a
hash table that has a space-time tradeoff. Thus, the memory space is mainly
occupied by the hash table during the development of production rules.
Alternatively, we build a dynamic data structure for the naming function by
leveraging the idea behind the wavelet tree. The space is strictly bounded by
2n log n(1 + o(1)) bits, while supporting O(log n) query and update time.
