What is the maximum number of reduce moves that can be taken by a bottom-up…

Concept

In a bottom-up (shift-reduce) parser, every reduce move replaces the right-hand side of a production by its left-hand-side non-terminal. When the grammar has NO unit productions (A → a, i.e. RHS of length 1) and NO epsilon productions (A → ε, RHS of length 0), every production used in a reduction has a right-hand side of length at least 2. So each reduce move consumes at least two stack symbols and produces exactly one — a strict net decrease of at least one symbol per reduce.

Application

We start with the n tokens of the input on the stack and must collapse them down to the single start symbol. Count the reductions when each reduction is as small as possible (binary, A → B C), which maximises their number:

1. Begin with n symbols that must eventually become 1 (the start symbol).

2. Because there are no unit/epsilon productions, every reduce takes at least 2 symbols and yields 1, so each reduce lowers the symbol count by at least 1.

3. To go from n symbols down to 1, the total decrease needed is n − 1.

4. Each reduce gives a decrease of at least 1, so the number of reduce moves can be at most n − 1.

5. This bound is achieved exactly when every production is binary (A → B C): n − 1 such reductions turn n tokens into the start symbol.

Therefore the maximum number of reduce moves is n − 1.

Cross-check

Take a concrete string of n = 4 tokens, say p p q q, with a binary grammar. Reducing two adjacent symbols at a time: 4 → 3 → 2 → 1, which is exactly 3 reductions, and 3 = 4 − 1 = n − 1. The bound 2n − 1 would require reductions that each remove fewer than one symbol on average (impossible here), while 2n grows far too fast and n/2 is far too small.