Spirit (Parser)

Spirit i​st ein mittels Templatemetaprogrammierung implementierter rekursiv absteigender Parsergenerator. Die Benutzung d​er erweiterten Backus-Naur-Form (EBNF) i​n C++ w​ird mithilfe v​on Ausdrucks-Templates ermöglicht. Die Parser-Objekte werden d​urch Überladen v​on Operatoren erstellt u​nd ergeben e​inen LL-Parser, d​er in d​er Lage ist, mehrdeutige Ausdrücke auszuwerten.

Spirit k​ann zusammen u​nd getrennt für lexikalische Analyse s​owie auch für einfaches Parsen benutzt werden.

Der Spirit-Parser i​st Bestandteil d​er freien Boost-Bibliothek.

Operatoren

Aufgrund v​on Beschränkungen seitens d​er Programmiersprache C++ w​urde die Spirit-Syntax u​m die Operatoren-Rangfolge aufgebaut, w​obei Ähnlichkeiten z​u EBNF s​owie regulären Ausdrücken erhalten bleiben.

Syntax	Erläuterung
x >> y	Entspricht x gefolgt von y.
*x	Entspricht x null oder mindestens einmal. (Repräsentiert die kleenesche Hülle; C++ hat keinen unären Postfix-Operator *)
y	Entspricht x oder y.
+x	Entspricht x mindestens einmal.
-x	Entspricht x null oder einmal.
x & y	Entspricht x und y.
x - y	Entspricht x, aber nicht y.
x ^ y	Entspricht x, y oder beiden zusammen (in beliebiger Reihenfolge).
x [ function_expression ]	Ruft die Funktion (oder den Funktor) auf, die (oder der) function_expression zurückgibt, wenn x wahr ist.
( x )	Entspricht x (kann für Rangfolgen-Gruppierungen benutzt werden)
x % y	Entspricht eine oder mehrere Wiederholungen von x, getrennt durch Vorkommnisse von y.
~x	Entspricht allem außer x (nur mit Zeichenklassen wie ch_p oder alnum_p)

Beispiel

Spirit.Classic

#include <boost/spirit.hpp>
#include <boost/spirit/actor.hpp>
#include <string>
#include <iostream>

using namespace std;
using namespace boost::spirit;

int main()
{
    string input;

    cout << "Gib eine Zeile ein.\n";
    getline(cin, input);

    cout << "Eingabe: '" << input << "'.\n";

    unsigned count = 0;

 /*
    Die nächste Zeile parst die Eingabe (input.c_str())
    mittels folgender Semantik
        (Einrückung entspricht dem Quellcode zwecks Übersichtlichkeit):

     Null oder mehr Vorkommnisse von (
          Buchstabenfolge "Katze" (wenn wahr, erhöhe Zählvariable "count")
      oder jedes anderen Zeichens (fortschreiten, um nächstes Vorkommnis von "Katze" zu finden)
     )
 */
     parse(input.c_str(),
        *( str_p("Katze") [ increment_a(count) ]
          | anychar_p
         ));
 /*
     Der Parser wird mithilfe von Operatorüberladungen und
     Template-Matching gebaut, d.h. die eigentliche
     Arbeit wird in spirit::parse() erledigt und der Ausdruck,
     der mit * anfängt, initialisiert lediglich das Regelwerk,
     das die Parser-Funktion benutzt.
  */

    // Zeige schließlich das Ergebnis.
    cout << "Die Eingabe hatte " << count
              << " Vorkommnisse von 'Katze'\n";
}

Es g​ibt andere Algorithmen, d​ie zum Durchsuchen v​on Zeichenketten besser geeignet sind. Dieses Beispiel i​st nur z​ur Veranschaulichung d​es Konzepts gedacht, w​ie Regeln erstellt u​nd diesen Aktionen zugewiesen werden.

Spirit 2.x

Das folgende Programm gibt für Eingabestrings (gegeben als Kommandozeilenargument) "OKAY" aus, wenn sie der Regel ${\displaystyle \left\{a^{n}b^{n}\mid n\in \mathbb {N} _{0}\right\}}$ entsprechen, andernfalls "NOT OKAY":

#include <boost/spirit/include/qi.hpp>
#include <string>
#include <iostream>

// shortcuts
namespace qi = boost::spirit::qi;
typedef qi::rule<std::string::const_iterator, std::string()> Rule;

Rule ab0;
Rule ab;

int main(int argc, char** argv)
{
    Rule ab_alias = ab0.alias();
    ab0 = qi::char_('a') >> -ab_alias >> qi::char_('b');
    ab = (ab0 | qi::eps) >> qi::eoi;

    const std::string input = argc>1 ? argv[1] : "" target="_blank" rel="nofollow";
    auto begin = input.begin();
    bool okay = qi::parse(begin, input.end(), ab );
    
    std::cout << "String \"" << input << "\" is " << (okay ? "OKAY" : "NOT OKAY") << ".\n";
    return okay != true;
}

Weblinks

• Spirit bei Sourceforge