8 ms·

The problem is that "regular expression" is equivocal. Sometimes you hear "regular expression" used to mean the language of things accepted by some Finite Stat

The problem is that "regular expression" is equivocal. Sometimes you hear "regular expression" used to mean the language of things accepted by some Finite State machine. Lots of folks on HN took a Theory of Computation class and learned about these in that class. In that meaning, yes, you are right. But sometimes in professional conversations you hear "regular expression" used to mean the strings that can be matched using, say, Perl's regular expressions. I know I have heard it used that way often. Since Perl regular expressions can accept anything a Turing machine can accept, the answer to the question in this case is yes.

mannykannot 7y ago
Sort of, but if (and only if) you know what a regular expression formally means, you can disambiguate the equivocation introduced by ambiguous usage.
wahern 7y ago
Very few people know that Perl's regex engine (since 5.10) supports recursion. And recursive matching cannot perform recursive captures, which is why at best it can only be used to validate a string, not parse it, making it not particularly useful in practice. For these reasons I would never assume that someone using the term "regular expression" inclusively of Perl would have in mind such capabilities. IME, such a loose definition simply implies things like zero-width assertions, backcaptures, etc. Here's a proof-of-concept Perl 5.10+ JSON validator I came up with for a presentation to Perl engineers introducing PEGs and Lua's LPeg module. Of the 20-30 people in the room, I doubt anybody in the audience knew this was even possible with Perl. my $grammar = qr{ ^(?&Value) $ (?(DEFINE) (?<Value> \s∗ (?: (?&Array) | (?&Object) | (?&Boolean) | (?&Number) | (?&String) | (?&Null) ) \s∗ ) (?<Array> \[ \s∗ (?:(?&Value) (?:\s∗,\s∗ (?&Value))∗)? \s∗ \]) (?<Object> \{ \s∗ (?:(?&KeyV) (?:\s∗,\s∗ (?&KeyV))∗)? \s∗ \}) (?<KeyV> \s∗ (?:(?&String) \s∗:\s∗ (?&Value))) \s∗ (?<Boolean> true | false) (?<Number> \d+) (?<String> "[^\"]∗") (?<Null> null) ) }xs; Note: I was trying to fit it all on a single slide, so the definition for String doesn't handle escaped characters. There may be other deficiencies. I copy+pasted this from the PDF slide deck as I can't find the original Beamer source. Any broken spacing and Unicode substitutions probably aren't original.

mannykannot 7y ago

Sort of, but if (and only if) you know what a regular expression formally means, you can disambiguate the equivocation introduced by ambiguous usage.

wahern 7y ago

Very few people know that Perl's regex engine (since 5.10) supports recursion. And recursive matching cannot perform recursive captures, which is why at best it can only be used to validate a string, not parse it, making it not particularly useful in practice. For these reasons I would never assume that someone using the term "regular expression" inclusively of Perl would have in mind such capabilities. IME, such a loose definition simply implies things like zero-width assertions, backcaptures, etc. Here's a proof-of-concept Perl 5.10+ JSON validator I came up with for a presentation to Perl engineers introducing PEGs and Lua's LPeg module. Of the 20-30 people in the room, I doubt anybody in the audience knew this was even possible with Perl. my $grammar = qr{ ^(?&Value) $ (?(DEFINE) (?<Value> \s∗ (?: (?&Array) | (?&Object) | (?&Boolean) | (?&Number) | (?&String) | (?&Null) ) \s∗ ) (?<Array> \[ \s∗ (?:(?&Value) (?:\s∗,\s∗ (?&Value))∗)? \s∗ \]) (?<Object> \{ \s∗ (?:(?&KeyV) (?:\s∗,\s∗ (?&KeyV))∗)? \s∗ \}) (?<KeyV> \s∗ (?:(?&String) \s∗:\s∗ (?&Value))) \s∗ (?<Boolean> true | false) (?<Number> \d+) (?<String> "[^\"]∗") (?<Null> null) ) }xs; Note: I was trying to fit it all on a single slide, so the definition for String doesn't handle escaped characters. There may be other deficiencies. I copy+pasted this from the PDF slide deck as I can't find the original Beamer source. Any broken spacing and Unicode substitutions probably aren't original.