====== Erzeugung formaler Sprachen ====== Um festzulegen, welche Wörter zu einer Sprache gehören, formuliert man meist eine **Menge von Regeln (Syntax)**, nach denen alle Wörter der Sprache aus ihrem Alphabet gebildet werden können (**Produktionsregeln**). \\ Die Bildung eines Wortes mithilfe der Produktionsregeln nennt man seine **Ableitung**. ===== Beispiel: Bezeichnung von Fernstraßen in Deutschland ==== Die [[https://de.wikipedia.org/wiki/Liste_der_Bundesautobahnen_in_Deutschland|Bezeichnungen aller Bundsstraßen und Autobahnen in Deutschland]] ist eine Sprache über dem Alphabet A = {A, B, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, die durch folgende **Produktionsregeln** ( = Syntax) definiert wird: R1: Fernstraße = Autobahn R2: Fernstraße = Bundesstraße R3: Autobahn = "A" ZahlMaxDreistellig R4: Bundestraße = "B" ZahlMaxDreistellig R7: ZahlMaxDreistellig = Ziffer R6: ZahlMaxDreistellig = Ziffer Ziffer R8: ZahlMaxDreistellig = Ziffer Ziffer Ziffer R9: Ziffer = "1" R10: Ziffer = "2" R11: Ziffer = "3" R12: Ziffer = "4" R13: Ziffer = "5" R14: Ziffer = "6" R15: Ziffer = "7" R16: Ziffer = "8" R17: Ziffer = "9" R18: Ziffer = "0" **Begriffe:** \\ Kommt in den Produktionsregeln ein Element des Alphabets vor, so bezeichnet man es als **Terminal**, weil es sich im Verlauf der Ableitung eines Wortes nicht mehr ändert. Die Variablen ''Fernstraße'', ''Autobahn'', ... bezeichnet man als **Nichtterminale**, weil sie im Lauf der Ableitung noch ersetzt werden müssen. Terminale werden in Anführungszeichen gesetzt, damit sie von Nichtterminalen unterschieden werden können. \\ \\ **Kurzschreibweise:** \\ Falls mehrere Produktionsregeln auf der linken Seite das selbe Nichtterminalsymbol haben, kann man sie mit Hilfe des Operators | ("oder") zu einer Regel zusammenfassen. Die Regeln 9 - 18 oben kann man bspw. zusammenfassen zu \\ Ziffer = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0" **Backus-Naur-Form** \\ Die oben beschriebene Form, mit der wir Produktionsregeln notieren können, bezeichnet man als [[https://de.wikipedia.org/wiki/Backus-Naur-Form|Backus-Naur-Form]] (**BNF**). Wir werden etwas später noch die [[https://de.wikipedia.org/wiki/Erweiterte_Backus-Naur-Form|erweiterte Backus-Naur-Form]] (**EBNF**) kennenlernen, die exakt gleich mächtig ist, jedoch in vielen Fällen eine kompaktere, griffigere Darstellung der Produktionsregeln ermöglicht. ===== Aufgabe 1 ===== Geben Sie die **Ableitungen** der Wörter "A34" und "B903" an und zeichnen Sie zur ersten der beiden Ableitungen einen **Ableitungsbaum**. ==== Lösung ==== $$Fernstraße\xrightarrow[]{(R1)}Autobahn\xrightarrow[]{(R3)}\mathrm{"A"}ZahlMaxDreistellig\xrightarrow[]{(R6)}\mathrm{"A"}Ziffer\ Ziffer$$ $$\xrightarrow[]{(R11)}\mathrm{"A3"}Ziffer\xrightarrow[]{(R12)}\mathrm{"A34"}$$ \\ \\ $$Fernstraße\xrightarrow[]{(R2)}Bundesstraße\xrightarrow[]{(R4)}\mathrm{"B"}ZahlMaxDreistellig\xrightarrow[]{(R8)}\mathrm{"B"}Ziffer\ Ziffer\ Ziffer$$ $$\xrightarrow[]{(R17)}\mathrm{"B9"}Ziffer\ Ziffer\xrightarrow[]{(R18)}\mathrm{"B90"}Ziffer\xrightarrow[]{(R11)}\mathrm{"B903"}$$ Zur ersten der beiden Ableitungen hier der **Ableitungsbaum**: {{ :formalesprachen:pasted:20250714-145442.png?400 }} Sicherlich werden Sie sich schon die ganze Zeit fragen: \\ \\ **Wozu braucht man das in der Praxis?** \\ * Wenn Sie ein Programm in einer höheren Programmiersprache, z.B. Java, geschrieben haben, ist dieses gesamte Programm ein **Wort** dieser Sprache. Die [[https://docs.oracle.com/javase/specs/jls/se25/html/jls-19.html|EBNF von Java finden Sie hier!]] \\ Ein **Java-Compiler** ist ein Programm, das ein Java-Programm einliest und in eine Sprache übersetzt, die der Computer ausführen kann. Im den ersten beiden Schritten dieses Prozesses (genannt //lexing// und //parsing//) wandelt der Compiler das Programm anhand der EBNF in einen **Ableitungsbaum** (genannt //abstract syntax tree//) um. Dieser dient dann als Grundlage der nachfolgenden Schritte. \\ Neugierig geworden? [[https://www.learnj.de/doku.php?id=compilerbau:start#compilerbau_einfuehrung|Hier finden Sie eine anschauliche Einführung in die Programmierung eines Compilers mit vielen einfachen Beispielen zum Ausprobieren im Browser.]] * Wenn ein Objektbaum (z.B. den eines Textes im Textverarbeitungsprogramm) auf einem Massenspeichermedium (SSD, NVMe, ...) gespeichert oder per Internet übertragen wird, muss er zuerst serialisiert, d.h. in eine Zeichenkette umgewandelt werden. Diese Zeichenkette ist ein Wort einer wohldefinierten Sprache, meist auf Basis von [[https://de.wikipedia.org/wiki/JSON|JSON]] oder [[https://de.wikipedia.org/wiki/Extensible_Markup_Language|XML]]. Will man auf Empfängerseite aus der Zeichenkette wieder einen Objektbaum generieren, so entspricht dieser Vorgang der Erstellung des Ableitungsbaumes anhand der Grammatik der Sprache. Es gibt noch viele weitere Anwendungsbeispiele, z.B. die Verarbeitung einer Benutzereingabe, das Einlesen einer Grafikdatei usw... ===== Aufgabe 2 ===== Ist die Ableitung eines Wortes immer eindeutig? Begründen Sie Ihre Antwort beispielhaft mit den obigen Produktionsregeln! ====== Definition "Grammatik": ====== Eine **formale Grammatik** $$G = (V, A, P, S)$$ besteht aus * der Menge der **Nichtterminale** $V$ * dem **Alphabet** $A$ * einer Menge von **Produktionsregeln** $P$ und * einem Startsymbol $S\in V$ Dabei müssen $A$ und $V$ disjunkt sein, d.h. $A \bigcap V = \{\}$. \\ $G$ definiert eine **formale Sprache**, die aus allen Wörtern aus $A^*$ besteht, die aus dem Startsymbol $S$ durch Anwendung endlich vieler Produktionsregeln aus $P$ abgeleitet werden können. \\ \\ //(Erinnerung: $A^*$ ist die Menge aller Wörter über dem Alphabet $A$, ungeachtet der Produktionsregeln)// ===== Aufgabe 3 ===== a) Geben Sie eine Grammatik an, die die Sprache beschreibt, in der deutsche Autokennzeichen notiert werden. * Die Sprache soll alle Autokennzeichen der Formen "ND WW 16" und "IN XE 312E" beschreiben (Ortskürzel mit bis zu drei Buchstaben, Zwischenbereich mit bis zu zwei Buchstaben, ein- bis dreistellige Zahl, optional "E" am Ende). * Auch nichtexistente Ortskürzel dürfen vorkommen. b) Geben Sie zur Grammatik aus a) die Ableitung des Kennzeichens "SOB AX 12E" an. \\ [[.aufgabe3loesung:start|Lösung]] ===== Rekursive Produktionsregeln ===== Gegeben ist die Grammatik $G = (V, A, P, S)$ mit dem Alphabet $A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, den Nichtterminalen $V=\{Zahl,\ Ziffer\}$, dem Startsymbol $S = Zahl$ und folgenden Produktionsregeln: R1: Zahl = Ziffer | Ziffer Zahl R2: Ziffer = "0" | "1" | ... | "9" \\ \\ Beschreiben Sie die [[formalesprachen:start#definitionalphabet_wort_syntax|Semantik]] der erzeugten Sprache! Inwiefern sind diese Produktionsregeln rekursiv? ===== Aufgabe 4 ===== Erweitern sie obige Grammatik G so, dass die Sprache genau die Dezimaldarstellungen aller **ganzen** Zahlen umfasst, wobei keine Vornullen erlaubt sein sollen. \\ \\ //**Bemerkung:** (Das Wort **"genau"** in der Aufgabenstellung ist **wesentlich**. Damit wird ausgedrückt, dass nicht nur gefordert ist, dass die Sprache die Dezimaldarstellungen aller ganzen Zahlen umfasst, sondern dass darüber hinaus gefordert ist, dass die Sprache **keine** Wörter enthält, die **nicht** Dezimaldarstellungen ganzer Zahlen sind.)// ===== Aufgabe 5 ===== Geben Sie die Grammatik einer Sprache an, die alle ungeklammerten Terme enthält, die * nur die Rechenzeichen + und - sowie * als Operanden nur die Variablen a, b und c besitzen. Gemeint sind also Terme der Form $a$, $b$, $c$, $a + b$, $a - b$, $a + b - c$, $a + a - b + b$ usw. ===== Aufgabe 6 ====== Die Sprache aller symmetrischen Wörter über den Alphabet $A = \{a, b\}$ enthält das leere Wort $\varepsilon$, die Wörter $a$, $b$, $aa$, $bb$, $aba$, usw. \\ \\ Geben Sie eine Grammatik an, die diese Sprache erzeugt.