On 21 Dec 2020, at 13:46, Taco Hoekwater wrote:

...

On 21 Dec 2020, at 13:16, Mojca Miklavec wrote:

My only explanation would be that perhaps "^1" is so greedy that the rest of the pattern doesn't get found. But I don't want to believe that explanation.

Which (of course) means that that is exactly what happens ;)

The ones that match are

ababbb (a (ba+bb) b) => r4 r1(r3(r5 r4) r2(r5 r5)) r5 abbbab (a (bb+ba) b) => r4 r1(r2(r5 r5) r3(r5 r4)) r5

With the ^1, in the “bb” cases the first “b” eats all three “b”s:

ababbb fails the r5 at the end

Sorry, that was wrong, it fails at the second r5 in the r2 as well, for the same reason as below.

abbbab fails the first r2 already (since the second r5 therein never happens)

Best wishes, Taco

On 21 Dec 2020, at 14:08, Mojca Miklavec wrote:

Dear Taco,

On Mon, 21 Dec 2020 at 13:46, Taco Hoekwater wrote:

...

...

On 21 Dec 2020, at 13:16, Mojca Miklavec wrote:

My only explanation would be that perhaps "^1" is so greedy that the rest of the pattern doesn't get found. But I don't want to believe that explanation.

Which (of course) means that that is exactly what happens ;)

The ones that match are

ababbb (a (ba+bb) b) => r4 r1(r3(r5 r4) r2(r5 r5)) r5 abbbab (a (bb+ba) b) => r4 r1(r2(r5 r5) r3(r5 r4)) r5

With the ^1, in the “bb” cases the first “b” eats all three “b”s:

ababbb fails the r5 at the end

abbbab fails the first r2 already (since the second r5 therein never happens)

Is this a deliberate choice, a limitation of the grammar expressiveness, some misuse on my side that could/should/needs to be implemented in a different way, or does it count as a "bug" on the lpeg side?

For example, I wouldn't expect a regexp "b+b" to fail on "bbb" just because "b+" would eat all three "b"s at once (the regexp "b+b" in fact finds "bbb", and I would expect a less-than-totally-greedy hit with lpeg as well). Or is my reasoning wrong here?

PEGs are greedy by design, which is a consequence of the fact that PEGS do not backtrack, which goes back to the underlying assumptive rule of PEGs that there is one (and only one!) ‘correct’ way to parse the input. Allowing backtracking destroys that assumption and by doing so would complicate the system to a level that would make it comparable to PCRE (with all the associated penalties on processing speed and a much greater codebase). Another way of thinking of it (perhaps that helps): PEGs are _declarative_ on the input, whereas REs are _interpretive_. Yet another way of thinking about it: PEGs rigorously define the (programming) language of the input. It takes a bit of rewiring your brain to get comfortable with PEGs when you are used to REs, and unpredictable input is much harder to tackle in PEGs. OTOH, using PEGs are much better if there is an explicit grammar. In your example, the fact that you even considered ^1 means that you were still thinking too much in terms of regular expressions, but I know it is very hard to learn how to do something that is _only a little_ different from something you know well already. Best wishes, Taco

Hi, Thanks to both Taco and Arthur for clarifying this and pointing out the difference between PEG and PCRE. I'll put some links like https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions on my reading list and try to understand it more thoroughly than I do at the moment. After that I'll probably need to re-read Taco's answer a couple more times, and probably write some parsing grammar as an exercise, but I'll eventually get there :) Just a correction of my previous statement. The following doesn't really work either: lpeg.P('b') + lpeg.P('bb') + lpeg.P('bbb') it just happened to work in one particular case on my minimal example, but it doesn't help in general. That's probably expected based on what Arthur and Taco explained to me.

In your example, the fact that you even considered ^1 means that you were still thinking too much in terms of regular expressions,

In reality it just means that I was trying to add a new rule to solve the second part of the puzzle (hidden on the website until you solve the first part), which read something like 6: 3 | 3 6 which would in theory be translated into something like r6 = lpeg.V"r3" + lpeg.V"r3" * lpeg.V"r6", if PEGs worked the way I imagined they worked, that is. Apparently they don't :) It seemed so obvious, but it would be too easy if it was true ;), so it will force me to solve it "ab initio" (as it was initially meant) anyway. Thanks a lot to everyone for the extra patience to explain me those basic principles & differences, Mojca

On 12/21/2020 3:10 PM, Mojca Miklavec wrote:

lpeg.P('b') + lpeg.P('bb') + lpeg.P('bbb')

always put the longest (for overlapping) first, in this case you could do: P('b')^-3 at most 3 ----------------------------------------------------------------- Hans Hagen | PRAGMA ADE Ridderstraat 27 | 8061 GH Hasselt | The Netherlands tel: 038 477 53 69 | www.pragma-ade.nl | www.pragma-pod.nl -----------------------------------------------------------------