Why is left recursion not a problem for bottom up parsers?

Question

I know the parsing logic of bottom up parsers, that they start from the terminal and reduce it to the start symbol. But what really confuses me is the construction of LR(0)/LR(1) sets :

Eg : S->Sa|a

Then in LR(0) set :

S'->.S

S->.Sa

S->.a

Now the dot is in front of S , so shouldn't the S production be generated again and again and make it go to an inf. loop?

Answer 1

this is a ambiguous grammer

Answer 2

In bottom up parsing the string will keep on getting reduced(or handles will prune) resulting in bottom up parse tree.

eg-  consider the code-                 if (condition)----→  if(condition) + statement / Φ

so here for the top down parser will result in infinite left recursive tree until condition isn’t satisfied.       

                         if(condition)

                                  /\   

              if(condition)      statement                         <----- left recursive tree

                    /\

 if(condition)    statement                                                                                                       

        /\                                                                                                                                            

and so on

 

but in bottom up parser there is reduction of string resulting as follows-

                     if(condition)      

                            /\                                                                                      ᐎ

           if(condition) + statement                                                                   ||           bottom to up movement

                                                                                                                     ||