--- Begin Message ---
|
Subject: |
Re: What year was YACC born? |
|
Date: |
Wed, 13 Feb 2019 10:34:07 -0800 |
Hi, Eric,
Yacc was born in 1971, but went through many transformations -- it was
close to its current form in late 1973.
Before that, here was a version of TMG that served as a parser
generator -- I think McIlroy or Morris lifted it from Multics.
It did recursive descent parsing, so the languages it could handle
were very powerful. However, if you made a
syntax error, it would potentially go all the way back to the
beginning of the text looking for another legal parse.
So the syntax error message gave you no hint whatsoever as to where
the error was. Dennis' B and C compilers
used top-down parsers-- they were gloriously useful with statements,
but expressions sucked.
I took over Dennis' B compiler and ported it to the GE mainframe in
the computation center. I was writing
something that really needed an XOR operator. After discussions with
Dennis, we picked the ^ character
and I went to work. It was pretty terrible--took me a week to get
the precedence right. I was bitching about
this at lunch one day, and Al Aho said that Knuth had a paper on a
better way to build parsers.
We made a date to meet a couple of days later, and I had written out a
set of grammar rules for B expressions--
it had about 30 rules. Al went up to the stockroom and came back
with a huge piece of graph paper, marked
off into little squares. He looked at the rules and started filling
in the squares. After an hour or two he said
he would need a little more time, and I should come back later. I
think it was the next day before he had
filled out the table. I asked him what I should do with this, and he
showed me how to build the parsing engine.
A day later, I had typed in the table and built the parsing engine.
I got through a = b and a = b + c and
even a = b + c * d, but it failed with a = b*c + d. Al went back and
in a couple of hours gave me a revised
table. I think the next thing that went wrong was something with
parentheses. After a couple of more spins,
I asked him what he was doing to build the tables. He showed me, and
I said "I can write a program to
do that!" and did.
The original Yacc didn't really make it that much easier to add
operators, so I figured out how the
tables could be bullt to incorporate precedence information...
The name cames as a result of a comment by Jeff Ullman -- Al was
telling him about the program,
and he said "What? Yet Another Parser Generator?" So I started
calling it Yacc.
The first implementation was really slow. We were all sharing a
single PDP 11 with Unix on it, and
Yacc could take 20 minutes to generate a 50-rule grammar table.
Everyone would groan when i
started the program: "Ohhhh. Johnson's running Yacc again".
I spent the next couple of years engineering the algorithms and data
structures -- I estimated that
in those two years I sped Yacc up by a factor of 10,000. I had to
prove a couple of theorems
along the way to convince myself that the result would be correct,
especially with precedence,
empty productions, and ambiguous grammars. The other effort was to
minimize the amount of
space used so we could do bigger grammars on the PDP-11. We were
finally able to do F77.
The "YA" prefix picked up a life of its own. Probably the best known
derivative was YAHOO
(Yet Another Hierarchical Officious Oracle).
Hope this was helpful...
Steve
----- Original Message -----
From: "address@hidden (Eric S." <Raymond)>
To:<address@hidden>
Cc:
Sent:Tue, 12 Feb 2019 05:48:12 -0500 (EST)
Subject:What year was YACC born?
I'm trying to write "A Brief History of the Greater Ungulates".
What year was YACC born? Web searches don't pin this down.
It was "Yet Another" but I can't find any traces of previous
compiler-compilers. Which previous one(s) dod you have in mind?
--
<a href="http://www.catb.org/~esr/";>Eric S. Raymond</a>
A true libertarian supports free enterprise, opposes big business;
supports local self-government, opposes the nation-state; supports
the
National Rifle Association, opposes the Pentagon. -- Edward Abbey
--- End Message ---