GATE CS 2013 Q.9 (CS Q.9): Parsing and Syntax Analysis (LL and LR)

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 \to \epsilon$ and $A \to a$ ) to parse a string with $n$ tokens?

$n/2$

$n - 1$

$2n - 1$

$2^n$

Official answer and solution

Official answer: B
From: Official GATE 2013 answer key

Solution

Analyze how reductions reduce the symbol count on the parser stack when no epsilon or unit productions exist.

In a bottom-up parser:

The input string consists of $n$ tokens.
In each reduction step, a right-hand side of a production is replaced by its left-hand side non-terminal.
Since the grammar has no $\epsilon$ -productions ( $A \to \epsilon$ ) and no unit productions ( $A \to B$ or single symbol reductions where length does not decrease), every reduction rule must have $|\text{RHS}| \ge 2$ .
Each reduction replaces at least 2 symbols with 1 non-terminal, thereby reducing the net number of symbols on the stack by at least $2 - 1 = 1$ .
The parse begins with $n$ tokens and finishes with 1 start symbol.
To reduce the total number of symbols from $n$ to $1$ , the parser can perform at most: $n - 1 \text{ reductions}$

Thus, the maximum number of reduce moves is $n - 1$ .

Final answer

Option (B)

Common trap

Thinking that $2n - 1$ moves are possible, which is the total number of steps (shifts + reduces) rather than reduce moves alone.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 9 of 65, printed as CS Q.9
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source