The Unix Heritage Society mailing list
 help / color / mirror / Atom feed
From: Tony Finch <dot@dotat.at>
To: Bakul Shah <bakul@iitbombay.org>
Cc: The Unix Heritage Society mailing list <tuhs@minnie.tuhs.org>
Subject: Re: [TUHS] Dennis Ritchie's couch
Date: Fri, 2 Jul 2021 18:17:35 +0100	[thread overview]
Message-ID: <424dde98-7a42-57e6-e13a-83c3e6ccc020@dotat.at> (raw)
In-Reply-To: <C728300B-6E54-4C25-A160-C1392BE37469@iitbombay.org>

Bakul Shah <bakul@iitbombay.org> wrote:
> > George Michaelson <ggm@algebras.org> wrote:
> >
> > a table.. hmm. so like.. we could write .. engines to "read" the table
> > and do things in some kind of (maybe.. finite) way?
> >
> > I know, lets write a DSL to MAKE THE TABLE...
> >
> > Is all software "wheel of life" ?
>
> It would be just an operator precedence table and two functions. One to
> parse a factor and one for binary expressions. The table might be something
> like an array of {singles, doubles, associativity}, where the Nth entry
> has precedence N. The binary expr parser uses the table to essentially
> group sub expressions based on precedence and associativity. This is an old
> idea. I think at least 4-5 decades old.

Yes, it's a fairly straightforward to write an operator precedence parser
using a pushdown automaton. Knuth wrote about it in 1962 :-) [page 8]
https://archive.org/details/bitsavers_computersA_13990695

I crufted together a #if evaluator for unifdef nearly 20 years ago, but
it's, um, rather messy. (I was hacking on Dave Yost's code from the 1980s)
http://dotat.at/cgi/git/unifdef.git/blob/HEAD:/unifdef.c#l950

More recently I learned how to write a Pratt parser (1973), which is just
a particular style of operator precedence parser, but when it's done
properly it can be really neat.

https://dl.acm.org/doi/10.1145/512927.512931

The driver loop is tiny, if you set up the table mapping tokens to actions
in the right way, so that the state transition functions handle errors as
well as happy-path evaluation. (Blame Pratt for the field names!)

	static Value
	eval(Parser *p, int rbp) {
		Value v = token[p->tok].nud(p);
		while(token[p->tok].lbp > rbp)
			v = token[p->tok].led(p, v);
		return(v);
	}

Vaughan Pratt also designed the pretty neat Sun logo.

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  https://dotat.at/
Channel Islands: Variable or northeasterly 1 to 3, becoming west to
southwest 2 to 4 late evening, backing south to southeast soon after dawn,
veering southwest to west 3 to 5 by noon, locally variable 1 to 3 in the
far south of the area. Smooth or slight, with a low swell developing
later. Mist and fog patches clearing early by early afternoon showers at
first and again later rain and drizzle for a time, overnight and in the
morning. Moderate to good, occasionally poor locally very poor.


  reply	other threads:[~2021-07-02 17:33 UTC|newest]

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-05-26  0:12 [TUHS] [tuhs] " Nelson H. F. Beebe
2021-05-26  0:37 ` Rob Pike
2021-05-26  3:03   ` Larry McVoy
2021-05-26  4:02     ` Rob Pike
2021-05-26  6:20     ` Bakul Shah
2021-05-26  6:52       ` Rob Pike
2021-07-02  2:13         ` scj
2021-07-02  3:30           ` Rob Pike
2021-07-02  3:34             ` Rob Pike
2021-07-02  4:40               ` Rob Pike
2021-07-02  6:29                 ` George Michaelson
2021-07-02  7:00                   ` Bakul Shah
2021-07-02 17:17                     ` Tony Finch [this message]
2021-07-04 23:40                       ` [TUHS] " George Michaelson
2021-07-05  3:41                         ` Bakul Shah
2021-05-26  5:13   ` [TUHS] [tuhs] " arnold
2021-05-26  4:10 ` Avindra G

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=424dde98-7a42-57e6-e13a-83c3e6ccc020@dotat.at \
    --to=dot@dotat.at \
    --cc=bakul@iitbombay.org \
    --cc=tuhs@minnie.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).