TI2—Kapitel 5

5. Reguläre Sprachen

Hier sehen Sie einige Beispiele für gültige und ungültige Email-Adressen. Mit gültig meine ich, dass sie syntaktisch korrekt sind, ungeachtet, ob ein Konto mit dieser Email-Adresse besteht.

thomas.schmitz@hszg.de                              Gültig
dominik@cs.sjtu.edu.cn                              Gültig
raffaela@mayer@gmail.com                            Ungültig: @ kommt zweimal vor
lorenz.klein@greatest/company/in/the/world.com      Ungültig: Domain-Name darf kein / enthalten
.schlaumeier@gmail.com                              Ungültig: Google will kein . an erster Stelle

Hier sehen Sie den Teil eines HTML-Dokuments. Beachten Sie die typische hierarchisch-geschachtelte Struktur (sie müssen es nicht im Detail lesen):

<div class="carousel-inner" style="display:inline-block">
    <div class="item active">
        <p>$110 x + 794$</p><img loading="lazy" src="img/hash/hashfunction_110_794.svg">
    </div>
    <div class="item">
        <p>$502 x + 121$</p><img loading="lazy" src="img/hash/hashfunction_502_121.svg">
    </div>
    <div class="item">
        <p>$617 x + 5$</p><img loading="lazy" src="img/hash/hashfunction_617_5.svg">
    </div>
    <div class="item">
        <p>$815 x + 562$</p><img loading="lazy" src="img/hash/hashfunction_851_562.svg">
    </div>
    <div class="item">
        <p>$868 x + 858$</p><img loading="lazy" src="img/hash/hashfunction_868_858.svg">
    </div>
    <div class="item">
        <p>$915 x + 320$</p><img loading="lazy" src="img/hash/hashfunction_915_320.svg">
    </div>
</div class="carousel-inner">

Hier sehen Sie einen Ausschnitt aus einem Elm-Programm (auch diesen müssen Sie nicht im Detail lesen):

find : Bst -> String -> Maybe String
find tree key =
    case tree of
        Empty _ ->
            Nothing
        Node ( keyHere, valueHere ) leftChild rightChild ->
            if key == keyHere then
                Just valueHere
            else if key < keyHere then
                find leftChild key
            else
                find rightChild key

Als letztes Beispiel sehen Sie hier eine svg-Datei. Dies ist ein Dateiformat für Vektorgrafiken. In diesem Falle ein Kreis mit einer Geraden:

<?xml version="1.0" encoding="UTF-8"?>
<svg
    xmlns="http://www.w3.org/2000/svg"
    xmlns:xlink="http://www.w3.org/1999/xlink"
    width="204px" height="204px"
    viewBox="0 0 102 102"
    version="1.1"
>
    <g id="layer 1">
        <circle
            style="fill:none;stroke:rgba(255,0,0,255);stroke-width:0.7;"
            cx="51"
            cy="51"
            r="40"
        />
        <path
            style="fill:none;stroke:rgba(255,0,0,255);stroke-width:0.7;"
            d="M 51 51 l 33.5 -22.5"
        />
    </g>
</svg>

Was haben diese vier Beispiele gemeinsam? Es handelt sich in allen Fällen um Daten, die in einem bestimmten festgelegten Format dargelegt werden. Soll ein Rechner etwas sinnvolles damit anfangen (zum Beispiel das Elm-Programm starten oder die HTML-Seite oder die Svg-Datei auf dem Bildschirm darstellen), muss er dieses Format erst einmal "verstehen", also den bloßen String aus ASCII-Zeichen umwandeln in eine logisch sinnvolle Struktur. Und genau darum geht es in den Formalen Sprachen: wir wollen Begriffe, Regeln, Methoden, Algorithmen entwickeln, um Daten, die in einem bestimmten Format vorliegen, zu verarbeiten; ja auch erst einmal überhaupt Begriffe festlegen, wie man solche Formate definiert.

Korrekte Email-Adressen

Kommen wir auf unser erstes, einfachstes Beispiel zurück: die Email-Adressen. Können Sie möglichst präzise und möglichst formal beschreiben, wie eine korrekte Email-Adresse auszusehen hat? Hier versuche ich es einmal:

Eine Emailadresse besteht aus einem Benutzernamen und einem Domainnamen, die mit einem @ verbunden sind. Der Benutzername ist ein nichtleerer String bestehend aus Groß- und Kleinbuchstaben, Zahlen, und Punkten (.). Erster und letzter Buchstaben dürfen keine Punkte sein, außerdem dürfen keine zwei Punkte nebeneinander stehen. Der Domainname ist eine Folge von mindestenes zwei Labels, die jeweils mit einem . separiert sind. Ein Label ist ein nichtleerer String aus Groß- und Kleinbuchstaben, Zahlen und dem Bindestrich (-).

Die genauen Regeln mögen von Anbieter zu Anbieter variieren; ich habe mich mal an das gehalten, was ich experimentell bei gmail.com herausgefunden habe. Die obige Beschreibung ist (hoffentlich) verständlich und präzise und unzweideutig. Allerdings ist sie in natürlicher Sprache verfasst; es ist beispielsweise nicht klar, wie ein Rechner aus der obigen Beschreibung einen Algorithmus konstruieren kann, der Korrektheit einer Email-Adresse überprüft. Außerdem schleichen sich bei natürlicher Sprache schnell Zweideutigkeiten ein, die a priori nicht immer zu erkennen sind. Wir wollen daher ein formales Regelwerk erstellen, wie wir Formate dieser Art vollständig und eindeutig beschreiben können. Ich werde dies nun Schritt für Schritt entwickeln, erst informell anhand des Email-Adressen-Beispiels und dann, im nächsten Kapitel, formal und abstrakt. Eine Emailadresse ist von der Form Benutzername@Domainnname. Dies können wir als Ableitungsregel darstellen:

<EmailAdress> -> <User> @ <Domain>

Wie können wir nun beispielsweise eine ähnliche Ableitungsregeln für <Domain> erstellen? Eine <Domain> soll eine Folge aus mindestens zwei <Label> sein, jeweils durch einen . separiert. Wir erreichen dies, indem wir einen an Rekursion erinnernden Trick anwenden: entweder gibt es genau zwei Labels oder die Domain beginnt mit einem Label, gefolgt von einem Punkt und wiederum einer Folge von mindestens zwei durch . separierten Labels, also wiederum etwas, das wie ein Domainname aussieht. Daher:

<Domain> -> <Label> . <Label>
<Domain> -> <Label> . <Domain>

Wir geben also zwei Möglichkeiten an, wie mit einem <Domain> zu verfahren ist. Was ist nun <Label>? Dies ist eine nichtleere Folge von in Domainnamen erlaubten Zeichen. Diese sind alphanumerisch (Buchstaben und Zahlen) und der Strich - (in der Praxis sind eventuell noch weitere Zeichen erlaubt; im Ernstfall hängt dies davon ab, was die Domain Name Server des jeweiligen Landes / der jeweiligen Top-Level-Domain erlauben, siehe zum Beispiel Wikipedia: Internationalized Domain Name. Wie formulieren wir nichtleere Folge von ... mit unserer -->;-Notation? Wieder mit dem Rekursionstrick:

<Label> -> <AlphaNumOrDash>
<Label> -> <AlphaNumOrDash> <Label>
<AlphaNumOrDash> -> <AlphaNum>
<AlphaNumOrDash> -> -

Nun müssen wir noch Regeln für <AlphaNum> angeben. Hier führen wir eine weitere Konvention ein: nämlich, dass wir verschiedene Alternativen mit einem senkrechten Strich | separieren:

<AlphaNum> -> a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
<AlphaNum> -> A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
<AlphaNum> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Beachten Sie: ich habe hier absichtlich nicht <AlphaNum> *->* a *|* ... *|* z geschrieben, weil ich in diesem Beispiel wirklich alles ausschreiben wollte und mit der ...-Notation schon wieder etwas menschen- aber nicht maschinenlesbares eingeführt hätte. Wir brauchen noch Regeln für <User>. Dies ist ein nichtleerer String aus alphanumerischen Zeichen und dem Punkt ., wobei der Punkt nicht am Anfang und nicht am Ende stehen darf. Also: eine nichtleere Folge von Namensblöcken, die jeweils durch . separiert sind, wobei ein Namensblock eine nichtleere Folge alphanumerischer Zeichen ist.

<User> -> <NameBlock> | <NameBlock> . <User>
<NameBlock> -> <AlphaNum> | <AlphaNum> <NameBlock>

Nun haben wir unser Emailformat vollständig beschrieben. Das gesamte Regelwerk sehen Sie hier noch einmal im Ganzen:

<EmailAddress>    ->    <User> @ <Domain>
<Domain>          ->    <Label> . <Label> | <Label> . <Domain>
<User>            ->    <NameBlock> | <NameBlock> . <User>
<NameBlock>       ->    <AlphaNum> | <AlphaNum> <NameBlock>
<Label>           ->    <AlphaNumOrDash> | <AlphaNumOrDash> <Label>
<AlphaNumOrDash>  ->    <AlphaNum> | -
<AlphaNum>        ->    a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
<AlphaNum>        ->    A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Ein Beispiel einer formalen Grammatik und einer Ableitung

Was Sie hier sehen, nennt man eine formale Grammatik. Ihre Bestandteile sind:

Das Alphabet $\Sigma$ aller verwendeten Zeichen, in unserem Fall also $\Sigma = \{a,\dots,z,A,\dots,Z,.,-,@\}$ . Wir nennen $\Sigma$ die Menge der terminalen Symbole.
Eine Menge $N$ abstrakter Symbole, hier
$N = \{\texttt{<EmailAddress>,<Domain>,<User>,<NameBlock>,<Label>,<AlphaNumOrDash>,<AlphaNum>}\} \ .$
Diese Menge nennen wir die nichtterminalen Symbole. Wir verlangen, dass $N \cap \Sigma = \emptyset$ gilt; ein Symbol kann also nicht gleichzeitig Terminalsymbol und Nichtterminalsymbol sein.
Eine Menge $P$ von Regeln, auch Produktionen genannt, wobei jede Regel die Form $X \rightarrow \alpha$ hat, wobei $\alpha$ eine beliebig lange endliche Folge von Symbolen in $\Sigma \cup N$ ist.
Ein Startsymbol $S \in N$, das angibt, wo wir mit unserer Ableitung beginnen sollen. Im obigen Beispiel sind wir ja an Emailadressen interessiert, also ist <EmailAddress> das Startsymbol.

Wenn wir nun so eine Grammatik gegeben haben, können wir Wörter ableiten; das heißt, wir beginnen mit dem Startsymbol und ersetzen in jedem Schritt ein nichtterminales Symbol durch die rechte Seite einer entsprechenden Regel. Dieser Vorgang ist nicht eindeutig und lässt mehrere Möglichkeiten offen; das ist auch gut so, denn es soll ja mehr als eine Email-Adresse geben. Hier ist ein Beispiel für eine Ableitung basierend auf der obigen Grammatik:

<EmailAddress> -> <User>@<Domain>
            -> <NameBlock>.<User>@<Domain>
            -> <NameBlock>.<NameBlock>@<Domain>
            -> <NameBlock>.<NameBlock>@<Label>.<Domain>
            -> <NameBlock>.<NameBlock>@<Label>.<Label>.<Label>
            -> <AlphaNum>.<NameBlock>@<Label>.<Label>.<Label>
            -> <AlphaNum>.<AlphaNum>@<Label>.<Label>.<Label>
            -> <AlphaNum>.<AlphaNum>@<AlphaNumOrDash>.<Label>.<Label>
            -> <AlphaNum>.<AlphaNum>@<AlphaNumOrDash>.<AlphaNumOrDash>.<Label>
            -> <AlphaNum>.<AlphaNum>@<AlphaNumOrDash>.<AlphaNumOrDash>.<AlphaNumOrDash><Label>
            -> <AlphaNum>.<AlphaNum>@<AlphaNumOrDash>.<AlphaNumOrDash>.<AlphaNumOrDash><AlphaNumOrDash>
            -> d.<AlphaNum>@<AlphaNumOrDash>.<AlphaNumOrDash>.<AlphaNumOrDash><AlphaNumOrDash>
            -> d.<AlphaNum>@<AlphaNumOrDash>.<AlphaNumOrDash>.<AlphaNumOrDash>e
            -> d.<AlphaNum>@<AlphaNumOrDash>.<AlphaNumOrDash>.de
            -> d.s@<AlphaNumOrDash>.<AlphaNumOrDash>.de
            -> d.s@<AlphaNumOrDash>.b.de
            -> d.s@a.b.de

Nach dem gleichen Schema könnten wir d.s.@-.-.-- ableiten, was darauf schließen lässt, dass unsere Grammatik nicht wirklich das tut, was wir beabsichtigen, dass sie nämlich zu viele Emailadressen herleitet, auch solche, die wir nicht als zulässige Adressen gelten lassen wollen.

Übungsaufgabe 5.1 Formulieren Sie weitere Regeln, um unsinnige Domainnamen wie -.-.-- zu verbieten. Wie müssen Sie die obige Grammatik ändern?

Terminologie, formale Definitionen und Beispiele

Im letzten Abschnitt haben wir die Regeln für die Bildung syntaktisch korrekter Emailadressen formalisiert. Zwar unvollständig, doch hoffe ich, dass das allgemeine Schema klar geworden ist. Wir werden nun alles formaler und abstrakter definieren.

Alphabet

Wenn wir über formale Sprachen reden, so liegt immer eine (endliche) Menge von Symbolen zugrunde, das Alphabet $\Sigma$. Im Emailadressen-Beispiel war (\Sigma) recht groß: die 52 Buchstaben; 10 Ziffern; die Zeichen @ . - . Für Java-Programme oder andere Programmiersprachen kämen noch weitere Zeichen hinzu, zum Beispiel + - / \ { } und so weiter; wenn wir alle Unicode-Zeichen miteinschließen, landen wir im Millionenbereich. In den theoretischen Beispielen, die in diesem Kurs folgen werden, ist das Alphabet fast immer viel kleiner: typische Alphabete zum Beispiel sind $\{0,1\}$ , $\{a,b,c,d\}$ oder auch $\{1\}$ , ein Alphabet mit nur einem Zeichen. Für ein Alphabet $\Sigma$ bezeichnen wir mit $\Sigma^*$ die Menge aller endlichen Strings über diesem Alphabet; das schließt den leeren String mit ein, den wir mit $\epsilon$ bezeichnen. So ist beispielsweise

\{a,b\}^* = \{\epsilon, a, b, aa, ab, ba, bb, aaa, aab, aba, ...\}

Ein Element $x \in \Sigma^*$, also einen endlichen String aus $\Sigma$-Symbolen, bezeichnen wir als Wort über $\Sigma$. Mit $\Sigma^+$ bezeichnen wir die Menge aller nichtleeren Strings, also $\Sigma^+ = \Sigma^* \setminus \{\epsilon\}$.

Sprachen

Eine Teilmenge $L \subseteq \Sigma$ bezeichnen wir in diesem Kontext als Sprache und kürzen Sie oft mit $L$ ab, was für language steht. Beispiele für Sprachen wären

Die Sprache aller syntaktisch korrekten Emailadressen.
Die Sprache aller Java-Programme, die ohne Fehlermeldung kompilieren
Die Sprache aller Java-Programme, die kompilieren, dann aber mit einem Laufzeitfehler abbrechen.
Die Sprache aller Java-Programme, die kompilieren und nicht mit einem Laufzeitfehler abbrechen.
Die Sprache aller Wörter über $\{a,b\}$, die gleich viele $a$'s wie $b$'s enthalten.
Die Sprache aller Palindrome über $\{a,b,c,d\}$, also Wörter, die von vorne wie hinten gelesen gleich aussehen.

Wir wollen herausfinden, welche Arten von Sprachen wir mit den im letzten Abschnitt eingeführen Regelwerk aus Ableitungen beschreiben können. Für die gerade aufgelisteten sechs Sprachen lautet die Antwort

Ja, können wir.
Ja, wenn wir leicht komplexere Ableitungsregeln erlauben.
Ja, wenn wir leicht komplexere Ableitungsregeln erlaubten.
Nein, können wir nicht.
Ja, können wir.
Ja, können wir.

Grammatiken

Definition 5.1 (Kontextfreie Grammatik). Eine kontextfreie Grammatik besteht aus

einem endlichen Alphabet $\Sigma$, den terminalen Symbolen;
einer dazu disjunkten endlichen Menge $N$, genannt die nichtterminalen Symbole;
einer endlichen Menge $P$ von Produktionsregeln der Form $X \rightarrow \alpha$ mit $X \in N$ und $\alpha \in (\Sigma \cup \N)^*$; formal also $P \subseteq N \times (\Sigma \cup \N)^*$.
einem Startsymbol $S \in N$.

Die Grammatik $G$ ist also ein 4-Tupel $(\Sigma, N, P, S)$.

Woher der Name kontextfrei kommt, werden Sie hoffentlich verstehen, wenn wir Ableitungen definiert haben. Die Tradition will es, dass wir für die terminalen Symbole Zahlen oder lateinsiche Kleinbuchstaben und für die nichtterminalen Symbole lateinische Großbuchstaben verwenden. Dies ist eine Konvention, die hilfreich ist, solange wir auf abstrakt-theoretischer Ebene über formale Grammatiken sprechen; wenn Sie z.B. eine Grammatik für Java erstellen wollen, dann wird $\Sigma$ natürlich auch Großbuchstaben enthalten.

Beispiel 5.2 Wir betrachten die Grammatik $G = (\{a,b\}, \{S, A, B\}, P, S)$ mit den Produktionsregeln

\begin{align*} S&\rightarrow A B \\ A&\rightarrow \epsilon \ | \ a A \\ B&\rightarrow \epsilon \ | \ b B \ . \\ \end{align*}

Formal sind die Produktionsregeln $P$ eine Teilmenge von $N \times (\Sigma \cup \N)^*$, also

P = \{ (S, AB), (A, \epsilon), (A, aA), (B, \epsilon), (B, bB) \} \ .

Für konkrete Beispiele wie die gerade betrachtete Grammatik jedoch verwenden wir einfach die Pfeilschreibweise $S \rightarrow AB, \dots$. Hier ist eine Ableitung basierend auf der Grammatik:

\begin{align*} S \Rightarrow AB \Rightarrow aAB \Rightarrow aAbB \Rightarrow aAbbB \Rightarrow aAbb \Rightarrow abb \ . \end{align*}

In jedem Schritt wählen wir ein Nichtterminal aus, zum Beispiel im zweiten Schritt $A$, und wenden eine Regel an, zum Beispiel $A \rightarrow aA$. Dadurch wird $AB$ zu $aAB$. Wir setzen diese Ableitungsschritte so lange fort, bis nur noch terminale Symbole übrigbleiben. Dann hat sich ein Wort $\alpha \in \Sigma^*$ ergeben.

Definition 5.3 Gegeben sei eine kontextfreie Grammatik $G = (\Sigma, N, P, S)$. Ein String $\alpha \in (\Sigma \cup N)^*$ heißt Wortform (im Gegensatz zu einem Wort $x \in \Sigma^*)$. Für zwei Wortformen $\alpha , \beta$ schreiben wir

\alpha \Rightarrow \beta

wenn wir $\alpha$ zu $\beta$ machen können, indem wir ein nichtterminales Symbol $X$ in $\alpha$ durch die rechte Seite $X \rightarrow \gamma$ ersetzen können. Formal gesprochen, wenn wir $\alpha = \alpha_1 X \alpha_2$ und $\beta = \beta_1 \gamma \beta_2$ mit Wortformen $\alpha_1, \alpha_2, \beta_1, \gamma, \beta_2$ und einem Nichtterminal $X$ schreiben können, so dass $X \rightarrow \gamma$ eine Produktionsregel in $P$ ist. Wenn wir $\alpha = \beta$ "vorlesen", dann sagen wir $\beta$ kann aus $\alpha$ in einem Schritt abgeleitet werden. Wenn $\beta$ aus $\alpha$ in mehreren (im Extremfall null) Schritten abgeleitet werden kann, so schreiben wir $\alpha \Rightarrow^* \beta$. Formal bedeutet $\alpha \Rightarrow^* \beta$, dass es ein $k \geq 0$ gibt und "Zwischenwortformen" $\alpha_0, \alpha_1, \dots, \alpha_k$ mit $\alpha = \alpha_0$ und $\alpha_k = \beta$, sodass $\alpha_i \Rightarrow \alpha_{i+1}$ für alle $i = 0, 1, \dots, k-1$ gilt. Dies schließt den "trivialen" Fall $k=0$ mit ein, in welchem $\alpha = \beta$ gilt.

Nochmals: wenn $\alpha$ die Form $\alpha_1 X \alpha_2$ hat, dann dürfen Sie das Nichtterminal $X$ durch die rechte Seite einer Produktionsregel $X \rightarrow \gamma$ ersetzen; Sie dürfen das unabhängig von dem Kontext, in welchem $X$ in der Wortform $\alpha$ vorkommt. Daher rührt der Name kontextfreie Grammatik. Beachten Sie, dass $P$ per Definition eine endliche Menge von Regeln sein muss, dass jedoch $\Rightarrow$ im Allgemeinen unendlich ist. Bereits für unsere einfache Grammatik mit den Produktionsregeln

\begin{align*} S&\rightarrow A B \\ A&\rightarrow \epsilon \ | \ a A \\ B&\rightarrow \epsilon \ | \ b B \ . \\ \end{align*}

haben wir beispielsweise

\begin{align*} A&\rightarrow aA \\ aA&\rightarrow aaA \\ aaA&\rightarrow aaaA \\ \dots \end{align*}

und sehen, dass die Menge aller Paare $\alpha \Rightarrow \beta$ unendlich ist.

Definition 5.4 (Die von einer Grammatik erzeugte Sprache). Sei $G = (\Sigma, N, P, S)$ eine kontextfreie Grammatik. Die von $G$ erzeugte Sprache $L(G)$ ist die Menge aller Wörter, die vom Startsymbol $S$ abgeleitet werden können, also

\begin{align*} L(G) := \{x \in \Sigma^* \ | \ S \Rightarrow^* x\} \ . \end{align*}

Wenn es zu einer Sprache $L \subseteq \Sigma^*$ eine kontextfreie Grammatik $G$ mit $L(G) = L$ gibt, so nennen wir $L$ eine kontextfreie Sprache. Beachten Sie, dass in dem obigen Beispiel die Wortform $aaAB$ zwar aus $S$ abgeleitet werden kann, allerdings kein Wort ist, da es noch nichtterminale Symbole enthält. Es gilt also $aaAB \not \in L(G)$. Oft können wir $L(G)$ kompakt mit natürlicher Sprache beschreiben:

Beispiel 5.5 Sei $G$ die zuletzt betrachtete Grammatik. Dann ist $L(G)$ die Menge aller Wörter der Form $a^* b^*$, also Wörter, in denen auf beliebig viele $a$'s beliebig viele $b$'s folgen.

Wir betrachten nun einige weitere Beispiele

Beispiel 5.6 Wir betrachten die Grammatik $G_2 = (\{a,b\}, \{S\}, P, S)$ mit den Produktionsregeln

\begin{align} S&\rightarrow aSbS \\ S&\rightarrow bSaS \\ S&\rightarrow \epsilon \ . \end{align}

Hier sind mögliche Ableitungen des Wortes $abab$. Zur Verdeutlichung schreiben wir über den Pfeil $\Rightarrow$ die Nummer der Regel, die wir angewendet haben:

\begin{align*} S&\stackrel{(1)}{\Rightarrow} aSbS \stackrel{(1)}{\Rightarrow} aSbaSbS \stackrel{(3)}{\Rightarrow} aSbaSb \stackrel{(3)}{\Rightarrow} abaSb \stackrel{(3)}{\Rightarrow} abab \\ S&\stackrel{(1)}{\Rightarrow} aSbS \stackrel{(3)}{\Rightarrow} abS \stackrel{(1)}{\Rightarrow} abaSbS \stackrel{(3)}{\Rightarrow} ababS \stackrel{(3)}{\Rightarrow} abab \ . \end{align*}

Wir sehen also: das gleiche Wort kann mehrere Ableitungen haben. Da die Ersetzungsregeln kontextfrei sind, spielt es keine Rolle, in welcher Reihenfolge wir nichtterminale Symbole ersetzen. Wenn Sie scharf hinschauen, werden Sie erkennen, dass die beiden Ableitungen "irgendwie gleich" sind, dass nur die Ableitungen in anderer Reihenfolge durchgeführt worden sind. Ich werde das in einem späteren Kapitel formal definieren, was ich mit damit meine. Um Ordnung in das Chaos zu bringen, könnten wir uns zum Beispiel einigen, dass man immer das am weitesten links stehende Nichtterminal ersetzen muss. Das nennt man eine Linksableitung. Dies ist nicht wirklich eine Einschränkung, da die Ersetzungsreihenfolge keine Rolle spielt. Wir sehen, dass die zweite Ableitung des Wortes $abab$ oben eine Linksableitung ist; zusammen mit der Beschriftung $\stackrel{(i)}{\Rightarrow}$, die die Nummer der angewendeten Regel angibt, ist eindeutig, wie wir von $S$ zum abgeleiteten Wort gekommen sind. Betrachten Sie nun eine weitere Linksableitung $S \Rightarrow^* abab$:

\begin{align*} S&\stackrel{(1)}{\Rightarrow} aSbS \stackrel{(2)}{\Rightarrow} abSaSbS \stackrel{(3)}{\Rightarrow} abaSbS \stackrel{(3)}{\Rightarrow} ababS \stackrel{(3)}{\Rightarrow} abab \end{align*}

Sehen Sie, dass diese Ableitung qualitativ anders ist, da wir hier auch die Regel $S \rightarrow bSaS$ angewendet haben? Um die Struktur der Ableitung zu verdeutlichen, könnten wir die ersten beiden Ableitungen mit Wort $S \Rightarrow^* (ab)(ab)$ bezeichnen und die dritte mit Wort $S \Rightarrow^* a(ba)b$.

Ziele der Theorie der formalen Sprachen

Ganz allgemein gesagt wollen wir lernen, wie wir Sprachen formal beschreiben können; wie wir, gegeben eine Grammatik $G$ und ein Zielwort $x$, eine Ableitung $G \Rightarrow^* x$ finden können. Anhand der Ableitungssequenz können wir dann oft auf die logische Struktur von $x$ schließen. Handelt es sich bei $G$ zum Beispiel um eine Grammatik für die Programmiersprache Java, so wäre ein Ziel, aus der Ableitungssequenz $G \Rightarrow^* x$ die Struktur des Programms $x$, also Klassenstruktur, Methoden, etc., ablesen zu können und schlussendlich das Programm in ausführbaren Maschinencode kompilieren zu können.

Algorithmisches Problem: Parsing 5.7 Gegeben eine (kontextfreie) Grammatik $G$ und ein Zielwort $x$ , finde eine Ableitung $G \Rightarrow^* x$, falls es so eine gibt. Für einen String $x$ eine Ableitung zu finden bezeichnen wir als parsen, das zugehörige Hauptwort als Parsing.

Die gute Nachricht: Die gute Nachricht: wir kennen Algorithmen, die dieses Problem im effizient lösen, wenn wir den "theoretischen" Effizienzbegriff zugrund legen.

Die schlechte Nachricht: wir kennen keinen Algorithmus, der das Parsing kontextfreier Sprachen in seiner ganzen Allgemeinheit in linearer Zeit erledigt, dessen Laufzeit also proportional zur Länge des Zielwortes $x$ ist. Dies ist aber, was wir in der Praxis, zum Beispiel bei Compilern, erwarten.

Die gute Nachricht: in fast allen praktisch relevanten Fällen haben wir es mit Grammatiken zu tun, die Parsing in linearer Zeit ermöglichen. Und wenn wir Programmiersprachen, Datenformate etc. entwerfen, haben wir es ja in der Hand, Sprache und Grammatik so anzulegen, dass effizientes Parsen möglich ist. Im nächsten Kapitel lernen wir eine stark eingeschränkte, aber dennoch sehr wichtige Klasse kontextfreier Grammatik kennen, die allesamt ein sehr effizientes Parsing erlauben: die sogenannten regulären Grammatiken.