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 '19 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$ – Turing101 Jul 15 '19 at 9:07
  • $\begingroup$ @downvoter please explain the proper reason of downvote rather than downvoting without any justification..PEACE $\endgroup$ – Turing101 Jul 15 '19 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$ – Turing101 Jul 15 '19 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 '19 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.