From: Clifford Heath <no@...>
Date: 2008-09-30T20:59:03+09:00
Subject: Re: my ears are burning... ;)

parrt@antlr.org wrote:
> PEGs have a number of disadvantages.
> Two of which are that it cannot handle infinite streams like socket
> protocols.

Such protocols always consist of a continuous stream of packets,
and you can parse those one by one.

> Also, if you are always backtracking, the error message  is
> essentially "no, Your input does not match the syntax".

That's not what happens with Treetop, which is pure PEG,
and emits more useful error messages that most hard-core
parsers. It simply records for the furthermost failure
point which terminals would have allowed it to get further.
Cheap and cheerful, but eminently comprehensible to a human.

I should say that the goal of Treetop is different from most
parser generators - it's to be able to incrementally re-parse
input that's being edited with insertions and deletions, using
whatever is still valid of the memoization. Nathan's still
working on subtle bugs in the invalidation mechanism, but I
think it's an interesting project, no?

> Also, action
> execution is extremely difficult in the face of backtracking,
> particularly continuously.

That's not as much of an issue as you might think. Many
actions down in the leaves can be side-effect free, so
the effects get lost when that branch is abandoned. Near
the top of the tree there are very often rules that cannot
backtrack, and actions with side-effects are ok there. It
does take a little care and comprehension, but all coding
does.

At present, Treetop offers no mechanism for runtime execution,
unless you build it into the constructors of custom SyntaxNodes.

>  Consequently, it is my opinion that pure
> PEG based parser generators are not viable commercially

I believe I've established some counter-arguments, though in
general I agree that avoidance of backtracking is preferable
if you have an effective tool for it. I'd like to find the
time to make ANTLR work properly with Ruby, but I already have
a (more) significant project under way. Maybe Eric will do it?

Clifford Heath.