[antlr-interest] question on greedy matching

[Ric Klaren]

On 10/20/05, Andrei Alexandrescu <andrei at metalanguage.com> wrote:
> > (Side note: This is awfully horrid language design.... adding curlies
> > around the statement inside the try would make life a lot more
> > pleasant.)
>
> Definitely. But it's the most sensible example I could find for a
> situation where you want a non-greedy parsing. (Other examples?) In
> addition, it's an excellent exercise for understanding how to do some
> nontrivial parsing with antlr.

Wouldn't know good examples off the top of my head, had the luxury of
designing the language I was working on, so could prevent any
braindeadness.

> In other words, it's a Java-like language, not a Python-like language
> (indentation is irrelevant).

Some sanity prevails ;)

> > start out with a try rule with only one catch. Then define an extra
> > alternative (probably in the statement rule to collect trailing catch
> > statements) Some checks are probably necessary afterwards to see if
> > everything made sense. The catch all might need a predicate to prevent
> > it from being entered if the preceding statement was not a try.
>
> I believe this is not possible with syntactic predicates. You have to
> have semantic predicates, I think. Actually that's my fundamental
> question. Another fundamental question is how would a PEG deal with that
> (see http://pdos.csail.mit.edu/~baford/packrat/).

Come to think of it... if your intention is to build a tree during
parsing, then it's quite easy to implement it with this strategy and
end up with a tree with the right structure. It wouldn't even need
predicates (some action code though to fix the trees).

Strategy as above use a try catch with only one catch, build the tree
as usual, carry around a pointer to the last catch,  then when
entering the trailing catch rule see if there's a pointer around to
the last catch.. if not it's a syntax error. Then see if there's no
statements between this last catch and the trailers. If all is ok, add
the trailers to the tree of the last catch.

I'm not familiar with PEG's so can't comment on that.

Cheers,

Ric