The A-Z of Programming Languages: YACC

Computerworld is undertaking a series of investigations into the most widely-used programming languages. Previously we have spoken to Alfred v. Aho of AWK fame, S. Tucker Taft on the Ada 1995 and 2005 revisions, Microsoft about its server-side script engine ASP, Chet Ramey about his experience maintaining Bash, Bjarne Stroustrup of C++ fame, to Charles H. Moore about the design and development of Forth and a chat with the irreverent Don Woods about the development and uses of INTERCAL.

This interview is dedicated to the investigation of YACC, and to chatting with AT&T; alumni Stephen C. Johnson. Johnson is currently employed at The MathWorks, where he works daily with MATLAB. Computerworld snatched the opportunity recently to get his thoughts on working with Al Aho and Dennis Ritchie, as well as the development of Bison.

Please note that we are no longer following exact alphabetical order for this series due to popular demand. If you'd like to submit any suggestions for programming languages or language authors that you'd like to see covered, please email naomi@computerworld.com.au.

What made you name your parser generator in the form of an acronym: Yet Another Compiler Compiler?

There were other Compiler-compilers in use at Bell Labs, especially as part of the Multics project. I was familiar with a version of McClure's TMG. When Jeff Ullman heard about my program, he said in astonishment "Another compiler-compiler?". Thus the name...

What prompted the development of YACC? Was it part of a specific project at AT&T; Labs?

"Project" sounds very formal, and that wasn't the Bell Labs way. The Computer Science Research group had recently induced AT&T; to spend many million dollars on Multics, with nothing to say for it. Some of my co-workers felt that the group might be disbanded... But in general, Bell Labs hired smart people and left a lot of interesting problems around. And gave people years to do things that were useful. It's an environment that is almost unknown now.

YACC began for me as an attempt to solve a very simple, specific problem.

What problem were you trying to solve?

Dennis Ritchie had written a simple language, B, which ran on our GE (later Honeywell) system, and I started to use it to write some systems programs. When Dennis started to work on Unix, the compiler became an orphan, and I adopted it. I needed access to the exclusive-or operation on the computer, and B did not have any way to say that. So, talking to Dennis, we agreed that would be a good name for the operator, and I set out to put it into the compiler. I did it, but it was no fun.

One day at lunch I was griping about this, and Al Aho said "There's a paper by Knuth-I think he has a better way...". So Al agreed to build the tables for the B expression grammar. I remember giving him about 30 grammar rules, and he went up to the stockroom and got a big piece of paper, about 2 by 3 feet, ruled it into squares, and started making entries in it. After an hour of watching him, he said "this will take a while". In fact, it took about 2 days!

Finally, Al handed me the paper in triumph, and I said "what do I do with this?" He taught me how to interpret the table to guide the parser, but when I typed the table in and tried to parse, there were errors. Each error we found involved another hour of Al's time and some more rows in the table. Finally, after the third time I asked him "what are you doing when you make the table?" He told me, and I said "I could write a program to do that!" And I did...

• Bookmark this page
• Share this article
  •  
  • facebook
  • slashdot
  • digg
  • Reddit
  • stumbleupon
  • linkedin
  • twitter
• Got more on this story? Email TechWorld
• Follow TechWorld on twitter

• Share
  Share this article

  •  google+
  • facebookfacebook
  • slashdotslashdot
  • diggdigg
  • RedditReddit
  • stumbleuponstumbleupon
  • linkedinlinkedin
  • twittertwitter
• print
• email
• Bookmark