A very beautiful question on bottom up parser,help please?


4.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?



Now this indeed a beautiful question and after I solved it I saw some other threads and observed that there have been some confusion among students regarding this question.

The best approach in these type of questions where you need to find something for general n term is to start with small,lets say we start with :

  1. n = 1 - take for example string a or b,now since there are no production of the form A -> a or b or c ,a string length of 1 cant be derived from this restricted form of grammar given.

2)n = 2 - lets take example - ab and we will try to find a bottom up parsing for this which actually gives you a rightmost derivation in reverse,so alone a cant be reduced as above logic,alone b cant be reduced,ab together can be reduced to some Non terminal say C and say C then can be reduced to S.
Now some people have doubt here that after we reduced to C ,there can be infintely many production rule like A ->C,B ->C,D->C,E->C,then the number of reduce steps will become infinte,but keeping the things simple and with general common sense we assume that only such production rule is there.
So the derivation will be like S -> C -> ab,which has 2 reduce steps.
options c and d gets eliminated as they will give answer 3,4 respectively for n = 2.

3)Lets take n = 3,abb or you can take any string aaa,abb,baa doesnt matter.logic is same.Now there can be two ways to reduce it like we reduce first ab to some nonterminal C then Cb gets reduced to S or we reduce bb first to some non terminal C,then aC gets reduced to S,the starting symbol.,so there are only two reduce operations happening ,so for n = 3 ,answer is 2.The minimum can be 1 ,we can have a direct production of S->abb if you thinking about minimum.

You can try for n = 4 or some larger strings too.

The basic logic is we cant reduce a single terminal to a non terminal,now since we have to find maximum ,the best we can do is to reduce two terminals in the starting to some non terminal,if we reduce three non terminals to a single non terminal we will not get maximum reduce steps,the only restriction is the grammar should not have the epsiilon and unit production,rest how the grammar will be is we have to decide so that we can maximum number of reduce steps for a given string of length n.
So after reducing two terminals to a non terminal we might get like Cdd (if n = 4)now ,we either can reduce Cd to some non terminal D,then finally Dd to S,or dd can be reduced to D,then CD to S,in either case answer is n-1.