334 views
\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*}
edited | 334 views

Though, Tob Down parser suffers from backtracking ( takes exponential time in the worst case) but Predictive Top down parser does not suffer from backtracking and takes only linear time in parsing any input.

Now coming to Bottom Up parser, First of all, it is very difficult to make its parsing table and more over it takes O(n2) time in parsing any input. But it is efficient than predictive parsing in finding errors.

Hence ans should be true.

Parsing for both the parsers is essentially done in the same way in a slightly different fashion.

There are some instances where bottom-up performs faster than top-down .

Consider grammar:

E->E+T/T

T->T-F/F

F->id

Now, consider a derivation of the form:

E

=E+T

=E+T+T

=E+T+T+T

.

.

.

= E+T+T+T+T+T............................+T+T+T   (after 100 substitutions)

= T+T+T+T+T............................+T+T+T+T

= F+T+T+T+T............................+T+T+T+T

= id+T+T+T+T............................+T+T+T+T

.

.

.

= id+id - id+id+id......................+id+id

Now, consider the faulty string:

id+-id+id+id...........................id+id+id

Note the following derivation of bottom-up parser for the above faulty string in reverse:

id+-id+id+id...........................id+id+id

= F+-id+id+id...........................id+id+id            (the oncept of handle)

= T+-id+id+id...........................id+id+id            (the oncept of handle)

= E+-id+id+id...........................id+id+id            (the oncept of handle)

Now, '+' is shifted onto the stack and the finite automata enters some state si.

Now, si after looking at '-' will not be able to move ahead since its expecting 'id'. At this stage the error is detected.

So, bottom-up parser could detect the error in 3-4 steps.

But, top-down parser initially  is  just substitutuing for variable E at each step until it reaches the bottom of the parse  tree after 100 substitutions.  The derivations are shown above.

So, top-down will detect the error after more than 100 steps.

So, bottom-up outperformed top-down parser in error-detection.

But I am not able to think of a situation where top-down outperforms bottom-up in error detection.

So, for me, its false.

@Anusha. Sorry, I forgot that we cant parse left recursive grammar using top-down parser  :) So, ignore above answer.
I am not able to get any reference. I  think, they should be detecting the error more or less at the same time.

Thanks for awarding me with a downvote :)

https://www.quora.com/What-is-the-difference-between-Top-Down-parsing-and-Bottom-up-parsing-in-programming-languages

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

@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.

@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.

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.