From: Dennis Ritchie <dmr@bell-labs.com>
Newsgroups: comp.compilers
Subject: Re: O(n) Good Enough
Date: 19 Jan 1999 00:52:05 -0500
Keywords: C, parse, history

Glen Austin wrote, in an aside:

> (It's my understanding that the folks at AT&T
> used to design the yystate, yyreduce, yygoto, yyrule, etc. tables by
> hand, before yacc was designed, imagine that.)

Not for real compilers.  Probably for books/courses illustrating the
principles.  On the other hand there was compiler work at Bell Labs
outside the Sethi/Ullman/Aho/Johnson group that I don't know much
about.  E.g. there was a language called EPL/X used in switching
systems whose code generation techniques influenced those in the first
C compiler, but I know nothing about how it was parsed.

	Dennis

From: David R Tribble <dtribble@technologist.com>
Newsgroups: comp.compilers
Subject: Re: O(n) Good Enough
Date: 22 Jan 1999 21:27:32 -0500
Keywords: parse, history

Glen Austin wrote, in an aside:
>> (It's my understanding that the folks at AT&T used to design the
>> yystate, yyreduce, yygoto, yyrule, etc. tables by hand, before
>> yacc was designed, imagine that.)

Dennis Ritchie wrote:
> Not for real compilers.  Probably for books/courses illustrating the
> principles.  On the other hand there was compiler work at Bell Labs
> outside the Sethi/Ullman/Aho/Johnson group that I don't know much
> about.  E.g. there was a language called EPL/X used in switching
> systems whose code generation techniques influenced those in the first
> C compiler, but I know nothing about how it was parsed.

Glen got the story from me, which I got from the book "Twenty-Five
Years of Unix" by Peter Salus (ISBN 0-201-54777-5).  It was actually a
discussion of the origin of YACC by Steve Johnson.  It dealt with the
B compiler, not the C compiler, which is not exactly how I remembered
it when I passed the story on to Glen.  So Glen probably got the wrong
details from me.

Here's the relevant extract from the book (p.99):

  (Quoting Steve Johnson)

    I talked to Al Aho, because I had heard that he had an interest
  in new methods for handling expressions.  This was quite a funny
  scene.  Al kept on nodding and saying "Yes, I've read this paper
  by Knuth and it's a much better method."  So we worked out a
  simple grammar for expressions in B, and he kept on saying "I'll
  make up the parsing tables for you."  But it got postponed a
  couple of times.  Finally, he went up to the stockroom and got
  the biggest piece of paper they had, about two feet square,
  spread it out on the table, and divided it up into little, tiny
  squares.  And then he started making these little incantations
  over the thing and muttering and writing these little symbols in.
  And I watched him for a while, and he said "Why don't you go do
  something else, and I'll let you know when I'm done?"  So I went
  away and came back every couple of hours and he was still
  muttering over this thing, as his pencil moved across.  And
  eventually, at the end of the first day, he said, "I'll finish
  this up tomorrow."  Finally, the next day, he said, "It's
  finished" and handed it to me.  And I said, "What do I do with
  this?"
    So he showed me how to make a parser, and we typed the table
  in.  We parsed a couple of expressions correctly, and then we
  parsed another expression and it was wrong - there was a bug in
  the table.  And Al said, "Oh, no!" and spent another two or
  three hours erasing and we typed the new table in and got rid
  of that bug, and then there was another bug.  So I said, "Al,
  why don't you tell me what you're doing?"  And he said, "Well,
  okay, it's not really very hard."  And he told me how to make
  the table.  And I said, "Oh, I can write a program to do that."
  He said, "Really?"  So, that's how yacc was born.

I highly recommend the book.

-- David R. Tribble, dtribble@technologist.com --

From: Dennis Ritchie <dmr@bell-labs.com>
Newsgroups: comp.compilers
Subject: Re: O(n) Good Enough
Date: 23 Jan 1999 17:29:40 -0500
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.

	Dennis