For arbitrary RR(1) grammar $G$, is there an equivalent LL(1) grammar $G'$?

Question

Failed to find similar term, here I coin the noun RR(Right-to-left, Rightmost derivation) as an opposite concept of LL.

The question is inspired by an interesting example grammar $G$: $$S \rightarrow S S + | a$$ It's obviously an RR(1) language. After some time to explore, I find an equivalent LL(1) grammar: $$ \begin{array}{l} S \rightarrow a A \\ A \rightarrow S + | \epsilon \end{array}$$

So, there seems a road to more generalized conclusion. Consider arbitrary RR(1) grammar, is there an equivalent LL(1) grammar $G'$, where equivalent means $L(G) = L(G')$?

Answer 1

No. A language $\mathcal{L}$ is $RR(k)$ exactly if its reverse $\mathcal{L}^R$ is $LL(k)$. So if a $RR(k)$ grammar $G$ could be transformed into an $LL(k)$ grammar $G'$, that would mean that both $L(G^R)$ and $L(G') = L(G)$ are $LL(k)$.

But $LL(k)$ is not closed under reversal; there are $LL(k)$ languages whose reverse is no $LL(k)$. The classic demonstration that the set of $LL(1)$ languages is a proper subset of the set of $LR(1)$ languages also serves for this question.

The language $\{a^ib^j\mid 0 \le i\le j\}$ is $LL(1)$:

$$\begin{align} S &\to A B\\ A &\to \epsilon \\ A &\to a A b\\ B &\to \epsilon \\ B &\to b B \end{align}$$

However, its reverse $\{b^ja^i\mid 0 \le i \le j\}$ is not $LL(k)$ for any $k$, although the reverse is clearly $RR(1)$, since a n $RR(1)$ grammar for the reverse language can be constructed by simply reversing every production in the original grammar:

$$\begin{align} S &\to B A\\ A &\to \epsilon \\ A &\to b A a\\ B &\to \epsilon \\ B &\to B b \end{align}$$

(As it happens, the above grammar is LR(1). The language is an abstraction of the "dangling else" syntax.)