Gibt es einen regulären Ausdruck, um einen gültigen regulären Ausdruck zu erkennen?
1006
Ist es möglich, einen gültigen regulären Ausdruck mit einem anderen regulären Ausdruck zu erkennen? Wenn ja, geben Sie bitte den folgenden Beispielcode an.
Ihr Problem besteht also darin, einen regulären Ausdruck zu validieren. Sie haben einen regulären Ausdruck ausgewählt, um ihn zu lösen. Ich frage mich, ob die Eigenschaft zur Erhöhung der Problemzahl von Regexen additiv oder multiplikativ ist. Es fühlt sich an wie 4 Probleme statt 2 :)
Abesto
15
Es gibt viele Notationen für reguläre Ausdrücke - einige Funktionen und ihre Schreibweise sind den meisten gemeinsam, andere sind anders geschrieben oder nur in einer bestimmten Notation verfügbar. Die meisten dieser Notationen sind nicht "regulär" im Sinne der regulären Grammatik - Sie benötigen einen kontextfreien Parser, um die unbegrenzte Verschachtelung von Unterausdrücken zu handhaben - obwohl viele moderne Notationen mit "regulären Ausdrücken" Erweiterungen haben, die über die ursprüngliche formale Definition und hinausgehen könnte erlauben, dass ihre eigenen Notationen erkannt werden. Fragen Sie in jedem Fall einfach Ihre Regex-Bibliothek, ob jeder Regex gültig ist.
Steve314
1
@bevacqua Ich muss Regexp im XML-Schema validieren. Wie kann ich es ohne einen anderen regulären Ausdruck machen?
Zenden2k
3
Kompilieren / führen Sie den zu überprüfenden regulären Ausdruck (Muster) tatsächlich unter einem Ausnahmebehandlungsmechanismus aus, über den Ihre Sprache verfügt. Die Regex-Engine / der Compiler der Sprache selbst wird dies überprüfen. (Dies setzt eine korrekte Grundsyntax voraus, damit das Programm ausgeführt wird. Dies kann jedoch in die Prüfung einbezogen werden, indem die Zeichenfolgen für die Regex mithilfe der Sprachfunktionen als (möglicherweise syntaktisch falscher) Code oder dergleichen
/^# 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/
Dies ist eine rekursive Regex und wird von vielen Regex-Engines nicht unterstützt. PCRE-basierte sollten dies unterstützen.
.NET unterstützt die Rekursion nicht direkt. (Die (?1)und (?R)Konstrukte.) Die Rekursion müsste in das Zählen ausgeglichener Gruppen umgewandelt werden:
^# 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.
Wird dies Substitutionen und Übersetzungen validieren?
Es wird nur der Regex-Teil von Substitutionen und Übersetzungen validiert. s/<this part>/.../
Es ist theoretisch nicht möglich, alle gültigen Regex-Grammatiken mit einem Regex abzugleichen.
Es ist möglich, dass die Regex-Engine eine Rekursion wie PCRE unterstützt, dies kann jedoch nicht mehr als reguläre Ausdrücke bezeichnet werden.
In der Tat ist ein "rekursiver regulärer Ausdruck" kein regulärer Ausdruck. Aber dies ist eine häufig akzeptierte Erweiterung für Regex-Engines ... Ironischerweise stimmt diese erweiterte Regex nicht mit erweiterten Regex überein.
"In Theorie, Theorie und Praxis sind sie gleich. In der Praxis sind sie es nicht." Fast jeder, der reguläre Ausdrücke kennt, weiß, dass reguläre Ausdrücke keine Rekursion unterstützen. PCRE und die meisten anderen Implementierungen unterstützen jedoch weit mehr als grundlegende reguläre Ausdrücke.
Wenn ich dies mit dem Shell-Skript im Befehl grep verwende, wird mir ein Fehler angezeigt. grep: Ungültiger Inhalt von {}. Ich mache ein Skript, das eine Codebasis durchsuchen könnte, um alle Dateien zu finden, die reguläre Ausdrücke enthalten
Dieses Muster nutzt eine Erweiterung, die als rekursive reguläre Ausdrücke bezeichnet wird. Dies wird von der POSIX-Variante von Regex nicht unterstützt. Sie können versuchen, mit dem -P-Schalter die PCRE-Regex-Variante zu aktivieren.
Regex selbst "ist keine reguläre Sprache und kann daher nicht durch reguläre Ausdrücke analysiert werden ..."
Dies gilt für klassische reguläre Ausdrücke. Einige moderne Implementierungen erlauben eine Rekursion, wodurch sie zu einer kontextfreien Sprache wird, obwohl sie für diese Aufgabe etwas ausführlich ist.
Ich sehe, wo du zusammenpasst []()/\. und andere Regex-Sonderzeichen. Wo erlauben Sie nicht spezielle Zeichen? Es scheint, als würde dies übereinstimmen ^(?:[\.]+)$, aber nicht ^abcdefg$. Das ist eine gültige Regex.
[^?+*{}()[\]\\|]stimmt mit jedem einzelnen Zeichen überein, das nicht Teil eines der anderen Konstrukte ist. Dazu gehören sowohl die wörtliche ( a- z) und bestimmte Sonderzeichen ( ^, $, .).
Diese Antwort schickt die Leute in die völlig falsche Richtung. Sie sollten niemals regEx verwenden, um reguläre Ausdrücke zu finden, da dies nicht in allen Fällen korrekt funktionieren kann. Siehe meine Antwort hinzugefügt.
Vitaly-t
1
.{,1}ist unübertroffen. Wechseln Sie zu ^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d*(?:,\d*)?\})[?+]?)?|\|)*)$Übereinstimmungen. Ändern Sie \d+zu\d*
yunzen
4
Regex per Def sollte keine Rekursion haben, zumindest sagen Sie so etwas in Ihrer Antwort, Ihre Regex-Engine ist wahrscheinlich "zu leistungsfähig" und nicht wirklich eine Regex-Engine.
Charlie Parker
Nur eine Anmerkung, Sie haben die x-Flagge vergessen
RedClover
Dieser Validator scheint für PCRE-Ausdrücke gemacht zu sein, übergibt jedoch viele ungültige POSIX-EREs. Insbesondere sind sie in Zeichenklassenbereichen etwas wählerischer, z. B. gilt dies in PCRE, nicht jedoch in ERE : [a-b-c].
Pedro Gimeno
321
Unwahrscheinlich.
Bewerten Sie es in einer try..catchoder einer anderen Sprache.
Nein, wenn Sie streng genommen von regulären Ausdrücken sprechen und einige Implementierungen regulärer Ausdrücke nicht einschließen, die tatsächlich kontextfreie Grammatiken sind.
Es gibt eine Einschränkung für reguläre Ausdrücke, die es unmöglich macht, einen regulären Ausdruck zu schreiben, der allen und nur regulären Ausdrücken entspricht. Sie können keine Implementierungen wie gepaarte Klammern abgleichen. Regexes verwenden viele solcher Konstrukte. Nehmen wir []als Beispiel. Wann immer es eine [gibt, muss es eine Übereinstimmung geben ], die für einen regulären Ausdruck einfach genug ist "\[.*\]".
Was es für Regexes unmöglich macht, ist, dass sie verschachtelt werden können. Wie kann man einen regulären Ausdruck schreiben, der mit verschachtelten Klammern übereinstimmt? Die Antwort ist, dass Sie nicht ohne einen unendlich langen regulären Ausdruck auskommen können. Sie können eine beliebige Anzahl verschachtelter Klammern durch Brute Force abgleichen, aber Sie können niemals einen beliebig langen Satz verschachtelter Klammern abgleichen.
Diese Funktion wird häufig als Zählen bezeichnet, da Sie die Tiefe der Verschachtelung zählen. Ein Regex kann per Definition nicht zählen.
Echte reguläre Sprachen können nicht willkürlich tief verschachtelte, wohlgeformte Klammern bestimmen. Wenn Ihr Alphabet enthält '('und ')'das Ziel darin besteht, zu entscheiden, ob eine Zeichenfolge davon gut geformte übereinstimmende Klammern enthält. Da dies eine notwendige Voraussetzung für reguläre Ausdrücke ist, lautet die Antwort nein.
Wenn Sie jedoch die Anforderung lösen und eine Rekursion hinzufügen, können Sie dies wahrscheinlich tun. Der Grund dafür ist, dass die Rekursion als Stapel fungieren kann, mit dem Sie die aktuelle Verschachtelungstiefe "zählen" können, indem Sie auf diesen Stapel drücken.
Nein, wenn Sie reguläre Standardausdrücke verwenden.
Der Grund ist, dass Sie das Pump-Lemma für reguläre Sprachen nicht erfüllen können . Die Pump Lemma besagt , dass ein String Sprache „L“ gehört , ist regulär , wenn es eine Reihe existiert „N“ , so dass nach der Zeichenfolge in drei Teil Dividieren x, y, z, so dass |x|>=1 && |xy|<=NSie wiederholen können , yso oft wie Sie wollen , und die Die gesamte Zeichenfolge gehört weiterhin dazu L.
Eine Folge des Pump-Lemmas ist, dass Sie keine regulären Zeichenfolgen in der Form haben a^Nb^Mc^Nkönnen, dh zwei Teilzeichenfolgen mit derselben Länge, die durch eine andere Zeichenfolge getrennt sind. In keiner Weise geteilt Sie solche Strings x, yund zkönnen Sie nicht „Pumpe“ yohne einen String mit einer unterschiedlichen Anzahl von „a“ und „c“ zu erhalten, damit die ursprünglichen Sprache zu verlassen. Dies ist beispielsweise bei Klammern in regulären Ausdrücken der Fall.
Das ist keine sehr genaue Beschreibung des Pump-Lemmas. Erstens kann die gesamte Sprache regulär sein oder nicht, keine einzelne Zeichenfolge. Zweitens ist es eine notwendige, nicht ausreichende Bedingung für die Regelmäßigkeit. Schließlich sind nur ausreichend lange Saiten pumpbar.
Darij Grinberg
13
Obwohl es durchaus möglich ist, einen rekursiven regulären Ausdruck zu verwenden, wie MizardX es gepostet hat, ist es für diese Art von Dingen ein Parser viel nützlicher. Regexes sollten ursprünglich mit regulären Sprachen verwendet werden. Rekursiv zu sein oder Ausgleichsgruppen zu haben, ist nur ein Patch.
Die Sprache, die gültige reguläre Ausdrücke definiert, ist eigentlich eine kontextfreie Grammatik, und Sie sollten einen geeigneten Parser verwenden, um damit umzugehen. Hier ist ein Beispiel für ein Universitätsprojekt zum Parsen einfacher Regexe (ohne die meisten Konstrukte). Es verwendet JavaCC. Und ja, Kommentare sind auf Spanisch, obwohl Methodennamen ziemlich selbsterklärend sind.
Sie können den regulären Ausdruck senden, an den preg_matchfalse zurückgegeben wird, wenn der reguläre Ausdruck ungültig ist. Vergessen Sie nicht, die zu verwenden @, um Fehlermeldungen zu unterdrücken:
@preg_match($regexToTest,'');
Gibt 1 zurück, wenn der reguläre Ausdruck ist //.
Gibt 0 zurück, wenn der reguläre Ausdruck in Ordnung ist.
Das folgende Beispiel von Paul McGuire, das ursprünglich aus dem Pyparsing-Wiki stammt, jetzt aber nur über die Wayback-Maschine verfügbar ist , enthält eine Grammatik zum Parsen einiger regulärer Ausdrücke, um den Satz übereinstimmender Zeichenfolgen zurückzugeben. Als solches lehnt es diejenigen Re ab, die unbegrenzte Wiederholungsbegriffe wie '+' und '*' enthalten. Aber es sollte Ihnen eine Vorstellung davon geben, wie Sie einen Parser strukturieren, der Re's verarbeitet.
# # 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)classCharacterRangeEmitter(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 notin seen )def __str__(self):return'['+self.charset+']'def __repr__(self):return'['+self.charset+']'def makeGenerator(self):def genChars():for s inself.charset:yield s
return genChars
classOptionalEmitter(object):def __init__(self,expr):self.expr = expr
def makeGenerator(self):def optionalGen():yield""for s inself.expr.makeGenerator()():yield s
return optionalGen
classDotEmitter(object):def makeGenerator(self):def dotGen():for c in printables:yield c
return dotGen
classGroupEmitter(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
ifself.exprs:for s in recurseList(self.exprs):yield s
return groupGen
classAlternativeEmitter(object):def __init__(self,exprs):self.exprs = exprs
def makeGenerator(self):def altGen():for e inself.exprs:for s in e.makeGenerator()():yield s
return altGen
classLiteralEmitter(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():yieldself.lit
return litGen
def handleRange(toks):returnCharacterRangeEmitter(srange(toks[0]))def handleRepetition(toks):
toks=toks[0]if toks[1]in"*+":raiseParseFatalException("",0,"unbounded repetition operators not supported")if toks[1]=="?":returnOptionalEmitter(toks[0])if"count"in toks:returnGroupEmitter([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]))returnGroupEmitter([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
returnLiteralEmitter(lit)def handleMacro(toks):
macroChar = toks[0][1]if macroChar =="d":returnCharacterRangeEmitter("0123456789")elif macroChar =="w":returnCharacterRangeEmitter(srange("[A-Za-z0-9_]"))elif macroChar =="s":returnLiteralEmitter(" ")else:raiseParseFatalException("",0,"unsupported macro character ("+ macroChar +")")def handleSequence(toks):returnGroupEmitter(toks[0])def handleDot():returnCharacterRangeEmitter(printables)def handleAlternative(toks):returnAlternativeEmitter(toks[0])
_parser =Nonedef parser():global _parser
if _parser isNone: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 notin 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 =0for s in gen:
i +=1return 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()ifnot t:continueprint'-'*50print t
try:print count(invert(t))for s in invert(t):print s
exceptParseFatalException,pfe:print pfe.msg
printcontinueprintif __name__ =="__main__":
main()
Antworten:
Dies ist eine rekursive Regex und wird von vielen Regex-Engines nicht unterstützt. PCRE-basierte sollten dies unterstützen.
Ohne Leerzeichen und Kommentare:
.NET unterstützt die Rekursion nicht direkt. (Die
(?1)
und(?R)
Konstrukte.) Die Rekursion müsste in das Zählen ausgeglichener Gruppen umgewandelt werden:Verdichtet:
Aus den Kommentaren:
Es wird nur der Regex-Teil von Substitutionen und Übersetzungen validiert.
s/<this part>/.../
Es ist möglich, dass die Regex-Engine eine Rekursion wie PCRE unterstützt, dies kann jedoch nicht mehr als reguläre Ausdrücke bezeichnet werden.
"In Theorie, Theorie und Praxis sind sie gleich. In der Praxis sind sie es nicht." Fast jeder, der reguläre Ausdrücke kennt, weiß, dass reguläre Ausdrücke keine Rekursion unterstützen. PCRE und die meisten anderen Implementierungen unterstützen jedoch weit mehr als grundlegende reguläre Ausdrücke.
Dieses Muster nutzt eine Erweiterung, die als rekursive reguläre Ausdrücke bezeichnet wird. Dies wird von der POSIX-Variante von Regex nicht unterstützt. Sie können versuchen, mit dem -P-Schalter die PCRE-Regex-Variante zu aktivieren.
Dies gilt für klassische reguläre Ausdrücke. Einige moderne Implementierungen erlauben eine Rekursion, wodurch sie zu einer kontextfreien Sprache wird, obwohl sie für diese Aufgabe etwas ausführlich ist.
[^?+*{}()[\]\\|]
stimmt mit jedem einzelnen Zeichen überein, das nicht Teil eines der anderen Konstrukte ist. Dazu gehören sowohl die wörtliche (a
-z
) und bestimmte Sonderzeichen (^
,$
,.
).quelle
.{,1}
ist unübertroffen. Wechseln Sie zu^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d*(?:,\d*)?\})[?+]?)?|\|)*)$
Übereinstimmungen. Ändern Sie\d+
zu\d*
[a-b-c]
.Unwahrscheinlich.
Bewerten Sie es in einer
try..catch
oder einer anderen Sprache.quelle
Nein, wenn Sie streng genommen von regulären Ausdrücken sprechen und einige Implementierungen regulärer Ausdrücke nicht einschließen, die tatsächlich kontextfreie Grammatiken sind.
Es gibt eine Einschränkung für reguläre Ausdrücke, die es unmöglich macht, einen regulären Ausdruck zu schreiben, der allen und nur regulären Ausdrücken entspricht. Sie können keine Implementierungen wie gepaarte Klammern abgleichen. Regexes verwenden viele solcher Konstrukte. Nehmen wir
[]
als Beispiel. Wann immer es eine[
gibt, muss es eine Übereinstimmung geben]
, die für einen regulären Ausdruck einfach genug ist"\[.*\]"
.Was es für Regexes unmöglich macht, ist, dass sie verschachtelt werden können. Wie kann man einen regulären Ausdruck schreiben, der mit verschachtelten Klammern übereinstimmt? Die Antwort ist, dass Sie nicht ohne einen unendlich langen regulären Ausdruck auskommen können. Sie können eine beliebige Anzahl verschachtelter Klammern durch Brute Force abgleichen, aber Sie können niemals einen beliebig langen Satz verschachtelter Klammern abgleichen.
Diese Funktion wird häufig als Zählen bezeichnet, da Sie die Tiefe der Verschachtelung zählen. Ein Regex kann per Definition nicht zählen.
Am Ende schrieb ich " Einschränkungen für reguläre Ausdrücke " darüber.
quelle
Gute Frage.
Echte reguläre Sprachen können nicht willkürlich tief verschachtelte, wohlgeformte Klammern bestimmen. Wenn Ihr Alphabet enthält
'('
und')'
das Ziel darin besteht, zu entscheiden, ob eine Zeichenfolge davon gut geformte übereinstimmende Klammern enthält. Da dies eine notwendige Voraussetzung für reguläre Ausdrücke ist, lautet die Antwort nein.Wenn Sie jedoch die Anforderung lösen und eine Rekursion hinzufügen, können Sie dies wahrscheinlich tun. Der Grund dafür ist, dass die Rekursion als Stapel fungieren kann, mit dem Sie die aktuelle Verschachtelungstiefe "zählen" können, indem Sie auf diesen Stapel drücken.
Russ Cox schrieb " Regular Expression Matching kann einfach und schnell sein ", eine wunderbare Abhandlung über die Implementierung von Regex-Engines.
quelle
Nein, wenn Sie reguläre Standardausdrücke verwenden.
Der Grund ist, dass Sie das Pump-Lemma für reguläre Sprachen nicht erfüllen können . Die Pump Lemma besagt , dass ein String Sprache „L“ gehört , ist regulär , wenn es eine Reihe existiert „N“ , so dass nach der Zeichenfolge in drei Teil Dividieren
x
,y
,z
, so dass|x|>=1 && |xy|<=N
Sie wiederholen können ,y
so oft wie Sie wollen , und die Die gesamte Zeichenfolge gehört weiterhin dazuL
.Eine Folge des Pump-Lemmas ist, dass Sie keine regulären Zeichenfolgen in der Form haben
a^Nb^Mc^N
können, dh zwei Teilzeichenfolgen mit derselben Länge, die durch eine andere Zeichenfolge getrennt sind. In keiner Weise geteilt Sie solche Stringsx
,y
undz
können Sie nicht „Pumpe“y
ohne einen String mit einer unterschiedlichen Anzahl von „a“ und „c“ zu erhalten, damit die ursprünglichen Sprache zu verlassen. Dies ist beispielsweise bei Klammern in regulären Ausdrücken der Fall.quelle
Obwohl es durchaus möglich ist, einen rekursiven regulären Ausdruck zu verwenden, wie MizardX es gepostet hat, ist es für diese Art von Dingen ein Parser viel nützlicher. Regexes sollten ursprünglich mit regulären Sprachen verwendet werden. Rekursiv zu sein oder Ausgleichsgruppen zu haben, ist nur ein Patch.
Die Sprache, die gültige reguläre Ausdrücke definiert, ist eigentlich eine kontextfreie Grammatik, und Sie sollten einen geeigneten Parser verwenden, um damit umzugehen. Hier ist ein Beispiel für ein Universitätsprojekt zum Parsen einfacher Regexe (ohne die meisten Konstrukte). Es verwendet JavaCC. Und ja, Kommentare sind auf Spanisch, obwohl Methodennamen ziemlich selbsterklärend sind.
quelle
Sie können den regulären Ausdruck senden, an den
preg_match
false zurückgegeben wird, wenn der reguläre Ausdruck ungültig ist. Vergessen Sie nicht, die zu verwenden@
, um Fehlermeldungen zu unterdrücken://
.quelle
Das folgende Beispiel von Paul McGuire, das ursprünglich aus dem Pyparsing-Wiki stammt, jetzt aber nur über die Wayback-Maschine verfügbar ist , enthält eine Grammatik zum Parsen einiger regulärer Ausdrücke, um den Satz übereinstimmender Zeichenfolgen zurückzugeben. Als solches lehnt es diejenigen Re ab, die unbegrenzte Wiederholungsbegriffe wie '+' und '*' enthalten. Aber es sollte Ihnen eine Vorstellung davon geben, wie Sie einen Parser strukturieren, der Re's verarbeitet.
quelle