Non-greedy matching in Treetop/PEG ?

Question

How would I do something like this in Treetop?

/.+?;/

It seems like the only way is to do:

[^;]+ ';'

Which is kind of ugly.. any other way? .+? doesn't seem to work..

Answer 1

I don't know Treetop, but would /[^;]+;/ work?

From a quick search, I saw suggestion that Treetop doesn't do greedy nor lazy (non-greedy) quantifiers, and that the + is actually a possessive quantifier (represented by ++ in other regex flavours).

If this is the case, I'm not sure you've got any other regex-based options than the negated class.

Answer 2

Well, I learnt PEGs are greedy, and there's no way around it. Lookaheads can be used to mimic this behavior though, like !(';' .)

Answer 3

PEGs are greedy and blind by default, that means they eat as much input as they can and they do not consider what comes afterwards:

S <- P1* P2 (greedy, blind)

That can be considerably easy fixed though by making use of the ordered choice (and without using lookaheads):

S <- P1 S / P2 (greedy, non-blind)

S <- P2 / P1 S (lazy, non-blind)