Grundlagen

Parser

Ein Parser ist ein Programm, das einen Text oder Token als Eingabe erhält. Diese Eingabe wird syntaktisch analysiert und in eine logische Struktur umgewandelt. Der Text kann zum Beispiel eine Programmiersprache, eine XML-Datei aber auch ein arithmetischer Ausdruck oder Datenbankbefehl sein. Die Ausgabe eines Parsers ist normalerweise ein Syntaxbaum oder Programmbaum. Dieser Syntaxbaum wird anhand der gegebenen Grammatik erstellt, wobei diese den Sprachumfang bzw. die Ableitungsregeln der zu analysierenden Sprache umfassen muss. Entspricht die Eingabe nicht der gegebenen Syntax, so sind entsprechende Fehlermeldungen zu generieren.

Grammatik

Für die Entwicklung eines Parsers ist zunächst die Definition einer Grammatik notwendig, damit der Parser den einzulesenden Text erkennen und strukturieren kann. Eine kontextfreie Grammatik ist ein Quadrupel $G=(T,N,P,S)$ wobei gilt:

$T:$ ist ein Alphabet von Terminalsymbolen.

$N:$ ist ein Alphabet von nichtterminalen Symbolen und beschreiben strukturierte Einheiten.

$P:$ ist eine Menge von Produktionsregeln. Eine Produktionsregel besteht aus einem Paar von Nichtterminal und einer Folge von Nichtterminal- und/oder Terminalsymbolen. Produktionsregeln sind auch die Ersetzungsregeln.

$S:$ ist das Startsymbol. Die Menge aller aus dem Startsymbol $S$ ableitbaren Terminalsymbolen $T$ ist die erzeugte Sprache $G$ .

mehrdeutige Grammatik

Im folgenden ist eine Grammatik $G1$ für arithmetische Ausdrücke gegeben.

$G1 = (T,N,P,S)$

$T = \{ num,+,-,*, / \}$

$N = \{ E \}$

$P = \{ E \}$

$E = \{ E -> num \vert E+E \vert E*E \vert E-E \vert E/E \}$

$S = E$

Hier steht $E$ für $expression$ .

Als Beispiel wird folgender Ausdruck betrachtet 10+2 .

Der Parser wird diesen Ausdruck von links nach rechts lesen, wobei ausgehend vom Startsymbol, E sich wie folgt ableiten lässt: $E-> E + E -> num + E -> num + num$ . Anhand dieser Ableitungsfolge lässt sich der zugehörige Syntaxbaum erstellen und wie folgt darstellen.

Syntaxbaum 1

Der dargestellte Syntaxbaum ist zunächst ausgehend von der Wurzel von oben nach unten aufgebaut. Dieses Prinzip nennt sich Topdown Analyse. Desweiteren lässt sich feststellen, dass sich an den Knoten die nichtterminalen Symbole und an den Blättern die terminalen Symbole befinden.

Als weiteres Beispiel betrachtet man das Terminalwort 4*5-8 und erstellt ebenfalls die Ableitungsfolge und den dazugehörigen Syntaxbaum.

$E -> E * E -> num * E -> num * E - E -> num * num - E -> num * num - num$

$E -> E - E -> E - num -> E * E - num -> num * E - num -> num * num - num$

Syntaxbaum 2 & 3

Hierbei lässt sich feststellen, dass sich für den gleichen Ausdruck mehrere Syntaxbäume erstellen lassen. Diese Syntaxbäume entstehen durch Anwendung unterschiedlicher Produktionsregeln. Das Problem hierbei liegt in der mehrdeutigen Semantik. Es darf nicht sein, dass ein Ausdruck unterschiedliche Bedeutung haben kann. Das Ergebnis muss durch die Grammatik eindeutig definiert sein. Mehrdeutigkeiten sind bei der Entwicklung einer Grammatik zu vermeiden. Ein möglicher Lösungsansatz ist zum Beispiel die Festlegung von Prioritäten, Assoziativitäten oder eine natürlich strukturierte Grammatik zum Beispiel durch Klammerung.

eindeutige Grammatik

Betrachtet man die gegebene Grammatik $G2$ .

$G2 = (T,N,P,S)$

$T = \{ num,+,-,*, / \}$

$N = \{E,D,F\}$

$P = \{E -> E + D \vert E - D \vert D, D -> D * F \vert D / F \vert F, F -> num \}$

$S = E$

$F$ steht für $factor$ . Durch das zusätzliche Symbol $F$ ist eine links Assoziativität definiert und eine Mehrdeutigkeit ausgeschlossen.

Wird für den gleichen Ausdruck 4*5-8 der dazugehörige Syntaxbaum betrachtet, so ist zu erkennen, dass vor der Berechnung des Ausdrucks E - D der Kindknoten D * F berechnet werden muss. Desweiteren ist festzuhalten, dass für den Ausdruck nur noch ein Syntaxbaum erstellt werden kann.

Syntaxbaum 4

Durch die Regel $D -> D * F \vert D / F \vert F$ ist die links Assoziativität festgelegt worden. Tauscht man zunächst den Ausdruck durch folgende Regel aus $D -> F * D \vert F / D \vert F$ so lässt sich eine rechts Assoziativität implementieren.

Linksrekursion

Bei der gegebenen Grammatik $G2$ aus dem Abschnitt   kann die Produktion der Form $A -> A alpha$ zu Problemen führen. Gemeint ist hierbei, dass das Nichtterminalsymbol $A$ auf der rechten Seite der Produktion wieder ganz links auftritt (Rekursion). Betrachtet man einen Ausschnitt der bekannten Regeln $E -> E + D \vert D$ , und überlegt sich eine mögliche Implementierung, so könnte diese wie folgt aussehen:

void E() {
  E();
  Symbol(); // Symbol + ueberlesen!
  T();
}

Bei der Betrachtung der gegebenen Implementierung wird sich E() rekursiv aufrufen welches unwiederbringlich zu einem Stacküberlauf führen wird. Dieser Implementierungsfehler lässt sich jedoch durch folgende Änderung der Grammatik beheben $E -> D + E \vert D$ . Durch diese Änderung wurde aus einer Linksrekursion eine Rechtsrekursion.