[antlr-interest] Reg LR-style expression parsing in wiki

[Ron Burk]

Of possible distant peripheral interest, I've been working on using
SLR(0) combined with operator precedence algorithms to handle
expressions in a (mostly) LL(1) parser generator in the smallest
possible space (both generated code and specification syntax).
The SLR(0) automaton ends up with innumerable shift/reduce
conflicts, all of which can be correctly (and cheaply) decided
by the operator precedence tables at runtime. Works great on
my whiteboard; time will tell how it works in practice.

http://code.google.com/p/blacc/wiki/DesignGuideIntro

Sample syntax in first code example on that page. Probably been
done somewhere before, as virtually everything to do with parsing
has. :-)

One pleasant result of using SLR(0) with op prec is it seems like it
keeps me within spitting distance of provable correctness. If the
SLR(0) automaton contains any reduce-reduce conflicts, then the
user has asked me to do something I'm unwilling to support. If
operator precedence should ever claim to have found a handle
when the SLR(0) automaton is not in an accepting state, there's
either a bug or a great lapse in understanding on my part of the
two algorithms.

One minor complication is the need to switch back to LL(1) parsing
from the midst of the bottom-up parser (e.g., to handle C's cast
operator), but this seems fairly confinable as, once again,
the SLR(0) automaton has the information needed (e.g.)
to know it's reached the point of expecting a nonterminal that exists
outside its own tiny, highly constrained portion of the grammar.
Thoroughly tested on my whiteboard, only the detail of implementation
remains. :-)