[TUHS] Knuth and Unix

[Bakul Shah]

On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" <scj at 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.

Good to know all this. The Stanford paper you refer, would
that be "fast pattern matching" by Knuth, Morris & Pratt?

I remember struggling with empty strings and I also missed
other yacc tricks.  In my formulation I had two kinds of
rules: set rules and sequence rules. Set rules avoided
unnecessary reductions in rules such as foo: bar|...

For example:

// sets
expr = relexpr  | expr1
expr1 = addexpr | expr2
expr2 = mulexpr | expr3
...

// sequences
relexpr: expr1  RELOP expr1
addexpr: expr1 ('+'|'-') expr2
mulexpr: expr2 ('*'|'/') expr3
...

Basically I completely avoided empty symbols -- even an empty
file has an EOF! [I didn't try it on anything more complicated
than (extended) Pascal so no idea how it would have fared on
complexificated lanuages]