3 votes 3 votes Compiler Design compiler-design parsing + – Ashwani Kumar 2 asked Dec 11, 2016 • edited Jun 21, 2022 by Lakshman Bhaiya Ashwani Kumar 2 1.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 5 votes Both are true.. For top down parser , the worst case complexity is O(n4) for left recursive grammar and O(n3) for right recursive grammar.. However for bottom up parser using the CYK algorithm , we will get upper bound of O(n3) whatever the CFG be (either left recursive or right recursive).. Hence C) is the correct answer.. Reference : https://en.wikipedia.org/wiki/CYK_algorithm https://en.wikipedia.org/wiki/Top-down_parsing Habibkhan answered Dec 11, 2016 • selected Jul 14, 2019 by Bikram Habibkhan comment Share Follow See 1 comment See all 1 1 comment reply jatin khachane 1 commented Nov 15, 2018 reply Follow Share Sir, we can think of Parsing as nothing but Membership problem for CFL right .. 0 votes 0 votes Please log in or register to add a comment.
