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

Deity

in 'parslet' I would do rule(:line) { (str(";").absent? >> any).repeat(1) >> str(";") } which I guess is the same as your second option. – Vanden

Answer 1

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)

Hawkshaw

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 !(';' .)

Deity

Answer 3

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.

Raasch

/[^;]+;/ works, it's written as [^;]+ ';', like shown in my question. But I was hoping there was a better way. – Deity