Syntax Analyse (Parsing)

Martin Sulzmann

Übersicht

Parser

Umwandlung einer Eingabe (in der Regel in Textformat) in ein für die Weiterverarbeitung geeigneteres Format (in der Regel abstrakter Syntaxbaum).

Dieser Vorgang wird benannt als Syntaxanalyse/Parsing.

Typisches Beispiel. Java source code wird umgewandelt ("geparsed"), so dass der Compiler daraus Java Byte generiert.

Beachte. Parsing ist verschieden von "recognize". Mit recognize bezeichnen wir den Vorgang zu überprüfen, ob die Eingabe wohlgeformt. Z.B. ob ein Wort Teil einer kontext-freien Grammatik ist.

Für eine allgemeine Übersicht siehe folgenden wikipedia Artikel.

Inhalt

Wir bauen einen einfachen top-down Parser für arithmetische Ausdrücke.

Hintergrund - Kontext-freie Sprachen/Grammatiken

Wie sieht ein (syntaktisch) wohlgeformter arithmetischer Ausdruck aus?

Beispiele

1, 2, ...

1 + 2

(1 + 3) * 2

...

Formalere Sicht.

E ist ein arithmetischer Ausdruck genau dann wenn (gdw)

Aha, die Regeln zur Beschreibung von arithmetischen Ausdrücken entsprechen Regel einer kontext-freien Grammatik

E -> 0
E -> 1
...
...
E -> E + E
E -> E * E
E -> (E)

Hm, Regeln aufwändig für Zahlen allgemein

E -> N
N -> 0
...
N -> 9
N -> 0N
...
N -> 9N

Kann stark vereinfacht werden mit Hilfe von regulären Ausdrücken! Z.B.

E -> ['0'-'9']+

wobei r+ = r r*. Sprich, einmalige Wiederholung von r gefolgt von r+. Wir schreiben ['0'-'9'] als Kurznotation für '0'|...|'9'.

Es gibt eine Reihen von Metasyntax Notationen zur Beschreibung von kontext-freien Sprachen. Siehe z.B. Extended Backus–Naur form.

Unsere Syntax von arithmetischen Ausdrücken

Angelehnt an EBNF, betrachten wir folgende Syntax. Der Einfachheithalber betrachten wir nur die Zahlen, 0, 1 und 2.

 N ::= 0 | 1 | 2

 E ::= N | (E) | E + E | E * E

Wir bezeichnen N und E als Nicht-Terminal Symbole und 0, 1, 2, (, ), + und * als Terminal Symbole.

Was fällt auf? Die EBNF Grammatik ist nicht eindeutig!. D.h. für ein Wort gibt es zwei verschiedene Ableitungen.

 (1)
          E
       -> E + E
       -> N + E
       -> 1 + E
       -> 1 + E * E
       -> 1 + N * E
       -> 1 + 2 * E
       -> 1 + 2 * N
       -> 1 + 2 * 1
 (2)

          E
       -> E * E
       -> E + E * E
       -> 1 + E * E
       -> 1 + 2 * E
       -> 1 + 2 * 1

Was ist die Konsequenz verschiedener Ableitungen? Im Fall von (1) wird das Wort "1 + 2 * 1" interpretiert als 1 + (2 * 1). Im Fall von (2) wird das Wort "1 + 2 * 1" interpretiert als (1 + 2) * 1.

Eindeutige Grammatik (bzw. Regeln welche Nicht-eindeutigkeiten Einschränkungen) sind wichtig. Weil sonst könnte Compiler A (Oracle) die Interpretation (1) verwenden und Compiler B (Microsoft) die Interpretation (2). Deshalb sollte wir eine eindeutige Beschreibung (der Syntax) von arithmetischen Ausdrücken haben.

In der Regel gehen wir von "Punkt vor Strich" aus. Gibt es eine äquivalente (eindeutige) Grammatik welche die "Punkt vor Strich" umsetzt? Ja. Betrachte folgende Grammatik.

E ::= E + T | T

T ::= T * F | F

F ::= N | (E)

Betrachte Beispiel von oben.

          E
       -> E + T
       -> E + T * F
       -> T + T * F
       -> F + T * F
       -> F + F * F
       -> N + F * F
       -> 1 + F * F
       -> 1 + N * F
       -> 1 + 2 * F
       -> 1 + 2 * N
       -> 1 + 2 * 1

Interpretiert als 1 + (2 * 1).

Randbemerkung zu Chomsky Normal Form

Wir betrachten (einen Auszug) der Grammatik für arithmetische Ausdrücken. Klammerung ignorieren wir.

 N ::= 0 | 1 | 2

 E ::= N | E + E | E * E

Eine dazu äquivalente Grammatik in Chomsky Normal Form (CNF) ist wie folgt.

 N ::= 0 | 1 | 2

E ::= N | E E1 | E E4

E1 ::= E3 E

E3 ::= +

E4 ::= E5 E

E5 ::= *

Obige CNF Grammatik ist nicht eindeutig. Betrachte z.B.

(1)
       E
    -> E E1
    -> N E1
    -> 1 E1
    -> 1 E3 E
    -> 1 + E
    -> 1 + E E4
    -> 1 + N E4
    -> 1 + 2 E4
    -> 1 + 2 E5 E
    -> 1 + 2 * E
    -> 1 + 2 * N
    -> 1 + 2 * 1
(2)
       E
    -> E E4
    -> E E5 E
    -> E * E
    -> E * N
    -> E * 1
    -> E E1 * 1
    -> E E3 E * 1
    -> N E3 E * 1
    -> 1 E3 E * 1
    -> 1 + E * 1
    -> 1 + N * 1
    -> 1 + 2 * 1

Ableitungsbäume

Eine Ableitung ist ein Beweis, dass z.B. das Wort "1 + 2 * 1" Teil der Sprache beschrieben durch obige Grammatik ist.

Jede Ableitung kann als (Ableitungs)baum dargestellt werden.

Von der Ableitung zum Baum:

Jede Regel (sprich deren Anwendung) besteht aus einer linken Seite (Nicht-Terminal Symbol) und rechten Seite (Mix aus Terminal und Nicht-Terminal Symbolen).

Jedes Nicht-Terminal Symbol entspricht einem Zwischenknoten. Jedes Terminal Symbol entspricht einem Blatt(knoten).

Das auf der linken Seite stehende Nicht-Terminal Symbol ist daher der Elternknoten und die Kinderknoten sind alle Symbole auf der rechten Seite.

Betrachte z.B.

E ::= E + T

dargestellt als Baum

        E
      / | \
     E  +  T

Beispiele

Betrachte die Ableitung

     E
  -> T
  -> F
  -> (E)
  -> (E + T)
  -> (T + T)
  -> (F + T)
  -> (F + F)
  -> (N + F)
  -> (N + N)
  -> (1 + 0)

Darstellung als Ableitungsbaum.

         E
         |
         T
         |
         F
       / | \
      (  E  )
       / | \
      E  +  T
      |     |
      T     F
      |     |
      F     N
      |     |
      N     0
      |
      1

Konkrete versus abstrakter Ableitungsbaum

Obiger Ableitungsbaum gibt die konkrete Syntax wieder und wird daher als konkreter Ableitungsbaum bezeichnet. Alle Details bleiben erhalten.

Zur weiteren (maschinellen) Verarbeitung sind nicht alle (konkreten) Details notwendig. Zumindest Zwischenschritte wie "E abgeleitet zu T" etc sind nicht relevant. Auch sind Klammern nicht notwendig, da die Klammerung durch die Struktur des Baumes gewährleistet wird.

Deshalb betrachten wir die abstrakten Syntax beschrieben durch den abstrakten Ableitungsbaum.

         +
        / \
       1   0

In der abstrakten Ableitungsbaum Darstellung werden ausserdem die (Nicht-Terminale) Operatoren als Zwischenknoten verwendet.

Darstellung in C++

Wie kann die Syntax in C++ dargestellt werden?

Idee:

Unten finden Sie eine Skizze. Beachte. Die Skizze ist stark vereinfacht im Vergleich zur Implementierung die Ihnen zur Verfügung gestellt ist.

class Exp {};

class IntExp : Exp {
   int val;
   IntExp(int x) { val = x; }
};

class PlusExp : Exp {
   Exp l,r;
   PlusExp(Exp x,y) { l = x; r = y; }
};

class MultExp : Exp {
   Exp l,r;
   MultExp(Exp x,y) { l = x; r = y; }
};

Beachte. Klammerung muss nicht in C++ dargestellt werden. Implizit behandelt durch Klammerung der jeweiligen Objekte.

Beispiel.

"1 + (3 + 5)"

==>

PlusExp(IntExp(1), PlusExp(IntExp(3), IntExp(5)))

Aha! In der C++ Darstellung ist die "Klammerung" implizit garantiert durch die Struktur des Objekts!

Parser

Ziel:

Wandle Eingabe um in einen abstrakten Ableitungsbaum. In der Regel bezeichnet als abstrakter Syntax Baum. Auf Englisch: Abstract syntax tree (AST).

Allgemeine Parser

Siehe Cocke–Younger–Kasami algorithm.

Kubische Komplexität.

Top-Down Parsing

Deterministisches parsen in linearer Zeit.

Beispiel

Betrachte unsere Grammatik.

E ::= E + T | T

T ::= T * F | F

F ::= N | (E)

N ::= 0 | 1 | 2

Vorgehen:

Problem! Links-Rekursion in der Grammatik. Ersetze T durch T * F oder durch F?

Wir könnten beide Alternativen probieren was dann aber möglicherweise "back-tracking" erfordert.

E ::= T E'

E' ::= + T E' |

T ::= F T'

T' ::= * F T' |

F ::= N | (E)

N ::= 0 | 1 | 2

Baue daraus Parser. Wie?

Die Idee

Jedes Nicht-Terminal impliziert eine Funktion.

Falls diese Funktion erfolgreich ausgeführt wird, wurde ein Wort erkannt welches ableitbar ist via dem korrespondierenden Nicht-Terminal.

Der Funktionsrumpf ist definiert durch die rechte Regelseite.

Beachte: Links-Rekursion wurde eliminiert. Dadurch können wir garantierten, dass die Funktion terminiert (nicht notwendigerweise erfolgreich, falls ein Wort nicht erkannt wird).

Betrachte die Regel.

E ::= T E'

Daraus generieren wir

E() {
  T();
  E2();
}
// In C++ duerfen Funktionsnamen mit Grossbuchstaben beginnen.
// Anstatt E', verwenden wir E2.
// T und E2 muessen noch definiert werden.

Vor jedem Funktionsaufruf können wir testen, ob ein erfolgreicher Aufruf möglich ist.

Wir berechnen die "first" Menge für alle Nicht-Terminale.

first(E) = first(T) = first(F) = { 0, 1, 2, ( }

Entspricht den an erster Position erscheinenden Zeichen.

Weitere Annahmen.

Globale Variable token referenziert das aktuelle Zeichen.

Via getNext() wird token auf das nachfolgende Zeichen gesetzt.

Alternative Definition von E.

E() {
  if token not in first(T) then ABORT;
  T();
  E2();
}

Beide Definitionen sind möglich (Geschmackssache). Wir verwenden den ersten Stil.

Die Grammatik

E ::= T E'

E' ::= + T E' |

T ::= F T'

T' ::= * F T' |

F ::= N | (E)

N ::= 0 | 1 | 2

wird übersetzt wie folgt.

E() {
  T();  E2();
}

E2() {
 if token = +
 then  getNext(); T(); E2();
}

T() {
  F(); T2();
}

T2() {
  if token = *
  then getNext(); F(); T2();
}

F() {
  if token in {0, 1, 2}
  then getNext(); return;
  if token = (
  then getNext();
       E();
       if token = )
       then getNext(); return;
       else ABORT;
  else ABORT;
}

Obige Funktionen definieren einen "top-down Parser". Wir fangen "top-down" an. Beginnend mit dem Startsymbol E usw.

Erfolgreiche Ausfuehrung von E() impliziert ein Wort der Sprache wie oben beschrieben wurde erkannt.

Bemerkung: Wir muessen noch überprüfen, ob alle Zeichen verarbeitet wurden (end of string).

Vorverarbeitung (Tokenizer)

Elimination von Leerzeichen.

Elimination von Kommentaren.

Erkennen von Variablennamen, Zahlen (bestehend aus mehreren digits), Schluesselwoertern, ...

Top-Down Matcher

#include <iostream>
#include <string>
#include <vector>

using namespace std;


typedef enum {
  EOS,           // End of string
  ZERO,
  ONE,
  TWO,
  OPEN,
  CLOSE,
  PLUS,
  MULT
} Token_t;


string showTok(Token_t t) {
  switch(t) {
  case EOS:   return "EOS";
  case ZERO:  return "ZERO";
  case ONE:   return "ONE";
  case TWO:   return "TWO";
  case OPEN:  return "OPEN";
  case CLOSE: return "CLOSE";
  case PLUS:  return "PLUS";
  case MULT:  return "MULT";
  }
  // NOTE: The (clang) compiler is able to figure out that
  // along all control-flow paths, a return statement will be reached.
}


class Tokenize {
  string s;
  int pos;
public:
  Tokenize(string s) {
         this->s = s;
     pos = 0;
  }

  // Scan throuh string, letter (symbol) by letter.
  Token_t next() {
    if(s.length() <= pos)
      return EOS;

    while(1) {

       if(s.length() <= pos)
         return EOS;

       switch(s[pos]) {
       case '0': pos++;
                 return ZERO;
       case '1': pos++;
                 return ONE;
       case '2': pos++;
                 return TWO;
       case '(': pos++;
                 return OPEN;
       case ')': pos++;
                 return CLOSE;
       case '+': pos++;
                 return PLUS;
       case '*': pos++;
                 return MULT;
       default:  // we simply skip all other symbols !
                 pos++;
             break;
       }
    }
  } // next

  vector<Token_t> scan() {
    vector<Token_t> v;
    Token_t t;

    do {
      t = next();
      v.push_back(t);
    }
    while(t != EOS);

    return v;
  } // scan

  string show() {
    vector<Token_t> v = this->scan();
    string s;

    for(int i=0; i < v.size(); i++) {
      s += showTok(v[i]);
      if(i+1 < v.size())
    s += ";" ;         // Add delimiter
    }
    return s;
  } // show
};

// Wrapper class, provide the (current) token.
class Tokenizer : Tokenize {
public:
  Token_t token;
  Tokenizer(string s) : Tokenize(s) { token = next(); }
  void nextToken() {
    token = next();
  }
};

void testTokenize() {
  //  Tokenize t1("1 + (3 * 4)");
  {
    Tokenize t1("  1 + (0 * 1)");

  cout << t1.show() << endl;
  }

  {
    Tokenize t1("");

  cout << t1.show() << endl;
  }
}



// We first build a matcher (with pretty much zero error handling).
// Functional style where we thread through the tokenizer.
// The alternative would be to define a "matcher" class
// where the tokenizer is part of the match object's internal state.


// Note: Call-by reference for tokenizer, why?
// Hint: Consider the tokenizer's internal state.
bool matchE(Tokenizer &t);
bool matchT(Tokenizer &t);
bool matchE2(Tokenizer &t);
bool matchF(Tokenizer &t);
bool matchT2(Tokenizer &t);

// E  ::= T E'
bool matchE(Tokenizer &t) {

  if(!matchT(t))
    return false;
  if(!matchE2(t))
    return false;

  return true;
}

// E' ::= + T E' |
bool matchE2(Tokenizer &t) {

  if(t.token == PLUS) {
    t.nextToken();
    if(!matchT(t))
      return false;
    if(!matchE2(t))
      return false;
  }

  return true;
}

// T  ::= F T'
bool matchT(Tokenizer &t) {
  if(!matchF(t))
    return false;
  if(!matchT2(t))
    return false;

  return true;
}

// T' ::= * F T' |
bool matchT2(Tokenizer &t) {

  if(t.token == MULT) {
    t.nextToken();
    if(!matchF(t))
      return false;
    if(!matchT2(t))
      return false;
  }

  return true;
}

// F ::= N | (E)
bool matchF(Tokenizer &t) {
  switch(t.token) {
  case ZERO:
      t.nextToken();
      return true;
  case ONE:
      t.nextToken();
      return true;
  case TWO:
      t.nextToken();
      return true;
  case OPEN:
      t.nextToken();
      if(!matchE(t))
         return false;
      if(t.token != CLOSE)
    return false;
      t.nextToken();
      return true;
  default: return false;
  }
}



bool match(string s) {
  Tokenizer t(s);
  bool b = matchE(t);
  if(b && t.token == EOS)
    return true;
  return false;
}

void testMatcherBad() {

  cout << match("");

  cout << match("1 + ");

  cout << match("1 + *");

  cout << match("(1 ");

  cout << match("(1 ) )");
}

void testMatcherGood() {

  cout << match("1");

  cout << match("1 + 0");

  cout << match("1 * 2");

  cout << match("(1)");

  cout << match("1 * (2)");

  cout << match("(1 + 2) * 0");


}

void testMatcher() {

  cout << "good: ";
  testMatcherGood();

  cout << "\n bad: ";
  testMatcherBad();
}



int main() {

  testTokenize();

  testMatcher();

  return 1;
}

Top-Down Parser mit AST Generierung

Jetzt geht es an den Parser. Anstatt bool verwenden wir Parser Funktionen welche einen AST zurückliefern. Da Parsing fehlschlagen kann verwenden wir einen "Optional" Datentyp. Siehe unten.

Der Top-Down Parser folgt (fast) direkt aus dem Top-Down Matcher.

Betrachte.

E  ::= T E2

E2 ::= + T E2 |

E liefert einen AST das gleiche gilt für E2. Bei der Generierung des ASTs in E2 benötigen wir den linken Operanden von +T. Dieser linke Operand wird innerhalb der Parserfunktion von E gebaut und als Argument an E2 geliefert. Details siehe unten.


// g++ --std=c++11 expParser.cpp

#include <iostream>
#include <string>
#include <vector>

using namespace std;


// Utility stuff

// Haskell's Maybe
template<typename T>
class Optional {
  bool b;
  T val;
public:
  Optional() : b(false) {}
  Optional(T v) : val(v), b(true) {}
  bool isJust() { return b; }
  bool isNothing() { return !b; }
  T fromJust() { return val; }
};

template<typename T>
Optional<T> nothing() {
  return Optional<T>();
}

template<typename T>
Optional<T> just(T v) {
  return Optional<T>(v);
}


typedef enum {
  EOS,           // End of string
  ZERO,
  ONE,
  TWO,
  OPEN,
  CLOSE,
  PLUS,
  MULT
} Token_t;


string showTok(Token_t t) {
  switch(t) {
  case EOS:   return "EOS";
  case ZERO:  return "ZERO";
  case ONE:   return "ONE";
  case TWO:   return "TWO";
  case OPEN:  return "OPEN";
  case CLOSE: return "CLOSE";
  case PLUS:  return "PLUS";
  case MULT:  return "MULT";
  }
  // NOTE: The (clang) compiler is able to figure out that
  // along all control-flow paths, a return statement will be reached.
}


class Tokenize {
  string s;
  int pos;
public:
  Tokenize(string s) {
         this->s = s;
     pos = 0;
  }

  // Scan throuh string, letter (symbol) by letter.
  Token_t next() {
    if(s.length() <= pos)
      return EOS;

    while(1) {

       if(s.length() <= pos)
         return EOS;

       switch(s[pos]) {
       case '0': pos++;
                 return ZERO;
       case '1': pos++;
                 return ONE;
       case '2': pos++;
                 return TWO;
       case '(': pos++;
                 return OPEN;
       case ')': pos++;
                 return CLOSE;
       case '+': pos++;
                 return PLUS;
       case '*': pos++;
                 return MULT;
       default:  // we simply skip all other symbols !
                 pos++;
             break;
       }
    }
  } // next

  vector<Token_t> scan() {
    vector<Token_t> v;
    Token_t t;

    do {
      t = next();
      v.push_back(t);
    }
    while(t != EOS);

    return v;
  } // scan

  string show() {
    vector<Token_t> v = this->scan();
    string s;

    for(int i=0; i < v.size(); i++) {
      s += showTok(v[i]);
      if(i+1 < v.size())
    s += ";" ;         // Add delimiter
    }
    return s;
  } // show
};

// Wrapper class, provide the (current) token.
class Tokenizer : Tokenize {
public:
  Token_t token;
  Tokenizer(string s) : Tokenize(s) { token = next(); }
  void nextToken() {
    token = next();
  }
};

void testTokenize() {
  //  Tokenize t1("1 + (3 * 4)");
  {
    Tokenize t1("  1 + (0 * 1)");

  cout << t1.show() << endl;
  }

  {
    Tokenize t1("");

  cout << t1.show() << endl;
  }
}


// Exp AST

class Exp {
public:
  virtual int eval() = 0;
  virtual string pretty() = 0;
};


class IntExp : public Exp {
  int val;
  public:
  IntExp(int _val) { val = _val; }
  int eval() { return val;}
    string pretty() {
      return to_string(val);
  }
};

class PlusExp : public Exp {
  std::shared_ptr<Exp> e1;
  std::shared_ptr<Exp> e2;
  public:
  PlusExp(std::shared_ptr<Exp> _e1, std::shared_ptr<Exp> _e2) {
      e1 = _e1; e2 = _e2;
  }
  int eval() { return e1->eval() + e2->eval(); }
    string pretty() {
    string s("(");
    s.append(e1->pretty());
    s.append("+");
    s.append(e2->pretty());
    s.append(")");
    return s;
  }
};


class MultExp : public Exp {
  std::shared_ptr<Exp> e1;
  std::shared_ptr<Exp> e2;
  public:
  MultExp(std::shared_ptr <Exp> _e1, std::shared_ptr<Exp> _e2) {
      e1 = _e1; e2 = _e2;
  }
  int eval() { return e1->eval() * e2->eval(); }
    string pretty() {
    string s("(");
    s.append(e1->pretty());
    s.append("*");
    s.append(e2->pretty());
    s.append(")");
    return s;
  }
};

// Short-hands

typedef std::shared_ptr<Exp> EXP;

EXP newInt(int i) {
  return std::make_shared<IntExp>(i);
}

EXP newPlus(EXP l, EXP r) {
  return std::make_shared<PlusExp>(l,r);
}

EXP newMult(EXP l, EXP r) {
  return std::make_shared<MultExp>(l,r);
}




// Now comes the parser (OO-style)

class Parser {
  Tokenizer t;

  // E  ::= T E'
  Optional<EXP> parseE() {

    Optional<EXP> t = parseT();
    if(t.isNothing())
      return t;

    return parseE2(t.fromJust());
  }

  // E' ::= + T E' |
  Optional<EXP> parseE2(EXP left) {

    if(t.token == PLUS) {
        t.nextToken();

    Optional<EXP> right = parseT();
    if(right.isNothing())
      return right;

    return parseE2(newPlus(left, right.fromJust()));
    }

    return just<EXP>(left);
  }

  // T  ::= F T'
  Optional<EXP> parseT() {

    Optional<EXP> f = parseF();
    if(f.isNothing())
      return f;

    return parseT2(f.fromJust());
  }

  // T' ::= * F T' |
  Optional<EXP> parseT2(EXP left) {
    if(t.token == MULT) {
      t.nextToken();

      Optional<EXP> right = parseF();
      if(right.isNothing())
    return right;

      return parseT2(newMult(left, right.fromJust()));
    }

    return just<EXP>(left);
  }

  // F ::= N | (E)
  Optional<EXP> parseF() {
      switch(t.token) {
      case ZERO:
          t.nextToken();
          return just<EXP>(newInt(0));
      case ONE:
          t.nextToken();
          return just<EXP>(newInt(1));
      case TWO:
          t.nextToken();
          return just<EXP>(newInt(2));
      case OPEN: { // introduce new scope
          t.nextToken();
      Optional<EXP> e = parseE();
      if(e.isNothing())
        return e;
          if(t.token != CLOSE)
        return nothing<EXP>();
      t.nextToken();
      return e; }
      default: return nothing<EXP>();
      }

  }

public:
  Parser(string s) : t(Tokenizer(s)) { }

  Optional<EXP> parse() {
    Optional<EXP> e= parseE();

    return e;
  }
};

void display(Optional<EXP> e) {
  if(e.isNothing()) {
    cout << "nothing \n";
  } else {
    cout << (e.fromJust())->pretty() << "\n";
  }
  return;
}

void testParserGood() {

  /*
  display(Parser("1").parse());

  display(Parser("1 + 0 ").parse());

  display(Parser("1 + (0) ").parse());

  display(Parser("1 + 2 * 0 ").parse());

  display(Parser("1 * 2 + 0 ").parse());
  */

  display(Parser("(1 + 2) * 0 ").parse());

  display(Parser("(1 + 2) * 0 + 2").parse());
}

void testParser() {

  testParserGood();
}





int main() {
  std::shared_ptr<Exp> e = std::make_shared<IntExp>(5);

  testParser();

  return 1;
}

Zusammenfassung

Top-down Parser:

Anstatt Parser Funktionen kann auch eine Parser Tabelle generiert werden, welche die Parser Funktionen emuliert.

Parser Generatoren:

Parser Generatoren wie ANTLR und yacc erwarten die Grammatik in einem geeigneten Eingabeformat. Beides sind DSLs ("domain-specific languages") zum Zweck der Syntaxanalyse.

Parser combinators sind clevere Top-down Parser Funktionen direkt integriert in einer Programmiersprache. Eine exemplarische Umsetzung in C++11 findet sich hier.