# 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?

Posted on Categories proxies