Just because it's a regex does not mean you can't document it. There are many regex tracers that can tell you exactly where a match fails. Plus regexes condense a lot of information in small spaces, which makes them easier (imho) to debug. Most other parsing syntaxes are one-offs, and very verbose.
And your average parsing library is not going to be using boyer-moore state machine parsing like you can easily achieve with regexes. It's complex, terse, fast, and the code that will be running your match is probably better debugged than any code you could hope to produce (it's most programmers' understanding of regexes that could use some debugging). Regexes also just make sense if you know the theory behind the state machines.
So how about this way of writing the regex :
regex = r"""(?x) # Extended syntax (ignores \n and whitespace, allows comments)
# Regex to match email addresses
\b # Word boundary
(?P\w+) # Username part
@
(?P[\w.]+) # Domain
\b # Word boundary
"""
# Example use
import re
m = re.match(regex, "john@snow")
print m.group('username') # john
print m.group('domain') # snow
I find parser combinators very hard to use. I wrote parser combinator libraries in C and one in java thinking it'd be easier to use than a parser generator like ANTLR, and I've since rethought the process. ANTLR studio is just so useful for writing a parser to example data.
There's also the concern that parsers are strictly more expressive than regexes. If you need that, then regexes are simply out. However, most parser generators allow you to easily combine regex(-like) tokenization with parsing.