Skip to main content
1 of 2

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

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