Folge 29 - kontextfreie Grammatiken

1. Keller-Automaten

Wir wollen jetzt einen Determinierten Endlichen Automaten (DEA) konstruieren, der arithmetische Klammerausdrücke mit maximal zwei Klammerebenen erkennen kann, also zum Beispiel:

5 * (3 - 7)

oder

( (1 + 5) * (7 + 12) - 5 ) * 13

Das Eingabealphabet S eines solchen Automaten sähe so aus:

S = { num, op, ( , ) }

und die Übergangsfunktion d könnte durch folgendes Diagramm veranschaulicht werden:

Wollte man den Automaten so erweitern, dass er maximal drei Klammerebenen erkennt, so müssten wir zwei weitere Zustände 7 und 8 ergänzen. Für jede weitere Klammerebene kämen zwei neue Zustände dazu. Ein DEA für maximal vier Klammerebenen hätte also schon zehn Zustände. Und ein DEA für beliebig viele Klammerebenen müsste unendlich viele Zustände haben, was - wie jeder sofort einsieht - natürlich nur theoretisch möglich ist. Eine Umsetzung in eine Java-Methode wäre allerdings nicht möglich.

Bei solchen Problemen hilft eine Erweiterung des Konzepts der Determinierten Endlichen Automaten. Wir ergänzen den DEALösung:
um eine Speichervorrichtung für Klammern. Dieser Speicher kann sich merken, wieviele Klammern geöffnet bzw. geschlossen sind. Ein Kellerspeicher oer Stack würde sich dazu gut eignen: Offene Klammern werden gepusht, für jede geschlossene Klammer wird einmal gepoppt. Solche Automaten, die einen DEA mit einer Stackverwaltung kombinieren, nennt man Stack-Automaten oder Keller-Automaten. Das folgende Bild zeigt die graphische Darstellung der Übergangsfunktion eines Keller-Automaten für Klammerausdrücke mit beliebig vielen Klammerebenen:

Die Übergangsfunktion sieht jetzt extrem einfach aus; nur zwei Zustände werden noch benötigt. Bei jedem 1-1-Übergang wird ein Symbol auf den Stack gepusht, bei jedem 2-2-Übergang wird das oberste Symbol wieder entfernt.

Ein Wort w gehört zur Sprache L(K) des Kellerautomaten K, wenn zwei Bedingungen erfüllt sind:

1. Der Automat K muss sich im Endzustand (2) befinden, wenn das letzte Zeichen "verzehrt" wurde.
2. Der zugeordnete Stack muss leer sein.

2. Realisierung von Kellerautomaten

Einen Stack kann man prinzipiell auf zwei verschiedene Weisen realisieren. Entweder direkt über eine selbstgeschriebene Stackverwaltung, oder indirekt über Rekursion. Die Stackmaschine aus der Folge 21 basierte auf einer selbstgeschriebenen Stackverwaltung in Form der Klasse Stack. Auch wir könnten hier jetzt eine Klasse Kellerautomat entwickeln, die auf einem solchen Stack beruhte. In diesem Kurs verfolge ich aber einen etwas anderen, abstrakteren Ansatz, und dazu ist es erforderlich, dass wir uns zunächst mit sogenannten kontextfreien Grammatiken beschäftigen.

Um zu einem besseren Verständnis zu gelangen, was man unter einer kontextfreien Grammatik versteht, betrachten Sie bitte folgendes Syntaxdiagramm:

Dieses Syntaxdiagramm definiert, was man unter einer expr (arithmetischer Ausdruck) versteht.

Eine expr kann eine simple Zahl oder ein einfacher Bezeichner sein (zweite und dritte Reihe des Diagramms). Eine expr kann sich aber auch aus zwei anderen expr zusammensetzen, zwischen denen ein arithmetischer Operator steht (erste Reihe des Diagramms). Hier erkennen Sie vielleicht schon, dass das Syntaxdiagramm rekursiv aufgebaut ist. Der Begriff expr wird mit Hilfe des Begriffs expr definiert. Das erinnert stark an die rekursive Definition eines Binärbaums: Entweder ist ein Binärbaum leer oder besteht aus einem Knoten mit einem mit einem linken und einem rechten Binärbaum als Nachfolger. Schließlich kann eine expr auch aus einer expr bestehen, die geklammert ist (letzte Reie des Diagramms).

Mit Hilfe eines solchen Syntaxdiagramms kann man nun beliebig große und tief geschachtelte Klammerausdrücke generieren. Wir fangen immer mit dem "Startsymbol" expr an und wenden dann eine der vier durch das Syntaxdiagramm vorgegebenen "Regeln" an. Als erstes wenden wir mal die Regel 1 an:

expr ===> expr * expr

Wir wollen nun auf das am weitesten links stehende expr die Regel 2 anwenden:

expr * expr ===> num * expr

Auf das rechte expr wenden wir jetzt die Regel 3 an:

num * expr ===> num * id

Wir haben also einen einfachen arithmetischen Ausdruck generiert, der z.B. für

3.14 * radius

stehen kann.

Übung 29.1 (3 Punkte, gut geeignet als Hausaufgabe)

Erzeugen Sie auf die gleiche Weise den folgenden arithmetischen Audruck:

(17 + 4) * 3

3. Kontextfreie Grammatiken

Kommen wir nun zu dem eigentlichen Thema dieser Seite. Das Zeichnen von Syntaxdiagrammen ist eine zeitaufwändige Sache, viel einfacher kann man die Syntax von bestimmten Strukturen definieren, wenn man sogenannte Produktionsregeln einsetzt:

1. Expr ---> Expr + Expr
2. Expr ---> Expr * Expr
3. Expr ---> Expr - Expr
4. Expr ---> Expr / Expr
5. Expr ---> num
6. Expr ---> id
7. Expr ---> ( Expr)

Diese Regeln lassen sich viel einfacher aufschreiben als ein Syntaxdiagramm, sind allerdings nicht so schön bunt und vielleicht etwas unübersichtlicher. Wir wollen jetzt mal sehen, was man mit diesen Regeln anfangen kann. Wir beginnen wieder mit dem Startsymbol Expr und wenden rein willkürlich mal die Regel 6 an:

Expr =6=> id

Damit wären wir schon fertig mit der "Ableitung". Der Ausdruck "id" ist ein arithmetischer Ausdruck!

Jetzt versuchen wir uns an einer zweiten Ableitung. Beginnend mit Expr wenden wir als erstes die Regel 2 an:

Expr =2=> Expr * Expr

Jetzt wenden wir auf das erste Expr rechts vom Pfeil die Regel 7 an:

Expr * Expr =7=> (Expr) * Expr

Auf das erste Expr rechts vom Pfeil wird jetzt die Regel 1 angewandt:

(Expr) * Expr =1=> (Expr + Expr) * Expr

Und wieder wenden wir die nächste Regel auf das am weitesten links stehende Symbol an, diesmal die Regel 3:

(Expr + Expr) * Expr =3=> (Expr - Expr + Expr) * Expr

Jetzt wird die Regel 5 dreimal hintereinander angewandt:

(Expr - Expr + Expr) * Expr =5,5,5=> (num - num + num) * Expr

Und - um die Sache nicht zu lang zu machen - wenden wir jetzt die Regel 6 auf das am weitesten links stehende Expr an:

(num - num + num) * Expr =6=> (num - num + num) * num

Wir haben also die Produktionsregeln auf das Startsymbol angewandt und dabei einen Tokenstrom erzeugt. Dieser Begriff sollte Ihnen ja bereits bekannt sein: Ein Lexer erzeugt ebenfalls einen Tokenstrom. Ein Tokenstrom ist eine endliche Liste von allgemeinen Symbolen, die aber in ihrem Stringattribut oder in ihrem numerischen Attribut dann einen konkreten Wert gespeichert haben. So könnte der Tokenstrom

(num - num + num) * num

zum Beispiel für den konkreten arithmetischen Ausdruck

(20 + 5 - 3.14) * 70

stehen.

Übung 29.2 (4 Punkte, gut geeignet als Hausaufgabe)

Erzeugen Sie mit den obigen Produktionsregeln einen Tokenstrom, der für den arithmetischen Ausdruck

( (200 + 50) / (300 + 60) + 6 ) * 7

stehen könnte. Schreiben Sie die Ableitung auf ähnliche Weise auf wie hier auf dieser Seite gezeigt.

Da Sie sich erst in der Jahrgangsstufe 13 und noch nicht im Informatikstudium befinden, will ich diesen unverständlichen rosa Kasten mal etwas näher erläutern. Betrachten wir dazu folgendes System von Produktionsregeln:

1. Expr --> Expr + Expr
2. Expr --> Expr * Expr
3. Expr --> ( Expr)
4. Expr --> id

Es handelt sich um das gleiche System wie weiter oben, allerdings auf nur vier Regeln zusammengekürzt.

Endliche Menge von Nichtterminalen N

Die zu untersuchende Grammatik enthält nur ein einziges Nichtterminal, nämlich das Symbol Expr, das ich jetzt absichtlich nicht in Anführungszeichen schreibe.

Endliche Menge von Terminalen T

Die Grammatik enthält fünf Terminale oder Terminalsymbole, und zwar folgende:

{+, *, (, ), id}

Die Zeichen "+", "*", "(" und ")" sind dabei echte Terminalsymbole - sie erscheinen genau so im arithmetischen Ausdruck. Das Zeichen id dagegen ist ein Token, es repräsentiert eine ganze Gruppe von Terminalsymbolen wie z.B. "5", "20", "3.14" und so weiter.

Endliche Menge von Produktionsregeln P

Die Grammatik besitzt genau vier Produktionsregeln:

1. Expr --> Expr + Expr
2. Expr --> Expr * Expr
3. Expr --> ( Expr)
4. Expr --> id

Jede Regel hat bei der Beispielgrammatik die folgende Form:

• A --> a

Dabei ist A ein Symbol aus N und a eine Zeichenkette, die aus Symbolen aus N und T zusammengesetzt sein kann. Grammatiken, bei denen alle Produktionsregeln diese Form haben, werden auch als kontextfreie Grammatiken bezeichnet:

Startsymbol s

Eines der Symbole aus N wird als Startsymbol bezeichnet. In der vorliegenden Beispielgrammatik besteht N aus nur einem Element, welches dann gleichzeitig Startsymbol sein muss.

Was kann man mit einer solchen Grammatik nun anfangen? Ein - wenn auch eher theoretisches - Anwendungsgebiet haben wir bereits kennengelernt. Man kann Ketten von Terminalsymbolen, sogenannte Tokenströme, aus dem Startsymbol ableiten, indem man die verschiedenen Produktionsregeln anwendet.

So ist z.B. die Menge aller korrekten arithmetischen Ausdrücke die Sprache der behandelten Beispielgrammatik

Übung 29.3 (8 Punkte, gut geeignet als Hausaufgabe)

Gegeben sei eine Grammatik G mit folgenden Produktionsregeln (aus CHIP Professional von 1989):

1. Satz --> Nominativartikel Subjekt Prädikat Akkusativartikel Objekt .
2. Nominativartikel --> "Der" | "Die" | "Das"
3. Subjekt --> "Forelle" | "Hecht" | "Krebs"
4. Prädikat --> "frisst"
5. Akkusativartikel --> "den" | "die" | "das"
6. Objekt --> "Forelle" | "Krebs" | "Plankton"

Ein senkrechter Strich trennt verschiedene alternative Terminalsymbole voneinander.

a) Geben Sie die Mengen N und T sowie das Startsymbol s dieser Grammatik an (1 Punkt).

b) Produzieren Sie fünf verschiedene Sätze der Sprache L(G) (2 Punkte).

c) Überprüfen Sie anhand der Produktionsregeln, ob der Satz "Die Plankton frisst den Forelle" syntaktisch korrekt ist (1 Punkt).

d) Erläutern Sie den Unterschied zwischen syntaktischer Richtigkeit und semantischer Richtigkeit anhand des Satzes aus c) (1 Punkt).

e) Welche "Nebenabsprachen" müsste man zusätzlich zu den Produktionsregeln treffen, damit nur "sinnvolle" Sätze wie z.B. "Der Hecht frisst die Forelle" produziert werden können (2 Punkte)?

f) Beurteilen Sie abschließend kritisch und begründend: Kann man die deutsche Sprache mit Hilfe einer beliebig umfangreichen kontextfreien Grammatik vollständig erfassen (1 Punkt)?

Übung 29.4 (4 Punkte, gut geeignet als Hausaufgabe)

Betrachten Sie die Produktionsregeln einer Grammatik:

1. Expr --> Term
2. Expr --> Expr + Term
3. Expr --> Expr - Term
4. Term --> Fact
5. Term --> Term * Fact
6. Term --> Term / Fact
7. Fact --> num
8. Fact --> id
9. Fact --> (Expr)

a) Geben Sie die Mengen N und T sowie das Startsymbol s dieser Grammatik an (1 Punkt).

b) Produzieren Sie fünf verschiedene Sätze der Sprache L(G) (2 Punkte).

c) Beweisen Sie anhand der Produktionsregeln, dass der Satz "(3 + 4) * (5 + 6)" syntaktisch korrekt ist (1 Punkt).

Übung 29.5 (6 Punkte, Arbeit am PC)

Sie haben schon einmal den Zufallsgenerator von Java kennengelernt (z.B. bei der Behandlung der Sortieralgorithmen). Schreiben Sie nun ein Java-Applet, welches mit Hilfe der Grammatik aus Übung 29.3 syntaktisch korrekte Sätze in die Konsole ausgibt. Sie dürfen die Produktionsregeln dazu gern erweitern, z.B. weitere Subjekte oder Objekte definieren.

Übung 29.6 (3+1 Punkte, gut geeignet als Hausaufgabe)

Welche Sprache hat die folgende Grammatik:

G = (N, T, P, S) mit N = {S}, T = {a, b} und P = {S --> aSb, S --> ab} ?

(aus: Hopcroft, Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Bonn 1988, S. 84f)

Für einen mathematisch exakten Beweis bekommen Sie einen Zusatzpunkt!

Übung 29.7 (5 Punkte, als Hausaufgabe geeignet)

Welche Sprache hat die folgende Grammatik:

G = (N, T, P, S) mit N = {S, A, B}, T = {a, b} und P wie folgt:

1. S --> aB
2. S --> bA
3. A --> a
4. A --> aS
5. A --> bAA
6. B --> b
7. B --> bS
8. B --> aBB

a) Geben Sie sechs verschiedene Beispiele für L(G) an (3 Punkte)

b) Versuchen Sie allgemein zu erläutern (also ohne konkretes Beispiel), welche Sprache L(G) ist (2 Punkte).

weiter mit Folge 30: Syntaxanalyse

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 31. Juli 2006.