Which of the following is TRUE regarding the running time of a LR(1) parser?
- It runs in linear time for all inputs
- It runs in polynomial time but not necessarily $O(n^3)$ for all inputs
- For some inputs it may take exponential time
- It runs in $O(n^3)$ but not always $O(n^2)$