The Unix Heritage Society mailing list
 help / Atom feed
* [TUHS] Knuth and Unix
@ 2019-01-10  0:19 Dave Horsfall
  2019-01-10  0:54 ` Ed Cashin
  2019-01-10  3:14 ` Jim Capp
  0 siblings, 2 replies; 15+ messages in thread
From: Dave Horsfall @ 2019-01-10  0:19 UTC (permalink / raw)
  To: The Eunuchs Hysterical Society

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

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-10  0:19 [TUHS] Knuth and Unix Dave Horsfall
@ 2019-01-10  0:54 ` Ed Cashin
  2019-01-10  7:39   ` arnold
  2019-01-10  3:14 ` Jim Capp
  1 sibling, 1 reply; 15+ messages in thread
From: Ed Cashin @ 2019-01-10  0:54 UTC (permalink / raw)
  To: Dave Horsfall; +Cc: The Eunuchs Hysterical Society

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.

(A little Googling suggests I'm not misremembering.)

On Wed, Jan 9, 2019 at 7:19 PM Dave Horsfall <dave@horsfall.org> wrote:
>
> 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



-- 
  Ed Cashin <ecashin@noserose.net>

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-10  0:19 [TUHS] Knuth and Unix Dave Horsfall
  2019-01-10  0:54 ` Ed Cashin
@ 2019-01-10  3:14 ` Jim Capp
  1 sibling, 0 replies; 15+ messages in thread
From: Jim Capp @ 2019-01-10  3:14 UTC (permalink / raw)
  To: Dave Horsfall; +Cc: The Eunuchs Hysterical Society

[-- Attachment #1: Type: text/plain, Size: 830 bytes --]

I learned about Knuth from reading Unix man pages. I was intrigued enough to purchase his 3 volume set "Art of Computer Programming". 


From: "Dave Horsfall" <dave@horsfall.org> 
To: "The Eunuchs Hysterical Society" <tuhs@tuhs.org> 
Sent: Wednesday, January 9, 2019 7:19:05 PM 
Subject: [TUHS] Knuth and Unix 

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 

[-- Attachment #2: Type: text/html, Size: 1117 bytes --]

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-10  0:54 ` Ed Cashin
@ 2019-01-10  7:39   ` arnold
  2019-01-13  3:41     ` Steve Johnson
  0 siblings, 1 reply; 15+ messages in thread
From: arnold @ 2019-01-10  7:39 UTC (permalink / raw)
  To: ecashin, dave; +Cc: tuhs

Ed Cashin <ecashin@noserose.net> wrote:

> 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.

Hoare did indeed invent it. He describes the history, IIRC, in his Turing Award
lecture. (I know I read it, written by him, somewhere.)

Arnold

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-10  7:39   ` arnold
@ 2019-01-13  3:41     ` Steve Johnson
  2019-01-13  4:40       ` Bakul Shah
  0 siblings, 1 reply; 15+ messages in thread
From: Steve Johnson @ 2019-01-13  3:41 UTC (permalink / raw)
  To: arnold, ecashin, dave; +Cc: tuhs

[-- Attachment #1: Type: text/plain, Size: 1180 bytes --]

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 seem to recall also that a lot of us at that time were underwhelmed
by The Art of Computer Programming, especially the use of MIX. 
Perhaps it just meant that Knuth was doing things bottom up, while we
were doing amazing things in small spaces with B and C.

Steve

----- Original Message -----
From: arnold@skeeve.com
To:<ecashin@noserose.net>, <dave@horsfall.org>
Cc:<tuhs@tuhs.org>
Sent:Thu, 10 Jan 2019 00:39:28 -0700
Subject:Re: [TUHS] Knuth and Unix

 Ed Cashin <ecashin@noserose.net> wrote:

 > 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.

 Hoare did indeed invent it. He describes the history, IIRC, in his
Turing Award
 lecture. (I know I read it, written by him, somewhere.)

 Arnold



[-- Attachment #2: Type: text/html, Size: 1903 bytes --]

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-13  3:41     ` Steve Johnson
@ 2019-01-13  4:40       ` Bakul Shah
  2019-01-15 22:32         ` Steve Johnson
  0 siblings, 1 reply; 15+ messages in thread
From: Bakul Shah @ 2019-01-13  4:40 UTC (permalink / raw)
  To: Steve Johnson; +Cc: tuhs

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

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-13  4:40       ` Bakul Shah
@ 2019-01-15 22:32         ` Steve Johnson
  2019-01-16  2:53           ` Rob Pike
  2019-01-16 20:50           ` Bakul Shah
  0 siblings, 2 replies; 15+ messages in thread
From: Steve Johnson @ 2019-01-15 22:32 UTC (permalink / raw)
  To: Bakul Shah, Steve Johnson; +Cc: tuhs

[-- Attachment #1: Type: text/plain, Size: 1871 bytes --]


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@bitblocks.com>
To:"Steve Johnson" <scj@yaccman.com>
Cc:<arnold@skeeve.com>, <ecashin@noserose.net>, <dave@horsfall.org>,
<tuhs@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@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.



[-- Attachment #2: Type: text/html, Size: 2607 bytes --]

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-15 22:32         ` Steve Johnson
@ 2019-01-16  2:53           ` Rob Pike
  2019-01-16 18:22             ` arnold
  2019-01-16 20:50           ` Bakul Shah
  1 sibling, 1 reply; 15+ messages in thread
From: Rob Pike @ 2019-01-16  2:53 UTC (permalink / raw)
  To: Steve Johnson; +Cc: tuhs

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@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@bitblocks.com>
> To:"Steve Johnson" <scj@yaccman.com>
> Cc:<arnold@skeeve.com>, <ecashin@noserose.net>, <dave@horsfall.org>, <tuhs@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@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.
>

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
@ 2019-01-16 15:57 Doug McIlroy
  0 siblings, 0 replies; 15+ messages in thread
From: Doug McIlroy @ 2019-01-16 15:57 UTC (permalink / raw)
  To: tuhs

Tsort was  a direct reference to Knuth's recognition and
christening of topological sort as a worthy software component.

This is a typical example of the interweaving of R and D
which characterized the culture of Bell Labs. Builders
and thinkers were acutely aware of each other, and often
were two faces of one person. Grander examples may be
seen in the roles that  automata theory and formal languages
played in Unix. (Alas, these are the subjects of projected
Knuthian volumes that are still over the horizon.)

Doug

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-16  2:53           ` Rob Pike
@ 2019-01-16 18:22             ` arnold
  2019-01-16 20:10               ` Rob Pike
  0 siblings, 1 reply; 15+ messages in thread
From: arnold @ 2019-01-16 18:22 UTC (permalink / raw)
  To: scj, robpike; +Cc: tuhs

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@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@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@bitblocks.com>
> > To:"Steve Johnson" <scj@yaccman.com>
> > Cc:<arnold@skeeve.com>, <ecashin@noserose.net>, <dave@horsfall.org>, <tuhs@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@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.
> >

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-16 18:22             ` arnold
@ 2019-01-16 20:10               ` Rob Pike
  2019-01-17  6:58                 ` arnold
  2019-01-18  0:55                 ` Steve Johnson
  0 siblings, 2 replies; 15+ messages in thread
From: Rob Pike @ 2019-01-16 20:10 UTC (permalink / raw)
  To: arnold; +Cc: tuhs

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@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@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@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@bitblocks.com>
> > > To:"Steve Johnson" <scj@yaccman.com>
> > > Cc:<arnold@skeeve.com>, <ecashin@noserose.net>, <dave@horsfall.org>, <tuhs@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@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.
> > >

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-15 22:32         ` Steve Johnson
  2019-01-16  2:53           ` Rob Pike
@ 2019-01-16 20:50           ` Bakul Shah
  2019-01-18 21:57             ` Steve Johnson
  1 sibling, 1 reply; 15+ messages in thread
From: Bakul Shah @ 2019-01-16 20:50 UTC (permalink / raw)
  To: Steve Johnson; +Cc: tuhs

On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" <scj@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.

Good to know all this. The Stanford paper you refer, would
that be "fast pattern matching" by Knuth, Morris & Pratt?

I remember struggling with empty strings and I also missed
other yacc tricks.  In my formulation I had two kinds of
rules: set rules and sequence rules. Set rules avoided
unnecessary reductions in rules such as foo: bar|...

For example:

// sets
expr = relexpr  | expr1
expr1 = addexpr | expr2
expr2 = mulexpr | expr3
...

// sequences
relexpr: expr1  RELOP expr1
addexpr: expr1 ('+'|'-') expr2
mulexpr: expr2 ('*'|'/') expr3
...

Basically I completely avoided empty symbols -- even an empty
file has an EOF! [I didn't try it on anything more complicated
than (extended) Pascal so no idea how it would have fared on
complexificated lanuages]

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-16 20:10               ` Rob Pike
@ 2019-01-17  6:58                 ` arnold
  2019-01-18  0:55                 ` Steve Johnson
  1 sibling, 0 replies; 15+ messages in thread
From: arnold @ 2019-01-17  6:58 UTC (permalink / raw)
  To: robpike, arnold; +Cc: tuhs

Rob Pike <robpike@gmail.com> wrote:

> I was speaking in jest...

Yes, but ...

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

Indeed.  I wonder who actually wrote the grammar?  I know that
Brian won't touch it these days. :-)

Thanks,

Arnold

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-16 20:10               ` Rob Pike
  2019-01-17  6:58                 ` arnold
@ 2019-01-18  0:55                 ` Steve Johnson
  1 sibling, 0 replies; 15+ messages in thread
From: Steve Johnson @ 2019-01-18  0:55 UTC (permalink / raw)
  To: Rob Pike, arnold; +Cc: tuhs

[-- Attachment #1: Type: text/plain, Size: 3355 bytes --]


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@gmail.com>
To:<arnold@skeeve.com>
Cc:<scj@yaccman.com>, <tuhs@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@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@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@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@bitblocks.com>
 > > > To:"Steve Johnson" <scj@yaccman.com>
 > > > Cc:<arnold@skeeve.com>, <ecashin@noserose.net>,
<dave@horsfall.org>, <tuhs@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@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.
 > > >



[-- Attachment #2: Type: text/html, Size: 4608 bytes --]

^ permalink raw reply	[flat|nested] 15+ messages in thread

* Re: [TUHS] Knuth and Unix
  2019-01-16 20:50           ` Bakul Shah
@ 2019-01-18 21:57             ` Steve Johnson
  0 siblings, 0 replies; 15+ messages in thread
From: Steve Johnson @ 2019-01-18 21:57 UTC (permalink / raw)
  To: Bakul Shah, Steve Johnson; +Cc: tuhs

[-- Attachment #1: Type: text/plain, Size: 2834 bytes --]


The paper  was called "The Competence/Performance Dichotomy" by
Pratt.  He borrowed an idea from Chompsky and distinguished between
being able to understand something and being able to produce it.  The
idea I took from it was to recognize grammar rules even if the parse
was ambiguous and then use other mechanisms (e.g., Shift/Reduce,
precedence) to decide what to do.

About empty productions: one of the most useful versions of this was
in handling scopes in programming languages, especially in C where xyz
could be a variable in one scope and a typedef in an inner one, or
vice versa.  The empty production could get called at the right
moment to make the appropriate symbol table fixes, where otherwise we
would have had a syntax error. 

Steve

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

 On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" <scj@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.

 Good to know all this. The Stanford paper you refer, would
 that be "fast pattern matching" by Knuth, Morris & Pratt?

 I remember struggling with empty strings and I also missed
 other yacc tricks. In my formulation I had two kinds of
 rules: set rules and sequence rules. Set rules avoided
 unnecessary reductions in rules such as foo: bar|...

 For example:

 // sets
 expr = relexpr | expr1
 expr1 = addexpr | expr2
 expr2 = mulexpr | expr3
 ...

 // sequences
 relexpr: expr1 RELOP expr1
 addexpr: expr1 ('+'|'-') expr2
 mulexpr: expr2 ('*'|'/') expr3
 ...

 Basically I completely avoided empty symbols -- even an empty
 file has an EOF! [I didn't try it on anything more complicated
 than (extended) Pascal so no idea how it would have fared on
 complexificated lanuages]



[-- Attachment #2: Type: text/html, Size: 3730 bytes --]

^ permalink raw reply	[flat|nested] 15+ messages in thread

end of thread, back to index

Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-01-10  0:19 [TUHS] Knuth and Unix Dave Horsfall
2019-01-10  0:54 ` Ed Cashin
2019-01-10  7:39   ` arnold
2019-01-13  3:41     ` Steve Johnson
2019-01-13  4:40       ` Bakul Shah
2019-01-15 22:32         ` Steve Johnson
2019-01-16  2:53           ` Rob Pike
2019-01-16 18:22             ` arnold
2019-01-16 20:10               ` Rob Pike
2019-01-17  6:58                 ` arnold
2019-01-18  0:55                 ` Steve Johnson
2019-01-16 20:50           ` Bakul Shah
2019-01-18 21:57             ` Steve Johnson
2019-01-10  3:14 ` Jim Capp
2019-01-16 15:57 Doug McIlroy

The Unix Heritage Society mailing list

Archives are clonable: git clone --mirror http://inbox.vuxu.org/tuhs

Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.tuhs


AGPL code for this site: git clone https://public-inbox.org/ public-inbox