GATE CS 2003 Q58 — Parsing (LL, LR)

To find the output printed by the translation scheme for the input string 9 + 5 + 2, we construct the parse tree and execute the semantic actions during a depth-first (left-to-right) traversal.

1. Parse Tree Construction

The input string is 9 + 5 + 2. The parse tree based on the given grammar is shown below:

       S
      / \
     T   R
     |   / | \
     9  +  T  {print('+')}  R
           |               / | \
           5              +  T  {print('+')}  R
                             |                |
                             2                ε

2. Traversal and Action Execution

We perform a left-to-right depth-first traversal of the parse tree, executing the semantic actions (enclosed in curly braces { }) as they are encountered:

1. Traverse the leftmost child of $S$, which is $T \rightarrow \mathbf{num}\{\text{print}(\mathbf{num}.\text{val});\}$ with $\mathbf{num}.\text{val} = 9$.
   Action: print(9)
   Output so far: 9
2. Move to $R$. Match the terminal symbol +.
3. Traverse $T \rightarrow \mathbf{num}\{\text{print}(\mathbf{num}.\text{val});\}$ with $\mathbf{num}.\text{val} = 5$.
   Action: print(5)
   Output so far: 9 5
4. Execute the action associated with $R \rightarrow + T \{\text{print}('+');\} R$.
   Action: print('+')
   Output so far: 9 5 +
5. Traverse the nested $R$. Match the terminal symbol +.
6. Traverse $T \rightarrow \mathbf{num}\{\text{print}(\mathbf{num}.\text{val});\}$ with $\mathbf{num}.\text{val} = 2$.
   Action: print(2)
   Output so far: 9 5 + 2
7. Execute the action associated with the nested $R$.
   Action: print('+')
   Output so far: 9 5 + 2 +
8. Traverse the innermost $R \rightarrow \varepsilon$, which performs no action.

The final printed output is 9 5 + 2 +.