retagged by
10,288 views
2 votes
2 votes
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?
retagged by

6 Answers

3 votes
3 votes

Left recursion is a problem in top-down parsers because top down parsers use left-most derivation to derive the required string by using the start symbol of the grammar. Due to this reason top-down parsers might go into infinite loop with left recursive grammar.

Whereas in case of bottom-up parsers, we just reduce the string of terminals using productions of given grammar. There is no concept of derivation of string of terminals (neither left-most nor right-most derivation). So,whether it is left recursive or right recursive, no grammar would cause any problem. Only ambiguous grammars cause a problem.

2 votes
2 votes

The main reason why Bottom up parser doesnt have any problem with Left recursive is that it start building tree from leaves . After seeing through a input you will check the next lookahead , if that lookahead lies in follow of a NT then you will reduce and if not then shift .So by any mean you are not doing that recursive work Hence it doesnt have problem with Left recursive .

Where as in top you start from Root 

so if you have production s-->Sa

s->Saa

s-->Saaa

and so on

you may run to infinite ( or to precise till stack doesnt get full )

0 votes
0 votes
First of all there should not be any confusion between LR(0) and LR(1). In LR(0) there is no lookahed while constructing the DFA using grammar where as in LR(1) there is a lookahead.

Now when dot(.S) comes in front of the production i.e S'->.S then it is not your Grammar Production, it is a Augumented Production. So, it is only the end part when the sting is accepted this producton evaluated in the table at token '$'. So it will not go to loop as before dot means parser is going to see the Terminal S and after dot means it had seen the terminal S and perform REDUCE-ACTION.

Thank U.

Related questions

2 votes
2 votes
2 answers
1
gate19 asked May 26, 2018
1,106 views
What is the difference between $SLR(1)$ and $LALR(1)$ parser ? Both parser have same parsing table then how $SLR$ is subset of $LALR$ ?
0 votes
0 votes
1 answer
2
aditi19 asked Jul 6, 2018
357 views
Does bottom up parsers give postfix expression?
0 votes
0 votes
2 answers
3
prasitamukherjee asked Jul 16, 2015
855 views
q. 23 : can anyone explain why both statements are false? I thought option B is correct?