2 votes 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 asked Dec 26, 2016 • edited Oct 4, 2017 by LeenSharma Anusha Motamarri 1.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 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 See all 2 2 Comments reply Vijay Thakur commented Dec 26, 2016 i edited by Vijay Thakur Dec 26, 2016 reply Follow Share Yes, Correct! but S-grammar has very limited scope which takes TC proportional to the length of the generated string. 0 votes 0 votes Habibkhan commented Dec 26, 2016 reply Follow Share I am talking about best case scenario..Anyways we are concerned about worst case.. 0 votes 0 votes Please log in or register to add a comment.
