Dieser und noch weitere Artikel wurde von phlox81 erstellt.


Folgende Themen werden von diesem Artikel berührt:


Druckversion des Artikels


1 Vorbemerkungen

Dieser Artikel beschäftigt sich mit boost::spirit 2.0, welches der Nachfolger von boost::spirit1.x ist.
Für Einsteiger empfiehlt sich deshalb auch die Lektüre von Boost::Spirit - Eine Einführung, da ich nicht auf alle Details der Syntax eingehen werde.

Auch gilt für die meisten Codebeispiele, dass die Namespaces eingebunden werden:
C++:
using namespace boost::spirit;
using namespace boost::spirit::qi;
using namespace boost::spirit::ascii;
using namespace boost::spirit::arg_names;
using boost::phoenix::ref;


1.1 Vorwort

Hartmut Kaiser, einer der Spiritentwickler, war so freundlich, das Vorwort zu diesem Artikel zu schreiben:

Der Geist aus der Flasche: Parsen und Ausgabegenerierung in C++ mit Spirit V2

Viele Programmierer bringen das Parsen von Zeichenketten immer noch mit schwarzer Magie in Zusammenhang, wobei man, um es zu beherrschen, auf solche esotherischen Werkzeuge wie Lex und Yacc zurückgreifen muss. Das führt dazu, dass Parser oft von Hand geschrieben werden, was dem Mythos zusätzlichen Nährboden verschafft.

Ähnlich verhält es sich mit dem Generieren von (formatierten) Ausgaben. Auch hier wird zumeist auf die altbewährte Handarbeit zurückgegriffen, nur dass in diesem Fall kaum Werkzeuge existieren (zumindest nicht in C++), die uns 'normalen' Programmierern helfen könnten, einfach, flexibel und schnell unsere auszugebeneden Zeichenketten zu erzeugen. Da wird oft auf printf und die doch etwas unbequemen C++-Streams zurückgegriffen. Nur selten werden externe Werkzeuge wie templatebasierte Generatoren verwendet.

In beiden Fällen, beim handgeschriebenen Programm für das Parsen und für das Generieren von Ausgaben erhalten wir oft im Ergebnis Code, der nicht nur unübersichtlich und schlecht wartbar ist, sondern gleichzeitig dem falschen Eindruck Vorschub leistet, C++ sei zu komplex für 'normale' Programmierer. Jede kleinste Änderung in den zu Grunde liegenden Datenstrukturen führt dazu, dass man große Teile des Codes umschreiben muss.

Eine Einführung

Wer sich in der Welt der Parser umsieht, dem fällt (neben BNFC vielleicht) eine Bibliothek ganz besonders auf: Spirit - eine templatebasierte C++-Bibliothek, die Bestandteil der wohlbekannten Boost-Bibliothekssammlung ist. Während die meisten Parsertools auf der einen oder anderen Form von Codegenerierung beruhen (oder sogar auf "Codegenerierung-Generierung" wie im Fall von BNFC), so ist Spirit im Gegensatz dazu eine Meta-Programmierungs-Bibliothek, die sich ausschließlich auf die Möglichkeiten des C++-Compilers selbst stützt. Zur Codegenerierung verlässt Spirit nie die Zielsprache: C++ eben. Wem das zu abstrakt klingt, der kann sich das als "coole Dinge mit C++ innerhalb der Sprache selbst machen" vorstellen.

Die Vorteile sind offensichtlich: man benötigt keine separaten Tools um seinen Parser zu erzeugen, man muss auch keine neue Sprache erlernen, nur um diesen Tools beizubringen, was man von ihnen möchte. Spirit nutzt lediglich die Möglichkeiten, die C++ sowieso bietet. Man kann also Parser schreiben und sich dabei vollständig auf seine Kenntnisse der Sprache verlassen.

In der Welt der Parsergeneratoren hat sich über lange Zeit bewährt, die Zeichenketten, die durch einen Parser 'verstanden' werden sollen, formal zu beschreiben. Eine der neueren Erkenntnisse auf diesem Gebiet sind die Parser Expression Grammars (PEGs), die im wesentlichen eine Weiterentwicklung von EBNF (Extended Backus-Naur-Form) mit Elementen regulärer Ausdrücke sind. Wir werden weiter unten auf PEGs zurückkommen und diese näher erläutern. Diese Parsergeneratoren sind zumeist als externe Werkzeuge verfügbar, die diese formale Beschreibung einlesen und daraus Code generieren. Dieser Code kann für 2 Dinge verwendet werden. Zum Einen kann man prüfen, ob die Struktur einer Zeichenkette der formalen Beschreibung entspricht, und zum Anderen, um eine 'richtig strukturierte' Zeichenkette in eine passende interne Datenstruktur einzulesen. Spirit greift PEGs auf und verallgemeinert ihren Einsatz nicht nur für das Parsen sondern auch für das Generieren formatierter Ausgaben.

Wir wollen die Theorie hier verlassen und anschauen, was das für den normalsterblichen Programmierer bedeutet. Angenommen, wir wollen eine Liste von Komma-separierten double-Zahlen einlesen (später werden wir diese Zahlen direkt in einem std::vector<double> ablegen). Eine zu simple Aufgabe um einen Parser zu schreiben? Nicht mit Spirit! Hier erstmal der Code, welche die Liste der double Zahlen einlesen kann:
C++:
double_ >> *(',' >> double_)
Das sieht fast wie eine der allseits bekannten Eingabe-(Stream-)Operationen aus, bedeutet aber etwas anderes. Dieser Ausdruck teilt Spirit mit: bitte erkenne für mich in der Eingabezeichenkette eine double Zahl gefolgt von (>>) null oder mehr Vorkommen (*) von einem Komma jeweils gefolgt von einer double-Zahl - eine Komma-separierte Liste von doubles also.

Dieses kleine Beispiel macht das zentrale Funktionsprinzip von Spirit klar: es benutzt die Eigenschaft von C++, die es erlaubt, fast beliebige Operatoren zu überladen und mit eigener Funktionalität zu versehen. In diesem Fall werden die überladenen Versionen des operator>>() und des operator*() verwendet. Im folgenden wird ein vollständiges (kompilierbares) Codebeispiel gegeben, die den eben definierten Parser einsetzt.

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Dieses Programm versucht das erste Kommandozeilenargument als eine Liste von
// doubles zu interpretieren und meldet, ob es eine ist.

#include <iostream>

#include <boost/spirit.hpp>
 
using namespace boost::spirit;
 
int main(int argc, char* argv[])
{
    if (argc != 2) {
        std::cerr << "Liste von doubles fehlt!" << std::endl;
        return -1;
    }
 
    if (qi::parse (argv[1], double_ >> *(',' >> double_))
        std::cout << "Ja, das ist eine Liste von doubles!" << std::endl;
    else
        std::cout << "War nix!" << std::endl;
       
    return 0;
}


Die Idee, eine formale Notation, also eine Grammatik, zu verwenden, um eine erwartete Struktur der zu untersuchenden Eingabe-Zeichenkette zu beschreiben, ist sehr flexibel und leicht verständlich. Offensichtlich läßt sich diese Grammatik aber auch dafür verwenden, die gewünschte Struktur einer entsprechenden Ausgabe-Zeichenkette zu formalisieren. Das funktioniert, weil Parsen zumeist durch den Vergleich der Eingabe mit den formalen Mustern in der Grammatik erfolgt. Wenn man also die selben Muster wieder verwendet um eine passende Ausgabe zu formatieren, wird diese Ausgabe auch den Regeln der Grammatik folgen.

In Spirit ist dieser Gedanke aufgegriffen und implementiert worden. Wir können das eben anhand unseres kleinen Beispiels gelernte Wissen anwenden, um eine Komma-separierte Liste von doubles auszugeben. Die entsprechende Formatierungsregel sieht so aus:
C++:
double_ << *(',' << double_)
Wieder werden C++-Operatoren überladen und mit einer neuen Bedeutung versehen. Die Sequenz mehrerer Ausgabeprimitive wird durch den operator<<() codiert, wobei der operator*() eine identische Bedeutung hat wie im Beispiel oben. Alles in allem teilt diese Regel Spirit mit: bitte erzeuge in der Ausgabe eine Zeichenkette die aus einer double-Zahl besteht, gefolgt von null oder mehr Vorkommen (*) eines Kommas, jeweils gefolgt von ebenfalls einer double-Zahl.

Eingabe und Ausgabe sind in Spirit symmetrisch und sich gegenseitig ergänzend implementiert. Viele der Primitive (hier: double_, man beachte den angehängten Unterstrich) sind für beides einsetzbar, viele Konzepte kompatibel. Eingabe und Ausgabe in Spirit sind wie Yin und Yang, die komplementären Seiten ein und der selben Medaille.

1.2 Was ist neu? Was ist anders?

Als allererstes sollte man vielleicht sagen, dass Spirit2 nicht unbedingt kompatibel zu seinem Vorgänger ist, da es die Erfahrungen und das Feedback der Spiritcommunitiy aufgreift, und von Grund auf neu entwickelt wurde. Zwar blieb bewährtes, wie z.B. die bekannten Regeldefinitionen, aber vieles hat sich verändert bzw. wurde erweitert oder neu hinzugefügt.

Die wohl größte Neuerung ist, dass Spirit2 nun über drei neue Toplevel-Namespaces verfügt:

Auf die Details zu diesen Modulen gehe ich später noch genauer ein.

2 Drei Beispiele für lex, qi & karma

Um einen Überblick über die neuen Bereiche in Spirit zu bekommen, ist es am besten, sich einige Beispiele selbst anzuschauen.
Leider gibt es noch keine Onlinedokumentation oder ähnliches, aus dem man mehr Informationen beziehen kann.
Aber es gibt die Möglichkeit, im Example-Verzeichnis zu lesen.

2.1 spirit::lex

Lex ist der neue Bereich für Lexer in Spirit. Es gibt die Möglichkeit, auch andere Lexer in Spirit zu verwenden, als den Standardlexer von Spirit. Lex dient dazu, den Zeichenstrom in Tokens aufzuteilen, sodass die eigentlichen Regeln des Parsers auf den Token des Lexers und nicht mit dem Eingabestrom arbeitet. Dies ist allerdings optional, es besteht in Spirit2.0 kein Zwang, einen Lexer zu benutzen. Allerdings ist dieser Bereich gerade im Umbruch, da einige Anregungen von der BoostCon im Frühjahr umgesetzt werden. Daher belasse ich es auch bei einem kurzen Lexerbeispiel, später wird es wahrscheinlich einen eigenständigen Artikel über die Möglichkeiten eines Lexers in Spirit2 geben.


Ein kleines Beispiel für die Definition eines Lexers in Spirit2.0:
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename Lexer>
struct example1_tokens : lexer_def<Lexer> // lexer_def<Lexer> ist die Basisklasse für Lexer in Spirit2.0
{
    template <typename Self>
    void def (Self& self)
    {
        // define tokens and associate them with the lexer
        identifier = "[a-zA-Z_][a-zA-Z0-9_]*";
        self = token_def<>(',') | '{' | '}' | identifier;
       
        // any token definition to be used as the skip parser during parsing
        // has to be associated with a separate lexer state (here 'WS')
        white_space = "[ \\t\\n]+";
        self("WS") = white_space;
    }
    token_def<> identifier, white_space;
};

Von oben nach unten:
Als erstes wird von lexer_def<Lexer> eine Lexerklasse abgeleitet. "lexer_def<Lexer>" stellt die Basisklasse für Lexer in Spirit2.0 dar. Danach wird eine Templatemethode für die Definition der Lexerregeln erstellt. Self ist hierbei die Startregel des Lexers. Vorher wird die Tokenregel für identifier definiert, welches wie man hier sieht auch als Regular Expression geht. Die Definition von Self ist dann wieder (fast) Spirittypisch: eine Verkettung von verschiedenen Regeln.
Die Definition des Skipparsers erfolgt darunter, wieder mit einer RegEx. Damit diese Regel als Skipparser aktiv wird, muss sie mit dem Lexerstatus "WS" verbunden werden. Skipparser bedeutet, dass diese Zeichen im Zeichenstrom bei der Tokengenerierung ignoriert/übersprungen werden.

2.2 spirit::qi

Mit spirit::qi und spirit::karma gibt es nun auch einen eigenständigen Bereich für die Textverarbeitung (parsen), wobei sich spirit::qi um den Input in der Textverarbeitung kümmert. Es gibt einige Veränderungen in diesem Bereich, der quasi auf die Erfahrungen von Spirit1.x aufsetzt. So haben sich die Grammatiken verändert und einige Operatoren sind neu, sowie eine neue Möglichkeit für die Fehlerbehandlung.

2.2.1 Regeldefinitionen

So gibt es nun mehrere Möglichkeiten, die Regel zum Einlesen einer CSV-Liste zu definieren:
C++:
double_ >> *(',' >> double_)

Dies ist schon einmal die "Standardregel", mit der man eine solche Aufgabe lösen könnte. Es gibt für Datentypen vordefinierte Regeln, hier double_. (Es gibt auch int_,char_, etc.) Jedoch speichert diese Regel noch keine Daten. Wenn wir die Werte in einen vector<double> ablegen wollen, sieht dies so aus:
C++:
using boost::spirit::fusion::push_back;
double_[push_back(v,_1)] >> *( ',' >> double_[push_back(v,_1)])

Hier ist push_back eine Funktion aus Fusion, welche das Ergebnis der double_-Regel in den Vector v einfügt. Die Klammern [] stellen wie in Spirit1.x den Block für die semantic Action. _1 ist ein Platzhalter für den Rückgabewert der angewendeten Regel.
Wie in Spirit1.x gibt es auch in Spirit2 einen Listoperator, der solche Konstrukte verkürzt, und performanter ist als obige Regel:
C++:
double_[push_back(v,_1)] % ','

Diese Regel macht dasselbe wie die Regel oben, jedoch in einer verkürzten Schreibweise.
Spirit2 erlaubt es, für bestimmte Regeln Defaulttypen anzugeben, bzw. definiert für bestimmte Regeln schon Defaulttypen. Bei % ist dies ein std::vector + der Defaulttyp der vorranstehenden Regel (hier also ein std::vector<double>). Somit lässt sich nun auch ohne Fusion der Vector füllen, indem man beim Aufruf der Parsingfunktion entsprechend den Vector v übergibt:
C++:
bool r = phrase_parse(first, last,( double_ % ',' ),v, space);


2.2.2 Grammatiken

Wie schon in Spirit1.x gibt es auch in Spirit2 die Möglichkeit, Regeldefinitionen in Grammatiken zusammenzufassen. Die Syntax dieser Grammatiken hat sich jedoch geändert. Während in Spirit1.x noch verschachteltes Definition Struct existierte, so erfolgt jetzt die Definition der Regeln in dem eigentlichen Grammatikkonstruktor.

Ein Beispiel für Spirit2-Grammatikklassen:
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename Iterator>
struct roman : grammar_def<Iterator, unsigned()>
{
    roman()
    {
        start
            =   +char_('M') [_val += 1000]
            ||  hundreds    [_val += _1]
            ||  tens        [_val += _1]
            ||  ones        [_val += _1];
 
        //  Note the use of the || operator. The expression
        //  a || b reads match a or b and in sequence. Try
        //  defining the roman numerals grammar in YACC or
        //  PCCTS. Spirit rules! :-)
    }
 
    rule<Iterator, unsigned()> start;
};

Die Grammatik wird als Template realisiert, damit sie auf unterschiedlichen Iteratoren anwendbar ist. Sie wird von einer entsprechenden Basisklasse (grammar_def<>) abgeleitet. Die beiden Parameter sind zum einen die Weiterleitung des Iteratortypen, und zum anderen die Definition des Defaulttypen dieser Grammatik. Es gibt noch zwei weitere, hier nicht sichtbare Parameter. Der 3. Parameter dient zur Definition sogenannter locals, also lokal gültiger Variablen innerhalb der Grammatik (locals<int,double,char>, angesprochen über _a,_b bzw. _c.). Der 4. Parameter dient zur Definition eines gültigen Skipparsers.
Im Konstruktor wird nun die Startregel definiert, wobei start die "default"-Startregel ist. Dies lässt sich ändern, in dem man die Startregel als 2. Parameter im Grammarkonstruktoraufruf einsetzt. Der ||-Operator stellt in Spirit ein sequenzielles Oder dar, sodasshier jede Regel ausgewertet wird, wenn sie erfolgreich angewendet wird, oder bei keinem Match die darauffolgende Regel. _val stellt den Defaultwert der Grammatik dar, quasi ihren Rückgabewert. Dieser wird hier einfach mit dem Ergebnis der Regel addiert. Die Grammatik soll so eine römische in eine arabische Zahl konvertieren. Am Ende wird dann noch die Startregel definiert. Richtig, es fehlt die Definition der anderen Regeln. Wie man die Regeln eines Lexers in Spirit auch in einer Grammatik verwenden kann, so ist es möglich auch andere Elemente als Regeln zu verwenden. Hier sind dies Symboltabellen, in dem Symbole aus dem Eingabestrom mit festen Werten verbunden werden.

Und so sieht dann eine Symboltabelle in Spirit2 aus:
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct ones_ : symbols<char, unsigned>
{
    ones_()
    {
        add
            ("I"    , 1)
            ("II"   , 2)
            ("III"  , 3)
            ("IV"   , 4)
            ("V"    , 5)
            ("VI"   , 6)
            ("VII"  , 7)
            ("VIII" , 8)
            ("IX"   , 9)
        ;
    }
 
} ones;


Auch hier wird ein Struct definiert, aber diesmal von symbols abgeleitet, mit den Typen char und unsingend. Welche die "Spalten" in der Tabelle darstellen, das heißt, es wird ein oder mehrere chars aus dem Input mit einem unsigned-Wert verknüpft. Im Konstruktor wird nun mit der Funktion add die Tabelle mit Symbolen gefüllt, welche dann später bei der Regelanwendung mit dem Eingabestrom verglichen werden, wobei das Symbol bevorzugt wird, was den meisten Input abdeckt (siehe "I,II,III").

2.3 spirit::karma

Dieser Namensraum ist neu. Es handelt sich hier um das Gegenstück zu spirit::qi und ist für die Ausgabe von Daten in einen Ausgabestrom zuständig. Karma nutzt hierfür den <<-Operator, analog zu qi, welches den >>-Operator für die Inputsequenz benutzt.
Karma ist daher auch vom Aufbau recht ähnlich zu qi, nur dass es keine Inputregeln, sondern Ausgaberegeln definiert. So könnte man mit spirit::karma z.B. XML ausgeben, welches man vorher mit spirit::qi eingelesen hat. Somit hätte man die Möglichkeit einen XML-Filter/Transformator zu schreiben:

C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template <typename OutputIterator>
struct mini_xml_generator
  : boost::spirit::karma::grammar_def<OutputIterator, void(mini_xml), space_type>
{
    mini_xml_generator()
    {
             text = verbatim[lit(text._r1)];
             node = (xml | text)[_1 = node._r1];
 
             start_tag =
                     '<'
                 <<  verbatim[lit(start_tag._r1)]
                 <<  '>'
             ;
 
             end_tag =
                     "</"
                 <<  verbatim[lit(end_tag._r1)]
                 <<  '>'
             ;
 
         xml =
                 start_tag(at_c<0>(xml._1))
                 <<  (*node)[ref(at_c<1>(xml._1))]
             <<  end_tag(at_c<0>(xml._1))
        ;
    }
 
    karma::rule<OutputIterator, void(mini_xml), space_type> xml;
    karma::rule<OutputIterator, void(mini_xml_node), space_type> node;
    karma::rule<OutputIterator, void(std::string), space_type> text;
    karma::rule<OutputIterator, void(std::string), space_type> start_tag;
    karma::rule<OutputIterator, void(std::string), space_type> end_tag;
};


Auch hier wird die Ausgabeklasse von einer entsprechenden Basisklasse abgeleitet. Ebenfalls werden ähnliche Regeln wie in der qi-Grammatik angewandt. Die Direktive verbatim ist das Gegenstück zu lexeme in qi, verbatim stellt sicher, dass keine zusätzlichen Trennzeichen in den Text eingefügt werden. Die korrekten Werte für die Ausgabe werden von der Hauptregel xml dann auch an die eingehängten Regeln wie z.B. start_tag weitergereicht. Mit Regelname._r1 greift man jeweils auf diesen Wert zu.

3 Infos zu Spirit2

Spirit2 wurde in diesem Frühjahr auf der Boostkonferenz in Aspen, Colorado vorgestellt. Es ist soweit lauffähig und einsatzbereit. Allerdings gibt es noch keine fertige Dokumentation, wie wir sie z.B. von Spirit1.x kennen, aber die aktuelle Version gibt es hier Es existiert ein SVN-Verzeichnis, welches auch Examples und einige Präsentationen enthält. Daran habe ich mich auch für meinen Vortrag auf dem Treffen und diesen Artikel orientiert. Wer nicht die Möglichkeit hat, Spirit2 aus dem SVN-Verzeichnis zu beziehen, kann sich hier auch den Snapshot von der Boostkonferenz herunterladen.
Spirit2 hat einige Abhängigkeiten zum aktuellen cvs::HEAD von Boost, somit benötigt man einen aktuellen Checkout von Boost um Spirit2 zu kompilieren. Dabei geht man so vor, dass man in einem Verzeichnis den aktuellen Checkout und in einem anderen Spirit liegen hat, bei den Pfadangaben des Compilers/der IDE muss man nun dafür sorgen, dass der Compiler zuerst das Spirit2-Verzeichnis findet, und dann erst das boost-Verzeichnis.
Wie sein Vorgänger benötigt Spirit2 einen recht standardkonformen Compiler, wie zum Beispiel gcc3.3.x, VC ab VC7.1 oder Intel9.x, wobei Intel recht hohe Übersetzungszeiten für Spiritprogramme hat.

Sie können Kommentare zu diesem Artikel im Forum schreiben. (Eine Registrierung ist nicht notwendig.)

Logo-Design: MastaMind Webdesign