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')$?


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.)

| cite | improve this answer | |
  • $\begingroup$ I think first grammar in your example is not $LL(1)$ because in that $first(A)$ and $follow(A)$ both contains $a$. And as per my knowledge if any non terminal have first follow conflict than that grammar is not $LL(1)$. Please correct me if I'm wrong. $\endgroup$ – Vimal Patel Oct 23 '19 at 1:11
  • $\begingroup$ @VimalPatel: Quite right, sorry about the confusion. The grammar left in that answer was neither LL(1) nor was it a grammar for the target language, and the result was that I wrote the wrong grammar for the reverse language, too. I hope I've fixed both of them. I checked the grammar with this tool $\endgroup$ – rici Oct 23 '19 at 2:26
  • $\begingroup$ yes that tool is problematic. $\endgroup$ – Vimal Patel Oct 23 '19 at 3:11
  • 1
    $\begingroup$ @vimal: Perhaps, but in this case the result is correct. It's easy to verify the FIRST and FOLLOW sets by hand. (Note that this is not the same grammar as you saw before. I inserted the correct grammar after reading your previous comment.) $\endgroup$ – rici Oct 23 '19 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.