Top-Down Parser want to have decent case example left-recursion in a 'Code'

Question

Hello fellow stack over flow members.

I'm studying for compiler class. I did understand Top-Down Parser should avoid left-recursion, and transform into right-recursion way.

Questions are,

a) am I understanding right Top-Down Parser is equal to LL and Bottom-Up Parser is equal to LR ?

b) I've found out left-recursion is Rule that calls itself ex) Expr :== Expr '+' Term | Term which can cause infinite loop to find Expr. But anyhow, any example code of consider input in C or Java? ( I don't want the parser or scanner code ) what I need is case code example with sentential form that occur infinite loop by left recursion.

c) What actually makes difference in a way using Right Recursion in Top-Down Parser?

ANS c) Eliminating the need to backtrack. but something else?

ANS b) x - 2 * y but also something else? because this one works with backtrack way of parsing.

Case example that I have found out the both non-left recursion and left recursion.

Left Recursion Grammar

A -> Ax

Non-Left Recursion Grammar

A -> Bx
B -> Ay

Both are getting into infinite loop.

Thank you and appreciated for all your expert.

Answer 1

a) am I understanding right Top-Down Parser is equal to LL and Bottom-Up Parser is equal to LR ? yes

Top down parsers get into an infinite loop with left-recursion since the productions, in code, look like:

A() {
  A(); match(x);
}

A calls itself forever and never removes anything from the input stream.

Left recursion doesn't have to be immediate so your "non left recursive grammar" is still left recursive:

A -> Bx | z
B -> Ay

You can see that it is left recursive if you replace B by its production:

A -> Ayx | z

Here is an example of correctly converting a left-recursive grammar to a right-recursive grammar: Left recursive:

E -> E + T | T

Right recursive:

E -> T B
B -> + T B | Lambda

E -> T B since, in the rule E -> E + T | T, T will ALWAYS appear on the left most side after finishing the application of the rule. Since the left most side is taken care of by E -> T B, we are free to construct the right side of the string which we do with B -> + T B. We need a lambda production to give us a stopping point for the recursion.

A -> Ax and A -> xA would be equivalent grammars, just one is left and the other is right recursive.