  Grammar compression is a general compression framework in which a string $T$
of length $N$ is represented as a context-free grammar of size $n$ whose
language contains only $T$. In this paper, we focus on studying the limitations
of algorithms and data structures operating on strings in grammar-compressed
form. Previous work focused on proving lower bounds for grammars constructed
using algorithms that achieve the approximation ratio
$\rho=\mathcal{O}(\text{polylog }N)$. Unfortunately, for the majority of
grammar compressors, $\rho$ is either unknown or satisfies
$\rho=\omega(\text{polylog }N)$. In their seminal paper, Charikar et al. [IEEE
Trans. Inf. Theory 2005] studied seven popular grammar compression algorithms:
RePair, Greedy, LongestMatch, Sequential, Bisection, LZ78, and
$\alpha$-Balanced. Only one of them ($\alpha$-Balanced) is known to achieve
$\rho=\mathcal{O}(\text{polylog }N)$.
  We develop the first technique for proving lower bounds for data structures
and algorithms on grammars that is fully general and does not depend on the
approximation ratio $\rho$ of the used grammar compressor. Using this
technique, we first prove that $\Omega(\log N/\log \log N)$ time is required
for random access on RePair, Greedy, LongestMatch, Sequential, and Bisection,
while $\Omega(\log\log N)$ time is required for random access to LZ78. All
these lower bounds hold within space $\mathcal{O}(n\text{ polylog }N)$ and
match the existing upper bounds. We also generalize this technique to prove
several conditional lower bounds for compressed computation. For example, we
prove that unless the Combinatorial $k$-Clique Conjecture fails, there is no
combinatorial algorithm for CFG parsing on Bisection (for which it holds
$\rho=\tilde{\Theta}(N^{1/2})$) that runs in $\mathcal{O}(n^c\cdot
N^{3-\epsilon})$ time for all constants $c>0$ and $\epsilon>0$. Previously,
this was known only for $c<2\epsilon$.
