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.
A -> Ax
A -> Bx
B -> Ay
Both are getting into infinite loop.
Thank you and appreciated for all your expert.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With