GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
194 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*}$
asked in Compiler Design by Veteran (11.4k points)  
edited by | 194 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 :)

this article may be helpful.  

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.

Please log in or register to answer this question.

Related questions

Members at the site
Top Users Feb 2017
  1. Arjun

    4672 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,531 comments
21,923 users