Parser-Crashkurs

Markus Rudolph / Lotes

---

Motivation

• Verwendung von komplexen strukturierten Daten
• Erstellen eigener menschenlesbarer Datenformate
• Formulieren von Sachverhalt in der Domäne des Sachverhaltes (domänenspezifische Sprachen wie CSS)
• Angst nehmen Sprachen zu entwickeln

---

Abgrenzung

• keine vollständigen Compiler, nur Parser
• Literatur:

---

Inhalte

* Parsen mit Generator * Grammatik schreiben * Grammatikbestandteile * Sprachklassen * Gängige Probleme * Parsen ohne Generator

---

Grammatik schreiben

"Mich beliebt es Angular-like HTML-Komponenten mittels Expressions zu definieren. Ich gedenke mir dafür einen Parser zu schreiben. Alle existierenden Lösungen sind Firlefanz!" - Siegbert von Schnösel -

---

Erklärung: Angular Expressions

• einfache Ausdrücke
• wenn sich eine Variable ändert, wird der komplette Ausdruck neu berechnet und die HTML-Komponente aktualisiert

---

Operationen in Grammatik

• ein Wort A ist eine Abfolge von Buchstaben
• die Konkatenation von Wörtern A und B ist wieder ein Wort AB.
• die endliche Wiederholung eines Wortes A ist wieder ein Wort
  • A* bedeutet 0 bis n mal
  • A+ bedeutet 1 bis n mal
  • A? bedeutet 0 oder 1 mal
• Die Vereinigung zweier Wörter A und B ist wieder ein Wort A | B (Alternation).
• keine Sorge, es gibt noch mehr, aber zur weiteren Erklärung reicht das

[aa]* = ε | aa | aaaa | aaaaaa | ...

---

Grammatikaufbau

Grammatikregeln

Eine Regel besteht aus einem Nichtterminal auf der linken Seite und einem Mix von Terminalen und Nichtterminalen auf der rechten Seite. Getrennt durch den ::=-Operator.

NICHT-TERMINAL-A ::= MIX VON 'terminal' 'und' NICHT-TERMINAL-B

Terminale

Terminale produzieren Buchstaben für die zu bildene Sprache. Entweder in From von Strings oder in Form von regulären Ausdrücken.

'&&'    //in Form von Text
[0-9]+  //in Form von regulären Ausdrücken

---

Grammatikaufbau...

Nichtterminale

Nichtterminale auf der linken Seite einer Regel kann man als Funktionsdefinition ansehen. Nichtterminale auf der rechten Seite sind so etwas wie Funktionsaufrufe innerhalb der Sprache.

NUM ::= DIGIT+
DIGIT ::= '0' | ... | '9'

---

Grammatikaufbau...

Pseudoterminale und Rückgabetypen

Pseudoterminale produzieren keine Sprachteile, werden aber ausgeführt wenn der Parser an diesem Teil der Grammatik ankommt.

Num  <int> ::= Num Digit { $$ = $1 * 10 + atoi($2); }
             | Digit     { $$ = atoi($1); }

Pseudoterminale sind ein gängiges Vorgehen um abstrakte Syntaxbäume aufzubauen und meistens unvermeidbar. Sie blähen die Grammatik stark auf!

---

Grammatikaufbau...

Plattformspezifische Bestandteile

• Metadaten wie Klassennamen
• Importe von Bilbliotheken oder Headers

Beipiel aus NPegasus:

@namespace MainCore.Common.Comments
@classname CommentLineParser
@using System.Linq;

• sonst "syntaktischer Zucker" wie [Referenzen_in_XText]
• Prüfungen am Lookahead auch denkbar
• ... das wird jetzt zu speziell

---

Welches Tool?

Ich benutze Jison. NodeJS. Installieren mit npm i -g jison.

//Importe, Tokendefinitionen, Startdefinition, weitere Regeln...
expression      : literal
                | ID args?
                | expression DOT ID args?
                | expression PIPE ID filterArg*
                | expression LBRACKET expression RBRACKET
                | preOp expression
                | expression binOp expression
                | expression QUESTION expression COLON expression
                ;

• bauen des Parsers mit jison input.jison output.js

---

Ergebnis

1.563 Zeilen an Fehlern

"A fool with a tool is still a fool!"

---

Wie wäre es mit etwas...

---

Sprackklassen

• Formale Sprachen (Chomsky-Hierarchie)
  • Typ-0-Grammatik: alle Sprachen
  • Typ-1-Grammatik: kontextsensitive Sprachen
  • Typ-2-Grammatik: kontextfreie Sprachen
  • Typ-3-Grammatik: reguläre Ausdrücke
  • Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0

"Form"-AL

---

Und es gibt noch...

"PEG"

Parser Expression Grammar auch "praktische Grammatik" genannt implementierbar mittels parser combinators

---

Problem

Domänspezifische Sprachen sind meistens vom Typ-0 oder Typ-1.

Das heißt: "Im Allgemeinen kann ein Wort der Sprache nicht in effizienter Laufzeit erkannt werden."

---

Lösung

Es bleiben uns nur noch Typ-2- und Typ-3-Grammatiken.

Diese Sprachen sind in polynomieller Laufzeit erkennbar!

Das heißt aber auch, dass nach der Erkennung noch Validierungsarbeit zu leisten ist!

---

Allgemeiner Verlauf

...für formale Grammatiken:

PEGs dagegen haben keine lexikalische Analyse.

---

Lexikalische Analyse

Beispiel: 12 * i + 5

Ein Strom von Charactern

wird zu einen Strom von Tokens

• "Komplexität" 10 zu 5
• Werkzeug dazu: "Lexer" oder "Scanner" oder "Tokenizer"
• Artikel: Wie schreibt man einen Lexer?

---

Syntaktische Analyse

Beispiel

wird zu einem abstrakten Syntaxbaum umgewandelt

---

Semantische Analyse

• abstrakten Syntaxbaum validieren (Visitor pattern!)
• Baum mit neuen Eigenschaften annotieren oder Fehler generieren

---

Nächste Phasen

Die semantische Phase erfordert Wissen über die Domäne.

Darauffolgende Phasen auch! Darum gibt es hier einen Schnitt!

---

Kontextfreie Parser

LL und LR

• das erste L ist die Leserichtung
• der zweite Buchstabe sagt: "Ich fange mit der linken (rechten) Seite einer Grammatikregel an."
• LL heißen auch "Top-Down-Parser"
• LR heißen "Bottom-Up-Parser"

---

Mächtigkeit von LL, LR und PEG

• LL ist einfacher nachzubauen, hat aber mehr Einschränkungen
• LR gibt es in verschiedenen Schwierigkeitsgeraden
  • SLR, LALR, LR(1), LR(0), LR(k)...
  • Linksfaktoren und Linksrekursionen möglich

---

LL-Parser, kurz und gut

---

LR-Parser, kurz und gut

---

LR-Parser in Aktion

---

Nur 4 Regeln!

---

Mehrdeutigkeiten verstehen

Stmt ::= 'if' Expr 'then' Stmt 'else' Stmt
      | 'if' Expr 'then' Stmt

Mögliche Syntaxbäume für

if condition then
if condition2 then A
else B

---

Vorrangregeln umsetzen

Folgende Grammatik ist mehrdeutig. Durch Umssetzen von Vorrangregeln mittels Operator-Kaskade oder Operator-Deklaration.

E ::= E '*' E |  E '+' E
    | NUM |  E '++' |  '(' E ')'

Dabei liegen die stärker bindenen Operatoren näher an der Low-Level-Regel F und lockere Operatoren näher an der High-Level-Regel E (Test: Versucht mal 2 Bäume zum selben Ausdruck zu finden!).

E ::= T '+' E | T
T ::= F '*' T | F
F ::= F '++'  | NUM | '(' E ')'

LR-Parser sind ab jetzt schon zufrieden. LL-Parser ist unschlüssig, weil E zwei Alternativen hat, die mit T anfangen.

---

Linksfaktoren eliminieren

LL-Parser streikt, da Linksfaktoren mehrdeutige Einträge in der Parsingtabelle eintragen würde.

E ::= T '+' E
   |  T
T ::= F '*' T
   |  F
F ::= F '++'
   |  NUM
   | '(' E ')'

Lösung: Faktoren rausziehen und einzeln aufführen.

E  ::= T E'
E' ::= '+' E
    |  ε
T  ::= F T'
T' ::= '*' T
    |  ε
F  ::= F '++'
    |  NUM
    |  '(' E ')'

LL-Parser beschwert sich jetzt noch über die Linksrekursion in F.

---

Linksrekursionen ersetzen

Linksrekursionen würden den Parser in eine Endlosschleife schicken.

F  ::= F '++'
    |  NUM
    |  '(' E ')'

Die folgende Transformation löst die Rekursion auf!

F  ::= NUM F'
    | '(' E ')' F'
F' ::= '++' F'
    |  ε

---

Noch nicht ganz fertig!

LR-Generatoren (wie jison) mögen keine mit * oder + definierten Listen.

FunctionCall ::= Id '(' Arguments? ')'
Arguments    ::= Argument (',' Argument)*

---

Listen ausbauen

Hier muss man die Iteration durch eine Rekursion ersetzen!

FunctionCall ::= Id '(' Arguments? ')'
Arguments    ::= Argument (',' Argument)*

wird also zu:

FunctionCall ::= Id '(' ArgumentList ')'
ArgumentList ::= Arguments
              |  ε
Arguments    ::= Argument Arguments'
Arguments'   ::= ε
              | ',' Arguments

---

Assoziativität

Links oder rechts? Verdammt wichtig bei nicht-assoziativen Operatoren!

Beispiel: Subtraktion mit -!

Was ist der Syntaxbaum zu 10 - 20 - 30 - 40?

---

Linksassoziativität	Rechtsassoziativität
SUB ::= SUB '-' NUM | NUM	SUB ::= NUM '-' SUB | NUM
Linksrekursion auflösen wie vorhin gezeigt.	Linksfaktor eliminieren wie vorhin gezeigt.

---

Manuelles Parsen

Zwei Wege

Rekursiver Abstieg

---

Parsen mittels Rekursion

Zum Beispiel:

Expr ::= Term '+' Expr | Term
Term ::= Primary '*' Term | Primary
Primary ::= NUMBER | '(' Expr  ')'

Man benötigt hierfür eine LL-Grammatik!

---

Parsen mittels Rekursion

Implementierung: Jede Grammatikregel eine Funktion!

Expr ::= Term '+' Expr | Term

wird zu

ExpressionNode Expression() {
  var left = Term();
  if(TryConsume(PLUS)) {
    var right = Expr();
    return new BinaryExprNode(ADD, left, right);
  } else {
    return left;
  }
}

---

Parsen mittels Rekursion

Term ::= Primary '*' Term | Primary

wird zu

ExpressionNode Term() {
  var left = Primary();
  if(TryConsume(MUL)) { //lookahead
    var right = Term();
    return new BinaryExprNode(MULTIPLY, left, right);
  } else {
    return left;
  }
}

---

Parsen mittels Rekursion

Primary ::= NUMBER | '(' Expr  ')'

wird zu

ExpressionNode Primary() {
  var left = Primary();
  switch(lookahead.Type) {
    case NUMBER:
      var result = new NumberLiteral(Convert.ToInt32(lookahead.Text)));
      lookahead++;
      return result;
    case LPARENTHESIS:
      lookahead++;
      var result = Expr();
      Consume(RPARENTHESIS); //throws exception, if not exists
      return result;
  }
  throw new Exception("No match, NUMBER OR '(' expected!");
}

---

Parsen mittels Kombinatoren

Im Prinzip genau das selbe! Nur in Funktionen versteckt.

Grundlegende Operationen auf praktischen Grammatiken sind:

• Konsumierung von Buchstaben 'hallo' (bilden ein Wort)
• Konkatenierung von Wörtern A und B zu AB
• endliche Wiederholung von Wörtern A zu A*
• priorisierte Alternativen von Wörtern A / B / C (Patternmatching oder switch-Anweisung)

---

Parsen mittels Kombinatoren

Beispiel für die Erkennung von Zahlen:

Start = Code(OneOrMore(Digit), text => Convert.ToInt32(text));
Digit = Or(Char('0'), Char('1'), ... Char('8'), Char('9'));

Assert.AreEqual(123, Start.Parse("123"));

Start.Parse("abc"); //throws exception

---

Parsen mittels Kombinatoren

Grundsätzliches Vorgehen:

public ParseResult<string> Parse_X(string input, int postition, X x) {
  //gebe den AST zurück, falls X parsebar, ansonsten NOTHING
}

---

Parsen mittels Kombinatoren

Einfaches Beispiel:

public ParseResult Parse_Char(string input, int postition, Char c) {
  if(input[position] == c)
    return new ParseResult(position, c);
  return ParseResult.Nothing;
}

---

Parsen mittels Kombinatoren

Komplexeres Beispiel:

public ParseResult Parse_Choice(string input, int postition, Choice choice) {
  foreach (var element in choice.Choices)
  {
    var result = element.ParseAt(this, position); //visitor pattern!
    if (result != ParseResult.Nothing)
      return new ParseResult(result.Value, choice, ...);
  }
  return ParseResult.Nothing;
}

---

Abschließende Worte

• Parser mittels Generatoren zu schreiben ist einfach
• manuell zu schreiben ist unnötige sich wiederholende Arbeit (hat aber auch etwas meditatives xD...)
• empfohlenes Vorgehen:
  • Grammatik und Grammatiktests ausschreiben
  • Syntaxbaum generieren lassen
  • Syntaxbaum validieren
  • aus dem Baum das Endartefakt generieren

---

Danke für die Aufmerksamkeit!

Happy hacking!