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 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 Backus-Naur-Form (BNF). Wir werden etwas später noch die 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:

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 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? 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 JSON oder 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.

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 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.