Time for a new thread :-) As today is Knuth's birthday (posted over in COFF), I was wondering (in the cesspool that is my mind) how much of Unix would have been influenced by Knuth? We have qsort() of course (which Hoare actually wrote, based on one of Knuth's algorithms), but I'm guessing that Ken and Dennis would have been familiar with his work? Or am I spreading fake news again? :-) Look, I love being corrected if I make a mistake on a technical mailing list, so fire at will if need be... -- Dave

Knuth is great, and I too am interested to know about his influence on UNIX, but Hoare is credited with the quicksort algorithm by the authorities I've encountered.

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.

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" &lt;bakul(a)bitblocks.com&gt; To:"Steve Johnson" &lt;scj(a)yaccman.com&gt; Cc:<arnold@skeeve.com>, &lt;ecashin(a)noserose.net&gt;et>, &lt;dave(a)horsfall.org&gt;rg>, &lt;tuhs(a)tuhs.org&gt; 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" &lt;scj(a)yaccman.com&gt; wrote: 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.

You can't lay the blame for that on Steve. The GNU Awk grammar has only 36 shift-reduce conflicts and no reduce-reduce conflicts. The mawk 1.3.4 grammar has an amazing count of only *four* shift-reduce conflicts. (But then, Mike Brennan is an amazing programmer.) I have no idea what happens if you run the POSIX awk grammar through yacc / bison, but it'd be an interesting experiment. Arnold Rob Pike &lt;robpike(a)gmail.com&gt; wrote: > So you're the reason (Plan 9) awk has 83 reduce-reduce conflicts (and > 42 shift-reduce). > > -rob > > On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson &lt;scj(a)yaccman.com&gt; wrote: > > > > 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" &lt;bakul(a)bitblocks.com&gt; > > To:"Steve Johnson" &lt;scj(a)yaccman.com&gt; > > Cc:<arnold@skeeve.com>, &lt;ecashin(a)noserose.net&gt;et>, &lt;dave(a)horsfall.org&gt;rg>, &lt;tuhs(a)tuhs.org&gt; > > 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" &lt;scj(a)yaccman.com&gt; 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. > >

I was speaking in jest...

But the (official) awk grammar has been an eye-opener for years.

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.