# What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows:

Assume a rightmost derivation $\require{AMScd}$ \begin{CD} S @>{\text{*}}>> \alpha X\omega @>{}>>\alpha\beta\omega \end{CD} Then $\alpha\beta$ is a handle of $\alpha\beta\omega$.

When I referred the Dragon Book, it says:

if $\require{AMScd}$ \begin{CD} S @>{\text{*}}>> \alpha A\omega @>{}>>\alpha\beta\omega \end{CD} then production $A\rightarrow\beta$ in the position following $\alpha$ is a handle of $\alpha\beta\omega$. For convenience, we refer to the body $\beta$ rather than $A\rightarrow\beta$ as a handle.

So which one is correct? Is $\alpha\beta$ called as handle, or just $\beta$?

"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."

Charles Dodgson -- who wrote those words under the name of Lewis Carroll -- was a brilliant mathematician with a taste for whimsy, all of which provide an interesting undercurrent to works such as Through the Looking Glass. Humpty's creed could have been taken directly from Dodgson's textbook on Symbolic Logic:

[Authors of other textbooks on logic]… speak of the Copula of a Proposition “with bated breath”, almost as if it were a living, conscious Entity, capable of declaring for itself what it chose to mean, and that we, poor human creatures, had nothing to do but to ascertain what was its sovereign will and pleasure, and submit to it.

In opposition to this view, I maintain that any writer of a book is fully authorised in attaching any meaning he likes to any word or phrase he intends to use. If I find an author saying, at the beginning of his book, “Let it be understood that by the word ‘black’ I shall always mean ‘white’, and that by the word ‘white’ I shall always mean ‘black’,” I meekly accept his ruling, however injudicious I may think it. (Dodgson18??, p. 166)

This is particularly true in computer science, in which most papers seem to be about 75% definitions, loosely interconnected with proofs. The definitions need to be repeated in every paper because there are often conflicting uses of the same phrases in the literature. This often creates a kind of cognitive dissonance for learners, who have been schooled in a model of teaching which presents definitions as received truth:

To be more accurate, we might say that what eludes the students is the distinction between a dictionary definition as a description of pre-existing objects and a mathematical definition as the chosen basis for deduction, one which serves to determine the nature of the objects. (AS2002, p. 33, emphasis added).

The distinction is important. Definitions are a way to organise one's understanding of the world, and the liberty to choose categories appropriately is an important part of mathematical thinking. So Dodgson's advice and Simon & Alcock's observation, both directed at teachers of mathematics, seem to me to continue to be relevant.

On that basis, I assert that Alex Aiken has every right to define "handle" as he sees fit. Perhaps he has a good reason to use this particular definition, which will be revealed later. Or perhaps not, because we all make mistakes, even famous presenters of popular courses. The test will come later, when the definition proves to be useful (or not). Because definitions (in the mathematical sense) are neither right nor wrong; they are simply useful or not.

However, like Dodgson, I too reserve the right to think that a definition may be injudicious, and it seems to me that Aiken's definition of handle as being the entire input up to the point of reduction is not as useful as the normal definition of handle as a production which could be reduced at a given point of input. (As the authors of the Dragon book point out, although they often talk about handles as though they were a subsequence of the stack, they actually define the handle to be the production itself.)

Both definitions involve the necessary fact that a handle is rooted in a moment in the parse. The fact that the right-hand side of a production happens to match the top of the stack does not necessarily make that production into a handle; it is only a handle because the reduced stack could appear in a rightmost derivation.

Aiken later talks about the handle as something which can be reduced, which implies that it is not simply the stack at the point of the reduction, as his definition appears to say, but the stack at the point of the reduction with a marker indicating what reduction will take place. If it were just the stack, an ambiguous grammar would have a single handle, which obscures the concept of ambiguity. I prefer to say that a grammar is ambiguous if there could be more than one handle at a point in the parse.

I have no doubt that Aiken, Aho&al, and, less importantly, I have the same concept of what a handle is for. And the essential point of that concept is that a reduction (or right-hand side) is a handle for the entire parser stack, not just a reduction whose right-hand side happens to match the top of the stack.

This would all be a minor point if it were not for the quiz Aiken inserts into the course immediately following his definition, which asks the student to focus on the definition rather than the use (in the sense highlighted by Alcock & Simpson).

[AS2002] Alcock, L. and Simpson, A. P. (2002) 'Definitions : dealing with categories mathematically'. In For the learning of mathematics, vol. 22 No. 2, pp. 28-34.

[Dodgson1896] Dodgson, Charles Ludwig (published under the name Lewis Carroll) (1896), 'Symbolic Logic', 2nd edition.