Question 56

The SDTS productions with semantic actions are:

1. $S \to aA \quad \{ \text{print } 1 \}$
2. $S \to a \quad \{ \text{print } 2 \}$
3. $A \to Sb \quad \{ \text{print } 3 \}$

To find the bottom-up parsing sequence for input string aab, determine the rightmost derivation in reverse:

In reverse, this corresponds to the following sequence of reductions:

1. The second a is reduced to $S$ using rule $S \to a$.
2. The handle $Sb$ is reduced to $A$ using rule $A \to Sb$.
3. The handle $aA$ is reduced to $S$ using rule $S \to aA$.

Step-by-step bottom-up parser actions:

1. Shift a. (Stack: a, Remaining: ab)
2. Shift a. (Stack: aa, Remaining: b)
3. Reduce top a using $S \to a$. This executes { print 2 }. (Stack: a S, Remaining: b)
4. Shift b. (Stack: a S b, Remaining: $)
5. Reduce Sb using $A \to Sb$. This executes { print 3 }. (Stack: a A, Remaining: $)
6. Reduce aA using $S \to aA$. This executes { print 1 }. (Stack: S, Remaining: $)
7. Accept.

Concatenating the printed values yields: 2 3 1. This corresponds to option C.