Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
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
Replies are listed 'Best First'.
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 pondering the Monastery: (12)
As of 2015-07-31 10:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (276 votes), past polls