Question

Consider the following Syntax Directed Translation Scheme, with non-terminals \(\{S,A\}\) and terminals \(\{a,b\}\):

The output printed by a bottom-up parser for the input \(aab\) is

• A. \(1\;3\;2\)
• B. \(2\;2\;3\)
• C. \(2\;3\;1\)
• D. \(3\;2\;1\)

Hint:

For bottom-up parsing, semantic actions are executed during reductions. Therefore: \[ \text{Output order} = \text{Reverse of derivation order}. \] Always construct the derivation first and then reverse the production sequence to obtain the output.

Answer 1

The Correct Option is C

Concept: In a bottom-up parser, semantic actions associated with productions are executed when the corresponding reduction is performed. Thus, to determine the output, we must find the order in which reductions occur during parsing.

Step 1: Analyze the input string.
The given input is \[ aab \] We first determine its derivation from the grammar. Starting with \[ S \Rightarrow aA \] and using \[ A \Rightarrow Sb \] we obtain \[ S \Rightarrow aA \Rightarrow aSb. \] Now replace \(S\) by \(a\): \[ aSb \Rightarrow aab. \] Hence the derivation is \[ S \Rightarrow aA \Rightarrow aSb \Rightarrow aab. \]

Step 2: Determine the reductions in bottom-up parsing.
Bottom-up parsing performs reductions in the reverse order of the derivation. The input is \[ aab. \] The first reducible substring is the second \(a\). Using \[ S \rightarrow a \] we reduce \[ aab \Rightarrow aSb. \] At this reduction, the action \[ \{print\;2\} \] is executed. Therefore, the first output is \[ 2. \]

Step 3: Perform the second reduction.
Now the string is \[ aSb. \] Using \[ A \rightarrow Sb, \] we reduce \[ Sb \Rightarrow A. \] Thus \[ aSb \Rightarrow aA. \] The semantic action attached to this production is \[ \{print\;3\}. \] Hence the second output is \[ 3. \]

Step 4: Perform the final reduction.
We now have \[ aA. \] Using \[ S \rightarrow aA, \] we reduce \[ aA \Rightarrow S. \] The associated action is \[ \{print\;1\}. \] Hence the third output is \[ 1. \]

Step 5: Write the sequence of outputs.
The outputs are generated in the order \[ 2,\;3,\;1. \] Therefore, \[ \boxed{2\;3\;1} \] is printed by the bottom-up parser.

Step 6: Select the correct option.
Hence the correct answer is \[ \boxed{\text{Option (C)}} \]