Is it possible to detect a valid regular expression with another regular expression? If so please give example code below.
Is there a regular expression to detect a valid regular expression?
The above may or may not be useful in practice (I didn't review them in detail, nor am I a particularly good judge), but formally, IIRC (at least some) regular expression languages are Turing complete, and as such it is impossible to construct a tester that will correctly evaluate the correctness of all possible regular expressions in those languages. See Gödel's Incompleteness Theorem and the Church-Turing thesis. –
Highbinder
Who validates the validating regex? –
Pathe
@Nico Community. –
Chekiang
I've seen regex for parsing regexes in JavaScript in one of Douglas Crockford talks. –
Osteomalacia
So your problem is validating a regex, you chose a regex for solving it. I wonder if the problem-number-increasing property of regexes is additive or multiplicative. It feels like 4 problems instead of 2 :) –
Tabulate
There are many notations for regular expressions - some features and their spellings are common to most, some are spelled differently or only available in one particular notation. Most of those notations aren't "regular" in the regular grammar sense - you'd need a context free parser to handle the unbounded nesting of subexpressions - though many modern "regular expression" notations have extensions that go beyond the original formal definition and might allow their own notations to be recognized. In any case, why not simply ask your regex library if each regex is valid? –
Mallorymallow
@Pathe i need to validate regexp in XML schema. How can i do it without another regexp? –
Renowned
Actually compile/run the regex (pattern) to be checked, under an exception-handling mechanism that your language has. So the language's regex engine/compiler itself will check it. (This assumes correct basic syntax so that the program runs, but that can be included in the check by using your languages' facilities to evaluate the string for the regex as (possibly syntactically wrong) code, or such .) –
Burrow
/
^ # start of string
( # first group start
(?:
(?:[^?+*{}()[\]\\|]+ # literals and ^, $
| \\. # escaped characters
| \[ (?: \^?\\. | \^[^\\] | [^\\^] ) # character classes
(?: [^\]\\]+ | \\. )* \]
| \( (?:\?[:=!]|\?<[=!]|\?>)? (?1)?? \) # parenthesis, with recursive content
| \(\? (?:R|[+-]?\d+) \) # recursive matching
)
(?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )? # quantifiers
| \| # alternative
)* # repeat content
) # end first group
$ # end of string
/
This is a recursive regex, and is not supported by many regex engines. PCRE based ones should support it.
Without whitespace and comments:
/^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*)$/
.NET does not support recursion directly. (The (?1) and (?R) constructs.) The recursion would have to be converted to counting balanced groups:
^ # start of string
(?:
(?: [^?+*{}()[\]\\|]+ # literals and ^, $
| \\. # escaped characters
| \[ (?: \^?\\. | \^[^\\] | [^\\^] ) # character classes
(?: [^\]\\]+ | \\. )* \]
| \( (?:\?[:=!]
| \?<[=!]
| \?>
| \?<[^\W\d]\w*>
| \?'[^\W\d]\w*'
)? # opening of group
(?<N>) # increment counter
| \) # closing of group
(?<-N>) # decrement counter
)
(?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )? # quantifiers
| \| # alternative
)* # repeat content
$ # end of string
(?(N)(?!)) # fail if counter is non-zero.
Compacted:
^(?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>|\?<[^\W\d]\w*>|\?'[^\W\d]\w*')?(?<N>)|\)(?<-N>))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*$(?(N)(?!))
From the comments:
Will this validate substitutions and translations?
It will validate just the regex part of substitutions and translations. s/<this part>/.../
It is not theoretically possible to match all valid regex grammars with a regex.
It is possible if the regex engine supports recursion, such as PCRE, but that can't really be called regular expressions any more.
Indeed, a "recursive regular expression" is not a regular expression. But this an often-accepted extension to regex engines... Ironically, this extended regex doesn't match extended regexes.
"In theory, theory and practice are the same. In practice, they're not." Almost everyone who knows regular expressions knows that regular expressions does not support recursion. But PCRE and most other implementations support much more than basic regular expressions.
using this with shell script in the grep command , it shows me some error.. grep: Invalid content of {} . I am making a script that could grep a code base to find all the files that contain regular expressions
This pattern exploits an extension called recursive regular expressions. This is not supported by the POSIX flavor of regex. You could try with the -P switch, to enable the PCRE regex flavor.
Regex itself "is not a regular language and hence cannot be parsed by regular expression..."
This is true for classical regular expressions. Some modern implementations allow recursion, which makes it into a Context Free language, although it is somewhat verbose for this task.
I see where you're matching
[]()/\. and other special regex characters. Where are you allowing non-special characters? It seems like this will match^(?:[\.]+)$, but not^abcdefg$. That's a valid regex.
[^?+*{}()[\]\\|] will match any single character, not part of any of the other constructs. This includes both literal (a - z), and certain special characters (^, $, .).
This answer sends people in completely the wrong direction. They should never use regEx to locate regular expressions, because it cannot work correctly in all cases. See my answer added. –
Sparling
.{,1} is unmatched. Change to ^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d*(?:,\d*)?\})[?+]?)?|\|)*)$ matches. CHange \d+ to \d* –
Buggs regex by def should not have recursion, at least say something like that in ur answer, ur regex engine is probably "too powerful" and not really a regex engine. –
Cetane
Just a note you forgot the x flag –
Ancillary
This validator seems to be made for PCRE expressions, but it will pass many invalid POSIX EREs. Notably, they are a bit pickier in character class ranges, e.g. this is valid in PCRE but not in ERE:
[a-b-c]. –
Indirection @vitaly-t: Where is your answer? –
Pickens
@PeterV.Mørch I deleted it, because oddly enough, it received many downvotes. Here, I copied my answer to a Gist. –
Sparling
This answer really needs some strict proof of suggested solution. –
Ley
Unlikely.
Evaluate it in a try..catch or whatever your language provides.
But if a value received from user he get wide surface to exploit some vulnerability in Regex engine. –
Ley
"validating" the regex through another regex or not, would have no effect on such a regex injection attack, though –
Saez
No, if you are strictly speaking about regular expressions and not including some regular expression implementations that are actually context free grammars.
There is one limitation of regular expressions which makes it impossible to write a regex that matches all and only regexes. You cannot match implementations such as braces which are paired. Regexes use many such constructs, let's take [] as an example. Whenever there is an [ there must be a matching ], which is simple enough for a regex "\[.*\]".
What makes it impossible for regexes is that they can be nested. How can you write a regex that matches nested brackets? The answer is you can't without an infinitely long regex. You can match any number of nested parenthesis through brute force but you can't ever match an arbitrarily long set of nested brackets.
This capability is often referred to as counting, because you're counting the depth of the nesting. A regex by definition does not have the capability to count.
I ended up writing "Regular Expression Limitations" about this.
Did you ever write the piece in recursive regexes to which you refer in your article referenced above (
In a future (hopefully soon) post I will explore the recursive extensions to the .Net regular expression language.)? –
Cradlesong Use a recursive regex as @Markus Jarderot pointed out in his answer. Alternatively use a regex to annotate the brackets/parenthesis with nesting level, followed by recursive function calls with a regex to match pairs, and resolve/validate the regex in question -- see https://mcmap.net/q/46820/-how-to-parse-a-regular-expression –
Scherzando
Good question.
True regular languages can not decide arbitrarily deeply nested well-formed parenthesis. If your alphabet contains '(' and ')' the goal is to decide if a string of these has well-formed matching parenthesis. Since this is a necessary requirement for regular expressions the answer is no.
However, if you loosen the requirement and add recursion you can probably do it. The reason is that the recursion can act as a stack letting you "count" the current nesting depth by pushing onto this stack.
Russ Cox wrote "Regular Expression Matching Can Be Simple And Fast" which is a wonderful treatise on regex engine implementation.
Exactly. You can use a regex to annotate the brackets/parenthesis with nesting level, followed by recursive function calls with a regex to match pairs, and resolve/validate the regex in question -- see https://mcmap.net/q/46820/-how-to-parse-a-regular-expression –
Scherzando
No, if you use standard regular expressions.
The reason is that you cannot satisfy the pumping lemma for regular languages. The pumping lemma states that a string belonging to language "L" is regular if there exists a number "N" such that, after dividing the string into three substrings x, y, z, such that |x|>=1 && |xy|<=N, you can repeat y as many times as you want and the entire string will still belong to L.
A consequence of the pumping lemma is that you cannot have regular strings in the form a^Nb^Mc^N, that is, two substrings having the same length separated by another string. In any way you split such strings in x, y and z, you cannot "pump" y without obtaining a string with a different number of "a" and "c", thus leaving the original language. That's the case, for example, with parentheses in regular expressions.
That's not a very precise description of the pumping lemma. First, it is the whole language that can be regular or not, not a single string. Second, it is a necessary, not a sufficient, condition for regularity. Finally, only sufficiently long strings are pumpable. –
Mojica
Though it is perfectly possible to use a recursive regex as MizardX has posted, for this kind of things it is much more useful a parser. Regexes were originally intended to be used with regular languages, being recursive or having balancing groups is just a patch.
The language that defines valid regexes is actually a context free grammar, and you should use an appropriate parser for handling it. Here is an example for a university project for parsing simple regexes (without most constructs). It uses JavaCC. And yes, comments are in Spanish, though method names are pretty self-explanatory.
SKIP :
{
" "
| "\r"
| "\t"
| "\n"
}
TOKEN :
{
< DIGITO: ["0" - "9"] >
| < MAYUSCULA: ["A" - "Z"] >
| < MINUSCULA: ["a" - "z"] >
| < LAMBDA: "LAMBDA" >
| < VACIO: "VACIO" >
}
IRegularExpression Expression() :
{
IRegularExpression r;
}
{
r=Alternation() { return r; }
}
// Matchea disyunciones: ER | ER
IRegularExpression Alternation() :
{
IRegularExpression r1 = null, r2 = null;
}
{
r1=Concatenation() ( "|" r2=Alternation() )?
{
if (r2 == null) {
return r1;
} else {
return createAlternation(r1,r2);
}
}
}
// Matchea concatenaciones: ER.ER
IRegularExpression Concatenation() :
{
IRegularExpression r1 = null, r2 = null;
}
{
r1=Repetition() ( "." r2=Repetition() { r1 = createConcatenation(r1,r2); } )*
{ return r1; }
}
// Matchea repeticiones: ER*
IRegularExpression Repetition() :
{
IRegularExpression r;
}
{
r=Atom() ( "*" { r = createRepetition(r); } )*
{ return r; }
}
// Matchea regex atomicas: (ER), Terminal, Vacio, Lambda
IRegularExpression Atom() :
{
String t;
IRegularExpression r;
}
{
( "(" r=Expression() ")" {return r;})
| t=Terminal() { return createTerminal(t); }
| <LAMBDA> { return createLambda(); }
| <VACIO> { return createEmpty(); }
}
// Matchea un terminal (digito o minuscula) y devuelve su valor
String Terminal() :
{
Token t;
}
{
( t=<DIGITO> | t=<MINUSCULA> ) { return t.image; }
}
to any non-spanish interested in this. matchea means "matches", vacio means "empty", digito means "digit" and miniscula means "lowercase". Matchea disyunciones = matches disjunctions. Matchea concatenaciones = matches concatenations. Matchea repeticiones = matches repetition. Matchea regex atomicas = matches atomic regex. Matchea un terminal (digito o minuscula) y devuelve su valor = matches a terminal (digit or lowercase) and returns its value. –
Smelly
Matchear is not Spanish, but I see where it is coming from... Proper Spanish for "matches" would be "coincide con" (matches). –
Elinaelinor
You can submit the regex to preg_match which will return false if the regex is not valid. Don't forget to use the @ to suppress error messages:
@preg_match($regexToTest, '');
- Will return 1 if the regex is
//. - Will return 0 if the regex is okay.
- Will return false otherwise.
This example, originally from the pyparsing wiki, but now available only through the Wayback Machine, gives a grammar for parsing some regexes, for the purposes of returning the set of matching strings. As such, it rejects those re's that include unbounded repetition terms, like '+' and '*'. But it should give you an idea about how to structure a parser that would process re's.
#
# invRegex.py
#
# Copyright 2008, Paul McGuire
#
# pyparsing script to expand a regular expression into all possible matching strings
# Supports:
# - {n} and {m,n} repetition, but not unbounded + or * repetition
# - ? optional elements
# - [] character ranges
# - () grouping
# - | alternation
#
__all__ = ["count","invert"]
from pyparsing import (Literal, oneOf, printables, ParserElement, Combine,
SkipTo, operatorPrecedence, ParseFatalException, Word, nums, opAssoc,
Suppress, ParseResults, srange)
class CharacterRangeEmitter(object):
def __init__(self,chars):
# remove duplicate chars in character range, but preserve original order
seen = set()
self.charset = "".join( seen.add(c) or c for c in chars if c not in seen )
def __str__(self):
return '['+self.charset+']'
def __repr__(self):
return '['+self.charset+']'
def makeGenerator(self):
def genChars():
for s in self.charset:
yield s
return genChars
class OptionalEmitter(object):
def __init__(self,expr):
self.expr = expr
def makeGenerator(self):
def optionalGen():
yield ""
for s in self.expr.makeGenerator()():
yield s
return optionalGen
class DotEmitter(object):
def makeGenerator(self):
def dotGen():
for c in printables:
yield c
return dotGen
class GroupEmitter(object):
def __init__(self,exprs):
self.exprs = ParseResults(exprs)
def makeGenerator(self):
def groupGen():
def recurseList(elist):
if len(elist)==1:
for s in elist[0].makeGenerator()():
yield s
else:
for s in elist[0].makeGenerator()():
for s2 in recurseList(elist[1:]):
yield s + s2
if self.exprs:
for s in recurseList(self.exprs):
yield s
return groupGen
class AlternativeEmitter(object):
def __init__(self,exprs):
self.exprs = exprs
def makeGenerator(self):
def altGen():
for e in self.exprs:
for s in e.makeGenerator()():
yield s
return altGen
class LiteralEmitter(object):
def __init__(self,lit):
self.lit = lit
def __str__(self):
return "Lit:"+self.lit
def __repr__(self):
return "Lit:"+self.lit
def makeGenerator(self):
def litGen():
yield self.lit
return litGen
def handleRange(toks):
return CharacterRangeEmitter(srange(toks[0]))
def handleRepetition(toks):
toks=toks[0]
if toks[1] in "*+":
raise ParseFatalException("",0,"unbounded repetition operators not supported")
if toks[1] == "?":
return OptionalEmitter(toks[0])
if "count" in toks:
return GroupEmitter([toks[0]] * int(toks.count))
if "minCount" in toks:
mincount = int(toks.minCount)
maxcount = int(toks.maxCount)
optcount = maxcount - mincount
if optcount:
opt = OptionalEmitter(toks[0])
for i in range(1,optcount):
opt = OptionalEmitter(GroupEmitter([toks[0],opt]))
return GroupEmitter([toks[0]] * mincount + [opt])
else:
return [toks[0]] * mincount
def handleLiteral(toks):
lit = ""
for t in toks:
if t[0] == "\\":
if t[1] == "t":
lit += '\t'
else:
lit += t[1]
else:
lit += t
return LiteralEmitter(lit)
def handleMacro(toks):
macroChar = toks[0][1]
if macroChar == "d":
return CharacterRangeEmitter("0123456789")
elif macroChar == "w":
return CharacterRangeEmitter(srange("[A-Za-z0-9_]"))
elif macroChar == "s":
return LiteralEmitter(" ")
else:
raise ParseFatalException("",0,"unsupported macro character (" + macroChar + ")")
def handleSequence(toks):
return GroupEmitter(toks[0])
def handleDot():
return CharacterRangeEmitter(printables)
def handleAlternative(toks):
return AlternativeEmitter(toks[0])
_parser = None
def parser():
global _parser
if _parser is None:
ParserElement.setDefaultWhitespaceChars("")
lbrack,rbrack,lbrace,rbrace,lparen,rparen = map(Literal,"[]{}()")
reMacro = Combine("\\" + oneOf(list("dws")))
escapedChar = ~reMacro + Combine("\\" + oneOf(list(printables)))
reLiteralChar = "".join(c for c in printables if c not in r"\[]{}().*?+|") + " \t"
reRange = Combine(lbrack + SkipTo(rbrack,ignore=escapedChar) + rbrack)
reLiteral = ( escapedChar | oneOf(list(reLiteralChar)) )
reDot = Literal(".")
repetition = (
( lbrace + Word(nums).setResultsName("count") + rbrace ) |
( lbrace + Word(nums).setResultsName("minCount")+","+ Word(nums).setResultsName("maxCount") + rbrace ) |
oneOf(list("*+?"))
)
reRange.setParseAction(handleRange)
reLiteral.setParseAction(handleLiteral)
reMacro.setParseAction(handleMacro)
reDot.setParseAction(handleDot)
reTerm = ( reLiteral | reRange | reMacro | reDot )
reExpr = operatorPrecedence( reTerm,
[
(repetition, 1, opAssoc.LEFT, handleRepetition),
(None, 2, opAssoc.LEFT, handleSequence),
(Suppress('|'), 2, opAssoc.LEFT, handleAlternative),
]
)
_parser = reExpr
return _parser
def count(gen):
"""Simple function to count the number of elements returned by a generator."""
i = 0
for s in gen:
i += 1
return i
def invert(regex):
"""Call this routine as a generator to return all the strings that
match the input regular expression.
for s in invert("[A-Z]{3}\d{3}"):
print s
"""
invReGenerator = GroupEmitter(parser().parseString(regex)).makeGenerator()
return invReGenerator()
def main():
tests = r"""
[A-EA]
[A-D]*
[A-D]{3}
X[A-C]{3}Y
X[A-C]{3}\(
X\d
foobar\d\d
foobar{2}
foobar{2,9}
fooba[rz]{2}
(foobar){2}
([01]\d)|(2[0-5])
([01]\d\d)|(2[0-4]\d)|(25[0-5])
[A-C]{1,2}
[A-C]{0,3}
[A-C]\s[A-C]\s[A-C]
[A-C]\s?[A-C][A-C]
[A-C]\s([A-C][A-C])
[A-C]\s([A-C][A-C])?
[A-C]{2}\d{2}
@|TH[12]
@(@|TH[12])?
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))?
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))?
(([ECMP]|HA|AK)[SD]|HS)T
[A-CV]{2}
A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr]
(a|b)|(x|y)
(a|b) (x|y)
""".split('\n')
for t in tests:
t = t.strip()
if not t: continue
print '-'*50
print t
try:
print count(invert(t))
for s in invert(t):
print s
except ParseFatalException,pfe:
print pfe.msg
print
continue
print
if __name__ == "__main__":
main()
Also available in the examples directory of the pyparsing Github repository. –
Ravo
In Javascript:
SyntaxError
is thrown when an invalid regex is passed to evaluate.
// VALID ONE
> /yes[^]*day/
Out: /yes[^]*day/
// INVALID ONE
> /yes[^*day/
Out: VM227:1 Uncaught SyntaxError: Invalid regular expression: missing /
Here's the function to check if the regex string is valid:
Step 1: Regex Parser
var RegexParser = function(input) {
// Parse input
var m = input.match(/(\/?)(.+)\1([a-z]*)/i);
// Invalid flags
if (m[3] && !/^(?!.*?(.).*?\1)[gmixXsuUAJ]+$/.test(m[3])) {
return RegExp(input);
}
// Create the regular expression
return new RegExp(m[2], m[3]);
};
Step 2: Use parser
var RegexString = "/yes.*day/"
var isRegexValid = input => {
try {
const regex = RegexParser(input);
}
catch(error) {
if(error.name === "SyntaxError")
{
return false;
}
else
{
throw error;
}
}
return true;
}
With this version you can check a string for regex with php - i took the example from above and modified a bit:
$re = '/((?:(?:[^?+*{}()[\]\\\\|]+|\\\\.|\[(?:\^?\\\\.|\^[^\\\\]|[^\\\\^])(?:[^\]\\\\]+|\\\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d*(?:,\d*)?\})[?+]?)?|\|)*)/';
$str = '[0-9]{1,}[a-z]';
preg_match($re, $str, $matches, PREG_OFFSET_CAPTURE, 0);
$length = strlen($str);
$length2 = strlen($matches[0][0]);
if($length == $length2) {
echo "is regex";
} else {
echo "is no regex";
}
© 2022 - 2024 — McMap. All rights reserved.