in Compiler Design
1,168 views
3 votes
3 votes
Which of the following is TRUE regarding the running time of a LR(1) parser?
  1. It runs in linear time for all inputs
  2. It runs in polynomial time but not necessarily $O(n^3)$ for all inputs
  3. For some inputs it may take exponential time
  4. It runs in $O(n^3)$ but not always $O(n^2)$
in Compiler Design
by
1.2k views

19 Comments

B?

Cause CYK algorithm takes O($n^3$) time.

Best case can be O(n) though.
0
0
When simply asked for running time it means worst case. You can confirm from Dragon book.
0
0
So, is the ans B or D?
0
0
Did you check the book?
0
0
checked chapter 4.7 on LR(1) parsers but found no mention regarding the running time
0
0

I'm sure it must be there. Anyway you can refer here too

https://en.m.wikipedia.org/wiki/LR_parser

0
0
edited by
Thank you sir, for the link... :)
0
0

But Arjun sir there are various contradicting comments in these posts on GO for linear running time of LR parsers

https://gateoverflow.in/84654/complexityofparser

Here Habibkhan sir has said that it takes O(n) time, but various comments are contradicting his statement..

0
0

And even in this also, https://gateoverflow.in/91761/parsers-complexity

Bottom up parsers exhibit O($n^3$) and LR parser being a bottom up parser should do the same i guess.

I am finding it difficult to grasp this concept.. :(

0
0
Wikipedia is not perfect but should be better than some comments. Anyway can you give the time complexity of CLR parser?
0
0
Is there any difference between CLR and LR(1) parser?
0
0
I think that there is no difference then LR(1)/CLR being a bottom up parser must hold O($n^3$)
0
0
It'll hold O(n^3) - the question is if it'll also hold O(n).

CLR(1) parsing technique you must be knowing. So you can count it's time complexity.
0
0
okay sir, thanks. :)
0
0
According to Wikipedia, any bottom-up parser takes $O\left ( n^{3} \right )$ time.

But as in LR parser it has done single stack operation (like matching and then reduction), so it can take $O\left ( n \right )$ time too.

right??
0
0
4
4
So how can option A be true ?
0
0
From the above image isn't A option straight forward?
1
1

For LR parsers the ideal time complexity is linear time but some methods may take O(n^3)  time in the worst case.

so,In more general way, good to take it as an ideal condition, the answer will be A.

 

0
0

Please log in or register to answer this question.

Answer:

Related questions