# How to determine valid handle for given bottom up parser?

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?

## bumped to the homepage by Community♦yesterday

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

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.