Skip to main content
Computer Science

Return to Question

Fix typo to correct the given LL(1) CFG.
Source Link
namasikanam
namasikanam
  • 215
  • 1
  • 9

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

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

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

Bumped by Community user
Source Link
namasikanam
namasikanam
  • 215
  • 1
  • 9

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