Note that most implementations of both parser combinators and regexes can fail very badly (exponential time). Never use either on untrusted input, unless you can prove your implementation lets you stay linear.
replies(4):
(I guess part of the problem is just that regular languages have been studied since Kleene had a full head of hair, while parser combinators were more or less unknown until the 80's.)
Basically, a monadic parser combinator can have code that "inspects" a previously parsed value (context-sensitivity) but an applicative parser cannot.
Imagine an input like "3 alice bob dave", with a number and then that many names.
We want to parse
data Parsed = Parsed {count :: Int, names :: [Name]}
count <- parseInt
names <- parseN count name
return (Parsed count names)
Applicative parsers don't let you "inspect" the parsed values. You can do stuff like
Parsed <$> parseInt <*> many name
You could do something like:
Parsed <$> literal "1" <*> replicateM 1 name
<|> Parsed <$> literal "2" <*> replicateM 2 name
<|> ...
Technically, you can use Haskell's laziness to parse this particular grammar efficiently enough using applicatives+alternatives to construct an infinite parse tree, but that's kind of an advanced edge case that won't work in most languages.
And then it does lead back to your "????" - which presumably represents the answer to the question of "What's the simplest abstraction that allows one to build a "Parser" (would this still be using combinators??) that is powerful enough to parse regular languages, but, by design, not powerful enough to parse context-free languages?"