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

Best case can be O(n) though.

Dark Mode

Arjun
asked
in Compiler Design
Jan 26, 2019

1,168 views
3 votes

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)$

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

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

0

0