1,168 views
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)$

### 19 Comments

B?

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

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

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

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

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

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

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.. :(

Wikipedia is not perfect but should be better than some comments. Anyway can you give the time complexity of CLR parser?
Is there any difference between CLR and LR(1) parser?
I think that there is no difference then LR(1)/CLR being a bottom up parser must hold O($n^3$)
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.
okay sir, thanks. :)
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??
So how can option A be true ?
From the above image isn't A option straight forward?

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.

Answer:

6 votes
2 answers
1
1,194 views
3 votes
2 answers
2
598 views
5 votes
3 answers
3
3 votes
1 answer
4
2,929 views