GATE Overflow | Compiler Design | Test 1 | Parsing | Question: 11

Question

Which of the following is TRUE regarding the running time of a LR(1) parser?

• A. It runs in linear time for all inputs
  
• B. It runs in polynomial time but not necessarily $O(n^3)$ for all inputs
  
• C. For some inputs it may take exponential time
  
• D. It runs in $O(n^3)$ but not always $O(n^2)$

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

---

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

---

https://nptel.ac.in/courses/106108113/module3/Lecture6.pdf

Page 8.

 

 

 

---

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.