Re: O(n) Good Enough

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

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