ISRO CS 2023 Q.8: solution and answer

Official answer: CSource: ISRO's revised and final answer key of 16 February 2024

1. The grammar is $E\to E+E\mid E\times E\mid \text{id}$. It gives no precedence or associativity, so a string with several operators can be grouped in more than one way.

2. The string id + id × id has two operators. The root of a parse tree uses either $E\to E+E$ or $E\to E\times E$, and the root's operator is the one applied last. The root cannot use $E\to \text{id}$, because the string has more than one token.

3. Root $E\to E+E$: the string splits at the +. The left $E$ must derive id, which is possible only by $E\to \text{id}$. The right $E$ must derive id × id, which is possible only by $E\to E\times E$ with each side $E\to \text{id}$. This gives exactly one tree, with grouping $\text{id}+(\text{id}\times \text{id})$.

4. Root $E\to E\times E$: the string splits at the ×. The left $E$ must derive id + id, which is possible only by $E\to E+E$ with each side $E\to \text{id}$. The right $E$ derives id. This gives exactly one tree, with grouping $(\text{id}+\text{id})\times \text{id}$.

5. Each operator occurs once in the string, so each root choice splits the string at a single, fixed place, and each part has a unique tree. The total is $1+1=2$ parse trees.

6. So trees exist (option (a) is false), more than one exists (option (b) is false), and there are not more than two (option (d) is false). The statement that the string has exactly two parse trees is true: option (c).