17 Jan
2019
17 Jan
'19
2:50 a.m.
On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" <scj(a)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]