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 dazu führen würde, dass es sich nicht mehr um einen determinierten ENDLICHEN Automaten handelt. 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 DEA um eine Speichervorrichtung für Klammern. Dieser Speicher kann sich merken, wie viele 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 (hier: 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. Wir könnten jetzt eine Klasse Kellerautomat entwickeln, die ein entsprechendes Stack-Objekt als Attribut eingebunden hätte. In diesem Kurs verfolge ich aber den anderen Ansatz über die Rekursion. Wir werden (im nächsten Kapitel) einen rekursiven Parser betrachten, mit dem man arithmetische Klammerausdrücke analysieren kann. Dazu ist es aber erforderlich, dass wir uns zunächst mit sogenannten kontextfreien Grammatiken beschäftigen. Aus didaktisch-methodischen Gründen möchte ich hier aber nicht mit der Tür ins Haus fallen, sondern zunächst einmal mit den Syntaxdiagrammen beginnen, die Sie vielleicht noch aus dem Kurs der Stufe 10 bzw. 11 kennen.

Hier sehen Sie ein solches Syntaxdiagramm, und zwar das Syntaxdiagramm für eine if-Anweisung.

Und nun betrachten Sie bitte folgendes Syntaxdiagramm:

Dieses Syntaxdiagramm definiert, was man unter einem arithmetischen Ausdruck (expr) versteht.

Eine solcher Ausdruck kann eine einfache Zahl (num) oder ein einfacher Bezeichner sein (id). Ein Ausdruck des Typs expr kann sich aber auch aus zwei anderen Ausdrücken (expr) zusammensetzen, zwischen denen ein arithmetischer Operator steht (+ oder *; weitere Operatoren möglich, aber nicht eingezeichnet).

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 auf das Startsymbol expr an:

expr ===> num

Das ist ja toll. Wir haben soeben festgestellt, dass beispielsweise die Zahl 7 ein korrekter arithmetischer Ausdruck ist.

Wenden wir nun die Regel 4 auf das Startsymbol expr an:

expr ===> expr * expr

Irgendwie sind wir noch nicht am Ende. Das, was wir da produziert haben, ist noch kein arithmetischer Ausdruck, sondern eher ein grammatikalischer Ausdruck. So ähnlich wir im Englischunterricht "Subjekt - Prädikat - Objekt" ist auch kein englischer Satz, sondern beschreibt den grammatischen Aufbau eines solchen. Und die Phrase "while (Bedingung) Anweisung" ist keine gültige Java-Zeile, sondern die Beschreibung einer while-Schleife. In eine ähnliche Kategorie gehört das "expr * expr", das wir durch die Anwendung der vierten Regel auf das Startsymbol expr gerade erzeugt haben.

Machen wir also weiter. Auf das linke "expr" des Ausdrucks "expr * expr" können wir jetzt die Regel 1 anwenden und erhalten folgende Ableitung:

expr * expr ===> num * expr

Auf das rechte expr wenden wir anschließend die Regel 2 an:

num * expr ===> num * id

Jetzt erst sind wir fertig; wir haben einen einfachen arithmetischen Ausdruck generiert, der z.B. für "3.14 * radius" stehen könnte.

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

Erzeugen Sie auf die gleiche Weise die folgenden arithmetischen Audrücke:

(17 + 4) * 3
(17 + 4) * (18 + 5)
17 + 4 + 5

3. Kontextfreie Grammatiken

Kommen wir nun zu dem eigentlichen Thema dieser Seite. Das Zeichnen von Syntaxdiagrammen ist eine zeitaufwändige Sache, und nicht jeder kann so schön zeichnen wie ich (hüstel hüstel...). Vergleichen Sie bitte die Zeichnung von eben

mit folgender schriftlichen Notierung:

1. Expr ---> num
2. Expr ---> id
3. Expr ---> Expr + Expr
4. Expr ---> Expr * Expr
5. 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 1 an:

Expr ===> id

Damit wären wir schon fertig mit der Ableitung. Der Ausdruck "id" ist ein arithmetischer Ausdruck, er steht beispielsweise für die Zahl 14.

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

Expr ==> Expr * Expr

Auf der rechten Seite wenden wir auf das am weitesten links stehende Expr die Regel 5 an:

Expr * Expr ==> (Expr) * Expr

Auf das am weitesten links stehende Expr wird jetzt die Regel 3 angewandt:

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

Und wieder wenden wir Regel 3 auf das am weitesten links stehende Symbol an:

(Expr + Expr) * Expr ==> 

						(Expr + Expr + Expr) * Expr

Nun kommt die Regel 1 an die Reihe:

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

						(num + Expr + Expr) * Expr

Das am weitesten links stehende Expr ist wieder unterstrichen. Auf dieses Nichtterminal wird die nächste Produktionsregel angewandt. Unter einem Nichtterminal versteht man das Gegenteil von einem Terminal. Ein Terminal ist immer ein konkretes Wort aus der Sprache der zugehörigen Grammatik. Unsere "Grammatik der arithmetischen Ausdrücke" hat folgende Worte:

• num
• id
• (
• )
• +
• *

Betrachten wir den letzten Ausdruck noch einmal, diesmal sind aber die Terminale rot eingefärbt:

(num + Expr + Expr) * Expr

Solange ein solcher Ausdruck noch Nichtterminale enthält (hier blau gefärbt), sind wir mit unseren Ableitungen noch nicht am Ende. Machen wir also weiter. Anwendung der Produktionsregel 2 (Expr ---> id) auf das am weitesten links stehende Nichtterminal führt zum Ausdruck

(num + id + Expr) * Expr

Das am weitesten links stehende Nichtterminal ist wieder unterstrichen. Auf dieses Nichtterminal wenden wir nun die Regel 1 an:

(num + id + num) * Expr

Und schließlich wird die Regel 2 auf das letzte Nichtterminal angewendet:

(num + id + num) * id

Jetzt besteht der Ausdruck nur noch aus Terminalen, und wir sind fertig. Der durch eine Reihe von Ableitungen produzierte allgemeine Ausdruck (wir könnten auch "Tokenstrom" sagen) steht jetzt für eine ganze Reihe korrekter arithmetischer Ausdrücke, beispielsweise

(13 + Radius + 18) * Farbe

oder

(4.5 + Umfang + 2.77) * Hoehe

oder

(3.14 + Breite + 500) * Anzahl

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

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

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

stehen könnte. Notieren Sie auch, welche Produktionsregel Sie jeweils benutzt haben.

Ich möchte diese Definition mit Hilfe des oben entwickelten Beispiels erläutern.

zu Punkt 1 - Nichtterminale

Die Grammatik, mit der wir uns eben beschäftigt haben, besteht aus folgenden Nichtterminalen:

• Expr

In der Tat, es gibt Grammatiken mit nur einem Nichtterminal. Meistens haben Grammatiken aber mehrere solcher Nichtterminale. Sie können darauf wetten, dass Sie im Laufe des Lehrgangs noch ein paar Beispiele hierfür kennenlernen werden.

Wir halten also fest: N = { Expr }

zu Punkt 2 - Terminale

Die Terminale unserer Grammatik haben Sie bereits kennengelernt:

• num
• id
• (
• )
• +
• *

Wir stellen also fest: T = {num, id, (, ), +, *}

zu Punkt 3 - Produktionsregeln

Auch die Produktionsregeln unserer Grammatik sollten Ihnen bekannt sein, schließlich haben wir schon fleißig damit gearbeitet:

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

Beachten Sie: Jede Regel hat bei unserer Grammatik 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:

zu Punkt 4 - Startsymbol

Eines der Symbole aus N wird als Startsymbol bezeichnet. In der vorliegenden Beispielgrammatik besteht N aus nur einem Element, nämlich Expr, 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, wenn wir diese um die Terminale { - , / } und die beiden entsprechenden Produktionsregeln erweitern würden.

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

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

• Satz --> Nominativartikel Subjekt Prädikat Akkusativartikel Objekt .
• Nominativartikel --> "Der" | "Die" | "Das"
• Subjekt --> "Forelle" | "Hecht" | "Krebs"
• Prädikat --> "frisst"
• Akkusativartikel --> "den" | "die" | "das"
• Objekt --> "Forelle" | "Krebs" | "Plankton"

Diese Grammatik unterscheidet sich etwas von der Grammatik für arithmetische Ausdrücke. Erstere erzeugt allgemeine Tokenströme, keine konkreten arithmetischen Ausdrücke mit Zahlenangaben. Die Grammatik hier dagegen erzeugt keinen Tokenstrom, sondern fertige Ketten von Terminalen wie beispielsweise "Der Forelle frisst die Krebs". Ob diese Terminalketten Sinn machen, steht auf einem anderen Blatt; einer kontextfreien Grammatik ist es egal, ob die von ihr produzierten Terminalketten Sinn machen - syntaktisch sind sie jedenfalls korrekt.

In Wirklichkeit besteht P, also die endliche Menge an Produktionsregeln, nicht aus sechs Produktionen, sondern aus 14 solcher Regeln. Produktionsregeln mit identischer linker Seite kann man einfach mit einem senkrechten Strich voneinander trennen.

Nun zu Ihren eigentlichen Aufgaben

1. Geben Sie die Mengen N und T sowie das Startsymbol s dieser Grammatik an
   (1 Punkt).
   
   
2. Produzieren Sie fünf verschiedene Sätze der Sprache L(G)
   (2 Punkte).
   
   
3. Überprüfen Sie anhand der Produktionsregeln, ob der Satz "Die Plankton frisst den Forelle" syntaktisch korrekt ist
   (1 Punkt).
   
   
4. Erläutern Sie den Unterschied zwischen syntaktischer Richtigkeit und semantischer Richtigkeit anhand des Satzes aus c)
   (1 Punkt).
   
   
5. 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)
   
   

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

Betrachten Sie folgende 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)

Hier nun die Aufgaben:

1. Geben Sie die Mengen N und T sowie das Startsymbol s dieser Grammatik an
   (1 Punkt).
   
   
2. Produzieren Sie fünf verschiedene Sätze der Sprache L(G)
   (2 Punkte).
   
   
3. 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

Und hier die Aufgaben:

1. Geben Sie sechs verschiedene Beispiele für L(G) an
   (3 Punkte)
   
   
2. 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 und stark überarbeitet am 20. Februar 2011.