  We present an algorithm for computing the Lyndon factorization of a string
that is given in grammar compressed form, namely, a Straight Line Program
(SLP). The algorithm runs in $O(n^4 + mn^3h)$ time and $O(n^2)$ space, where
$m$ is the size of the Lyndon factorization, $n$ is the size of the SLP, and
$h$ is the height of the derivation tree of the SLP. Since the length of the
decompressed string can be exponentially large w.r.t. $n, m$ and $h$, our
result is the first polynomial time solution when the string is given as SLP.
