Compilerbau/Kapitel 2: Syntaxanalyse

Aus Halloserv Wiki

Nachdem der Lexer den Quellcode in eine Liste von Token-Attribut Paaren aufgespalten hat, geht es nun darum, die syntaktische Struktur des Quellprogrammes zu erkennen. Ziel des zur syntaktischen Analyse eingesetzten Parsers ist es, aus der gegebenen Liste einen Ableitungsbaum (bzw. einen abstrakten Syntaxbaum, AST) zu bauen, der die Struktur des Programmes enkodiert. Um die Struktur zu definieren, und auch zu ihrer Erkennnung, benutzt man kontextfreie Grammatiken (KFG). KFGs haben den Vorteil, dass sie ein einfacher und verständlicher Formalismus sind, für viele Fälle eine Lösung für das Wortproblem in $O (n)$ liegt und es etliche Tools gibt, die Parser aus KFGs konstruieren (z.B. yacc, bison, antlr, javacc).

Beispiel: Ausdrucksgrammatik

Diese Grammatik klammert Operatoren nach links und beachtet Punkt- vor Strichrechnung.

$\begin{array}{ll} T & \to E | T + E \\ E & \to F | E * F \\ F & \to x | 2 | (T) \end{array}$

Für die Eingabe x + x + x erhält man dann diesen Ableitungsbaum:

zurück zur Compilerbau Übersicht

Inhaltsverzeichnis

1 Arten von Parsern
2 kontextfreie Grammatiken
3 Top-Down Parser mit Recursive Descent
4 Bottom-Up / Shift Reduce Parser
- 4.1 LR(0) Parser
- 4.2 Parsen mit dem Automaten
5 Kanonisches LR(k) Parsing
6 Praktikable Methoden für LR Parsing mit Lookahead
- 6.1 Simple LR
- 6.2 Lookahead LR
7 Ausgabe des Parsers
- 7.1 Ableitungsbaum
- 7.2 abstrakte Syntax

Arten von Parsern

Es existieren zwei grundsätzliche Arten von Parsern, Top-Down/Predictive Parser und Bottom-Up/Shift-Reduce Parser. Top-Down Parser bauen den Ableitungsbaum von der Wurzel zu den Blättern auf (Tiefensuche), während Bottom-Up Parser den Aufbau bei dem linkesten Blatt beginnen und zur Wurzel fortsetzen.

kontextfreie Grammatiken

So wie der Lexer mit regulären Ausdrücken und DFAs arbeitet, brauchen wir für den Parser die kontextfreie Grammatik. Sie wird in diesem Abschnitt definiert.

Definition: Wörter

Sei $M$ ein Alphabet und $M *$ Worte über $M$ . Dann ist

$\epsilon \in M^*$ das leere Wort
$|a_1, \ldots, a_n| = n$ Länge eines Wortes
$w^k = \underbrace{w \ldots w}_{k-mal}$ Wiederholung
$w{\downarrow}k = a_1 \ldots a_{min(k,n)}$ das k-Präfix von $w$ für $w = a_1 \ldots a_n$

Definition: kontextfreie Grammatik

Eine kontextfreie Grammatik ist ein 4-Tupel $G = (N, T, P, S)$ , wobei

$N$ eine Menge von Nichtterminalen Symbolen,
$T$ eine Menge von Terminalsymbolen,
$V = N \cup T$ die Vereinigung von Nichtterminalen und Terminalen,
$P \subseteq N \times V^*$ eine endliche Menge von Produktionen und
$S \in N$ das Startymbol darstellen.

Konvention: Grammatiksymbole

In den kommenden Abschnitten sind diese Symbole wie folgt definiert:

$A, B, C, E \in N$
$\xi, \rho, \tau \in T^*$
$\alpha, \beta\, \gamma, \delta, \nu, \mu \in V^*$
$X, Y, Z \in V$

Alle angegebenen Grammatikproduktion sind weiterhin Element in $P$

Defintion: Ableitungsrelation

Die Ableitungsrelation $\Rightarrow$ bezüglich $G$ , ist definiert als

$\Rightarrow \subseteq V^* \times V^*$ : $\alpha \Rightarrow \beta$ genau dann, wenn $α = α 1 A α 2,β = α 1 γα 2$ und $A \to \gamma$ . Es gilt weiterhin

$\overset{*}{\Rightarrow}$ ist die reflexive und transitive Hülle von $\Rightarrow$ , $\alpha_1 \overset{*}{\Rightarrow} \alpha_n$ , falls eine Ableitung $\alpha_1 \Rightarrow \alpha_2 \Rightarrow \ldots \Rightarrow \alpha_n$ von $α 1$ nach $α n$ , $n \geqslant 1$ existiert.
$\alpha \in V^*$ ist Satzform, falls $S \overset{*}{\Rightarrow} \alpha$ .

Definition: Linksableitungsrelation

In einer Linksableitungsrelation $\Rightarrow^l \subseteq V^* \times V^*$ wird immer das linkeste Nichtterminal abgeleitet.

$\xi{A}\beta \Rightarrow^l \xi\alpha\beta$ , falls $A \to \alpha$ (beachte, dass $\xi \in T^*$ ).

Die Linkssatzform sowie $\overset{*}{\Rightarrow}^l$ sind analog zur Ableitungsrelation definiert.

Top-Down Parser mit Recursive Descent

Dieser Abschnitt spezifiziert einen Parser formal. Wir beginnen damit, den Parser als nicht-deterministische Funktion zu entwerfen um ihn dann zu transformieren und vereinfachen. Schliesslich werden wir ein Kriterium für Determinismus suchen (dies schränkt die Grammatik ein).

Gegeben: KFG $G$ mit $L = L (G)$

Gesucht: Ein Parser für $L$ .

Definition: Parser

Ein Parser für $L$ ist eine Funktion $P_L:T^* \to \mathcal{P}(T^*)$ mit $P_L(w) = \lbrace u | v \in L, w = vu \rbrace$ .

Man erhält $\tau \in P_L(\rho\tau) \Leftrightarrow \rho \in L$ . Ein Spezialfall ist $v \in L \Leftrightarrow \epsilon \in P_L(v)$ .

Notation:

[α]

Für $\alpha \in V^*$ betrachte $L(\alpha) = \lbrace w \in T^*|\alpha \overset{*}{\Rightarrow}w \rbrace$ , beziehungsweise $[α]: = P L (α)$ .

Man kann nun aus der Definition und Struktur von $α$ mit konstruktiver Induktion (Fallunterscheidung über $α$ ) eine Implementierung für $[α]$ bestimmen:

Implementierung:

[α]

$\begin{array}{lrl} \alpha = \epsilon: & [\epsilon](w) & = \lbrace u | \epsilon \overset{*}{\Rightarrow} v, w = vu \rbrace \\ & & = \lbrace w \rbrace \\ \\ \alpha = X\beta: & [X\beta](w) & = \lbrace u | X\beta \overset{*}{\Rightarrow} v, w = vu \rbrace \\ & & = \lbrace u | X \overset{*}{\Rightarrow} v_1, \beta \overset{*}{\Rightarrow} v_2, w = v_1v_2u \rbrace \\ & & = \lbrace u | X \overset{*}{\Rightarrow} v_1, \beta \overset{*}{\Rightarrow} v_2, w = v_1w', w' = v_2u \rbrace \\ & & = \lbrace u | X \overset{*}{\Rightarrow} v_1, w = v_1w', \beta \overset{*}{\Rightarrow} v_2, w' = v_2u \rbrace \\ & & = \lbrace u | w' \in [X](w), u \in [\beta](w') \rbrace \\ & & = \bigcup \lbrace [\beta](w') | w' \in [X](w) \rbrace \\ \\ \alpha = x \in T: & [x](x_1 \ldots x_n) & = \begin{cases} \lbrace x_2 \ldots x_n \rbrace & \mbox{falls} x = x_1 \\ \emptyset & \mbox{sonst} \end{cases} \\ \\ \alpha = A \in N: & [A](w) & = \lbrace u | A \overset{*}{\Rightarrow} v, w = vu \lbrace \\ & & = \lbrace u | A \to \beta \in P, \beta \overset{*}{\Rightarrow} v, w = vu \rbrace \\ & & = \underset{A \Rightarrow \beta}{\bigcup} \lbrace u | \beta \overset{*}{\Rightarrow} v, w = vu \rbrace \\ & & = \underset{A \Rightarrow \beta}{\bigcup} [\beta](w) \end{array}$

Beispiel: Parser für Ausdrucksgrammatik

$\begin{array}{ll} [T](w) & = [E](w) \cup [T+E](w) \\ & = [E](w) \cup \bigcup \lbrace [+E](\rho) | \rho \in [T](w) \rbrace \\ {}[E](w) & = [F](w) \cup [E*F](w) \\ {}[F](w) & = [x](w) \cup [2](w) \cup [(T)](w) \end{array}$

Diese Spezifikation wäre einfach in ein Programm umzusetzen. Wie man an diesem Beispiel allerdings gut sieht, gibt es zwei Probleme:

Die Definition des Parsers ist nicht deterministisch: $[A](w)$ exploriert alle Teile der rechten Seite einer Produktion. Dies kann dazu führen, dass die Implementation exponentiell zum Input-String ist.
Parser rufen sich selbst mit dem gleichen Argument auf (siehe z.B. $[X](w)$ ), was zu Endlosrekursion führt. Alle Rekursiv-absteigenden Parser, die links-rekursive Regeln enthalten (Regeln, deren linke Seite auch als erstes Symbol der rechten Seite auftaucht), zeigen dieses Verhalten.

Zu beiden Problemen gibt es eine Lösung, die in den kommenden Abschnitten behandelt wird: Auflösen von Links-Rekursion und Lookahead.

Links-Rekursion

Wie vorher bemerkt, führt Links-Rekursion zu einer Endlosschleife im Parser. Hier wird erklärt, wie man sie auflöst.

Definition: Links-Rekursion

Eine Grammatik ist linksrekursiv, wenn ein Nichtterminal $A \in N$ existiert, das linksrekursiv ist.

Ein Nichtterminal $A \in N$ ist linksrekursiv, falls gilt $A \overset{+}{\Rightarrow} A\alpha$ , im speziellen ist es direkt linksrekursiv, falls gilt $A \to A\alpha \in P$ .

Um die Linksrekursion zu eliminieren, sind zwei Schritte nötig. Einmal muss die direkte Linksrekursion am Nichtterminal $A$ beseitigt werden, und zum anderen die allgemeine Rekursion, d.h. $G$ muss zykelfrei und frei von $ε$ -Produktionen sein.

Verfahren: Eliminieren direkter Linksrekursion

Seien $A \to A\alpha_1 | \ldots | A\alpha_m | \beta_1 | \ldots | \beta_k$ alle Regeln für $A$ (mit $β i$ startet nicht mit $A$ ). Dann kann man die Linksrekursion entfernen, in dem man die Regeln mit diesen neuen ersetzt - die neue Grammatik erkennt die gleiche Sprache wie die ursprüngliche:

$A \to \beta_1 A' | \ldots | \beta_k A'$

$A' \to \alpha_1A' | \ldots | \alpha_mA' | \epsilon$

Verfahren: Eliminieren allgemeiner Linksrekursion

Wähle die Reihenfolge $A_1, \ldots, A_n$ für Nichtterminale.

for i = 1 to n

for j = 1 to i - 1

Ersetze alle Produktionen der Form $A_i \to A_j\alpha$ mit $j < i$ und $A_j \to \delta_1 | \ldots | \delta_k$ durch $A_i \to \delta_1\alpha | \ldots | \delta_k\alpha$
Entferne direkte Linksrekursion für $A i$
Gibt es eine Produktion $A_k \to A_l\alpha$ und $k \leqslant i$ , dann ist $l > i$ (d.h. $l$ wird noch bearbeitet werden)

Beispiel: Eliminierung Linksrekursion in Ausdrucksgrammatik

$\begin{array}{lcl} T & \to & ET' \\ T' & \to & +ET' | \epsilon \\ E & \to & FE' \\ E' & \to & *FE' | \epsilon \\ F & \to & x | 2 | (T) \end{array}$

Lookahead

Wie vorher bemerkt, ist es ein Problem, dass der Parser nicht weiss, welcher Teil der rechten Seite zum Weitergehen verwendet werden soll. Würde der Parser alle Möglichkeiten ausprobieren, würde das zu einem Rechenaufwand führen, der exponentiell zur Eingabe ist. Um dieses Problem zu lösen, wird der Lookahead eingesetzt. Lookahead bedeutet, dass der Parser einige ( $k$ ) Symbole im Input vorausschaut, um zu erkennen, welche rechte Regelseite sinnvoll ist und welche nicht. Als Ergebnis erhält man einen Parser, der linear in der Größe der Eingabe arbeitet.

Um den Lookahead zu realisieren, verwenden wir zwei Funktionen, $f i r s t k$ und $f o l l o w k$ .

Definition:

f i r s t k, f o l l o w k

$first_k: V^* \to T^{\leqslant k}$ (bezüglich einer KFG)

$first_k(\alpha) = \lbrace w{\downarrow}k | \alpha \overset{*}{\Rightarrow} w \in T^* \rbrace$

$follow_k: N \to \mathcal{P}(T^k)$

$follow_k(A) = \lbrace w | S \overset{*}{\Rightarrow} \alpha{A}\beta, w \in first_k(\beta) \rbrace$

Man kann diese Funktionen nun verwenden, um die oben gestellte Frage nach der korrekten rechten Seite zu beantworten. Betrachtet man diese Ableitung: $S \overset{*}{\Rightarrow} \rho{A}\beta \Rightarrow \rho\alpha\beta \overset{*}{\Rightarrow} \rho\xi$ , so dass der Parser $[A]$ die Entscheidung für die Regel $A \to \alpha$ machen muss, wenn er $ξ$ in der Eingabe (genauer die ersten $k$ Zeichen von $ξ$ ) sieht. Wir können nun berechnen, das das k-Präfix von $ξ$ folgende Eigenschaft hat:

Eigenschaft: k-Präfix

$\xi{\downarrow}k \in first_k(\alpha\beta) = (first_k(\alpha)first_k(\beta)){\downarrow}k \subseteq (first_k(\alpha)follow_k(A)){\downarrow}k$

Das führt uns zur Definition der Lookahead-Menge einer Produktion und starken LL(K)-Grammatiken (das erste L steht für "von links nach rechts parsbar", das zweite für "generiert Linksableitung").

Definition: LL(k) Lookahead

Der LL(k) Lookahead einer Produktion berechnet sich wie folgt:

$LLLA_k(A \to \alpha) := (first_k(\alpha)follow_k(A)){\downarrow}k$

Eine Grammatik ist eine starke LL(K)-Grammatik, wenn für alle Regeln $A \to \alpha, A \to \beta, \alpha \neq \beta$ gilt: $LLLA_k(A \to \alpha) \cap LLLA_k(A \to \beta) = \emptyset$ .

Wir können nun eine deterministische Parserfunktion für Nichtterminale konstruieren:

Konstruktion: deterministischer Parser

$[A](w) = \begin{cases} [\alpha_1](w), & w{\downarrow}k \in LLLA_k(A \to \alpha_1) \\ \vdots \\ {}[\alpha_n](w), & w{\downarrow}k \in LLLA_k(A \to \alpha_n) \end{cases}$

Definition: LL(K) Grammatik

Eine KFG ist eine LL(K)-Grammatik, falls für alle Ableitungen der Form:

$S \overset{*}{\Rightarrow}^l wA\alpha \Rightarrow^l w\beta\alpha \overset{*}{\Rightarrow}^l wu$

$S \overset{*}{\Rightarrow}^l wA\alpha \Rightarrow^l w\gamma\alpha \overset{*}{\Rightarrow}^l wv$

gilt, dass $u{\downarrow}k = v{\downarrow}k$ impliziert $β = γ$ .

Satz:

L L (1)

Jede LL(1) Grammatik ist auch stark LL(1).

Beispiel:

L L (2)

Für $k \geqslant 2$ gibt es Grammatiken, die nicht stark LL(k) sind.

Betrachte $G$ mit den Produktionen $S \to aAaa | bAba, A \to b | \epsilon$ . G ist $L L (2)$ , da die in fett gehaltenen Abschnitte in beiden Fällen disjunkt sind:

$S \Rightarrow aAaa \begin{array}{ll} & a\mathbf{ba}a \\ \nearrow \\ \searrow \\ & a\mathbf{aa} \end{array}$

$S \Rightarrow bAba \begin{array}{ll} & b\mathbf{bb}a \\ \nearrow \\ \searrow \\ & b\mathbf{ba} \end{array}$

Die Bedingung für stark $L L (2)$ ist jedoch nicht erfüllt, da die Lookaheads für die Produktionen von $A$ nicht disjunkt sind:

$LLLA_2(A \to b) = (first_2(b)follow_2(A)){\downarrow}k = \lbrace ba, bb \rbrace$

$LLLA_2(A \to \epsilon) = (first_2(\epsilon)follow_2(A)){\downarrow}k = \lbrace aa, ba \rbrace$

Implementierung des Lookaheads

Die Implementierung von $f i r s t k$ betreiben wir ähnlich wie beim Parser durch Fallunterscheidung über $α$ .

Implementierung:

f i r s t k

$\begin{array}{lrl} \alpha = \epsilon: & first_k(\epsilon) & = \lbrace \epsilon \rbrace \\ \\ \alpha = X\beta: & first_k(X\beta) & = \lbrace (uv){\downarrow}k | X \overset{*}{\Rightarrow} u, \beta \overset{*}{\Rightarrow} v \rbrace \\ & & = \lbrace (u{\downarrow}k)(v{\downarrow}k) | X \overset{*}{\Rightarrow} u, \beta \overset{*}{\Rightarrow} v \rbrace \\ & & = (first_k(X)first_k(\beta)){\downarrow}k \end{array}$

Wir müssen nun noch eine Fallunterscheidung über $X$ durchführen:

$\begin{array}{lrl} X = a \in T: & first_k(a) & = \lbrace a \rbrace \\ \\ X = A \in N: & first_k(A) & = \lbrace w{\downarrow}k | A \overset{*}{\Rightarrow} w \rbrace \\ & & = \lbrace w{\downarrow}k | A \Rightarrow \alpha \overset{*}{\Rightarrow} w, A \to \alpha \rbrace \\ & & = \underset{A \to \alpha}{\bigcup} first_k(\alpha) \end{array}$

Wie man leicht sieht, hat diese Implementierung noch ein Problem: sie ist rekursiv. Man kann aber die Implementierung von $f i r s t k$ als Gleichungssystem mit der Unbekannten $first_k(A), A \in N$ auffassen. Dann ist eine Lösung der Vektor $\overline{L} = (L_A \subseteq T^{\leqslant k} | A \in N) \in \textstyle \prod_{A \in N} \mathcal{P}(T^{\leqslant k})$ von Mengen von terminalen Strings.

Beispiel: Fixpunktiteration für die modifizierte Ausdrucksgrammatik

Hier nutzen wir eine Fixpunktiteration, um den Vektor $\overline{L}$ zu berechnen. Um die nächste Iterationsstufe ( $L A'$ ) zu erreichen, müssen wir jeweils auf die aktuelle ( $L A$ ) zurückgreifen:

$\begin{array}{ll} L_T' & = (L_EL_{T'}){\downarrow}1 \\ L_{T'}' & = (+L_EL_{T'}){\downarrow}1 \cup \lbrace \epsilon \rbrace \\ L_E' & = (L_FL_{E'}){\downarrow}1 \\ L_{E'}' & = (*L_FL_{E'}){\downarrow}1 \cup \lbrace \epsilon \rbrace \\ L_F' & = \lbrace x \rbrace \cup \lbrace 2 \rbrace \cup ((L_T)){\downarrow}1 = \lbrace x, 2 \rbrace \cup ((L_T)){\downarrow}1 \end{array}$

Berechne $f i r s t 1 (A)$ für alle Nichterminale $A \in N$ :

$\begin{array}{c|c|c|c|c|c} & T & T' & E & E' & F \\ 0 & \emptyset & \emptyset & \emptyset & \emptyset & \emptyset \\ 1 & \emptyset & \lbrace \epsilon \rbrace & \emptyset & \lbrace \epsilon \rbrace & \lbrace 2,x \rbrace \\ 2 & \emptyset & \lbrace \epsilon \rbrace & \lbrace 2,x \rbrace & \lbrace *, \epsilon \rbrace & \lbrace 2,x \rbrace \\ 3 & \lbrace 2, x \rbrace & \lbrace +, \epsilon \rbrace & \lbrace 2,x \rbrace & \lbrace *, \epsilon \rbrace & \lbrace 2,x \rbrace \\ 4 & \lbrace 2, x \rbrace & \lbrace +, \epsilon \rbrace & \lbrace 2,x \rbrace & \lbrace *, \epsilon \rbrace & \lbrace 2,x, ( \rbrace \\ 5 & \lbrace 2, x \rbrace & \lbrace +, \epsilon \rbrace & \lbrace 2,x,( \rbrace & \lbrace *, \epsilon \rbrace & \lbrace 2,x, ( \rbrace \\ 6 & \lbrace 2, x, ( \rbrace & \lbrace +, \epsilon \rbrace & \lbrace 2,x,( \rbrace & \lbrace *, \epsilon \rbrace & \lbrace 2,x, ( \rbrace \end{array}$

Nach Schritt 6 verändern sich die Mengen nicht mehr - der Fixpunkt ist erreicht. Um den Lookahead zu berechnen, brauchen wir noch die $f o l l o w 1$ Mengen, diese berechnen sich ähnlich:

$follow_k'(A) = \bigcup_{B \to \beta A\alpha \in P} first_k(\alpha)follow_k(B)$

Für unsere modifizierte Ausdrucksgrammatik folgen deshalb diese $f o l l o w 1'$ Mengen:

$\begin{array}{ll} follow_1'(T) & = (first_1(\ )\ )follow_1(F)){\downarrow}1 \\ follow_1'(T') & = follow_1(T) \cup follow_1(T') \\ follow_1'(E) & = (first_1(T')follow_1(T)){\downarrow}1 \cup (first_1(T')follow_1(T')){\downarrow}1 \\ follow_1'(E') & = follow_1(E) \cup follow_1(E') \\ follow_1'(F) & = (first_1(E')follow_1(E)){\downarrow}1 \cup (first_1(E')follow_1(E')){\downarrow}1 \end{array}$

Berechne $f o l l o w 1 (A)$ für alle Nichtterminale $A \in N$ :

$\begin{array}{c|c|c|c|c|c} & T & T' & E & E' & F \\ 0 & \lbrace \epsilon \rbrace^{*)} & \emptyset & \emptyset & \emptyset & \emptyset \\ 1 & \lbrace \epsilon \rbrace & \lbrace \epsilon \rbrace & \lbrace +,\epsilon \rbrace & \emptyset & \emptyset \\ 2 & \lbrace \epsilon \rbrace & \lbrace \epsilon \rbrace & \lbrace +,\epsilon \rbrace & \lbrace +,\epsilon \rbrace & \lbrace +,*,\epsilon \rbrace \\ 3 & \lbrace \epsilon, ) \rbrace & \lbrace \epsilon \rbrace & \lbrace +,\epsilon \rbrace & \lbrace +,\epsilon \rbrace & \lbrace +,*,\epsilon \rbrace \\ 4 & \lbrace \epsilon, ) \rbrace & \lbrace \epsilon, ) \rbrace & \lbrace +,\epsilon, ) \rbrace & \lbrace +,\epsilon \rbrace & \lbrace +,*,\epsilon \rbrace \\ 5 & \lbrace \epsilon, ) \rbrace & \lbrace \epsilon, ) \rbrace & \lbrace +,\epsilon, ) \rbrace & \lbrace +,\epsilon, ) \rbrace & \lbrace +,*,\epsilon, ) \rbrace \end{array}$

$* )$ In der $f o l l o w$ Menge des Startsymbols muss $ε$ enthalten sein.

Auch hier haben wir einen Fixpunkt erreicht und die $f o l l o w 1$ Mengen erhalten. Nun können wir den Lookahead berechnen:

$\begin{array}{ll} LLLA_1(T' \to +ET') & = (first_1(+ET')follow(T')){\downarrow}1 = \lbrace + \rbrace \\ LLLA_1(T' \to \epsilon) & = (first_1(\epsilon)follow(T')){\downarrow}1 = \lbrace \epsilon, ) \rbrace \\ LLLA_1(E' \to *TE') & = (first_1(*TE')follow(E')){\downarrow}1 = \lbrace * \rbrace \\ LLLA_1(E' \to \epsilon) & = (first_1(\epsilon)follow(E')){\downarrow}1 = \lbrace +, \epsilon, ) \rbrace \end{array}$

Wie man hier sieht, ist die Grammatik stark LL(1), d.h. $L L (1)$ . Der rekursiv-absteigende Parser kann also mit einem Symbol Lookahead deterministisch werden.

Bottom-Up / Shift Reduce Parser

Der Bottom-Up Parser baut eine Rechtsableitung von den Blättern zur Wurzel auf (d.h. rückwärts). Die Startproduktion $S \to \alpha$ ist die letzte Produktion, die der Parser bearbeitet. Man kann sich den Parser als Stackmaschine vorstellen:

Startkonfiguration: $\epsilon \bullet w$ , wobei $ε$ den leeren Stack und $w$ das Eingabewort darstellt. Der Parser geht dann wie folgt vor:

In Konfiguration $\gamma \bullet w$

Gibt es eine rechte Regelseite auf dem Stack $γ = αβ$ und es existiert eine Regel $A \to \beta$ , dann ist der neue Zustand $\alpha{A} \bullet w$ (reduce)
Ist die Eingabe nicht leer, kann sie aufgespalten werden in ein Symbol und den Rest: $w = a w'$ . Der neue Zustand ist dann $\gamma{a} \bullet w'$ (shift)
Falls $\gamma \bullet w = S \bullet \epsilon$ wurde das Eingabewort erkannt

Man wiederholt die einzelnen Schritte bis keine weitere Aktion mehr möglich ist. Dabei kann nichtdeterministisches Verhalten auftreten, weil ein shift fast immer möglich ist, bei der Aufteilung $γ = αβ$ (reduce) und wenn es mehrere Nichtterminale mit gleicher rechter Seite gibt.

Beispiel: shift reduce der Ausdrucksgrammatik

parse $2 + x * x$

$\begin{array}{ll} \bullet 2 + x * x & \mbox{shift} \\ 2 \bullet + x * x & \mbox{reduce } F \to 2 \\ F \bullet + x * x & \mbox{reduce } E \to F \\ E \bullet + x * x & \mbox{reduce } T \to E \\ T \bullet + x * x & \mbox{shift} \\ T + \bullet x * x & \mbox{shift} \\ T + x \bullet * x & \mbox{reduce } F \to x \\ T + F \bullet * x & \mbox{reduce } E \to F \\ T + E \bullet * x & \mbox{shift} \\ T + E * \bullet x & \mbox{shift} \\ T + E * x \bullet \epsilon & \mbox{reduce } F \to x \\ T + E * F \bullet \epsilon & \mbox{reduce } E \to E * F \\ T + E \bullet \epsilon & \mbox{reduce } T \to T + E \\ T \bullet \epsilon & \mbox{accept} \end{array}$

Der so beschriebene Parser ist auch bekannt als LR Parser (L für "von links nach rechts", R für "Rechtsableitung"). Die Arbeitsweise dieses Stackparsers wird vollständig durch einen endlichen Automaten bestimmt, der auf dem Stack arbeitet: dem charakteristischen Automaten (CA) einer Grammatik. Generalvoraussetzung ist, dass jede Grammatik startseparierbar ist.

Definition: startseparierbar

Eine KFG $G = (N, T, P, S)$ ist startseparierbar, falls $S$ auf keiner rechten Regelseite in $P$ vorkommt. Jede Grammatik kann startsepariert werden durch $G' = (N \cup \lbrace S' \rbrace, T, P \cup \lbrace S' \to S \rbrace, S')$

Definition: Griff, erfolgreiches Präfix

$S \overset{*}{\Rightarrow}^r \gamma{Aw} \Rightarrow^r \gamma\alpha{w}$ mit $A \to \alpha$

$α$ ist Griff für $A \to \alpha$ . Jedes Präfix $γα$ ist ein erfolgreiches Präfix.

Definition: kontextfreies Item, predict Item, reduce Item

Ein kontextfreies Item ist eine Produktion mit einer Position auf der rechten Regelseite:

$\begin{array}{ll} A \to \alpha\beta & \rightarrowtail A \to \alpha \bullet \beta \\ A \to \epsilon & \rightarrowtail A \to \bullet \end{array}$

Ein predict Item ist ein Item der Form $A \to \bullet \gamma$ , ein reduce Item der Form $A \to \gamma \bullet$ .

Definition: gültiges Item

Ein Item $A \to \alpha \bullet \beta$ ist gültig für ein erfolgreiches Präfix $S \overset{*}{\Rightarrow}^r \gamma{Aw} \Rightarrow^r \gamma\alpha\beta{w}$ . Insbesondere gilt: Falls $A \to \alpha \bullet$ gültig: $S \overset{*}{\Rightarrow}^r \gamma{Aw} \Rightarrow^r \gamma\alpha{w}$ .

Definition: charakteristischer Automat

Der charakteristischer Automat $C h a r (G) = (Q,Σ, q 0,δ, F)$ von G erkennt die erfolgreichen Präfixe mit Griff am Ende.

$Q = I t e m s (G)$ Menge der kontextfreien Items von $G$
$Σ = V$
$q_0 = S' \to \bullet S$
$\begin{array}{ll} \delta(A \to \alpha \bullet a\beta, a) & = \lbrace A \to \alpha{a} \bullet \beta \rbrace \\ \delta(A \to \alpha \bullet B\beta, B) & = \lbrace A \to \alpha{B} \bullet \beta \rbrace \\ \delta(A \to \alpha \bullet B\beta, \epsilon) & = \lbrace B \to \bullet \gamma | B \to \gamma \in P \rbrace \end{array}$
$F = \lbrace A \to \alpha \bullet | A \to \alpha \in P \rbrace$

Beispiel: charakteristischer Automat

Beispielgrammatik:

$\begin{array}{ll} S & \to E \\ E & \to F | E * F \\ F & \to x | (E) \end{array}$

LR(0) Parser

Es gilt nun, das Problem des nicht-Determinismus zu lösen. Als ersten Schritt konstruieren wir eine deterministische Version des charakteristischen Automaten, den LR(0) Parser

Definition: predict

Die predict Operation fügt einem Zustand alle durch $ε$ Transitionen erreichbaren Items hinzu: $predict(q) = \lbrace B \to \bullet \gamma | A \to \alpha \bullet C\beta \in q, A \to \alpha \bullet C\beta \Downarrow^+ B \to \bullet \gamma \rbrace$ , wobei gilt: $A \to \alpha \bullet C\beta \Downarrow C \to \bullet \eta \Leftrightarrow C \to \eta \in P$ (d.h. $Item_1 \Downarrow Item_2$ bedeutet, dass man im CA von $I t e m 1$ mit Hilfe einer $ε$ -Transition zu $I t e m 2$ gelangt).

Beispiel: predict für charakteristischer Automat

$\begin{array}{ll} predict(S \to \bullet E) & = \lbrace E \to \bullet F, E \to \bullet E * F, F \to \bullet x, F \to \bullet (E) \rbrace \\ predict(E \to E * \bullet F) & = \lbrace F \to \bullet x, F \to \bullet (E) \rbrace \end{array}$

Definition: Closure einer Item-Menge

Der Abschluss einer Item-Menge $q$ ist definiert als $\overline{q} = q \cup predict(q)$ .

Definition:

L R (0)

Automat

Der $L R (0)$ Automat zu $G$ ist der DFA $A = (Q,Σ,δ, q 0, F)$ mit

$Q = \lbrace q \subseteq Items(G) | q = \overline{q} \rbrace$
$Σ = V$ (Der Automat arbeitet auf Stackworten)
$\delta(q, X) = \overline{\lbrace A \to \alpha{X} \bullet \beta | A \to \alpha \bullet X\beta \in q \rbrace }$
$q_0 = \overline{\lbrace S' \to \bullet S \rbrace}$
$F = \lbrace q \in Q | A \to \gamma \bullet \in q \rbrace$

Mit dem $L R (0)$ Automaten kann man jetzt einen Parser konstruieren. Allerdings ist dieser nur deterministisch, falls die Grammatik LR(0) ist - ansonsten treten Konflikte in den Zuständen des Automaten auf.

Beispiel:

L R (0)

Automat mit Konflikten

Hierzu verwenden wir den Automaten aus dem vorigen Beispiel und bauen ihn in einen $L R (0)$ Automaten um:

Die Indizes in diesem Automaten werden für ein späteres Beispiel benötigt.

Die auftretenden Konflikte lassen sich in shift-reduce und reduce-reduce Konflikte aufteilen. Im obigen Beispiel enthält der Zustand $\lbrace S \to E \bullet, E \to E \bullet * F \rbrace$ einen shift-reduce Konflikt, da sowohl ein shift auf dem Symbol $*$ ausgeführt werden kann, wie auch ein reduce auf dem Nichtterminal $E$ .

Definition: shift-reduce, reduce-reduce Konflikt

Ein shift-reduce Konflikt liegt vor, wenn ein Zustand ein reduce Item $A \to \alpha \bullet$ und ein Item $B \to \alpha \bullet a\beta, a \in T$ enthält.
Ein reduce-reduce Konflikt tritt auf, wenn ein Zustand zwei reduce Item $A \to \alpha \neq B \to \beta$ enthält.

Definition: LR(0) Grammatik

Eine Grammatik $G$ heisst LR(0), falls alle Zustände des zu $G$ gehörenden $L R (0)$ Automaten konfliktfrei sind.

Parsen mit dem Automaten

Um eine Eingabe mit Hilfe des LR(0) Automatens zu parsen, wenden wir so lange eine parse Funktion auf einen Stack mit Automatenzuständen und den verbleibenden Eingabestring an, bis die Eingabe leer ist und der oberste Zustand auf dem Stack ein Item $S \to S' \bullet$ enthält.

<div style="padding-left:4px;" id="Definition: goto & parse">Definition: goto & parse

$\begin{array}{lccl} \mbox{parse}(stack,w) & = & \mathbf{let}\ & q = \mbox{top}(stack)\ \mathbf{in} \\ && & \bigvee \lbrace \mbox{goto}(A, \mbox{pop}(|\alpha|, stack)^\dagger, w) | A \to \alpha \bullet \in q \rbrace \\ && \or & \bigvee \lbrace \mbox{goto}(a, stack, w') | w = aw', A \to \alpha \bullet a\beta \in q \rbrace \\ && \or & \bold{if} \ w = \epsilon \and S' \to S \bullet \in q\ \bold{then}\ \mbox{accept} \\ \\ \mbox{goto}(X, stack, w) & = & \mathbf{let}\ & q = \mbox{top}(stack)\ \mathbf{in} \\ && & \mbox{parse}(\delta(q,X), stack, w) \end{array}$

${}^\dagger$ Die in dieser Definition verwendete Funktion pop gibt den Stack (zweiter Parameter) ohne die obersten $| α |$ (erster Parameter) Einträge zurück.

</div>

Beispiel: Parsen der Eingabe

x * x

Die hier verwendeten Zustandsindizes finden sich im obigen Graphen an den Zuständen wieder.

$\begin{array}{lrcl} \bold{Stack} & \bold{verbleibende}\ \bold{Eingabe} & \bold{Aktion} & \bold{neuer Zustand} \\ q_0 & x * x & \mbox{shift} & q_4 = \mbox{goto}(x, q_0, * x) \\ q_0q_4 & * x & \mbox{reduce} & q_3 = \mbox{goto}(F, q_0, * x) \\ q_0q_3 & * x & \mbox{reduce} & q_1 = \mbox{goto}(E, q_0, * x) \\ q_0q_1 & * x & \mbox{shift} & q_5 = \mbox{goto}(*, q_0q_1, x) \\ q_0q_1q_5 & x & \mbox{shift} & q_4 = \mbox{goto}(x, q_0q_1q_5, \epsilon) \\ q_0q_1q_5q_4 & \epsilon & \mbox{reduce} & q_2 = \mbox{goto}(F, q_0q_1q_5, \epsilon) \\ q_0q_1q_5q_2 & \epsilon & \mbox{reduce} & q_1 = \mbox{goto}(E, q_0, \epsilon) \\ \bot & \epsilon & \mbox{accept} & \end{array}$

Kanonisches LR(k) Parsing

Um die im vorherigen Abschnitt beschriebenen Konflikte aufzuheben, greifen wir auf das bereits bekannte Mittel Lookahead zurück. Wir betrachten hier den kanonischen Weg, Lookahead zu implementieren, der aber sehr aufwendig in der Berechnung ist. Die folgenden Abschnitte zeigen dann effizientere Möglichkeiten auf.

Definition: LR(k) Grammatik

Eine Grammatik $G$ heisst LR(k) Grammatik, falls für alle Ableitungen der Form:

$S \overset{*}{\Rightarrow}^r \gamma{Aw} \Rightarrow^r \gamma\alpha{w}$

$S \overset{*}{\Rightarrow}^r \beta{Bv} \Rightarrow^r \gamma\alpha{v}$

gilt, dass $v{\downarrow}k = w{\downarrow}k$ impliziert $A = B,β = γ$ und $v = w$ ( $γα$ ist der Stackinhalt, Wissen über den Stackinhalt und die nächsten $k$ Symbole reicht zur Entscheidung, welche Produktion greift).

LR(k) Grammatiken haben einige interessante Eigenschaften:

Jede LL(K) Grammatik ist auch eine LR(k) Grammatik.
Für $k \geqslant 1$ kann jede LR(k+1) Grammatik zu einer äquivalenten LR(k) Grammatik umgeformt werden. Daraus ergibt sich, dass zu jeder LR(k) Grammatik eine äquivalente LR(1) Grammatik existiert.
Falls $L$ eine deterministisch erkennbare (mit deterministischem Stackautomaten), kontextfreie Sprache ist, gibt es eine LR(1) Grammatik für $L$ .

Die nun folgende Definition des $L R (k)$ DFA folgt generell der des $L R$ DFA, wobei der grösste Unterschied die hinzugefügten Lookahead Mengen sind.

Definition:

L R (k)

Item

Ein $L R (k)$ Item ist ein Tupel aus Produktion, Position und Lookahead Menge $L \subseteq T^{\leqslant k}$ : $A \to \alpha \bullet \beta (L)$ .

Definition: gültiges Item

Ein Item $A \to \alpha \bullet \beta (L)$ ist gültig, für ein erfolgreiches Präfix $γα$ , falls $S \overset{*}{\Rightarrow}^r \gamma\alpha\beta{w}$ mit $w{\downarrow}k \in L$ .

Lookahead Mengen werden durch predict propagiert:

<div style="padding-left:4px;" id="Definition: predict">Definition: predict

Sei $q$ eine Menge von $L R (k)$ Items. Dann ist $predict(q) = \lbrace C \to \alpha \bullet (M) | B \to \beta \bullet A\gamma (L) \in q, B \to \beta \bullet A\gamma (L) \Downarrow^+ C \to \alpha \bullet (M) \rbrace$ mit $A \to \alpha \bullet B\beta (L) \Downarrow B \to \bullet \gamma ((first_k(\beta){L})\downarrow k)$ .

</div>

Definition: Closure einer Item-Menge

Die Closure einer Item-Menge $q$ ist definiert als $\overline{q} = q \cup predict(q)$ .

Die Definition des $L R (k)$ Automaten ist sehr ähnlich der des $L R (0)$ Automaten:

Definition:

L R (k)

Automat

Der $L R (k)$ Automat zu $G$ ist der DFA $A = (Q,Σ,δ, q 0, F)$ mit

$Q = \lbrace q \subseteq Items(G) | q = \overline{q} \rbrace$
$Σ = V$ (Der Automat arbeitet auf Stackworten)
$\delta(q, X) = \overline{\lbrace A \to \alpha{X} \bullet \beta (L) | A \to \alpha \bullet X\beta (L) \in q \rbrace }$
$q_0 = \overline{\lbrace S' \to S (\lbrace \epsilon \rbrace)\rbrace}$
$F = \lbrace q \in Q | A \to \gamma \bullet (L) \in q \rbrace$

Auch ein $L R (k)$ Automat kann Konflikte enthalten, die zu einem nicht-Determinismus im Parser führen:

Definition:

L R (k)

Konflikte

Ein Zustand $q$ enthält einen shift-reduce Konflikt, falls er die Produktionen $A \to \alpha \bullet (L), B \to \beta \bullet a\gamma (M)$ enthält, mit $L \cap (first_k(a\gamma)M)\downarrow k \neq \emptyset$ .
Ein Zustand $q$ hat einen reduce-reduce Konflikt, wenn gilt: $A \to \alpha \bullet (L), B \to \beta \bullet (M) \in q$ mit $A \to \alpha \bullet \neq B \to \beta \bullet$ und $L \cap M \neq \emptyset$ .

Praktikable Methoden für LR Parsing mit Lookahead

Da die kanonischen Parser häufig zu unhandlich grossen Zustandsautomaten führen, suchen wir einen anderen Weg zum Konstruieren der Parser. Hier bieten sich zwei Methoden an: Simple LR Parsing (SLR) und Lookahead LR Parsing (LALR). Beide arbeiten mit LR(0) Parsern, wie sie weiter oben vorgestellt wurden.

Simple LR

SLR erweitert die Items eines $L R (0)$ Automaten um Lookahead-Informationen in Form der $f o l l o w k$ Mengen, das heisst: $A \to \alpha \bullet \beta (follow_k(A))$ .

Beispiel: Simple

L R (k)

Hier wird der Konflikt aus dem früheren Beispiel durch SLR aufgelöst, die Grammatik ist also $S L R (1)$ :

Lookahead LR

Der Lookahead $L R (k)$ (LALR) wird mit $k = 1$ in fast allen Parsergeneratoren eingesetzt. Anstelle von $f o l l o w k$ verwendet er Lookahead-Informationen, die von der Ableitung abhängig sind. Diese Informationen werden aus dem $L R (0)$ Automaten gewonnen.

Definition:

L A k

Mit $A \to \alpha \bullet \beta \in q$ gilt:

$LA_k(q, A \to \alpha \bullet \beta) = \lbrace w{\downarrow}k | q = \delta^*(q_0, \gamma\alpha), S' \overset{*}{\Rightarrow}^r \gamma{Aw} \rbrace$

Das heißt wir betrachten alle Pfade, die von $q 0$ nach $q$ führen und das Suffix $α$ besitzen; für jedes resultierendes Pfadpräfix $γ$ sehen wir uns alle Ableitungen vom Startsymbol an, die die Form $S' \overset{*}{\Rightarrow}^r \gamma Aw$ haben - die k-Präfixe der $w$ sind dann in der Lookahead Menge des Items $A \to \alpha \bullet \beta$ in $q$ .

Berechnung:

L A k

Man kann den $L A k$ mit drei Schritten berechnen:

Führe $LA_k(q, A \to \alpha \bullet \beta)$ zurück auf $LA_k(q', A \to \bullet \alpha \beta)$ :

$\begin{array}{ll} & La_k(q, A \to \alpha \bullet \beta) \\ = & \lbrace w{\downarrow}k | S' \overset{*}{\Rightarrow}^r \gamma{Aw}, q = \delta^*(q_0, \gamma\alpha) \rbrace \\ = & \lbrace w{\downarrow}k | S' \overset{*}{\Rightarrow}^r \gamma{Aw}, q' = \delta^*(q_0, \gamma), q = \delta^*(q', \alpha) \rbrace \\ = & \lbrace w{\downarrow}k |LA_k(q', A \to \bullet \alpha\beta), q = \delta^*(q', \alpha) \rbrace \\ = & \underset{q = \delta^*(q', \alpha)}{\bigcup} LA_k(q', A \to \bullet \alpha\beta) \end{array}$
Für die predict Items kann ein Gleichungssystem aufgestellt werden, das mit Fixpunktiteration gelöst wird: Setze . Unterscheide nach der Herkunft der predict Items:
- Start-Item $S' \to \bullet S$ :
  
  $\begin{array}{cl} & \widehat{LA_k}(q_0, S')\\ = & \lbrace w{\downarrow}k | S' \overset{*}{\Rightarrow}^r \gamma{Sw}, q_0 = \delta^*(q_0, \gamma) \rbrace\\ \overset{\gamma = w = \epsilon}{=} & \lbrace \epsilon \rbrace \end{array}$
- $A \neq S'$ , d.h. es existiert eine Regel $A \to \bullet \eta \in q$ - diese muss durch die Abschlussoperation ( $\overline{q}$ ) hier her gelangt sein, was wiederum heisst, dass eine Regel $B \to \alpha \bullet A\beta \in q$ existiert, mit $γα = γ 0$ :
  
  $\begin{array}{ll} & \widehat{LA_k}(q, A)\\ = & \lbrace w{\downarrow}k | S' \overset{*}{\Rightarrow}^r \gamma_0{Aw}, q = \delta^*(q_0, \gamma_0) \rbrace \\ = & \lbrace w{\downarrow}k | S' \overset{*}{\Rightarrow}^r \gamma_0{Bv} \Rightarrow^r \gamma\alpha{A}\beta{v} \overset{*}{\Rightarrow}^r \gamma\alpha{Aw}, q = \delta^*(q_0, \gamma\alpha) \rbrace \end{array}$
  Wir wissen, dass gilt: $v{\downarrow}k \in LA_k(q', B \to \alpha \bullet A\beta), q' = \delta^*(q_0, \gamma\alpha)$ , also gilt auch: $w \in (first_k(\beta)LA_k(q, B \to \alpha \bullet A\beta)){\downarrow}k$ .
  $\begin{array}{ll} = & \textstyle \bigcup_{B \to \alpha \bullet A\beta \in q} (first_k(\beta)LA_k(q, B \to \alpha \bullet A\beta ) ){\downarrow}k \\ = & \textstyle \bigcup_{B \to \alpha \bullet A\beta \in q} \textstyle \bigcup_{q = \delta^*(q', \beta)} (first_k(\beta)\widehat{LA_k}(q', B)){\downarrow}k \end{array}$
Für die reduce Items kann man setzen: $LA_k(q, A \to \alpha \bullet) = \textstyle \bigcup_{q = \delta^*(q', \alpha)} \widehat{LA_k}(q', A)$ .

Für $k = 1$ gibt es Algorithmen, die das in den Schritten 2 und 3 erstellte Gleichungssystem in linearer Zeit lösen.

Ausgabe des Parsers

Definition: parse

Ein Parser erzeugt eine Syntaxrepräsentation, d.h. $parse: T^* \to D$ , so dass $unparse: D \to T^*$ , mit $parse \circ unparse = \mbox{id}_D$ .

Es gibt zwei Möglichkeiten der Syntaxrepräsentation, einen Ableitungsbaum und die abstrakte Syntax.

Ableitungsbaum

Definition: Ableitungsbaum

Ein Ableitungsbaum zu $(N, T, P, S)$ ist ein endlicher, geordneter, gerichteter Baum mit Knotenmenge $V$ , so dass jeder Knoten mit einer Produktion $\pi \in P$ markiert ist.

Die Wurzel ist mit der Startporduktion $S\to S'$ markiert
Für jeden Knoten gilt: Mit $mark(v) = A_0 \to w_0A_1w_1\ldots{A_n}w_n$ , hat ein Knoten $v$ die Kinder $v_1,\ldots,v_n$ mit Markierungen $mark(v_i) = A_i \to \alpha_i$ .

Man kann die Produktion $A_0 \to w_0A_1\ldots{A_n}w_n$ als $n$ -stelligen Operator auffassen.

Beispiel: Reduktionen für

2 + x * x

Wir benutzen hierzu die bekannte Ausdrucksgrammatik. Erzeuge den Ableitungsbaum durch Anwenden der reduzierenden Produktionen auf einen Hilfsstack. Der $n$ -stellige Operator wirkt auf die obersten $n$ Stackeinträge.

Der Ableitungsbaum enthält auf diese Weise nutzlose Informationen (d.h. der Term hat keine Bedeutung, im Baum eingekreist), nämlich über Kettenproduktionen und Klammerstrukturen. Stattdessen kann man eine andere Methode wählen, die im nächsten Abschnitt behandelt wird.

abstrakte Syntax

Die Grammatik für die abstrakte Syntax enthält nur die wesentlichen Informationen:

$A \to 2 | x | A * A | A + A$

Für 2+x*x ergibt sich dann folgende Struktur:

<div style="padding-left:4px;" id="Beispiel: abstrakte Syntax für 2+x*x">Beispiel: abstrakte Syntax für 2+x*x

</div>

Diese Struktur entspricht auch Typdefinitionen in OCaml:

Code: arith

type arith = Two | X | Add of arith * arith | Mul of arith * arith

Und der Ausdruck würde dann folgendermassen aussehen:

<div style="padding-left:4px;" id="Beispiel: 2+x*x">Beispiel: 2+x*x

Add Two (Mul x x)

</div>

Compilerbau/Kapitel 2: Syntaxanalyse

Aus Halloserv Wiki

Inhaltsverzeichnis

Arten von Parsern

kontextfreie Grammatiken

Top-Down Parser mit Recursive Descent

Links-Rekursion

Lookahead

Implementierung des Lookaheads

Bottom-Up / Shift Reduce Parser

LR(0) Parser

Parsen mit dem Automaten

Kanonisches LR(k) Parsing

Praktikable Methoden für LR Parsing mit Lookahead

Simple LR

Lookahead LR

Ausgabe des Parsers

Ableitungsbaum

abstrakte Syntax

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge