What is the maximum number of reduce moves that can be taken by a bottom-up…
2013
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?
Answer: B. \(n-1\) — Key idea: every reduce replaces at least two symbols (no epsilon- or unit-productions), so each reduce decreases the total number of symbols by at least 1.…
- A.
\(n/2\) - B.
\(n-1\) - C.
\(2n-1\) - D.
\(2^n\)
Attempted by 42 students.
Show answer & explanation
Correct answer: B
Key idea: every reduce replaces at least two symbols (no epsilon- or unit-productions), so each reduce decreases the total number of symbols by at least 1.
Start with n tokens in the sentential form.
A reduce replacing k ≥ 2 symbols by one nonterminal reduces the total length by k − 1 ≥ 1.
To get from length n to a single start symbol we need a total decrease of n − 1, so there can be at most n − 1 reduce moves.
This maximum is achievable if every reduce combines exactly two symbols (binary merges), producing exactly n − 1 reduces.
Conclusion: The maximum number of reduce moves is n-1.