I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example:

$S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow SA \\ B \rightarrow b \\ B \rightarrow SB$

By substituting $S$ we arrive at:

$S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow ABA \\ B \rightarrow b \\ B \rightarrow ABB$

In an attempt to eliminate left recursion, we create $A'$:

$1.\text{ }S \rightarrow AB \\ 2.\text{ }A \rightarrow aA' \\ 3.\text{ }A' \rightarrow \epsilon \\ 4.\text{ }A' \rightarrow BaA' \\ 5.\text{ }B \rightarrow b \\ 6.\text{ }B \rightarrow aA'BB$

At this point, it is stated

The grammar is now in a form that will lend itself to recursive descent parser construction after some factoring and substitution.

I know that the problem production is $B \rightarrow aA'BB$ because it references $A'$, which comes before it. I can't figure out how to refactor it so that it does not refer to $A'$. When attempting to generate a series of rules that can be used to prove that a given string is in this grammar, I have trouble determining whether to use rule 3 or 4. Is this an $LL(k)$ grammar? If so, what is $k$?


Your Answer

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

Browse other questions tagged or ask your own question.