Spirit (Parser)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Spirit ist ein mittels Templatemetaprogrammierung implementierter rekursiv absteigender Parsergenerator. Die Benutzung der erweiterten Backus-Naur-Form (EBNF) in C++ wird mithilfe von Ausdrucks-Templates ermöglicht. Die Parser-Objekte werden durch Überladen von Operatoren erstellt und ergeben einen LL-Parser, der in der Lage ist, mehrdeutige Ausdrücke auszuwerten.

Spirit kann zusammen und getrennt für lexikalische Analyse sowie auch für einfaches Parsen benutzt werden.

Der Spirit-Parser ist Bestandteil der freien Boost-Bibliothek.

Aufgrund von Beschränkungen seitens der Programmiersprache C++ wurde die Spirit-Syntax um die Operatoren-Rangfolge aufgebaut, wobei Ähnlichkeiten zu EBNF sowie 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 *)
x | 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 [ Funktionsausdruck ] 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)
#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 gibt andere Algorithmen, die zum Durchsuchen von Zeichenketten besser geeignet sind. Dieses Beispiel ist nur zur Veranschaulichung des Konzepts gedacht, wie Regeln erstellt und diesen Aktionen zugewiesen werden.

Das folgende Programm gibt für Eingabestrings (gegeben als Kommandozeilenargument) "OKAY" aus, wenn sie der Regel 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] : "";
    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;
}