in Compiler Design retagged by
1,100 views
2 votes
2 votes
$\begin{align*} &\color{blue}{\text{Top down predictive parsers detect errors earlier than bottom up parsers (true/false)}} \\ &\color{maroon}{\text{Justify your answer}} \\ \end{align*}$
in Compiler Design retagged by
1.1k views

4 Comments

@Vijay. I didnt downvote :)   By the way, not getting from the article you have cited.
0
0

@Sushant, don't take that personally. :p [ downvoters should mention fault in the given logic by anyone rather than just downvoting any comment.... anyways it does not matter to me. :p]

In the above link, he has explained how does Top down and Bottom up parser parse an input string step by step.

And on the way, if there is any error then parser can detect that in any particular step.

Moreover, you can analyze their time complexity.(Just analyze the algorithm )

[It took me around 2-3 hr to understand the working of each parser and diff. ] 

Don't miss understand "top-down" ( recursive top-down) parser and predictive top-down parser. 

1
1
@vijaycs. Yes. I got to know the difference between recursive descent and predictive parsing.

My doubt is if you try to parse a string using LR parser(just take SLR for simplicity) using a stack, the parsing is almost the same as top-down parsing. I spent lot of time on this but couldnt detect the difference.

Top-down predictive parsing starts with making leftmost derivations.

IN bottom-up, parser  proceeds in the reverse direction of  how a particular string would be derived. So, in the reverse direction, its almost making leftmost derivations by uing shift and reduce actions.

 

Try parsing the string "a+b-c" using the following grammar. Trace the derivation of the given string in the reverse manner for LR parser and compare the reduce actions with top-down parsing:

E->T+E/T

T->F-T/F

F->id

 

Now, question is does there exist an instance of a sentence where bottom-up outperforms top-down in error detection? If so, then as I have cited in the wrong example above( where I used left recursive grammar for top-down) , top-down should go on making substitutions while bottom-up quickly makes reductions to detect the error.

So, could you try to get such an instance? I couldnt get it.
0
0

1 Answer

–1 vote
–1 vote

Every Parser top down or bottom up needs a parsing table to parse any input according to given grammar.

Consider two statements:

1. given that if a language is top down parsable it is definitly bottom up parsable and are a strict subset of bottom up parsers.

2. Errors are based upon the number of blank entries in thr parsing table, which are more in bottom up parsers (say CLR (1)), therefore it is clear that error detection capability is more in bottom up parser.

Now the question is whether TDP is faster than BUP in error detection? The answer is No.

For a grammar which is Left recursive the parser would still try to parse it and would not report any errors until a non recoverable state (different from the input string) or a blank entry is encountered.

Eg.

It will parse a string 'abcd' and create a parse tree from top to down, but if an error occurs it will not report until it reaches the very leaf node at which the error is. 

While this is not the case in BUP as it will parse from every leaf node to the root node, therefore it will be able to make out which leaf is not derivable from the grammar given, before it makes a parent node.

And since there does not exist any class of language which is TDP parsable but not BUP parsable (as stated in (1)) and also there can never be more strict error detection in TDP as stated in (2).

We can conclude that no TDP can detect an error before BUP.

Kindly correct me if i am wrong.