Given the Grammar has no unit or ɛ-productions,
What is minimum & maximum number of shifts and reduce needed by bottom-up parser?

  • $\begingroup$ What are your thoughts? What have you tried, and where did you get stuck? Have you tried playing with some examples? We expect you to make a serious effort before asking and to show us what you've tried in the question. Otherwise, it's difficult to know exactly where you're stuck or how best to help you. $\endgroup$ – D.W. Dec 22 '14 at 1:58
  • $\begingroup$ I did try . I found out maximum number of reductions in bottom up parser (with grammer having no unit or e productions ) = 2n-1 ..Example :to get inpt string abc.. max number of reductions are 5 (S->XC->ABC->ABc->Abc->abc)...but ans in book says n-1 and its correct for sure.. i want to find out how n-1 reductions ? $\endgroup$ – Jay Teli Dec 22 '14 at 5:53

I first assume that you are considering deterministic parsing. Other tpes of parser can mimic shift-reduce in a non-derterministic context.

Assuming the there is no unit production, and no $\epsilon$-production. The maximum number of reduce is precisely the number $k$ of non-leaf (non-terminal) nodes in the parse tree, i.e. the number of productions rules used to generate the string parsed.

This number is maximum when the grammar is in binary form, i.e. with right-hand sides (rhs) of length 2 (it does not have to be in Chomsky Normal Form). Then the parse tree is a binary tree. The number of non-leaf nodes is then $n-1$ when n is the length of the parsed string.

If the maximum length for a rhs of a rule is $p$, assuming it is possible to generate a terminal string of length $n$ with only such productions, then $n=k*(p-1)+1$. So the minimum number of reduce is $k=(n-1)/(p-1)$. This formula could have been used in the binary case too.

In other words, you consider the least branching tree (binary) and the most branching tree to estimate upper and lower bound to the number of reduce.

Since the shift is pushing an input symbol on the stack, the number of shifts is the length $n$ of the string being parsed.

A document with definitions: Introduction to Shift-Reduce Parsing

Proof of the formula

We want to show that if a tree has all nodes with $p$ daughters, we have the formula $n=k\times(p-1)+1$ where n is the number of leaf nodes, and k is the number of non-leaf nodes.

The proof goes by induction on the number $k$ of non-leaf nodes.

  • Base case: $k=0$ (no non-leaf node)
    The tree is reduced to a single leaf node. Thus $n=1$. The formula is verified trivially.

  • induction case: We suppose the formula verified for all trees with less than $k$ non-leaf nodes.

    Consider a tree $T$ with $k$ non-leaf nodes. Consider a maximal path from the root of $T$ to any of its leaves. Let $U$ be the last non-leaf node on that path. All daughters of $U$ are necessarily leaf nodes, because otherwise there would be a longer path to a leaf. If you remove the subtree rooted in $U$ and replace it with a leaf $u$, you have a tree with $k'=k-1$ non-leaf nodes, but you have lost $p$ leaf nodes that were dauthers of $U$ and gained one which is $u$. Hence the number of leaves is $n'=n-p+1$.

    Since $k'<k$, by induction hypothesis, the tree satisfies the formula $n'=k'\times(p-1)+1$

    Hence $n-p+1=(k-1)\times(p-1)+1$.

    Hence $n=(k-1)\times(p-1)+1+(p-1)$, from which we get the formula for the original tree $T$ with $k$ non-leaf nodes: $n=k\times(p-1)+1$

So the formula is verified for any tree where all nodes have $p$ daughters.

This proof is valid for all values of $p$ such that $p>0$

The formula is of course applicable to parse trees when all rules have a right-hand side of length $p$, which means $p$ daughters for each node in the parse tree. It even works if you have only unary rules (but is not very useful).

In te case of binary rules, you have $p=2$ and the formula becomes: $n=(k\times(2-1)+1$, i.e. $n=k+1$. Hence the number of non-terminals is $k=n-1$ where n is the number of terminals.

This could be extended to RHS with different sizes, but it would be more complex to write.

| cite | improve this answer | |
  • $\begingroup$ Can u elaborate please on how did u get n-1 ? in "This number is maximum when the grammar is in binary form, i.e. with right-hand sides (rhs) of length 2 (it does not have to be in Chomsky Normal Form). Then the parse tree is a binary tree. The number of non-leaf nodes is then n−1 when n is the length of the parsed string." $\endgroup$ – Jay Teli Dec 27 '14 at 19:42
  • $\begingroup$ I wanted to rewrite that, but no time just now. If you consider the formula below: $k=(n-1)/(p-1)$, with $p=2$, you have $k=n-1$. This derives from the previous formula $n=k*(p-1)+1$ which can be proved by induction on $k$, i.e. on the number of non-terminal nodes, i.e. the number of rules applied to generate the tree, i.e. the number of reduce nedded to parse it, assuming all production right-hand-sides have $p$ symbols. $\endgroup$ – babou Dec 27 '14 at 20:59
  • $\begingroup$ please elaborate how did u get n-1 ? whenever u find time . thanks in advance $\endgroup$ – Jay Teli Jan 1 '15 at 20:12
  • 1
    $\begingroup$ I added the proof of the formula in the answer. $\endgroup$ – babou Jan 1 '15 at 23:47

The number of shifts is always precisely the number of symbols in the input stream, since every symbol is shifted exactly once. The number of reductions depends on the grammar; it is impossible to answer that question without knowing something about the grammar.

For example, if the grammar were in Chomsky Normal Form, you could easily count the number of reductions because for CNF grammars, the concrete syntax tree must be a complete binary tree and each node in the tree corresponds to a single reduction.

| cite | improve this answer | |
  • $\begingroup$ SOrry , i forgot to mention The condition that Grammar has no Unit and ɛ -productions . Now its pssble to calculate number of reductions ..right ? $\endgroup$ – Jay Teli Dec 21 '14 at 19:47
  • $\begingroup$ I agree with the number of shifts should be n.. where n is lenght of input string. What about no of reductions ? $\endgroup$ – Jay Teli Dec 21 '14 at 19:49
  • $\begingroup$ @JaySatishTeli: Yes, by considering the minimum and maximum size of the syntax tree. The maximum size will be the CNF case, and the minimum size will depend on the size of the largest production. $\endgroup$ – rici Dec 21 '14 at 19:51
  • $\begingroup$ Sorry but the Answer can be written in terms of lenght of input string(n)... i have a question in book to find max no of reduction for bottom up parser (with no unit or ɛ rules ) .. options are n-1 , 2n-1 , n/2 or 2^n .. $\endgroup$ – Jay Teli Dec 21 '14 at 19:55
  • $\begingroup$ @JaySatishTeli: Absolutely. The maximum can be written in terms of the length of the input string. The minimum depends on the size of the largest production in the grammar. (See en.wikipedia.org/wiki/Binary_tree#Properties_of_binary_trees) $\endgroup$ – rici Dec 21 '14 at 19:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.