Die erste Programmiersprache, die ich in diesem Zusammenhang angegangen habe, ist Python. Fuer Python existiert mit PLY ein einfacher aber dennoch leistungsfaehiger Parser Generator, der gegenueber dem C++-Pendant boost::spirit auf die Vorteile einer dynamischen Sprache zurueckgreifen kann. Bereits nach 15 Minuten hatte ich einen funktionsfaehigen Lexer implementiert, der mir einen Tokenstream fuer das Konfigurationsformat lieferte. Nach weiteren 20 Minuten war auch der Parser fertiggestellt. Das zeigt, dass PLY viel besser als boost::spirit fuer Rapid Prototyping geeignet ist, zumal auch das Testen von Lexer und Parser dank schneller Instanziierung im Python Interpreter zuegig von der Hand geht.

In diesem Artikel moechte ich kurz anreissen, wie sich ein Parser fuer unser Konfigurationsformat (siehe vorangegangene Artikel) mit PLY implementieren laesst. Details sollen diesmal aussen vor bleiben, dazu verweise ich auf den Sourcecode, der am Ende des zweiten Teils verlinkt ist. Fuer ein erstes Experimentieren mit PLY sollten die Ausfuehrungen jedoch ausreichend sein, zumal Python mit seinem Interpreter eine ideale Testumgebung bietet.

Um den zu parsenden String in einzelne Tokens zu zerlegen, benoetigen wir einen Lexer. Dieser muss sowohl Keywords (in unserem Fall sind das ‘true’ und ‘false’), einzelne Zeichen (Klammern, Semikolon, Komma und ‘=’) sowie die atomaren Datentypen (double, long und string) erkennen koennen. Im Gegensatz zu boost::spirit koennen wir in PLY direkt regulaere Ausdruecke verwenden, um die einzelnen Token zu spezifizieren. Diese fassen wir geeigneterweise in einer Klasse zusammen (auch alle folgenden Codesegmente sollen als Member dieser Klasse angelegt werden). Zunaechst definieren wir eine Liste ‘tokens’ (der Name ist vorgegeben), die die (frei waehlbaren) Namen der Tokens enthaelt.

class CfgLexer(object):
  keywords = ('TRUE', 'FALSE')
  tokens = keywords + (
    'LPAREN', 'RPAREN',
    'LBRACKET', 'RBRACKET',
    'LBRACE', 'RBRACE',
    'COMMA',
    'EQUALS',
    'SEMICOLON',
    'LITERAL',
    'DOUBLE',
    'LONG',
    'STRING_LITERAL'
  )

Fuer die beiden Keywords ‘TRUE’ und ‘FALSE’ habe ich zudem eine separate Liste angelegt; der Grund dafuer ist, dass fuer die Keywords beim Parsen nicht zwischen Gross- und Kleinschreibung unterschieden werden soll und diese deshalb spaeter gesondert behandelt werden muessen.

Um die Tokens festzulegen, fuegen wir der Klasse nun regulaere Ausdruecke fuer jedes der Tokens hinzu und weisen diese jeweils einer Variablen ‘t_TOKENNAME’ hinzu, also folgendermassen:

t_LPAREN = "\("
t_RPAREN = "\)"
t_LBRACKET = "\["
t_RBRACKET = "\]"
t_LBRACE = "\{"
t_RBRACE = "\}"
t_COMMA = ","
t_EQUALS = "="
t_SEMICOLON = ";"

Beachten Sie, dass die Klammern escaped werden muessen, da es sich bei den Strings um regulaere Ausdruecke handelt, und die Klammern sonst als Steuerzeichen interpretiert werden.

Fuer die uebrigen Tokens reicht ein einfaches Matching nicht aus, wir muessen ausserdem Aktionen verknuepfen, die bei einem erfolgreichen Match ausgefuehrt werden. Dazu koennen wir wie zuvor eine Variable mit einem regulaeren Ausdruck definieren und diese anschliessend an eine Funktion binden:

literal = "[a-zA-Z_][0-9a-zA-Z]*"
 
@TOKEN(literal)
def t_LITERAL(self, t):
  t.type = self.keyword_map.get(t.value.lower(), "LITERAL")
  return t

Nach einem erfolgreichen Match des regulaeren Ausdrucks suchen wir also zuerst in einer Keyword Map, ob wir ein passendes Keyword finden (beachten Sie die lowercase Transformation!) und verwenden dieses fuer den Typ des Tokens, ansonsten weisen wir den Typ ‘LITERAL’ zu. Die Keyword Map definieren wir wie folgt:

keyword_map = {}
for k in keywords:
  keyword_map[k.lower()] = k

Auch fuer die uebrigen Tokens muessen wir Funktionen definieren:

string_literal = r'"[^"\n]*"' + '|' + r"'[^'\n]*'"
double_constant = r"\-?([1-9]\d* | 0)\.\d*"
long_constant = r"\-?[1-9]\d* | 0"
 
@TOKEN(string_literal)
def t_STRING_LITERAL(self, t):
  t.type = "STRING_LITERAL"
  t.value = t.value.strip("\"'")
  return t
 
@TOKEN(double_constant)
def t_DOUBLE(self, t):
  t.type = "DOUBLE"
  t.value = float(t.value)
  return t
 
@TOKEN(long_constant)
def t_LONG(self, t):
  t.type = "LONG"
  t.value = int(t.value)

Bei den String Literals entfernen wir die Anfuehrungszeichen am Anfang und Ende, waehrend wir die value Felder der ‘DOUBLE’ und ‘LONG’ Tokens in den jeweiligen Datentyp konvertieren. Es fehlt nun nur noch ein Skip Parser, der den insignifikanten Whitespace ueberspringt (d.h. kein Token dafuer anlegt). Dazu weisen wir einen String mit zu ignorierenden Zeichen der (reservierten) Variablen t_ignore zu:

t_ignore = " \t"

Wir ueberspringen damit sowohl Leerzeichen als auch Tabs. Was geschieht aber mit den Linefeeds? Diese beduerfen wieder einer Sonderbehandlung:

def t_newline(self, t):
  r'\n+'
  t.lexer.lineno += len(t.value)

Hier missbrauchen wir den Docstring, um den regulaeren Ausdruck unterzubringen (der Lexer interpretiert diesen automatisch als die zu verwendende Regular Expression) und addieren anschliessend die Anzahl der gematchten Linefeeds zur Variablen t.lexer.lineno, um in den Fehlermeldungen auch die richtige Zeilennummer des fehlerhaften Tokens ausgeben zu koennen.

Wie wird nun ein solches Lexer Objekt erzeugt und auf die gelexten Tokens zugegriffen? Dazu definieren wir noch drei weitere Funktionen:

def build(self):
  self.lexer = ply.lex.lex(object=self)
 
def input(self, text):
  self.lexer.input(text)
 
def token(self):
  t = self.lexer.token()
  return t

Nachdem wir noch die Import Statements “import ply.lex” und “from ply.lex import TOKEN” hinzugefuegt haben, koennen wir den Lexer bereits testen. Wir starten eine Python Konsole und importieren das Modul (das wir beispielsweise als cfg_lexer.py) gespeichert haben:

>>> import cfg_lexer
>>> lexer = cfg_lexer.CfgLexer()
>>> lexer.build()
>>> lexer.input("a=5; b=(1,2,"Hallo"); c = { test = "test"; hallo = "welt"; };")
>>> lexer.token()
LexToken(LITERAL,'a',1,0)
>>> lexer.token()
LexToken(EQUALS,'=',1,1)
>>> lexer.token()
LexToken(LONG,5,1,2)
[...]


Wie funktioniert das ganze nun ueberhaupt? Eine solch lose Zusammenstellung von Funktionen in einer Klasse kann doch unmoeglich einen funktionsfaehigen Lexer darstellen! Der Trick ist, dass PLY die Liste der Tokens benutzt, um dynamisch die passenden Variablen bzw. Funktionen mit den regulaeren Ausdruecken in der Klasse zu suchen. Daraus wird on-the-fly Python Code fuer das Lexing generiert. Damit wird auch klar, warum die Benennung der Member unserer CfgLexer Klasse wichtig ist. Werden sie falsch bezeichnet, so findet PLY waehrend dem build() Prozess die regulaeren Ausdruecke bzw. semantischen Aktionen nicht und kann den Lexer nicht erstellen. Die Fehlermeldungen sind aber in diesem Fall deutlich besser verstaendlich als die C++ Templateerrors, die einen bei der Parserentwicklung mit boost::spirit erwarten.

Im naechsten Teil werden wir unseren Lexer als Tokenfeed benutzen und darauf aufbauend einen Parser implementieren.

Warum benutzen wir nicht einfach den von Spirit automatisch generierten Baum? Wir koennten den Parser bereits im jetzigen Zustand (siehe Ende des Teils 2b) benutzen und den von Spirit generierten Objektbaum im aeusseren Attribut verwenden, um nachtraeglich den von uns gewuenschten Baum aus element Objekten aufzubauen. Betrachten wir jedoch einmal beispielsweise den Typ des automatisch generierten Attributs der Regel array, die wie folgt definiert war:

arrayDefinition
  =  lit('[')
  >> -( double_ % ','
      | long_ % ','
      | bool_ % ','
      | string % ','
      )
  >  ']'
  ;

Diese Regel generiert ein Attribut vom Typ

optional<
  variant<
    vector<double>,
    vector<long>,
    vector<bool>,
    vector<string>
  >
>

Die array Regel wird in listDefinition und variableAssignment verwendet, die ebenfalls ein variant generieren, welches wiederum das oben gezeigte variant der arrayDefinition in seiner Typenliste enthaelt usw. Wir wuerden fuer die aeussere Regel also ein Attribut erhalten, dessen Typdefinition so lang und verschachtelt ist, dass niemand ernsthaft darueber nachdenken wuerde, damit ueberhaupt eine Auswertung zu versuchen. Wir muessen also eine Loesung finden, uns von der statischen Typisierung zu loesen. Unsere element Klassenhierarchie ist dazu bestens geeignet und soll daher anstelle des automatisch generierten Baums verwendet werden.

Spirit ist eine DSEL (Domain Specific Embedded Language), die auf dem Sprachraum von C++ definiert ist. Dies bringt einige Nachteile mit sich, die insbesondere bei der Implementierung der semantischen Aktionen zum Tragen kommen. Da die Grammatik mitsamt der assoziierten semantischen Aktionen vom Compiler in ein Objekt uebersetzt wird, koennen wir fuer diese nicht einfach gewoehnlichen C++ Code benutzen, sondern muessen diesen wiederum in Objekte (Funktoren) kapseln, die dann zur Laufzeit ausgewertet werden koennen. Gluecklicherweise bietet boost::phoenix bereits eine Reihe von Funktoren an, die die meisten grundlegenden Operationen abdeckt (new, delete, Konstruktorenaufrufe, …).

Beginnen wir mit der atom Regel. Wir fuegen dieser eine semantische Aktion hinzu, die mit dem gesamten Ausdruck assoziiert sein soll (dazu klammern wir die Unterregeln einfach ein):

atom
  =  ( double_
     | long_
     | bool_
     | string
     ) [ _val = new_<cfg::atom>(_1) ]
  ;

Semantische Aktionen werden in eckige Klammern eingeschlossen und der Teilregel angehaengt, fuer die das Attribut verarbeitet werden soll. Der Typ des generierten Attributs fuer den gesamten Ausdruck

( double_ | long_ | bool_ | string )

ist

variant<double, long, bool, string>

Wir erinnern uns, dass wir in unserer Atom Klasse einen Konstruktor mit genau diesem Typ als Parameter definiert hatten. Normalerweise koennten wir dann ein Objekt vom Typ atom erzeugen, indem wir

new atom(generated_attribute)

schreiben. Fuer Spirit muessen wir dies allerdings in einen phoenix Ausdruck uebersetzen (new_ ist der phoenix Funktor fuer new).

Auf das generierte Attribut koennen wir ueber den Platzhalter _1 zugreifen. Den Zeiger auf das neu erzeugte atom Objekt weisen wir dem Platzhalter _val zu, der diesen als das generierte Attribut der gesamten Regel festlegt. Fassen wir noch einmal zusammen: Ohne die semantische Aktion wuerde die atom Regel ein Attribut vom Typ variant zurueckliefern, jedoch moechten wir stattdessen ein atom Objekt aus unserer Objekthierarchie zurueckgeben, und setzen dieses mittels Zuweisung an _val als das neue generierte Attribut.

Um das Attribut der Regel string (und literal) muessen wir uns nicht kuemmern, da Spirit automatisch ein std::string Attribut erzeugt, wenn wir std::string als Rueckgabewert der Regel festlegen (die Typen sind kompatibel, d.h. es existiert bereits eine Transformationsvorschrift, die das Attribut der Regel in einen String umwandeln kann – dies ist fuer benutzerdefinierte Typen natuerlich leider nie der Fall).

Betrachten wir als naechstes die listDefinition. Fuer diese muessen wir mehrere Aktionen verwenden. Zu Beginn der Regel muss ein neues Objekt vom Typ list (aus unserer Objekthierarchie) angelegt werden, das wir in _val zwischenspeichern. Fuer jede nun folgende groupDefinition, listDefinition, arrayDefinition oder atom muss das zugehoerige Attribut an das list Objekt angehaengt werden. Wir erinnern uns, dass wir dem list Objekt eine Funktion append(element*) gegeben hatten. Diese Funktion koennen wir allerdings in der semantischen Aktion nicht ohne weiteres verwenden, sondern muessen sie zunaechst in einen Struct kapseln:

struct append_impl
{
  template <typename C, typename Arg>
  struct result { typedef void type; };
 
  template <typename C, typename Arg>
  void operator()(C* c, const Arg& data) const
  { c->append(data); }
};
 
phoenix::function<append_impl> const append = append_impl();

Damit machen wir das struct append_impl zu einem Funktor, der unter dem Namen append zur Verfuegung steht. Die gesamte arrayDefinition Regel koennen wir dann folgendermassen schreiben:

arrayDefinition
  =  lit('[')     [_val = new_<cfg::list>()]
  >> -( double_   [append(_val, new_<cfg::atom>(_1))] % ','
      | long_     [append(_val, new_<cfg::atom>(_1))] % ','
      | bool_     [append(_val, new_<cfg::atom>(_1))] % ','
      | string    [append(_val, new_<cfg::atom>(_1))] % ','
      )
  >  ']'
  ;

Diese Folge von Aktionen erzeugt also zunaechst ein neues Objekt vom Typ list und ruft dann fuer jedes Auftreten von double, long, bool oder string Werten den append Funktor auf, der dem list Objekt (in _val) ein neues atom anfuegt, dass in-place erzeugt wird. Wer sich nun fragt, warum wir das append vier Mal geschrieben haben, statt es einfach einmal hinter dem geklammerten Ausdruck zu verwenden, der moege bitte den Listenoperator am Ende der Zeilen beachten. Dieser fuehrt, zusammen mit dem “-” Operator fuer einen optionalen Ausdruck zu einem generierten Attribut mit komplexem Typ (optional< variant<...> >, siehe Beginn des Artikels), fuer das wir sicherlich keine append Funktion haetten schreiben wollen. Dadurch, dass wir die semantischen Aktionen direkt mit den POD Typen assoziieren, koennen wir einfach den Konstruktor von atom benutzen, um ein zugehoeriges Objekt zu erzeugen und fuegen dieses direkt in die Liste ein.

Die Regel listDefinition wird aehnlich implementiert, jedoch muessen wir in diesem Fall kein neues atom erzeugen, sondern koennen das generierte Attribut der Unterregel an den append Aufruf durchschleifen. Die genaue Implementierung ist dem vollstaendigen Sourcecode zu entnehmen.

Kommen wir zur groupDefinition: Hier muessen wir natuerlich zunaechst ein group Objekt erzeugen (wozu wir die lit Regel missbrauchen), und anschliessend saemtliche enthaltenen variableAssignments einfuegen. Hierbei habe ich mich fuer eine etwas andere Loesung entschieden, die ein vererbtes Attribut benutzt. Das bedeutet, dass eine Referenz auf eine lokale Variable an eine Subregel uebergeben wird, die das vererbte Attribut verwenden und ggf. auch modifizieren kann:

groupDefinition
  =  lit('{') [_val = new_<cfg::group>()]
  >> *( variableAssignment(_val) )
  >  '}'
  ;

Das Einfuegen der variableAssignments geschieht also nicht in der Regel groupDefinition, sondern in variableAssignment selbst. Die Regel file kann analog implementiert werden, allerdings haben wir hier kein lit zur Verfuegung, an dass wir die Erzeugung des group Objekts anheften koennen und muessen deshalb eine Dummyregel (eps) verwenden, die keinerlei Auswirkung auf die Grammatik hat (siehe Sourcecode).

Die letzte Regel, die wir genauer analysieren wollen, ist variableAssignment. Diese bekommt das bereits erwaehnte vererbte Attribut uebergeben (dessen Platzhalter _r1 heisst), und sieht so aus:

variableAssignment
  =  literal            [_a = _1]
  >> '='
  >> ( groupDefinition  [insert(_r1, _a, _1)]
     | listDefinition   [insert(_r1, _a, _1)]
     | arrayDefinition  [insert(_r1, _a, _1)]
     | atom             [insert(_r1, _a, _1)]
     )
  >  ';'
  ;

Der Funktor insert wird dabei aehnlich wie append implementiert. Um den Namen der Variablen zwischenzuspeichern, benutzen wir eine lokale Variable vom Typ string, deren Platzhalter _a ist (weitere lokale Variablen wuerden _b, _c, usw. heissen). Der Typ von _a muss in der Deklaration der Regel angegeben werden (siehe Sourcecode).

Damit haben wir unseren Parser komplettiert und koennen nun noch eine Klasse cfg_file schreiben, die das Oeffnen der Datei und die Verwendung des Parsers kapselt. Der vollstaendige Code inklusive einem kleinen Testprogramm kann hier heruntergeladen werden:

cfg_file library v1.0 (cfg_file_1_0.tar.gz)

Ich hoffe Ihnen hat dieses kleine Tutorial gefallen. Fuer weitere Fragen und Kritik oder Anregungen stehe ich gerne zur Verfuegung.

• Interpretation eines element Objekts als group, list oder atom
• Zugriff auf die Child Elemente ueber Key (Gruppe) oder Index (Array und Liste)
• Konvertierung eines Leaf Elements in einen der unterstuetzten Typen
• Lookup eines Leaf Elements ueber Pfadangabe und optionalen Defaultwert

Der erste Punkt ist leicht zu realisieren. Wir schreiben drei Funktionen

const group& as_group() const { return dynamic_cast<const group&>(*this); }
const list& as_list() const { return dynamic_cast<const list&>(*this); }
const atom& as_atom() const { return dynamic_cast<const atom&>(*this); }

Der dynamic_cast mit einer Objektreferenz sorgt dafuer, dass automatisch eine Exception geworfen wird, wenn das Objekt nicht vom gewuenschten Typ ist. Dies sollte vom Benutzer abgefangen werden.

Auch der Zugriff auf einzelne Childelemente per Key oder Index stellt kein grosses Problem dar. Wir definieren die Indexoperatoren

const element& operator[](const std::string& key) const
{
  return this->as_group().get(key);
}
 
const element& operator[](size_t index) const
{
  return this->as_list().get(key);
}

Dabei setzen wir voraus, dass der Benutzer weiss, um welchen Typ es sich beim jeweiligen Element handelt und interpretieren es dementsprechend entweder als Gruppe oder Liste. Wird ein Operator auf einem ungeeigneten Datentyp aufgerufen, so werfen die as_group() bzw. as_list() Funktionen entsprechende Exceptions.

Falls es sich bei einem element Objekt um ein Leaf Element handelt, so muessen wir es in einen numerischen Typ oder String umwandeln koennen. Da wir bereits eine entsprechende Funktion in der atom Klasse definiert haben, koennen wir einfach durchschleifen:

template <typename T>
const T as() const
{
  return this->as_atom().as<T>();
}

Bleibt nur noch der Use Case des Wertelookups ueber eine Pfadangabe. Nehmen wir an, unsere Konfigurationsdatei sieht folgendermassen aus:

app = {
  windows = (
    {
      title = "Fenster 1";
      width = 400;
      height = 300;
    },
    {
      title = "Fenster 2";
      width = 600;
      heigh = 450;
    }
  );
};

Der Parser liefert uns ein Root Element, das wir r nennen wollen. Dann soll beispielsweise der Zugriff auf den height Wert des zweiten window Elements moeglich sein ueber

long height = r.lookup<long>("app.windows[1].height", 800);

wobei 800 der Defaultwert ist, wenn die Option nicht gefunden wurde. Weiterhin wollen wir die folgende Syntax erlauben:

long height = r["app.windows[1].height"].as<long>();

Dazu muessen wir spaeter den bereits oben definierten operator[] geeignet anpassen. Implementieren wir aber zunaechst die lookup() Funktion:

typedef std::deque<boost::variant<std::string, unsigned int> > token_list;
 
template <typename T>
const T lookup(const std::string& path) const
{
  token_list tokens = util::split(path);
  return recursive_lookup(*this, tokens).as<T>();
}
 
template <typename T>
const element& recursive_lookup(const element& e, token_list tokens) const
{
  if(tokens.empty())
    return e;
 
  boost::variant<std::string, unsigned int> t = tokens.front();
  tokens.pop_front();
 
  const element& next(boost::apply_visitor(visitor(e), t));
  return recursive_lookup(next, tokens);
}

Wir splitten hier zunaechst den Pfadstring in eine Liste von Tokens, die den einzelnen Zugriffsbezeichnern entspricht (in unserem Beispiel also ["app", "windows", 1, "height"]). Anschliessend rufen wir die Funktion recursive_lookup() mit dem aktuellen Element als Ausgangspunkt auf, die rekursiv durch den Baum traversiert und das letzte Element zurueckliefert, das schliesslich als atom interpretiert und in den gewuenschten Typ konvertiert wird. Die Implementierung der Funktion split sowie der Fall mit Defaultwert ist dem vollstaendigen Quellcode zu entnehmen.

Passen wir abschliessend noch den operator[] an, um den gleichen Lookup Mechanismus auch in der Indexschreibweise zu ermoeglichen:

const element& operator[](const std::string& key) const
{
  if(key.find_first_of('.') != std::string::npos)
  {
    token_list tokens = util::split(key);
    return recursive_lookup(*this, tokens);
  }
  else
    return this->as_group().get(key);
}

Damit haben wir nun alle folgenden (aequivalenten) Abfragemoeglichkeiten abgedeckt:

std::string title = r["app.windows[0].title"].as<std::string>();
std::string title = r["app"]["windows"][0]["title"].as<std::string>();
std::string title = r.lookup<std::string>("app.windows[0].title");

Mit Hilfe der im letzten Teil definierten Iteratoren koennen wir nun zum Beispiel auch ueber alle windows Elemente loopen und deren Eigenschaften ausgeben:

const cfg::list& windows = r["app.windows"].as_list();
cfg::list::const_iterator it1 = windows.begin();
for(; it1 != windows.end(); ++it1)
{
  const cfg::group& properties = it1->as_group();
  cfg::group::const_iterator it2 = properties.begin();
  for(; it2 != properties.end(); ++it2)
  {
    std::cout << it2->first << ": "
      << it2->second->as<std::string>() << std::endl;
  }
}

Die somit definierte Klassenstruktur ermoeglicht einen einfachen und effizienten Zugriff auf die Konfigurationsdaten, ist aber gleichzeitig noch ausreichend performant, um eine schnelle Erzeugung der Baumstruktur vom Parser aus zu gewaehrleisten. Die vollstaendige Implementierung kann hier heruntergeladen werden.

Im naechsten und letzten Teil der Serie vervollstaendigen wir endlich unsere kleine Parser Bibliothek, indem wir semantische Aktionen zum Parser hinzufuegen, um den Parsetree zu erzeugen.

Es gibt dabei prinzipiell mehrere Moeglichkeiten, wie vorgegangen werden kann. Meine erste Idee war, einen Baum aus polymorphen Objekten aufzubauen, der verschiedene Objekttypen fuer alle einzelnen Elemente der Konfigurationsstruktur enthaelt. Dies waere zwar fuer die Erstellung der Speicherstruktur durch den Parser am geeignetsten gewesen, haette jedoch den Benutzerzugriff auf die Daten unnoetig erschwert. In einem weiteren Prototyp waehlte ich als Datenstruktur einen monomorphen Baum aus nur einem einzigen Klassentyp, was allerdings Probleme bei der Abbildung der Hierarchie und der spaeteren Auswertung mit sich brachte.

Ich entschied mich daher fuer einen Kompromiss aus beiden Ansaetzen, bei dem ich die funktional gleichen Objekttypen zusammenfasse und in einen polymorphen Baum ueberfuehre. Intern wird dabei in Baum aus Zeigern erstellt (um eine hohe Performance zu gewaehrleisten), das externe Interface arbeitet jedoch ausschliesslich mit Objektreferenzen, so dass wir auch mit ueberladenen Operatoren arbeiten koennen.

Alle Konfigurationselemente erben gemeinsam von einer Klasse element, die wir zunaechst als leer definieren:

class element { };

Wir werden erst spaeter Funktionalitaet zu element hinzufuegen, wenn wir das externe Interface definieren.

Im naechsten Schritt muessen wir die hierarchiegenerierenden Elemente auf Klassen abbilden. Unser Format erlaubt Gruppen, Listen und Arrays. Listen und Arrays haben das gleiche Interface, sie unterscheiden sich lediglich in den zugelassenen Typen ihrer Subelemente. Da wir fuer dieses Tutorial keine Ruecktransformation unserer Objekthierarchie in eine Konfigurationsdatei benoetigen, koennen wir Liste und Array als gleichwertig betrachten und in einen Typ (list) zusammenfassen. Die Gruppe unterscheidet sich hingegen funktional von Liste und Array und wird deshalb getrennt abgebildet (group):

class group : public element
{
  void insert(const std::string& key, element* value)
  {
    std::string key_(key); settings_.insert(key_, value);
  }
 
  typedef boost::ptr_map<std::string, element> setting_map_t;
  setting_map_t settings_;
};
 
class list : public element
{
  void append(element* value) { settings_.push_back(value); }
 
  typedef boost::ptr_vector<element> setting_list_t;
  setting_list_t setting_;
};

Ich habe die insert bzw. append Funktionen absichtlich als private implementiert, da der Konfigurationsbaum fuer den Benutzer nicht modifizierbar sein soll. Den Parser werden wir spaeter als friend deklarieren.

Es fehlt nun nur noch eine Repraesentation der atomaren Elemente (Integer, Double, String und Bool). Wie bereits besprochen werden wir diese zu einer Klasse zusammenfassen:

class atom : public element
{
  explicit atom(const boost::variant<bool, long, double, std::string>& value) :
    value_(value)
  {}
 
  boost::variant<bool, long, double, std::string> value_;
};

Diese einfache Implementierung reicht bereits aus, um den Baum erzeugen zu koennen. Allerdings ist der Konfigurationsbaum recht nutzlos, wenn der Benutzer keine Moeglichkeit hat, diesen zu analysieren und einzelne Elemente zu extrahieren. Wir benoetigen also noch ein oeffentliches Interface, das uns eine Interaktion mit den Daten ermoeglicht.

Beginnen wir mit dem atom. Um auf den gekapselten Wert zugreifen zu koennen, koennten wir beispielsweise eine Funktion schreiben, die eine Kopie (oder konstante Referenz) des gespeicherten Variants zurueckgibt. Das hat jedoch den Nachteil, dass der Benutzer selbst boost::get aufrufen muss, um den Wert aus dem Variant zu extrahieren. Unser Ziel soll jedoch sein, die Verwendung der atom Klasse so transparent wie moeglich zu gestalten und die Implementierung nach aussen hin moeglichst zu verbergen. Daher fuegen wir besser der Klasse atom eine Funktion as() hinzu, die folgendermassen implementiert ist:

class atom : public element
{
  // ...
 
public:
  template <typename T>
  const T as() const
  {
    return boost::apply_visitor(atom_detail::visitor<T>(), value_);
  }
 
  // ...
};

Die Aufgabe des hier verwendeten Visitors ist nicht nur die Extraktion des gewuenschten Typs aus dem Variant, sondern gleichzeitig eine Konvertierung der zulaessigen Werte untereinander, um zum Beispiel einen Double Wert auch als String extrahieren zu koennen. Die Implementierung des Visitors ist etwas umfangreicher und nicht sonderlich interessant, daher verweise ich diesbezueglich auf den Quellcode, der im Teil 3b verlinkt ist.

Betrachten wir als naechstes die Klasse group. Sie benoetigt zum einen ein Interface, um ueber die Subelemente iterieren zu koennen, zum anderen eine Moeglichkeit, direkt das zugehoerige Element zu einem beliebigen Key extrahieren zu koennen. Beides ist einfach zu realisieren:

class group : public element
{
  // ...
 
public:  
  const element& get(const std::string& key) const
  {
    setting_map_t::const_iterator it = settings_.find(key);
    if(it == settings_.end())
      throw std::runtime_error("element not found");
    return *it->second;
  }
 
  typedef setting_map_t::const_iterator const_iterator;
  const_iterator begin() const { return settings_.begin(); }
  const_iterator end() const { return settings_.end(); }
 
  // ...
};

Fuer list implementieren wir die Iteratoren analog, statt der get Funktion mit einem String Key schreiben wir jedoch ein get mit Index:

class list : public element
{
  // ...
 
public:
  const element& get(size_t index) const { return settings_[index]; }
 
  // ...
};

Im naechsten Teil definieren wir das (umfangreichere) Interface fuer die Klasse element, die den zentralen Dreh- und Angelpunkt fuer den Zugriff auf die Konfigurationshierarchie darstellen wird.

arrayDefinition
   =      lit('[')
      >> -( double_ % ','
          | long_ % ','
          | bool_ % ','
          | string % ','
          )
      >  ']'
   ;

Gemaess unserer Syntaxspezifikation wird der Array durch eine oeffnende eckige Klammer eingeleitet, gefolgt von beliebig vielen kommagetrennten Werten vom Typ double, long, bool oder string. Die schliessende eckige Klammer darf nie fehlen, daher kann der Parser auch sofort abbrechen, wenn keines der inneren Elemente mehr matcht und kein “]” folgt. Dies wird durch das einzelne “>” erreicht. Der Prozent Operator hinter einer Regel (X % C) bedeutet so viel wie “ein oder mehrere Produktionen vom Typ X, jeweils getrennt durch das Token C”. Das “-” (das fuer “optional” steht) sorgt dafuer, dass auch leere Arrays erlaubt sind.

Diese Regel beinhaltet noch eine weitere Besonderheit, die vielleicht auf den ersten Blick nicht ganz offensichtlich ist. Haetten wir fuer den inneren Teil geschrieben

( double | long_ | bool_ | string) % ','

oder noch kuerzer

atom % ','

so haetten wir zwar (mehr oder weniger) Zeichen gespart, aber die Semantik dieser Regel waere nicht mehr dieselbe. Der Array ist so definiert, dass er nur Elemente ein und desselben Typs enthalten darf. Wenn das erste Element ein String ist, so muessen alle weiteren Elemente auch Strings sein. Diese Eigenschaft ist aber nur garantiert, wenn wir den Listenoperator auf jede Unterregel fuer sich anwenden und erst die daraus resultierenden Regeln verodern.

Die Regel fuer die Liste sieht sehr aehnlich aus, muss aber zusaetzlich Rekursion erlauben. Im Gegensatz zum Array darf sie ausserdem gleichzeitig Elemente unterschiedlicher Typen enthalten:

listDefinition
   =     lit('(')
      >> -( ( groupDefinition
            | listDefinition
            | arrayDefinition
            | atom
            ) % ','
          )
      >  ')'
   ;

Wie schon beim Array besprochen muss der Listenoperator bei der inneren Regel nun aussen stehen, um Listeneintraege unterschiedlichen Typs zuzulassen. Erlaubte Produktionen innerhalb der Liste sind die Array- und Gruppendefinition, die Listendefinition (Rekursion!) sowie Elemente vom Typ atom.

Die Gruppendefinition ist die letzte Produktion, die uns noch fehlt. Sie ist im Wesentlichen der Liste aehnlich, enthaelt aber nicht nur eine Menge von Objektdefinitionen sondern vielmehr eine Liste von Variablenzuweisungen und bildet damit die Semantik eines Dictionaries (Key-Value-Map) in unserem Konfigurationsformat ab:

groupDefinition
   =     lit('{')
      >> *variableAssignment
      >  '}'
   ;

Innerhalb der geschweiften Klammern erlauben wir also eine beliebige Anzahl von Produktionen vom Typ “variableAssignment”, die wir bereits im Teil 2a definiert hatten.

Im naechsten Teil der Serie werden wir eine Objektstruktur definieren, die es uns erlaubt, Konfigurationsdateien geeignet abzubilden. Dabei werden wir insbesondere Wert darauf legen, dass der Zugriff auf die Konfigurationswerte moeglichst einfach und flexibel ist.

Gewoehnliche Parsergeneratoren — wie zum Beispiel lex/yacc oder ANTLR — erwarten als Input eine Beschreibung der Syntax des zu parsenden Formats, die ueblicherweise in der Backus-Naur-Form (BNF) oder einer Erweiterung davon spezifiziert wird und die wir im Folgenden als Grammatik bezeichnen. Daraus erzeugt der Generator Code in der Zielsprache, der die Syntax analysiert und diese entweder in einen Syntaxbaum transformiert oder aber mit den Symbolen verknuepfte Aktionen ausfuehrt. Diese Separierung von Grammatik und generiertem Code hat den Vorteil, dass fuer verschiedene Zielsprachen ein und dieselbe Grammatik verwendet werden kann (sofern der Generator alle gewuenschten Zielsprachen unterstuetzt). Der Vorteil schmilzt jedoch dahin, sobald man semantische Aktionen verwenden will, da diese normalerweise bereits in der Grammatik angegeben werden und in der Zielsprache verfasst sein muessen.

Die boost Library bietet fuer C++ eine wesentlich bessere und elegantere Alternative: Den spirit Parser. Dieser verwendet Paradigmen des Template Metaprogramming, um eine Domain Specific Language auf dem C++ Syntaxraum zu definieren, die der BNF erstaunlich aehnlich ist. Was bedeutet das nun? Betrachten wir als Beispiel die Definition eines Symbols fuer ein if Konstrukt in der Sprache Pascal. In BNF wuerde man schreiben:

<if statement> ::= if <expression> then <statement> |
        if <expression> then <statement> else <statement>

Die verwendeten Symbole “expression” und “statement” werden als bereits definiert vorausgesetzt. Uebertragen wir diese Regel in boost::spirit, so erhalten wir

if_statement = "if" >> expression >> "then" >> statement
             | "if" >> expression >> "then" >> statement >> "else" >> statement;

Wir sehen, dass die Umsetzung der Grammatik in spirit fast eins zu eins der Backus Naur Form entspricht. Um den Syntaxregeln von C++ zu entsprechen, muessen wir allerdings die String Literale in Anfuehrungszeichen einschliessen und die einzelnen Elemente der Regel durch den Operator “>>” trennen (C++ erlaubt nicht die einfache Aneinanderreihung von Variablen ohne Verwendung von Operatoren zwischen den Variablen, weshalb in spirit der right shift Operator zu diesem Zweck ueberladen wurde). Regeln in spirit muessen zudem mit einem Semikolon abgeschlossen werden, da diese nichts anderes als gewoehnliche Variablenzuweisungen sind. Die Regel laesst sich mit Hilfe zusaetzlicher Operatoren noch vereinfachen zu

if_statement = "if" >> expression >> "then" >> statement >> -( "else" >> statement );

Der Operator “-” macht den folgenden, in Klammern eingeschlossenen Ausdruck optional und erspart uns damit die in der vorherigen Version noch vorhandene zweite Regelvariante. Ein ausfuehrliches Benutzerhandbuch und ein Tutorial zu boost::spirit finden Sie unter http://www.boost.org/doc/libs/1_41_0/libs/spirit/doc/html/index.html.

Kommen wir zurueck zu unserem Konfigurationsformat. Wir werden nun eine Grammatik dafuer definieren, ueberspringen dabei aber den Zwischenschritt BNF und schreiben direkt gueltige spirit Regeln. Zunaechst benoetigen wir eine Regel, die die gesamte Datei repraesentiert. Eine Konfigurationsdatei besteht aus beliebig vielen Variablenzuweisungen, also definieren wir eine Regel

file = *( variableAssignment ) >> eoi;

Der Asterisk vor dem geklammerten Ausdruck steht fuer “beliebig viele”. Das abschliessende “eoi” steht fuer “end of input” und sorgt dafuer, dass sowohl Leerzeichen am Ende der Datei erlaubt sind und gleichzeitig der gesamte String gematcht wird (ansonsten koennte man in der Datei auch ungueltige Syntax verwenden, solange davor ein Teil steht, auf den das file Symbol passt).

Als naechstes muessen wir das Symbol “variableAssignment” definieren. Eine solche Variablenzuweisung besteht gemaess unserer Syntaxvorgaben aus einem Variablennamen gefolgt von einem Gleichheitszeichen und einer Variablendefinition:

variableAssignment =
      literal
   >> '='
   >> ( groupDefinition
      | listDefinition
      | arrayDefinition
      | atom
      )
   >  ';'
   ;

Wir haben also festgelegt, dass eine Variablendefinition entweder eine “groupDefinition”, “listDefinition”, “arrayDefinition” oder ein “atom” sein kann. Um den Ausdruck abzuschliessen, fordern wir noch ein Semikolon am Ende, dass in diesem Fall nicht durch “>>” sondern durch “>” angehaengt wird, was dafuer sorgt, dass der Parser sofort einen Fehler wirft, wenn die vorherigen Symbole erfolgreich erkannt wurden, das Semikolon aber fehlt. Das letzte Semikolon dient wieder dazu, das eigentliche C++ Statement abzuschliessen und gehoert nicht zur Grammatik!

Das Symbol “literal” repraesentiert einen Variablennamen. Um gaengigen Programmiersprachenkonventionen zu folgen, erlauben wir hierfuer nur alphanumerische Zeichen und den Unterstrich “_”, und definieren zusaetzlich, dass das erste Zeichen keine Ziffer sein darf. Dies fuehrt uns auf folgende Regel:

literal = (alpha | '_') >> *(alnum | '_');

Ein “literal” ist also ein Buchstabe oder ein Unterstrich gefolgt von beliebig vielen Buchstaben, Ziffern oder Unterstrichen. Beachten Sie bitte, dass nur die zweite Teilregel optional ist, der Variablenname muss also mindestens ein Zeichen lang sein (was Sinn macht).

Betrachten wir nun noch die Definition des Symbols “atom”, das wir wie folgt festlegen:

atom = (strict_double | long_ | bool_ | string);

“long_” und “bool_” sind in spirit bereits eingebaute Parser, die, wie der Name schon suggeriert, long und bool Werte parsen. Das Symbol “string” wollen wir selbst definieren. Es sieht folgendermassen aus:

string = lexeme[ lit('"') >> *(char_ - '"') > '"' ];

Ein String in unserer Konfigurationsdatei muss also mit einem Anfuehrungszeichen beginnen, gefolgt von beliebig vielen Zeichen ausser dem Anfuehrungszeichen (char_ ist wieder ein eingebauter Parser und matcht jedes beliebige Zeichen), abgeschlossen von einem weiteren Anfuehrungszeichen.

Die Regel “strict_double” muessen wir noch definieren. Ein einfaches “double_” wuerde hier nicht wie gewuenscht funktionieren, da es auch Zahlen ohne Dezimalpunkt parst und damit der long_ Parser nie aufgerufen wuerde. Die Reihenfolge der Regeln umzukehren ist jedoch auch keine Loesung, da Floating Point Zahlen in der Regel mit einer Ziffer beginnen und daher die long_ Regel saemtliche Ziffern bis zum Dezimalpunkt konsumieren wuerde, waehrend die uebrigen Zeichen bis zum abschliessenden Semikolon nicht mehr in die Grammatik passen und somit einen Parser Fehler ausloesen wuerden. Wir koennen jedoch mit nur einer Zeile Code einen modifizierten double Parser definieren, der zwingend einen Dezimalpunkt voraussetzt:

namespace qi = boost::spirit::qi;
qi::real_parser<double, qi::strict_real_policies<double> > strict_double;

Fehlen noch die Symbole “groupDefinition”, “listDefinition” und “arrayDefinition”. Diese sind umfangreicher, weshalb wir ihnen einen separaten Teil widmen wollen (2b).

Beide Formate — INI wie XML — sind ausserdem meines Erachtens fuer die Verwendung als Konfigurationsdateien denkbar ungeeignet. Waehrend XML dem Entwickler zwar alle Moeglichkeiten bietet, die Konfigurationen hierarchisch zu gliedern und beliebige Metadaten dazu abzuspeichern, ist die Verwendung von Begin- und Endtags doch in hoechstem Masse speicherineffizient und redundant. Weiterhin gibt das Format an sich keinerlei Typstruktur vor, weshalb diese entweder zusaetzlich auf das Format aufgesetzt oder vom Benutzer gehandhabt werden muss (dies hat natuerlich Vor- und Nachteile!). Wer nun glaubt, mit INI Dateien besser zu fahren, der wird schnell an Grenzen stossen. Lediglich eine einzige Hierarchieebene ist fuer die meisten Anwendungen zu wenig. Und auch hier gibt es ausser Strings keine vorgegebenen Typen.

Welche Anforderungen muss eine Konfigurationsdatei erfuellen, um moeglichst viele Anwendungsbereiche abzudecken? Fassen wir diese in einem kurzen Brainstorming zusammen:

• Unterstuetzung der wichtigsten atomaren Typen (int, float, bool, string)
• Bereitstellung von Listen und Arrays als zusammengesetzte Datentypen (Listen koennen dabei beliebige Subelemente enthalten, Arrays hingegen sind homogene Felder atomarer Typen)
• Einfuehrung unbegrenzter Hierarchieebenen durch Verwendung von assoziativen Arraystrukturen, die mehrere Variablendeklarationen zusammenfassen und rekursiv definiert werden koennen

Damit haben wir Listen-, Array- und hierarchische Semantik gleichermassen abgedeckt und kommen damit schon sehr nahe an das XML Format heran. Bezueglich der Syntax des Formats habe ich mich an C++ bzw. Python angelehnt und fasse Listen in runden, Arrays in eckigen und assoziative Arrays in geschweiften Klammern zusammen. Ein Beispiel fuer eine solche Konfigurationsdatei ist im folgenden dargestellt:

a = 5;
b = 6.5;
c = {
  var1 = "Hallo";
  pi = 3.14159;
};
d = (
  { eins = 1; zwei = 2; drei = 3; },
  [1, 2, 3, 4, 5]
);

Im naechsten Teil der Serie schreiben wir unter Zuhilfenahme der neuesten Version von boost::spirit (v2.1) einen Parser fuer das soeben definierte Format. Im dritten Teil werden wir eine Objektstruktur fuer die C++ API definieren und diese im letzten Teil mit dem Parser verknuepfen.

Nach einem ersten Überfliegen des Buches steht fest: Dies ist nicht die durchschnittliche, anfängerkompatible Abhandlung über Harmonielehre. Hier werden auf den ersten 150 Seiten schon Themen behandelt, die in anderen Büchern nicht einmal im Anhang angesprochen werden. Wer nun glaubt, dass Sikora dafür weniger ins Detail geht als andere Autoren, der irrt: Jede noch so scheinbar unbedeutende Kleinigkeit wird genau erklärt und hervorragend motiviert. Selbst erfahrene Musiker werden erst beim Lesen dieses Buches verstehen, dass sie ganze Teilbereiche der Harmonielehre bisher schlichtweg nicht kannten.

Die Zielgruppe dieses Buches sind tatsächlich nur gut vorgebildete Musiker – Anfänger werden bereits nach den ersten 20 Seiten kapitulieren. Sikora macht es mit seinem hervorragenden Schreibstil und seinem zweifelsohne hervorragenden pädagogischen Talent dem interessierten Leser jedoch leicht, seinen Ausführungen zu folgen. Zahlreiche qualitativ hochwertige Notenbeispiele helfen, die harmonischen Zusammenhänge zu erfassen und zu verstehen.

Auf den ersten 40 Seiten werden die Grundlagen wie Tonsystem, Obertonreihe, Intervalle, Quintenzirkel und die Akkordsymbolschrift wiederholt. Weiter geht es mit detaillierten Ausführungen zu Modalität, Dur-Diatonik, Kadenzen, Skalen und ihre Beziehung zur Akkordsymbolik bis hin zu Modaler Harmonik und Modal Interchange. Bemerkenswert sind auch die mehr kompositorisch motivierten Kapitel zum musikalischen Motiv, Melodiebogen und harmonischen sowie melodischen Rhythmus.

Die verbleibenden 200 Seiten des Buches sind den Themen “Hören” und “Spielen” gewidmet und versuchen – soweit das mit einem Buch möglich ist – eine Beziehung zwischen dem inneren Ohr und dem Instrument herzustellen und sind nicht nur für Pianisten interessant. Auch das Kapitel zur Transkription ist hervorragend geschrieben und so ausführlich, dass keine Fragen offen bleiben dürften. Wer genug Eigenmotivation mitbringt, den werden Sikoras Ausführungen sicherlich einen großen Schritt weiterbringen.

Die Neue Jazz-Harmonielehre ist ein bemerkenswertes Buch – meines Erachtens sogar die beste Wahl zu diesem Thema – und sollte in keinem Bücherregal fehlen. Erfreulich ist auch der geringe Preis des Buches, das kaum mehr kostet als beispielsweise der hochgelobte Haunschild, der auf 150 Seiten jedoch sehr viele wichtige Themen auslässt und meiner Meinung nach vergleichsweise schlecht motiviert ist.

Dieser Artikel soll eine kurze Einführung in die Einbettung von Python in C++ Applikationen geben. Dabei wird die Library boost::python benutzt, die das Marshalling der Objekte erheblich vereinfacht (z.B. Kapselung der ansonsten notwendigen manuellen Verwaltung der Garbage Collection).

Betrachten wir ein sehr einfaches Python Modul mymodule.py mit nur einer einzigen Funktion:

def myfunction():
  c = 1234 * 5678
  print 'Result is', c

Um diese Funktion aus einem C++ Kontext heraus aufzurufen, schreiben wir folgendes minimales Programm:

#include <boost/python/import.hpp>
#include <boost/python/call.hpp>
using namespace boost::python;
 
int main(int argc, char* argv[])
{
	Py_Initialize();
 
	object mymodule = import("mymodule");
	object dict = mymodule.attr("__dict__");
	object func = dict["myfunction"];
	func();
 
	Py_Finalize();
	return 0;
}

Die Aufrufe von Py_Initialize() und Py_Finalize() sind notwendig, um den eingebetteten Python Interpreter zu initialisieren bzw. sicher herunterzufahren. Im nächsten Schritt wird zunächst das Modul importiert, das Dictionary des Moduls geholt und schließlich eine Referenz auf die gewünschte Funktion erzeugt. Mit func() wird diese anschließend aufgerufen.

Durch die Verwendung von boost::python werden die zurückgelieferten PyObject Pointer in object Objekten gekapselt, die sich um die Garbage Collection kümmern. Dadurch spart man sich gegenüber der nativen Python API das manuelle Freigeben der Pointer mittels Py_DECREF().

Auf manchen Systemen (z.B. Linux) funktioniert der Aufruf jedoch nicht wie gewünscht, da der eingebettete Python Interpreter das Modul nicht findet. Der Grund dafür ist, dass der Pfad, in dem das C++ Programm ausgeführt wird, nicht automatisch als Suchpfad für Python Module hinzugefügt wird. Die Lösung für dieses Problem ist meines Wissens nicht dokumentiert und besteht einfach darin, mittels PySys_SetArgv(1, progName) einen beliebigen Namen für das Programm zu setzen (oder einfach die argc und argv Parameter der main Methode zu benutzen). Das komplette Programm sieht dann beispielsweise folgendermaßen aus:

#include <boost/python/import.hpp>
#include <boost/python/call.hpp>
using namespace boost::python;
 
int main(int argc, char* argv[])
{
	Py_Initialize();
	char* progName[] = { const_cast<char*>("Embedded") };
	PySys_SetArgv(1, progName);
 
	object mymodule = import("mymodule");
	object dict = mymodule.attr("__dict__");
	object func = dict["myfunction"];
	func();
 
	Py_Finalize();
	return 0;
}