What is the maximum number of reduce moves that can be taken by a bottom-up…
2021
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon-production and no single-symbol production (i.e., productions of the form A → ε and A → a) to parse a string with n tokens?
- A.
n / 2
- B.
n − 1
- C.
2n − 1
- D.
2ⁿ
- E.
Question not attempted
Attempted by 23 students.
Show answer & explanation
Correct answer: B
In a bottom-up parser, a reduce move replaces the right-hand side of a production by its left-hand side non-terminal.
Here, productions of the form A → ε and A → a are not allowed. Therefore, every reduction must replace at least two stack symbols by one non-terminal. Each reduce move decreases the number of stack symbols by at least 1.
Initially, there are n input tokens on the stack. Finally, the parse must leave one start symbol. So the number of reductions can be at most n − 1. This maximum is achieved when every reduction combines exactly two symbols into one.
Hence, the maximum number of reduce moves is n − 1.