How to determine valid handle for given bottom up parser?

Question

I came across following question:

Consider the grammar:

$E → E + n\text{ | }E × n\text{ | }n$

For a sentence n + n × n, the handles in the right-sentential form of the reduction are
(A) $n, E + n$ and $E + n × n$
(B) $n, E + n$ and $E + E × n$
(C) $n, n + n$ and $n + n × n$
(D) $n, E + n$ and $E × n$

Solution given was:

n+n×n   
E+n×n  //reduce n to E
E×n    //reduce E+n to E
E      //reduce E×n to E

Hence option D

Then I came across following problem:

Consider the following grammar:
$A\rightarrow A(B)|B$
$B\rightarrow B*C | id $
$C\rightarrow (id)$
Which of the following can be the correct handle in bottom up parsing for the given grammar? (A) (id)
(B) id*C
(C) id
(D) none

The given solution was (A)(id)

Doubts

1. After thinking about the definition of the handle and two problems, I concluded following:

   • If problem asks which are valid handles for given string and grammar, then we have to actually try parsing that string with given grammar and determine which handles are reduced during parsing.

   • But, if no string is given, and just the grammar is given, then following are valid handles:
     (a) right hand side of each production
     (b) those sentential forms which can be derived from start symbol by doing rightmost derivation are valid handles. For example, $B*(id)$ is a valid handle as we can derive it by doing rightmost derivation as follows: $S\rightarrow B\rightarrow B*C\rightarrow B*(id)$

2. As explained in 2nd bullet point of point 1 above, answer of 2nd problem is wrong and both of $A$ and $C$ options are correct: both $(id)$ and $id$ are valid handles.

Am I correct with both conclusions above?

Answer 1

A handle is a production whose right-hand side can be reduced at a specific moment during a parse. (Or, as it is usually presented, it is the production which has been expanded at a specific point in a derivation for a sentence.) Although a handle is almost always defined as a production, it's common to talk about them as though they were just the right-hand side. That's clearly not correct because you cannot reduce a handle without knowing what it will reduce to, but in many contexts (including multiple-choice exams) it's possible to get away with this informality.

So I'd disagree that $B∗(id)$ is a handle, because it is not the right-hand side of any production. That doesn't really alter your question about whether $id$ is a handle.

A production (or its right-hand side) could be a handle for a grammar if there exists a derivation which involves that production. That is not necessarily the case for every production in a grammar, since grammars can include unreachable and useless productions. However, the grammar you present does not include any such productions. There exist derivations which use each of the productions, including $B\to id$ and $C\to (id)$. On that basis, I agree that both (A) and (C) are correct answers.