Topic: Compiler Design
Consider the context-free grammar G below for arithmetic expressions:
$E \rightarrow E+E|E \times E|id$
Which of the following statements is TRUE:
- A. The string $id+id \times id$ has no parse tree according to G
- B. The string "id + id \times id" has only one parse tree according to G
- C. The string "id + id \times id" has exactly two parse trees according to G
- D. The string "id + id \times id" has more than two parse trees according to G
Answer: C. The string "id + id \times id" has exactly two parse trees according to G
Explanation: The grammar is ambiguous as it does not enforce precedence. The string `id + id * id` can be parsed by first applying $E \rightarrow E+E$ or $E \rightarrow E \times E$. This leads to exactly two distinct parse trees (one grouping addition first, and the other grouping multiplication first).