[TUHS] Dennis Ritchie's couch

[Tony Finch]

Bakul Shah <bakul at iitbombay.org> wrote:
> > George Michaelson <ggm at 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 at 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.