Re: O(n) Good Enough

Dennis Ritchie <>
23 Jan 1999 17:29:40 -0500

          From comp.compilers

Related articles
O(n) Good Enough (Quinn Tyler Jackson) (1999-01-15)
Re: O(n) Good Enough (1999-01-17)
Re: O(n) Good Enough (James Jones) (1999-01-17)
Re: O(n) Good Enough (Glen Austin) (1999-01-17)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-19)
Re: O(n) Good Enough (David R Tribble) (1999-01-22)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-23)
| List of all articles for this month |

From: Dennis Ritchie <>
Newsgroups: comp.compilers
Date: 23 Jan 1999 17:29:40 -0500
Organization: Bell Labs, Lucent Technologies
References: 99-01-052 99-01-058 99-01-065 99-01-080
Keywords: parse, history

This thread (building parser tables by hand at Bell Labs) has probably
just about run out, but I can't resist a coda-- Aho was around a day
or so ago (yes, he's back at Bell Labs) and I mentioned Steve's story
to him. His memory is consistent enough with the Johnson account
quoted directly by Tribble from the Salus book and indirectly nearer
the start of the thread. The main difference is that Al remembered
laboring over the big pieces of paper on the weekend by himself, then
typing in the handwriting with Steve and debugging during the week.

In some ways the interesting thing is that the parser (probably for B,
couldn't have been C based on radiocarbon dating evidence) was tiny
and dead simple using recursive descent for most parts, a precedence
table for expressions. But out of the intellectual
culture-meets-culture encounter, an enduring tool was created.

An earlier example Aho related: he and Steve first started to work
together when Al remarked on a book on category theory and recursive
functions: he didn't understand the category theory notation. Steve,
a math PhD, approached Al and let him know that he understood category
theory quite well, but not recursive function theory. They connected.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.