[TUHS] Knuth and Unix

[Steve Johnson]

As I remember, the original EQN grammar had >300 S/R conflicts and 50
or so RR conflicts.  But it mostly did what you wanted.  I think Al
Aho got faint when he looked it it, though...  (It got better when
precedence was added...)

Steve

----- Original Message -----
From: "Rob Pike" <robpike at gmail.com>
To:<arnold at skeeve.com>
Cc:<scj at yaccman.com>, <tuhs at tuhs.org>
Sent:Thu, 17 Jan 2019 07:10:58 +1100
Subject:Re: [TUHS] Knuth and Unix

 I was speaking in jest... But the (official) awk grammar has been an
 eye-opener for years.

 -rob

 On Thu, Jan 17, 2019 at 5:22 AM <arnold at skeeve.com> wrote:
 >
 > 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 <robpike at gmail.com> 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 <scj at yaccman.com>
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" <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/20190117/0bc1cab8/attachment.html>