Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: back translating regular expressions

by Fletch (Chancellor)
on Mar 03, 2005 at 02:07 UTC ( #436070=note: print w/ replies, xml ) Need Help??


in reply to back translating regular expressions

". . . and then I fed it 'a.*b' and my computer just locked up." See also "Halting Problem, The". :)

Having said that, if you can wait a few more weeks until Higher Order Perl (ISBN 1558607013) comes out I believe one of the stream generator examples is generating possible matches for a regex. That lets you generate matches one at a time in a manner where you can stop at any time.


Comment on Re: back translating regular expressions
Re^2: back translating regular expressions
by blokhead (Monsignor) on Mar 03, 2005 at 05:27 UTC
    What on earth does that have to do with the halting problem? A computer going into an infinite loop is not the halting problem. If you meant that you can't tell whether a regular-expression denotes an infinite language, that's not quite right either. It's infinite if and only if it contains an infinite quantifier (+, *, {m,}), which is an easy property to check.

    blokhead

      /a/
      does not contain a quantifier, but there are an infinite amount of strings it will match. And if you only want to consider anchored strings:
      my $q1; $q1 = qr /a(??{$q1})?/; my $q2 = qr /^$q1$/;
      matches all strings containing nothing but a's. But it doesn't use any of the quantifiers you mentioned.

      Also,

      /^(?!)*$/
      contains a * quantifier, but it doesn't actually match any string. Perhaps you want to discount lookahead. Then I give you:
      /^(|)*$/
      It'll give a warning, but all it matches is the empty string. But it does have a * quantifier.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://436070]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (8)
As of 2014-08-28 00:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (253 votes), past polls