[tonyg]

Simple rules can give surprising, complex behaviour.

That's a good point. Unfortunately, it's also true not only of PEGs and recursive-descent parsing, but also of essentially every parsing formalism out there. So it doesn't seem to disqualify PEGs in particular.

(It's also true of programming languages generally: For which inputs does Collatz halt, and why?)

[bmn__]

I contest that. The parsers based on the formalism of CFG do not have that problem. The straightforward mental model of the user always matches their behaviour, no complexity, no surprises.