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

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.