Fachkonzept: Grammatik

Auch das Konzept der Grammatik kennt ihr bereits, und zwar aus dem Deutschunterricht. Eine Grammatik ist eine Sammlung von Regeln, die angeben, wie eine Sprache aufgebaut ist. So bestehen z.B. einfache Sätze in der deutschen Sprache immer aus einem Subjekt und einem Verb. Diese Grundform kann man natürlich durch Objekte, Adjektive, Nebensätze u.ä. immer komplexer machen.

Wikipedia sagt hierzu:

Die Grammatik oder auch Sprachlehre bezeichnet jede Form einer systematischen Sprachbeschreibung.
Dabei steht der Begriff der Grammatik einmal für das Regelwerk selbst, auf der anderen Seite aber auch für die Theorie über eine bestimmte Sprache.
Teile der Forschung, maßgeblich angeregt von Noam Chomsky, behandeln die Frage, wie weit sich natürliche Sprachen auf formale Sprachen reduzieren lassen.

Grammatik

Definition: Grammatik

Die eindeutige Festlegung einer formalen Sprache mit Regeln heißt Grammatik. Eine Grammatik $G$ wird durch ein 4-Tupel $(N,T,S,P)$ spezifiziert:

$N$ ist die Menge der Nichtterminalsymbole.
$T$ ist die Menge der Terminalsymbole.
$S\in N$ ist das Startsymbol.
$P$ ist die Menge der Regeln oder Produktionen.

Eine Grammatik erzeugt eine Sprache, die aus allen Wörtern besteht, die sich durch Anwendung der Regeln der Grammatik erzeugen (ableiten) lassen. Diese Regeln werden in der sogenannten erweiterte Backus-Naur-Form (EBNF) notiert, die Optionsklammern [], Wiederholungsklammern {} und Gruppierungsklammern () und die Alternative | kennt.

Jetzt wird es mir aber echt zu mathematisch…

Ja, das muss leider sein, um genau zu definieren, mit was wir hier arbeiten. Allerdings ist es wieder einfacher, als es aussieht. Überlege dir mal, wie eine EMail-Adresse aufgebaut ist. Welchen Regeln folgt dieser Aufbau? Man könnte bestimmt auf eine ähnliche Liste von Regeln kommen:

Eine E-Mail-Adresse hat links vom @-Zeichen eine Benutzerkennung und rechts davon den Namen einer Internet-Domain.
Die Benutzerkennung besteht aus mindestens einem Zeichen. Es dürfen Kleinbuchstaben, Zahlen, Punkt, Ausrufezeichen, Binde- und Unterstrich verwendet werden.
Die Internet-Domain setzt sich zusammen aus mindestens einer Unterdomain gefolgt von einer Top-Level-Domain wie de oder com. Dazwischen steht ein Punkt ..
Die Top-Level-Domain besteht nur aus Buchstaben. Es sind mindestens zwei und höchstens vier Buchstaben.
Jede Unterdomain kann Buchstaben, Ziffern und den Bindestrich enthalten. Es sind mindestens zwei Zeichen nötig. Am Anfang und am Ende darf kein Bindestrich stehen.

Und schon haben wir im Endeffekt eine gültige Grammatik. Mit diesen Regeln können wir einerseits EMail-Adressen erzeugen und andererseits überprüfen, ob eine gegebene Zeichenfolge eine gültige EMail-Adresse ist. Allerdings sind diese Regeln noch in menschlicher Sprache aufgeschrieben, also nicht von einem Computer interpretierbar. Hier eilt die Backus-Naur-Form zur Hilfe: Mit ihr können die Regeln so formuliert werden, dass auch ein Computer Wörter der Sprache erzeugen bzw. erkennen kann:

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

Regel	Erklärung
1	`EMailAdresse`, `Benutzerkennung` und `Domain` sind Nichtterminal-Symbole, d.h. so etwas wie Platzhalter, die noch durch weitere Regeln erklärt werden müssen. Das `@`-Zeichen ist ein Terminalsymbol, also ein Symbol aus dem Alphabet, über dem die Sprache definiert ist. Das erste Nichtterminal-Symbol (in diesem Fall `EMailAdresse`) ist das Startsymbol einer Grammatik.
2	Dies bedeutet, dass die Benutzerkennung aus mindestens einem Einzelzeichen besteht. Die geschweiften Klammern `{}` stehen für eine Wiederholung, was bedeutet, dass es kein, ein oder mehrere Zeichen sind, die an das erste Einzelzeichen angehängt werden können. Die geschweifte Klammer gehört nicht zur erzeugten Sprache, sondern sind Metazeichen.
3	Das Metazeichen `\|` steht für Alternativen und kann als "oder" gelesen werden…
4
5
6	Hier sieht man, dass auch innerhalb von Wiederholungen mehrere Symbole stehen können, und dass Wiederholungen beliebig in andere Aneinanderreihungen von Symbolen eingebettet werden können.
7	Hier wird angegeben, dass es mindestens zwei Einzelzeichen geben muss. Die eckigen Klammern `[]` stehen für eine Option, die angegeben werden kann, aber nicht angegeben werden muss.
8	Mit den runden Klammern `()` kann man den Ausdruck `Buchstabe \| Ziffer` geeignet gruppieren, d.h. hier das erste und letzte Zeichen festlegen. Diese klammern könnte man sich sparen, wenn man eine weitere Prodkution `ErstesZeichen = Buchstabe \| Ziffer` definieren würde. So ist es aber übersichtlicher und man versteht direkt, was gemeint ist.

Die Grammatik $G=(N,T,S,P)$ kann man nun so definieren:

$N=\{\text{EMailAdresse, Benutzerkennung, Domain}, \ldots\}$
$T=\{\text{"a"}, \ldots, \text{"z"}, \text{"0"}, \ldots, \text{"9", "@", "-", "_", ".", "!"}\}$
$S=\text{EMailAdresse}$
$P=\{\text{EMailAdresse = Benutzerkennung "@" Domain, Benutzerkennung = Einzelzeichen} \{\text{Einzelzeichen}\}, \ldots\}$

Definition: reguläre Grammatik

Wenn eine Grammatik $G=(N,T,S,P)$ mit $N=\{A,B,C,...\}$ und $T=\{a,b,c,...\}$ nur Regeln der Form $A\to aB|B|a|\varepsilon$ besitzt (rechts steht höchstens ein Nichtterminalsymbol hinter höchstens einem Terminalsymbol), dann nennt man die Grammatik rechtslinear oder rechtsregulär. Insbesondere gehört auch die rekursive Regel $A\to aA$ zu einer rechtsregulären Grammatik.

Entsprechend heißt die Grammatik mit diesen Regeln $A\to Ba|B|a|\varepsilon$ (links steht höchstens ein Nichtterminalsymbol vor höchstens einem Terminalsymbol) linkslinear oder linksregulär.

Eine Grammatik heißt regulär, wenn sie entweder linksregulär oder rechtsregulär ist.

Die E-Mail-Grammatik von oben ist nicht regulär, da z.B. die Produktion EMailAdresse = Benutzerkennung "@" Domain schon nicht regulär ist, da sowohl auf der rechten als auch auf der linken Seite der Produktion Nichtterminalsymbole.

Die Grammatik $G=(N,T,S,P)$ mit $N$, $T$, $S$ und $P$ wie unten ist dagegen regulär:

$N=\{X,A,B\}$
$T=\{0,1\}$
$S=X$
$P=\{X\to 1X|0A,A\to 1X|0B,B\to 1X|0B|0\}$

Eine gültige Ableitung (wird später genauer definiert, für jetzt erst einmal: "Ersetzungsfolge") ist z.B. $X\to 1X\to 10A\to 100B\to 1000$. 1000 ist ein Wort dieser Sprache. Die Sprache besteht aus bestimmten Binärzahlen.

Klassifizierung von Sprachen

Sprachen können mit Hilfe der Chomsky-Hierarchie in verschiedene Kategorien eingeteilt werden. Wir interessieren uns hier allerdings nur für Sprachen vom Typ 1 bis 3, zu denen die Programmiersprachen gehören.

3. Reguläre Sprachen	… sind Sprachen, die von einer regulären Grammatik erzeugt werden.
2. Kontextfreie Sprachen	… werden von Grammatiken erzeugt mit einer Regel der Form $A\to\alpha$, wobei $α$ eine nichtleere Symbolfolge aus Terminal- und/oder Nichtterminalsymbolen ist. Bei dieser Ersetzung kommt es nicht auf den Kontext, d.h. die Umgebung von $A$ an.
1. Kontextsensitive Sprachen	… werden von Grammatiken erzeugt, deren Regeln alle die Form $\beta A\gamma\to\beta\alpha\gamma$ haben, d.h. die Ersetzung des Nichtterminalsymbols $A$ erfolgt nur, wenn $A$ zwischen den Symbolfolgen $\beta$ und $\gamma$, d.h.im Kontext von $\beta$ und $\gamma$ auftritt.
0. Allgemeine Sprachen	… unterliegen keinerlei Einschränkungen bezüglich der Ersetzungsregeln.