Did you experience any particular problems in the development of YACC?

Especially after I moved to Unix, memory size and performance became an obsession. We had at most 64K bytes to hold the program and data, and we wanted to do FORTRAN...

When YACC first ran, it was very slow - it implemented Knuth's ideas very literally. A grammar with 50 rules took about 20 minutes to run, which made me very unpopular with my co-workers ('Damn, Johnson's running YACC again!'). I set out to improve the size and space characteristics. Over the next several years, I rewrote the program over a dozen times, speeding it up by a factor of 10,000 or so. Many of my speedups involved proving theorems that we could cut this or that corner and still have a valid parser. The introduction of precedence was one example of this.

Dennis was actively working on B while I was writing YACC. One day, I came in and YACC would not compile - it was out of space. It turns out that I had been using every single slot in the symbol table. The night before, Dennis had added the 'for' statement to B, and the word 'for' took a slot, so YACC no longer fit!

While small memory was a major pain, it also imposed a discipline on us that removed mental clutter from our programs, and that was a very good thing.

Would you do anything differently if you got the chance to develop YACC all over again?

I'd try harder to find a notation other than $1, $2, $$, etc. While simple and intuitive, the notation is a source of errors as grammars evolve.

What's the most interesting program you've seen that uses YACC?

Some of the most interesting uses I've seen came very early. Brian Kernighan was an early user when he wrote the eqn utility that typeset mathematical equations. And Mike Lesk wrote a grammar to try to parse English. Both grammars were highly ambiguous, with hundreds of conflicts. Al Aho used to break out in a rash when he contemplated them, but they worked fine in practice and gave me some very challenging practical applications of YACC.

Have you ever seen YACC used in a way that you didn't originally intend? If so, what was it? And did it or didn't it work?

Mike's use of YACC to parse English was one. He used the YACC tables, but wrote a parser that would keep multiple parses around simultaneously. It wasn't really that successful, because even rather simple sentences had dozens of legal parses. With 64K of memory to play with, there wasn't much he could do to resolve them.

How do you feel now that other programs such as Abraxas pcYACC and Berkeley YACC have taken over as default parser generators on Unix systems?

Actually, I'm amazed that YACC is still around at all after 35 years. It's a tribute to Knuth's insights. And I also have to say that the work I put into making YACC very fast and powerful kept it viable much longer that it otherwise would have been.