i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced. But why is this then a problem in LL(k) parsing?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
LL parsing must predict which production will be used before it starts parsing the contents of that production. (It is a top-down parse — it constructs the parse node and then fills in the children.)
LR parsing is bottom-up; first it lets the children be recognised, and only then does it apply the production and create the parse node. Consequently, it does not need to know which production will be used until the end of the production, so it can handle a grammar where two or more productions start with the same symbols.
Also, since LR parsing does not immediately expand the predicted production onto the stack (or recursively call itself to parse the predicted production) recursive productions are not problematic.
