Ableitung (Informatik)

Grundidee und Bedeutung

Eine Ableitung ist in der theoretischen Informatik der Vorgang, mit den Regeln einer formalen Grammatik ein Wort zu erzeugen. Ein Wort ist dabei eine beliebige endliche Zeichenkette. Die Grammatik legt fest, welche Wörter erzeugbar sind; ihre Gesamtheit heißt formale Sprache.

Man beginnt mit einem besonderen Startsymbol und ersetzt anschließend nach passenden Regeln Teile der Zeichenkette. Zwischenergebnisse dürfen neben den endgültigen Zeichen auch besondere Symbole enthalten. Endet der Vorgang in einer Zeichenkette, die nur noch aus den vorgesehenen endgültigen Zeichen besteht, ist das Wort abgeleitet.

Ob ein Wort zu einer Sprache gehört, heißt Wortproblem. Eine gefundene Ableitung ist zugleich ein mathematischer Beweis dafür, dass das Wort zur Sprache der Grammatik gehört. Bei kontextfreien Grammatiken kann eine Ableitung als Ableitungsbaum dargestellt werden. Mehrere Ableitungen eines Wortes mit unterschiedlichen Ableitungsbäumen machen die Grammatik mehrdeutig.

Grammatik, Satzformen und Regeln

Eine Chomsky-Grammatik wird als G = (V,T,P,S) beschrieben. T ist das endliche Alphabet der Terminale: Zeichen der erzeugten Sprache, die nicht weiter abgeleitet werden. V ist das gesamte Vokabular. Die Nichtterminale sind N := V\setminus T; sie müssen noch in Terminale umgewandelt werden und heißen gelegentlich Variablen. Das Startsymbol S ist ein Nichtterminal. Ein Zeichen kann nicht zugleich Terminal und Nichtterminal sein. P bezeichnet die Produktionsregeln.

Alternativ schreiben manche Autoren G = (N,T,P,S) und fordern N\cap T=\emptyset.

Eine Satzform x ist jede Folge aus Terminalen und Nichtterminalen: x\in(N\cup T)^{}=V^{}. Eine Regel p=(\alpha,\beta) wird als \alpha\rightarrow\beta notiert. Bei w=w_{1}\alpha w_{2}\in V^{+} und \alpha\rightarrow\beta\in P entsteht durch einen Schritt w'=w_{1}\beta w_{2}. Dies wird w\rightsquigarrow w' oder w\Rightarrow_{G}w' geschrieben; mit Regelangabe auch w\rightsquigarrow_{\alpha\rightarrow\beta}w'. Welche Formen für \alpha und \beta erlaubt sind, hängt vom Grammatiktyp ab.

Vom Schritt zur erzeugten Sprache

Ein Ableitungsstück ist eine endliche Folge von Satzformen, bei der jede nächste aus der vorherigen durch einen Ableitungsschritt entsteht: w_{0}\rightsquigarrow_{G}w_{1}\rightsquigarrow_{G}\dotsb\rightsquigarrow_{G}w_{n}. Mehrere Schritte fasst man als w{\rightsquigarrow_{G}}^{}w' zusammen. Formal gilt {\rightsquigarrow_{G}}^{}=\bigcup_{n\in\mathbb{N}{0}}{\rightsquigarrow{G}}^{n}.

Eine Ableitung beginnt mit S und endet mit einem Wort aus T^{}, also ohne Nichtterminale. Eine Ableitung in n Schritten hat die Form S{\rightsquigarrow_{G}}^{n}w_{n}; ohne Angabe der Schrittzahl schreibt man S{\rightsquigarrow_{G}}^{}w.

Die von G erzeugte Sprache ist genau die Menge der so erreichbaren Terminalwörter: L(G):={w\in T^{}\mid S{\rightsquigarrow_{G}}^{}w}. Auf eine Satzform können im Allgemeinen mehrere Produktionen passen; außerdem kann dieselbe Regel an mehreren Stellen anwendbar sein.

Beispiele für Grammatiken

Für Palindrome über T={a,b,c} genügt ein Nichtterminal S mit den Regeln S\rightarrow aSa, S\rightarrow bSb, S\rightarrow cSc, S\rightarrow a, S\rightarrow b, S\rightarrow c, S\rightarrow\epsilon. \epsilon ist das leere Wort. Damit lassen sich alle Palindrome aus a, b und c erzeugen, zum Beispiel: S\rightsquigarrow aSa\rightsquigarrow abSba\rightsquigarrow abcScba\rightsquigarrow abcacba.

Positive gerade Ganzzahlen mit beliebig vielen führenden Nullen können mit T={0,...9}, N={A,S} und Startsymbol S erzeugt werden. Es gelten S\rightarrow A0|A2|A4|A6|A8 sowie A\rightarrow A0|A1|A2|A3|A4|A5|A6|A7|A8|A9|\epsilon. Die letzte Ziffer bleibt gerade; A erzeugt davor beliebig viele Ziffern und verschwindet schließlich durch A\rightarrow\epsilon. Beispielsweise führt S\rightsquigarrow A2\rightsquigarrow A42\rightsquigarrow42. Andere Zahlen sind mit diesen Regeln nicht erzeugbar.

Die Strichzahlensprache wird etwa durch G_{3}=({Z,i},{i},{Z\rightarrow i,Z\rightarrow iZ},Z) erzeugt. Für fünf Striche gilt Z\rightsquigarrow iZ\rightsquigarrow iiZ\rightsquigarrow iiiZ\rightsquigarrow iiiiZ\rightsquigarrow iiiii. Jede Strichzahl hat hier genau eine Ableitung; alle sind Rechtsableitungen. Die Grammatik G_{4}=({Z,i},{i},{Z\rightarrow i,Z\rightarrow ZZ},Z) erzeugt dieselbe Sprache, kann aber bei mehreren Z unterschiedliche Ersetzungsstellen offenlassen. Diese werden durch die Angabe einer Rechtsableitung oder des Henkels (englisch handle) eindeutig.

Parsen und Rechtsableitungen

Parsen ist der umgekehrte Vorgang: Zu einem gegebenen Wort wird eine mögliche Ableitung gesucht. Automaten prüfen dabei, ob das Wort aus den Regeln entstanden sein kann. Besonders wichtig ist dies für die Syntaxprüfung von Programmiersprachen. Da diese häufig kontextfreie Sprachen sind, wird ein Kellerautomat benötigt.

Eine Rechtsableitung ersetzt in jedem Schritt das am weitesten rechts stehende Nichtterminal. Dieser Begriff gilt nur für kontextfreie Grammatiken (Chomsky-Grammatiken vom Typ 2). Dort hat jede Produktion die Form A\rightarrow\alpha: Links steht ein einzelnes Nichtterminal, rechts darf eine beliebige Folge stehen. Bei Rechtsableitungen reicht die Reihenfolge der verwendeten Produktionen aus, um alle Ersetzungsstellen und das Ergebnis eindeutig festzulegen.

Rechtsableitungen sind im Compilerbau wichtig, weil für LR(k)-Sprachen eine effiziente Syntaxanalyse darauf beruht. Analog ersetzt eine Linksableitung stets das am weitesten links stehende Nichtterminal. Sie ist für die Syntaxanalyse von LL(k)-Grammatiken bedeutsam, hat aber insgesamt eine geringere Rolle als die auf Rechtsableitungen beruhende Klasse der LR(k)-Grammatiken. Die Asymmetrie folgt aus der Konvention, Eingabezeichenketten von links nach rechts zu lesen und zu verarbeiten.