13 Jan
2019
13 Jan
'19
10:40 a.m.
On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj(a)yaccman.com>
wrote:
One connection Knuth had to Unix was inventing LALR
parsing, the basic
algorithm used in Yacc. I added some things (notably, the precedence
mechanism) and had to do a lot of engineering to be able to handle large
grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught to
my be Al Aho) was all Knuth.
Knuth invented LR parsing but IIRC it was DeRemer who came up
with LALR parsing. In 78-79 I was implementing a LALR(1)
parser generator in Pascal on strength of which I got my first
real job. At that job I used DeRemer and Pennello's 1979
paper to reimplement the parser generator.