Hallo!
In der Softwareentwicklung steht man regelmäßig vor der Aufgabe, eine Eingabe nach gewissen Regeln zu verarbeiten. Dazu bedient man sich in einfachen Fällen regulärer Ausdrücke, die man in C++ z.B. mit der boost::regex library verarbeiten kann. Wenn die Struktur der Eingabe zu komplex ist, definiert man eine Grammatik und verwendet einen Parser Generator wie lex/yacc oder ANTLR (wobei man in diesem Fall vorsichtig sein muss. Für die aktuelle Version 3.0 ist zum Zeitpunkt der Veröffentlichung dieses postings immer noch kein brauchbares C++ target verfügbar).
Reguläre Ausdrücke sind allerdings schwer zu lesen und eignen sich schlecht für rekursive Strukturen.
Einen Parser Generator aufzusetzen und in ein C++-Projekt einzubinden ist wiederum etwas lästig. Insbesondere wenn man verschiedene Plattformen (etwa, Visual C++ und MinGW unter Windows und gcc unter Linux) unterstützt, wiederholt sich der Aufwand.
Mit der boost::spirit library gibt es noch einen Weg dazwischen, der genau diese Lücke füllt. Man kann mit richtigen Grammatiken arbeiten und braucht trotzdem kein externes tool einzubinden.
Da die Arbeit mit Spirit nicht ganz trivial ist, wollte ich meine Erfahrungen anhand eines kleinen Beispiels festhalten und weitergeben.
Die zu lösende Aufgabe bestand darin, einen String zu parsen, der einen “instantiierten Typ” – i.A. template oder generic genannt – verarbeitet und die verwendeten Typen als Liste zurückgibt. Dabei sollten die in den gängigen Programmiersprachen üblichen Regeln für identifier berücksichtigt werden und die Eingabe sollte wie sonst üblich formatfrei sein, d.h. white space sollte ignoriert werden.
Beispiele für gültige Eingaben wären dann:
Set(String)
Set(Bag(String))
Set ( String )
My_Container1(Integer)
Eine solche Aufgabe ist genau von der richtigen Komplexität für boost::spirit.
Falls sich jemand über die runden Klammern wundert (üblich sind spitze Klammern) – der Parser soll im Kontext der Object Constraint Language (OCL) verwendet werden und dort werden runde Klammern verwendet. Dies ist aber ein irrelevantes Detail.
Spirit ist auf möglichst flexible Verwendbarkeit ausgelegt, es gibt verschiedene alternative Verfahren und es werden intensiv “Policy-Klassen” in der Form von template-Parametern verwendet.
Dies macht die Verwendung nicht gerade leichter, da es sehr viele mögliche Kombinationen der Verfahren und Policies gibt. Deshalb soll dieses posting auch eine Art Kochbuch sein, dass typische Anforderungen abdeckt. Gängige Beispiele wie etwa hier verwenden “semantic actions”, die direkt beim match einer Regel ausgeführt werden. Dieses Vorgehen hat einen grossen Nachteil, der es für viele Fälle unbrauchbar macht: bei einer mehrdeutigen Grammatik, wie sie in der Praxis häufig vorkommen, versucht der Parser durch “probieren” eine zur Eingabe passende Regel zu finden. Falls dies nicht klappt wird der Versuch abgebrochen und nochmal von vorne begonnen (”backtracking“). Dummerweise werden semantic actions die mit einer Regel assoziiert sind bei jedem versuchten match aufgerufen. Es kann aber sein, dass diese Aufrufe gar nicht relevant sind, weil der Parser später erkennt dass die aktuelle Regel nicht matcht und ein backtracking vornimmt.
Spirit bietet die Möglichkeit einen “tree parser” zu verwenden, der dieses Problem nicht hat. Ein solcher tree parser liefert einen Syntax Baum der immer gleich aussieht und exakt der Eingabe entspricht, unabhängig davon wie oft ein backtracking auftrat. Davon abgesehen ist es generell eine gute Idee, die Grammatik von der semantischen Verarbeitung zu trennen, was mit einem tree parser implizit gegeben ist.
Zusammenfassend würde ich also bei der Verwendung von Spirit immer einen Tree Parser empfehlen.
Angesichts der schweren Zugänglichkeit von Spirit ist man für Beispiele immer dankbar, z.B. hier für die Verwendung eines tree parsers. Wenn man sich an diesem Beispiel anlehnt, wird man aber feststellen, dass der Parser white space nicht ignoriert, ein Verhalten dass im allgemeinen unerwünscht ist. Die Lösung besteht darin, die Zeile
typedef scanner_policies<iteration_policy, match_policy_t, action_policy> scanner_policy_t;
in
typedef scanner_policies<skip_parser_iteration_policy<space_parser>, match_policy_t, action_policy> scanner_policy_t;
zu ändern. Auch wenn man herausgefunden hat, dass der erste template Parameter, die “iteration policy”, für das ignorieren von white space zuständig ist, ist es noch ein weiter Weg bis man den korrekten Wert kennt den man für diese policy angeben muss.
Nachdem ich in diesem posting die wichtige Festlegung auf einen tree parser empfohlen habe und die Hürde des ungünstigen Beispiels eines parser der white space nicht ignoriert genommen habe, werde ich im nächsten posting den konkreten code und insbesondere die Definition der Grammatik zeigen.
Knifflig wird es dann wieder beim Auswerten des parse trees, was leider keine triviale Aufgabe ist.
Viele Grüße,
Andreas
Technorati Tags: parsing, spirit, C++
