Name: Anonymous 2006-05-12 15:17
"Regular expression" engines long ago stopped being just regular expression parsers. Modern engines, like Perl's (today's de-facto standard, used in Perl, PHP, Python, C, JavaScript, Java, and many more) are capable of:
● Greedy or ungreedy matching with backtracking, and greedy matching without backtracking
● Variable length positive and negative lookahead assertions
● Fixed length positive and negative lookbehind assertions
● Backreferencing a submatch
● Testing whether an optional submatch matched
● Recursion of arbitrary submatches
● Detection of whether a submatch is being recursed or it's at top-level
Now gentlemen, I'm not sure what level in Chomsky's hierarchy regular expressions are. They are G2s for sure, but I believe they can recognize G1 (context-sensitive) grammars too since we have assertions, backreferences and arbitrary submatch recursion. Would you know this?
● Greedy or ungreedy matching with backtracking, and greedy matching without backtracking
● Variable length positive and negative lookahead assertions
● Fixed length positive and negative lookbehind assertions
● Backreferencing a submatch
● Testing whether an optional submatch matched
● Recursion of arbitrary submatches
● Detection of whether a submatch is being recursed or it's at top-level
Now gentlemen, I'm not sure what level in Chomsky's hierarchy regular expressions are. They are G2s for sure, but I believe they can recognize G1 (context-sensitive) grammars too since we have assertions, backreferences and arbitrary submatch recursion. Would you know this?