From: Bakul Shah <bakul@bitblocks.com>
To: "Steve Johnson" <scj@yaccman.com>
Cc: tuhs@tuhs.org
Subject: Re: [TUHS] Knuth and Unix
Date: Sat, 12 Jan 2019 20:40:11 -0800 [thread overview]
Message-ID: <20190113044018.B235E156E410@mail.bitblocks.com> (raw)
In-Reply-To: Your message of "Sat, 12 Jan 2019 19:41:26 -0800." <a6bdf98a8ada9ef9431ff9ceca189847958f77a7@webmail.yaccman.com>
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-13 4:41 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 [this message]
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
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=20190113044018.B235E156E410@mail.bitblocks.com \
--to=bakul@bitblocks.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).