Is it possible to detect a valid regular expression with another regular expression? If so please give example code below.
This question is related to
regex
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; }
}
Unlikely.
Evaluate it in a try..catch or whatever your language provides.
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, '');
//. 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.
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, '');
//. The following example by Paul McGuire, 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()
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; }
}
Unlikely.
Evaluate it in a try..catch or whatever your language provides.
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.
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; }
}
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.
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.
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.
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; }
}
The following example by Paul McGuire, 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()
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.
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.
Unlikely.
Evaluate it in a try..catch or whatever your language provides.
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.
Unlikely.
Evaluate it in a try..catch or whatever your language provides.
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.
Source: Stackoverflow.com