Bottom up parsers in worst case take O($n^3$) time, and i believe that LR parser being a bottom up parser should also take O($n^3$) time, but i read on wiki that they are able to solve problems in linear time. How can this be possible?

  • $\begingroup$ Which "wiki" did you read that? Could you provide a reference or quoted text? $\endgroup$ – dkaeae Jul 15 at 7:06
  • $\begingroup$ @dkaeae en.m.wikipedia.org/wiki/LR_parser , Moreover see the ans below provided by rici, so he is also suggesting O(n)! $\endgroup$ – HIRAK MONDAL Jul 15 at 9:07
  • $\begingroup$ @downvoter please explain the proper reason of downvote rather than downvoting without any justification..PEACE $\endgroup$ – HIRAK MONDAL Jul 15 at 17:19

It's because they can only recognise a subset of context-free languages. In fact, it is the subset which can be parsed in linear time: languages with a deterministic grammar.

  • $\begingroup$ so worst case case of LR parser is O(n)? $\endgroup$ – HIRAK MONDAL Jul 15 at 9:08
  • 1
    $\begingroup$ @hirak: yes, the LR parser always takes O(n) time. It can only take less time if the input can be rejected early. $\endgroup$ – rici Jul 15 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.