"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?
Name:
Anonymous2006-05-12 15:23 (sage)
is this some homework, or u serisouly want to know this.....
Name:
Anonymous2006-05-12 15:31
>>2
How can this be homework? Professors just discovered POSIX regex, they have their heads too far up their asses to ever notice Perl or any modern scripting language. If I spat that crap on any university student (and most professors) they'd just run away scared.
I really want to know because I want to mentally jerk off to it.
Name:
Anonymous2006-05-12 16:12
A perl regex is turing complete.
Name:
Anonymous2006-05-12 16:13
You should throw away some features of the regex so it is more interesting.
Name:
Anonymous2006-05-12 16:36
>>4
Oh, I forgot to say. Does this include embedded Perl like (?{}) ? I don't think we could consider that part of the regex language. Would it be Turing-complete (i.e. able to parse G0s) without Perl?
Name:
Anonymous2006-05-12 22:19
Ok it at least stack based (CFGs) because you have look ahead and look behind. The arbitrary back and forward lookahead with conditionals makes me think they are turing complete, but we won't know til someone makes a turing machine in it, or until someone just proves it.
Name:
Anonymous2006-05-12 22:20
When you combine the stack control with the recursion I think you have turing completeness.
Turing, considered by some to be the father of computing, died from taking a bite out of a poisoned apple.
Apple, considered by some to be a purveyor of off the shelf hardware wrapped in cheap gaudy plastic for a 10000% markup, use as a their logo an apple with a bite taken out of it.
Apple - we killed Alan Turing, and we'll kill you too. Buy our stuff.
Name:
Anonymous2006-06-01 7:01
>>10 died from taking a bite out of a poisoned apple.
Is this true?
Name:
Anonymous2006-06-01 8:45
>>14
Yep. Got fired from his job at the MoD for being gay, got depressed about it and injected an apple with poison.
Name:
Anonymous2006-06-01 8:58
>>15
No he was arrested and had been charged with being gay. The state was forcing him to take a chemical treatment.
Bringing /prog/ back to its people
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy