“aaaaaaaaaaaaaabbbbccccccccccccc” will match
“abbbbbbc” won’t match
No, definitely not. LL and LR parsers work in linear time, and they recognize languages inexpressible by any of the ‘extended regular _expression_’ systems I’ve seen (PCRE etc.).
It would be hard to formally describe the exact set of languages whose membership problem can be decided in time proportional to the size of the string. There are some oddballs in there, like strings that represent arithmetic expressions that evaluate to 42, and that does not have intermediate values outside the range [-1000, 1000]. Writing a linear time program to match that is not that hard, but coming up with a formalism that included this one but not anything that can’t be matched in linear time is probably impossible.