Improved Internal Representation for Parser Combinators

From: "andrew cooke" <andrew@...>

Date: Sun, 15 Apr 2007 12:32:17 -0400 (CLT)

As noted below I just dashed off another parser combinator library in
Erlang. While doing so I stumbled across an improvement that clarifies a
lot of the ugliness I've had in previous code.  Maybe this is already used
elsewhere, but I thought I'd make a note here in case it was new and
useful.

Parsers have type (Stream -> Result) where Stream is a list (in Erlang
Strings are lists of characters so this is nice and simple) and Result is
typically one of
{match, Result, Stream2}
fail
Then combinators use fail to do backtracking etc.

So far that's all normal.  My extension was to add an additional state:
{empty, Stream2}

This doesn't seem that useful, because typically you are working with
lists of results anyway, so
{match, [], Stream2}
is often a perfectly good way of representing this.  However, making this
explicit avoids ambiguity in a few odd corner cases (which I have already
forgotten, but it really did!), clarifies logic, keeps you from forcing
lists in the most basic combinators, and even stops Epsilon* from spinning
away :o)

I am now struck with doubt because looking back at the code I can't work
out how this helped.  But I distinctly remember that it did help, and the
cost is very low (it only appears in three or four functions)...

Andrew