2 2 votes Which of the following is correct? a) Top-down parser complexity is O(n4) b) Bottom-up parser complexity is O(n3) (A) True, False (B) False, True (C) True, True (D) False, False can anyone explain how to analyze this complexity? Theory of Computation compiler-design + – Anusha Motamarri 1.9k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 5 5 votes The top down parser actually takes O(n4) if the grammar is left recursive else O(n3) time to parse the string. Whereas in case of bottom up parser , it will take O(n3) using CYK algorithm which is a dynamic programming solution and takes O(n3)... Further there are grammars known as S- grammars which takes O(n) time to parse the string.. Reference : Read the Time and space complexity of top-down parsing part of https://en.wikipedia.org/wiki/Top-down_parsing Hence both statements given in the question are true.. Habibkhan answered Dec 26, 2016 • selected Dec 26, 2016 by Habibkhan Habibkhan comment Share Follow See all 2 Comments 2 2 Comments reply Vijay Thakur commented Dec 26, 2016 i edited by Vijay Thakur Dec 26, 2016 reply Follow flag Yes, Correct! but S-grammar has very limited scope which takes TC proportional to the length of the generated string. 0 0 replyShare Habibkhan commented Dec 26, 2016 reply Follow flag I am talking about best case scenario..Anyways we are concerned about worst case.. 0 0 replyShare Please log in or register to add a comment.
