Ableitung

aus www.iwiki.de, der freien Wissensdatenbank

Als Ableitung bezeichnet man eine Abfolge von Schritten bei denen Regeln einer formalen Grammatik angewandt werden. Um eine Ableitung übersichtlich darzustellen werden häufig Syntaxbäume verwendet.

Inhaltsverzeichnis

1 Definition
2 Typen
- 2.1 Linksableitung
- 2.2 Rechtsableitung
3 Beispiel

Definition

Für eine formale Grammatik $G = \left(N, T, P, S \right)$ bezeichnet eine Ableitung Wortes aus der durch die Grammatik erzeugten Sprache eine Folge von Worten $\left(w_0 , ..., w_n \right)$ mit $w 0 = S$ , $w_n \in L(G)$ und $w_0 \Rightarrow_G w_1 \Rightarrow_G \cdots \Rightarrow_G w_n$ . (Quelle: Wikipedia)

Typen

Um ein Wort (einer kontextfreien Sprache) abzuleiten gibt es verschiedene Ableitungswege

Linksableitung

Bei Linksableitungen wird immer das am weitesten Links stehende Nichtterminal ersetzt.

Rechtsableitung

Bei Rechtsableitungen wird immer das am weitesten Rechts stehende Nichtterminal ersetzt.

Beispiel

Grammatik:

$S \rightarrow AA$

$AB \rightarrow \mathrm a$

$A \rightarrow B$

$B \rightarrow \mathrm b$

Startsymbol: $S$

Linksableitung:

$S\rightarrow AA \rightarrow BA \rightarrow \mathrm bA \rightarrow \mathrm bB \rightarrow \mathrm b\mathrm b$

Rechtsableitung:

$S\rightarrow AA \rightarrow AB \rightarrow \mathrm a$

Von "http://www.iwiki.de/wiki/index.php/Ableitung"

Seitenkategorien: Compilerbau

Views

'Persönliche Werkzeuge

Anmelden

Suche

Werkzeuge