Re: [TUHS] [tuhs] Dennis Ritchie's couch

[Rob Pike <robpike@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 1064 bytes --]

<resending with the program as an attachment, as 100K is considered big
here, and no images hidden in reply. moderator, you can kill the prior
messages. computers are hard.>

To show you what I mean, here is a parser I wrote recently for a simple Go
expression evaluator, in Go. It has all Go's precedence levels and
operators. The one odd detail is that >= etc. can be combined, as in 1 >= 2
> 3, but that doesn't matter in the context of this program and is easily
avoided with a few more lines in cmpList.

I'm using a screen grab because GMail refuses to leave my indentation
alone. I left factor off. It's got all the usual details but it's the leaf
of the grammar and of no interest here.

Note that this could easily have been made a table instead of a bunch of
one-line functions.

Parsers are easy to write. It took us a generation (or more) to understand
that, but it's remarkable nonetheless. The first big step might have been
realizing that recursion was a good idea, even if you weren't writing LISP,
if the data structure is itself recursive.

-rob

[-- Attachment #1.2: Type: text/html, Size: 1307 bytes --]

[-- Attachment #2: parse.txt --]
[-- Type: text/plain, Size: 1314 bytes --]

// parse implements a production in the expression parse hierarchy. Singles and
// doubles are strings holding the operators that are available at at this precedence
// level, while nextLevel implements the next higher precendence level.
func (p *parser) parse(singles, doubles string, nextLevel func(*parser) *Expr) *Expr {
	e := nextLevel(p)
	for {
		if p.peek(true) == eof {
			return e
		}
		op := p.op(singles, doubles)
		if op == "" {
			return e
		}
		e = &Expr{
			op:    op,
			left:  e,
			right: nextLevel(p),
		}
	}
}

// orlist = andList | andList '||' orList.
func orList(p *parser) *Expr {
	return p.parse("", "||", andList)
}

// andlist = cmpList | cmpList '&&' andList.
func andList(p *parser) *Expr {
	return p.parse("", "&&", cmpList)
}

// cmpList = expr | expr ('>' | '<' | '==' | '!=' | '>=' | '<=') expr.
func cmpList(p *parser) *Expr {
	return p.parse("+-|^!><", "==!=>=<=", expr)
}

// expr = term | term ('+' | '-' | '|' | '^') term.
func expr(p *parser) *Expr {
	return p.parse("+-|^!", "", term)
}

// term = factor | factor ('*' | '/' | '%' | '>>' | '<<' | '&' | '&^') factor
func term(p *parser) *Expr {
	return p.parse("*/%&", ">><<&^", factor)
}

// factor = constant | identifier | '+' factor | '-' factor | '^' factor | '!' factor | '(' orList ')'
func factor(p *parser) *Expr {