GATE 2013 CSIT SET-A Q9 Compliers-Parsers HD

View it here too: http://www.gnostopedia.com/gate/video/gate-13-csit-q9 ORIGINAL QUESTION: Q9) What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → є and A → a) to parse a string with n tokens? (A) n/2 (B) n-1 (C) 2n-1 (D) 2n CORRECTED QUESTION WITH REASONS GIVEN IN THE VIDEO: Q9) What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → є and A → B) AND with no productions of the type A → a to parse a string with n tokens? (A) n/2 (B) n-1 (C) 2n-1 (D) 2n ANS: (B) Source for Unit Production Definiton: 1) NPTEL: http://www.learnerstv.com/video/Free-video-Lecture-15599-Computer-Science.htm 2) Google Books: http://books.google.co.in/books?id=s7gEErax71cC&pg=PA334&lpg=PA334&dq=unit+production+in+automata&source=bl&ots=__-ogXOvLl&sig=bvxaHHyi4RVjZO8M1XLCv0EdhLw&hl=en&sa=X&ei=6FA0U6HjDor9rAfmmYCQCA&sqi=2&ved=0CCkQ6AEwAA#v=onepage&q=unit%20production%20in%20automata&f=false Source for Shift Reduce Example: http://www.cs.york.ac.uk/fp/lsa/lectures/shiftreduce.pdf Reference Books: "Compilers - principles techniques and tools" by alfred aho - monica lam- ravi sethi- jeffrey ullman - second edition Designed, Created and Developed by Stanly Samuel (99.5 percentile holder in GATE 2013) facebook.com/stanlysir