Ableitung (Informatik)

Als Ableitung wird in der theoretischen Informatik der Vorgang bezeichnet, ein Wort nach den Regeln einer formalen Grammatik zu erzeugen.

Unter einem Wort versteht man eine beliebige Zeichenkette, also eine endliche Folge von Symbolen. Eine formale Grammatik ist ein mathematisches Modell, das eine Menge solcher ableitbaren Wörter festlegt. Diese Menge nennt man eine formale Sprache. Das einmalige Ersetzen von einem Teilabschnitt einer Zeichenkette, gemäß einer der Regeln der formalen Grammatik, stellt einen Ableitungsschritt dar. Durch die formale Grammatik werden auch die Symbole festgelegt, aus denen ein Wort bestehen darf, und solche, die alleine in den Zwischenergebnissen der Ableitung eines Wortes auftreten dürfen. Zum Ableiten eines Wortes beginnt man mit einem besonderen Symbol, dem Startsymbol, und führt dann nacheinander Ableitungsschritte durch (bei Wahl geeigneter Regeln), bis schließlich das Wort erzeugt worden ist.

Anwendungsbereich

Der Syntaxanalyseteil („Parser”) eines Compilers konstruiert bei der Übersetzung eines Programmes (das ein Wort der betreffenden Programmiersprache ist) ganz oder iterativ-stückweise den Ableitungsbaum für das Programm. Scheitert der Parser dabei, so zeigt das an, dass die Eingabe kein syntaktisch korrektes Programm ist. Der Parser hat also in diesem Falle das Wortproblem – Ist das Programm ein Wort der Programmiersprache? – negativ beantwortet; eine Zeichenkette gehört immer dann zu einer formalen Sprache, wenn die Zeichenkette eine Ableitung in ihr hat.

Definitionen

Sei $G = \left(N, T, P, S \right)$ eine Chomsky-Grammatik. T steht dabei für das endliche Alphabet der Terminale, also für Zeichen, die nicht weiter abgeleitet werden, N steht für die Nonterminale oder Nichtterminalsymbole, also die Zeichen, die noch zu Terminalen umgewandelt werden müssen. Das Startsymbol S ist ein Nichtterminal. Ein Zeichen kann nicht gleichzeitig Terminal und Nichtterminal sein. Die Produktionsregeln P beschreiben, in welcher Weise die Nichtterminale zu Terminale abgeleitet werden.

Satzform

Eine Satzform x aus G ist eine Folge von Symbolen aus N oder T : $x \in \left(N\cup T\right)^*$.

Ableitungsschritt

Ein Ableitungsschritt ist ein Teil einer Ableitung, der mit einer Produktionsregel w nach w' überführt. w und w' sind Kombinationen aus Terminalen und Nichtterminalen. Eine Ableitungsregel wird formal so notiert: $p = \alpha \rightarrow \beta$. Für α und β gelten je nach Typ der Grammatik bestimmte Regeln. In der Ableitungskette schreibt man $w \Rightarrow_G w'$. Werden mehrere Regeln auf einmal angewendet schreibt man $w \Rightarrow_G^* w'$

Ableitungsstück

Ein Ableitungsstück ist eine endliche Folge $\left(w_0, \ldots, w_n \right)$ von Satzformen, worin jede folgende stets aus der unmittelbaren Vorgängerin durch einen Ableitungsschritt hervorgeht. Geschrieben kurz

$w_0 \Rightarrow_G w_1 \Rightarrow_G \cdots \Rightarrow_G w_n$

Ableitung

Eine Ableitung ist eine Folge von angewendeten Produktionsregeln, mit der aus dem Startsymbol ein Wort erzeugt wird. $S \Rightarrow w_0 \Rightarrow_G w_1 \Rightarrow_G \cdots \Rightarrow_G w_n$. w_n enthält nur noch Terminale.

Erzeugte Sprache

Die von G erzeugte Sprache L(G) ist die Menge aller Worte über dem Zeichenalphabet Σ, die am Ende einer Ableitung stehen; man sagt auch, die ableitbar sind.

$L(G) := \{w \in \Sigma^* | S \Rightarrow_G \cdots \Rightarrow_G w\}$

Im allgemeinen sind auf eine Satzform mehrere verschiedene Produktionen anwendbar, und ein und dieselbe Produktion kann auch an verschiedenen Stellen anwendbar sein.

Beispiele

Sprache der Palindrome

Ein Ableitungsbaum für abcacba

Palindrome lassen sich durch eine kontextfreie Grammatik erzeugen. Wir beschränken uns im Beispiel auf ein Alphabet aus den drei Buchstaben a, b und c.

$G_1 = \left(N, T, S, P\right)$.

N = {S}

T = {a,b,c}

$P : S\rightarrow aSa, S\rightarrow bSb, S\rightarrow cSc, S\rightarrow a, S\rightarrow b, S\rightarrow c, S\rightarrow \epsilon$

$\epsilon$ steht für das leere Wort.

Mit dieser Grammatik lassen sich alle aus a, b und c bestehenden Palindrome erzeugen. Eine Ableitung des Wortes abcacba lautet $S\Rightarrow aSa\Rightarrow abSba\Rightarrow abcScba\Rightarrow abcacba$.

Sprache der positiven geraden Ganzzahlen

Auf eine formale Notation der Grammatik wurde an dieser Stelle verzichtet. Die Zahlen können beliebig viele führende Nullen haben.

Die Terminale sind die Ziffern von 0 bis 9, als Nonterminale dienen A und S, was gleichzeigit das Startsymbol ist.

Die Produktionsregeln sind :

$S \rightarrow A0 | A2 | A4 | A6 | A8, A\rightarrow A0 | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 |\epsilon$

$X\rightarrow a | b$ ist eine Kurzschreibwiese für $X\rightarrow a, X\rightarrow b$

Die Ableitung beginnt mit einer Regel, die auf der linken Seite das Startsymbol S enthält. Die Ableitung beginnt beispielsweise mit $S\Rightarrow A2$. Die 2 an Ende kann durch Regelanwendungen nicht entfernt werden, die entstehende Zahl ist also auf jeden Fall gerade. Das A muss nun nach einer der Regeln mit A auf der linken Seite weiter ersetzt werden. Eine mögliche Fortsetzung der Ableitung ist $A2\Rightarrow A42$. Es können noch weitere Ziffern erzeugt werden; da am Ende der Ableitung aber alle Nichtterminale verschwunden sein müssen, muss irgendwann die Regel $A\rightarrow \epsilon$ Anwendung finden. $\epsilon$ ist das leere Wort, umgangssprachen kann man sagen, dass das A durch nichts ersetzt wird. Die Beispielableitung wird also mit $A42\Rightarrow 42$ abgeschlossen.

Mit den Produktionsregeln lässt sich jede beliebige positive, gerade Zahl erzeugen. Andere Zahlen lassen sich mit ihnen nicht erzeugen.

Sprache der Strichzahlen

Die Sprache der Strichzahlen wird etwa erzeugt von

$G_3 = \left(\{Z\}, \{i\}, \{Z\rightarrow i, Z\rightarrow i Z\}, Z \right)$.

Die Ableitung, die zur 5-Strichzahl führt, ist etwa:

$Z \Longrightarrow_{Z\rightarrow i Z} i Z \Longrightarrow_{Z\rightarrow i i Z} i Z \Longrightarrow_{Z\rightarrow i i i Z} i Z \Longrightarrow_{Z\rightarrow i Z} i i i i Z \Longrightarrow_{Z\rightarrow i} i i i i i$

Im Falle dieser Grammatik enthält jede Satzform keinmal oder genau einmal die Z, die in diesem Falle auch stets am Ende der Satzform steht. Es sind also alle Ableitungen Rechtsableitungen. Jedes Strichzahl hat mit dieser Grammatik genau eine mögliche Ableitung.

Dieselbe Sprache wird ebenfalls erzeugt von der Grammatik

$G_4 = \left(\{Z\}, \{i\}, \{Z\rightarrow i, Z\rightarrow Z Z\}, Z \right)$.

Das folgende ist damit eine Ableitung für die 3-Strichzahl:

$Z \Longrightarrow_{Z\rightarrow Z Z} Z Z \Longrightarrow_{Z\rightarrow Z Z} Z Z Z \Longrightarrow_{Z\rightarrow i} Z Z i \Longrightarrow_{Z\rightarrow i} Z i i \Longrightarrow_{Z\rightarrow i} i i i$.

Man beachte, im zweiten Schritt bleibt hierbei unklar, ob das rechte oder das linke Z in ZZ durch ein weiteres ZZ ersetzt wird; beidesmal entsteht zunächst ZZZ. Mit der Angabe, dass es sich um eine Rechtsableitung handle, wird die Ersetzungsstelle eindeutig. Dieselbe Eindeutigkeit wird erreicht, wenn man immer die genaue Stelle der Ersetzung, den sogenannten Henkel (englisch handle) mit angibt.

Parsen

Den umgekehrten Vorgang, bei dem ein Wort gegeben ist und eine Ableitung gesucht ist, nennt man auch parsen. Hierbei finden Automaten Anwendung, die überprüfen, ob das gegebene Wort aus den Ableitungsregeln entstanden sein kann. Von besonderer Bedeutung ist die Syntaxüberprüfung bei Programmiersprachen. Da es sich hierbei häufig um kontextfreie Sprachen handelt, ist ein Kellerautomat nötig.

Rechtsableitung

Eine Ableitung heißt Rechtsableitung (englisch rightmost derivation), wenn in jedem ihrer Einzelschritte immer das am weitestens rechts stehende Nichtterminalsymbol der Satzform gemäß einer Produktion ersetzt wird.

Beachte: Von Rechtsableitung spricht man nur, wenn eine kontextfreie Grammatik (Chomsky-Grammatik vom Typ 2) vorliegt; solche Grammatiken sind auch der in der Praxis der Informatik am häufigsten auftretende Sprachtyp. In diesem Fall hat jede Produktion die einfache Gestalt $A \rightarrow \alpha$, alle linken Seiten sind also einzelne Nichtterminalsymbole, die rechten bleiben beliebig. Der einzelne Ableitungsschritt ersetzt deshalb ein Vorkommnis eines Nichtterminalsymbols A in der Ausgangs-Satzform durch eine der möglichen rechten Seiten α mit $A\rightarrow \alpha \in P$.

Im Falle von Rechtsableitungen genügt die Angabe allein der Folge angewandter Produktionen, um den Gesamt-Ersetzungsvorgang (welche Ersetzungen an welchen Stellen?) und sein Ergebnis eindeutig zu beschreiben, was für beliebige Ableitungen nicht so ist, weil eine auftretende Satzform etwa Nichtterminalsymbole mehrfach enthalten kann.

Im Bereich des Compilerbaus sind Rechtsableitungen bedeutsam, weil für eine dort wichtige Sprachklasse, die LR(k)-Sprachen, eine effiziente Methode der Syntaxanalyse bekannt ist, der wesentlich dieser Begriff zugrunde liegt.

Linksableitung

Analog zur Rechtsableitung spricht man von einer Linksableitung (englisch leftmost derivation), wenn immer das am weitesten links stehende Nichtterminalsymbol ersetzt wird.

Linksableitungen spielen eine Rolle bei der Syntaxanalyse von LL(k)-Grammatiken, da aber die ihrer größeren Erzeugungsmächtigkeit wegen wichtigere Klasse der LR(k)-Grammatiken auf Rechtsableitungen beruhen, insgesamt eine geringere. Diese scheinbare Asymmetrie ist eine Folge der Konvention, Eingabezeichenketten von links nach rechts zu lesen und zu verarbeiten.

Quellen

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Compilers - Principles, Techniques and Tools. Addison-Wesley, Reading MA u. a. 1986, ISBN 0-201-10088-6, (Addison-Wesley Series in Computer Science), S. 196–197.
• Arto K. Salomaa: Formale Sprachen. Springer Verlag, Berlin u. a. 1978, ISBN 3-540-09030-4.
• Seppo Sippu, Eljas Soisalon-Soininen: Parsing Theory. 2 Bände. Springer Verlag, Berlin u. a. 1988, ISBN 3-540-13720-3 (Bd. 1), ISBN 3-540-51732-4 (Bd. 2), (EATCS Monographs on theoretical Computer Science 15 und 20).

Siehe auch

• Rechtsreduktion
• Inhärent mehrdeutige Sprache
• Syntaxbaum
• LR-Parser