[thelist] Regular expression to check if other regular expressions are valid

VOLKAN ÖZÇELİK volkan.ozcelik at gmail.com
Wed Jun 22 14:36:02 CDT 2005

I've recently written a regular expression which matches a regular expression.


However it can match invalid reg exs as well. To verify the validity
of a regular expression cannot be done simply with a regular
expression imho.

Take for example

/1(?=(?=(?=1 ... )2)3)/

which is a valid regular expression with infinitely many positive
lookaheads. I've forgotten the stuff with theory of large numbers etc,
but hope that an interested can prove that it is impossible to match
such a regex with a regex.


On 6/22/05, lustig at brandeis.edu <lustig at brandeis.edu> wrote:
> Has anyone written a regular expression to check if other regular expressions
> are valid? Because regular expressions can't implement full turing machines,
> rice's theorum shouldn't apply to them. Has it been done?
> Jason
> --
> * * Please support the community that supports you.  * *
> http://evolt.org/help_support_evolt/
> For unsubscribe and other options, including the Tip Harvester
> and archives of thelist go to: http://lists.evolt.org
> Workers of the Web, evolt !

More information about the thelist mailing list