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

[Terence Parr]

Hi Ron, cool stuff!  I like this:

> By generating byte-codes for an interpreter, supporting multiple parsing algorithms became a matter of slightly expanding the number of opcodes. This also appears to be an easier structure (for me) to understand and inspect.

That is interesting...can the interpreter fetch/exec loop fit in L1 cache?  maybe...

i was thinking SLR(0) also instead of the prec climbing thing for expressions. I'll think about this hard.

Ter
On Feb 21, 2010, at 6:20 PM, Ron Burk wrote:

> 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. :-)