From: Rob Pike <robpike@gmail.com>
To: Steve Johnson <scj@yaccman.com>
Cc: tuhs@tuhs.org
Subject: Re: [TUHS] Knuth and Unix
Date: Wed, 16 Jan 2019 13:53:33 +1100 [thread overview]
Message-ID: <CAKzdPgxV2vOZxf+S8vWhRPH-qefUdNjfKFrEAw_5Na_5fwLDrw@mail.gmail.com> (raw)
In-Reply-To: <da4473180043bc7132425eb2fd15a6f766dc9321@webmail.yaccman.com>
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.
>
next prev parent reply other threads:[~2019-01-16 2:54 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-01-10 0:19 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 [this message]
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAKzdPgxV2vOZxf+S8vWhRPH-qefUdNjfKFrEAw_5Na_5fwLDrw@mail.gmail.com \
--to=robpike@gmail.com \
--cc=scj@yaccman.com \
--cc=tuhs@tuhs.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).