[TUHS] Knuth and Unix

[Steve Johnson]

I remember reading Knuth's paper, and certainly heard DeRemer's name,
but it didn't affect much of what I did.  There was a paper out of
Stanford about that time that influenced me greatly -- it was about
pattern matching languages, and proposed separating two ideas: 1. 
"Here are the patterns that match this tree".  And 2.  "If more than
one pattern matches, here's how to decide which one to use."   Given
the constraints of size on the PDP 11, anything but LR(1) was
infeasable.  But using ambiguous grammars and broadening the
shift/reduce test to trest operator precedence fit right into that
pattern.   Another thing that I think was unique to Yacc at the time
was introducing symbols that matched the empty string whose reduction
caused program actions.  Many similar parser systems at the time
could not deal with these "empty" symbols.

Steve

----- Original Message -----
From: "Bakul Shah" <bakul at bitblocks.com>
To:"Steve Johnson" <scj at yaccman.com>
Cc:<arnold at skeeve.com>, <ecashin at noserose.net>, <dave at horsfall.org>,
<tuhs at tuhs.org>
Sent:Sat, 12 Jan 2019 20:40:11 -0800
Subject:Re: [TUHS] Knuth and Unix

 On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj at 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.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20190115/d44ce78f/attachment.html>