parsing bracket pairs
-
Hallo,
Folgendes Problem: für einen Ausdruck, der aus Klammern ( ) und anderen Zeichen besteht, soll zu einer gegebenen öffnenden Klammer "(" die *zugehörige* schließende Klammer ")" gefunden werden.
Beispiel: Zur Eingabe (abc(de)(f)) soll der Inhalt des äußersten Klammerpaares, also abc(de)(f) ausgegeben werden.
Problem: Mit puren regulären Ausdrücken scheint das nicht zu gehen. Schließlich ist die Sprache aller wohlgeformten Klammerausdrücke nicht regulär, sondern kontextfrei. Gibt es in einer der in Frage kommenden Sprachen awk/sed/bash/python/ruby (notfalls auch C/C++) eine elegante Methode oder gar eingebaute Funktion zum Erkennen zusammengehöriger Klammern ? Oder zum automatischen Extrahieren des Klammerinhalts, selbst wenn weitere Klammerebenen dazwischenliegen, wie im Beispiel ?
[Natürlich läßt sich das Problem in jeder Sprache mittels eines Zählers lösen, der bei "(" eins hochzählt und bei ")" eins herunterzählt; bei Erreichen der Null ist die Klammer gefunden. Aber ich frage mich, ob es nicht noch eine einfachere Möglichkeit gibt, die mit "Bordmitteln" auskommt, ohne den beschriebenen Zählmechanismus implementieren zu müssen]
Grüße
-
dein "zählmechanismus" besteht aus 4 zeilen code, maximal, und die hättest du 10 mal tippen können in der zeit in der du den beitrag da geschrieben hast.
-
-
Gerard, das erlaubt aber keine Verschachtelung.
-
Bei Perl un Php gehts mit recuriven Regexen. Boost::regex hat diese Erweiterung aber leider (noch) nicht übernommen.
Ich glaub das geht so:
[(](?R)*[)]Wobei (?R) durch das gesamte Regex ersetzt wird. Dies wird dann recursive fortgesetzt.
Ohne Recurion geht das aber nicht mit Regexen.
Jemand der geübt in Boost.Spirit ist könnte da wahrscheinlich was hinzaubern. Wobei da dann doch der selbst geschriebene Parsers doch einfacher ist.
-
ok "[(][^()][)]" matcht nur (de) und (f)
aber
[(]([^()]|.*)[)] matcht auf abc(de)(f)http://regexp-evaluator.de/evaluator/
hat natürlich noch andere probleme, an die man sich rantasten muss
-
ok "[(][^()][)]" matcht nur (de) und (f)
aber
[(]([^()]|.*)[)] matcht auf abc(de)(f)Bringt dir aber leider nichts, da die Gruppierungen nicht entsprechend fortgesetzt werden. Bei (abc(de)(f)) wird lediglich abc(de)(f) als Gruppierung geliefert.
Es ist schlichtweg nicht möglich eine nicht-reguläre Sprache (wie C++, Java, ...) mit regulären Ausdrücken zu parsen. Rekursionen erweitern reguläre Ausdrücke dahingehend, dass man sie eigentlich gar nicht mehr als reguläre Ausdrücke bezeichnen kann, siehe auch Wikipedia.
Einzige Alternative die, dir bleibt ist eine Art Scanner Generator zu verwenden. Da ich selbst aus dem Java Umfeld komme, kenne ich auch nur Projekte wie jflex oder JavaCC, die in diese Richtung gehen, aber vielleicht findest ja selbst was.
Im Prinzip bleibts aber bei der Idee der Rekursion, es wird halt lediglich das Suchmuster "zerlegt".