Ihr habt im Fachkonzept Grammatiken gelernt, dass man mittels einer Grammatik gewissen Wörter einer Sprache beschreiben kann. Auf diesem Weg konntet ihr feststellen, ob ein Wort zu einer Grammatik gehört oder nicht. Im folgenden Fachkonzept wird erläutert, wie Wörter einer Sprache durch Ableitungen (nein, ihr braucht keinen Differenzenquotient oder ein $f'(x)$ bestimmen ) und Ableitungsbäume erzeugen kann.
Wir schauen uns hierfür erneut das Beispiel der EMailadressen an. Zur Erinnerung hier alle Ableitungsregeln in EBNF:
EMailAdresse = Benutzerkennung "@" Domain. Benutzerkennung = Einzelzeichen {Einzelzeichen}. Einzelzeichen = Buchstabe | Ziffer | "-" | "_" | "." | "!". Ziffer = "0" | "1" | "2" | "..." | "9". Buchstabe = "a" | "b" | "c" | "..." | "z". Domain = Subdomain { "." Subdomain } "." TopLevelDomain. TopLevelDomain = Buchstabe Buchstabe [Buchstabe] [Buchstabe]. Subdomain = (Buchstabe | Ziffer) { Buchstabe | Ziffer | "-" } (Buchstabe | Ziffer).
Unter einer Ableitung wird die Anwendung der Produktionen einer Grammatik verstanden. Ausgangspunkt bildet stets das Startsymbol aus der Menge der Nichtterminale. Daraufhin werden die Produktionen der Sprache solange angewandt, bis das gewünschte Wort erzeugt ist. Im Folgenden findet ihr ein Beispiel zur Ableitung einer EMailadresse. Da die Produktionen hier alle nacheinander angewandt werden, spricht man von einer linearen Ableitung.
Startsymbol | $\rightarrow$ | EMailAdresse |
Regel 1 | $\rightarrow$ | Benutzerkennung @ Domain |
Regel 2 | $\rightarrow$ | Einzelzeichen Einzelzeichen Einzelzeichen @ Domain |
Regel 3 | $\rightarrow$ | Buchstabe Buchstabe Buchstabe @ Domain |
Regel 5 | $\rightarrow$ | t i m @ Domain |
Regel 6 | $\rightarrow$ | t i m @ SubDomain . TopLevelDomain |
Regel 8 | $\rightarrow$ | t i m @ Buchstabe Buchstabe Buchstabe . TopLevelDomain |
Regel 5 | $\rightarrow$ | t i m @ t i p . TopLevelDomain |
Regel 7 | $\rightarrow$ | t i m @ t i p . Buchstabe Buchstabe Buchstabe |
Regel 5 | $\rightarrow$ | t i m @ t i p . t o p |
Eine weitere Möglichkeit zur Darstellung von Ableitungen bilden Ableitungsbäume. Im Gegensatz zur linearen Ableitung bieten Ableitungsbäume den Vorteil, dass viele Ableitungsschritte gleichzeitig dargestellt werden können. Gegen die Verwendung von Ableitungsbäumen spricht, dass sie meistens viel Platz brauchen . Ein Vorteil ist es, dass das Vorgehen besser visualisiert ist. Das Startsymbol wird hier gelb, Nichtterminale grün und Terminale blau dargestellt. Im Folgenden wird die gleiche Ableitung wie oben in Form eines Ableitungsbaumes dargestellt.
tim@tip.top