next up previous contents
Next: 6.2.4 Parser Up: 6.2 Eingabeanalyse Previous: 6.2.2 Lösungsansatz

6.2.3 Grammatik

Eine übersichtliche Methode, um Regeln für Parser darzustellen, ist die Backus-Normalform (BNF, [1]).

FETT für Terminale: FLOATNUMBER, :POINT);
kursiv für Nonterminale: point, line-mode;
tex2html_wrap_inline4792 trennt die linke Seite, ein Nonterminal, von der rechten Seite, die eine Ableitung angibt;
tex2html_wrap_inline4794 erlaubt eine beliebige Wiederholung (auch null-mal) des geklammerten Teiles;
tex2html_wrap_inline4796 verlangt mindestens n-maliges Auftreten des geklammerten Teiles.

Ein einfacher Auszug aus der Grammatik, die der PED akzeptiert:

  equation899

  equation904

  equation908

Regel 6.3 z.B. sagt aus, daß das Nonterminal line durch das Schlüsselwort :LINE und zweimaliges Anwenden von point abgeleitet werden kann. Anders ausgedrückt kann eine Linie, wenn :LINE auftritt, durch zwei folgende, auf beliebige Weise angegebene Punkte spezifiziert werden.

Eine erlaubte Eingabefolge für line ist demnach:
:LINE :POINT FLOATNUMBER FLOATNUMBER :POINT FLOATNUMBER
FLOATNUMBER

Da mit dem Erkennen der Eingaben und dem Auswählen und Anwenden der richtigen Regeln noch keine Reaktionen erfolgen, ist eine sogenannte Semantik erforderlich, die den obigen Regeln eine engere Bedeutung gibt:
FLOATNUMBER liefert eine Fließkommazahl;
coordinates liefert eine Liste von Fließkommazahlen;
point liefert einen Punkt;
line liefert eine Linie.

Um die Semantik der Terminale und Nonterminale sinnvoll auszunützen, sind bei Anwendung der Regeln Aktionen erforderlich:
Regel 6.1 hängt die Zahlen in einer Liste aneinander;
Regel 6.2 generiert einen Punkt aus der Liste der Koordinaten;
Regel 6.3 generiert eine Linie basierend auf den zwei Punkten.

Betrachtet man obige Folge von Terminalen unter dem Gesichtspunkt der graphischen Eingabe im zweidimensionalen Fall, dann sieht man, daß jeweils die Folge für einen Punkt, also
:POINT FLOATNUMBER FLOATNUMBER,
zu einem Mausklick in der Zeichenfläche zu rechnen ist. Die Anzahl der zu verarbeitenden Terminale läßt sich reduzieren, wenn das Zusammenfassen der Koordinaten und das anschließende Generieren des Punktes schon direkt mit dem Ereignis des Mausklicks gekoppelt werden kann, statt alles vom Parser durchführen zu lassen. Dieses liefert damit statt eines Schlüsselwortes und zweier Zahlen einen Punkt; für diesen wird ein neuer Terminaltyp POINT eingeführt (nicht zu verwechseln mit dem Schlüssel :POINT!)

Es wird also eine weitere Möglichkeit benötigt, wie ein Punkt vom Parser akzeptiert werden kann. Diese wird in einer neuen Regel definiert:

  equation936

Entsprechend erweist es sich als günstig, die weiteren Terminale
<list-of-floats>
und LINE
und die Regeln zu ihrer Aufnahme einzuführen:

  equation943

  equation947

Aufgrund dieser Definitionen werden unter anderen auch diese Folgen akzeptiert:
LINE
:LINE POINT POINT
:LINE :POINT <list-of-floats> POINT
:LINE POINT :POINT float float

Sollen mehrere Linien nacheinander ohne weitere Verarbeitung eingegeben werden, dann führt folgende Regel zum Ziel:

  equation951

Der semantische Typ dieser Regel ist undefiniert.

Ein praktikables System könnte nun so funktionieren:

Ein Menüpunkt ,,Linien`` sendet den Schlüssel :LINE-MODE an den Parser. Dieser wählt Regel 6.7 aus, weil nur diese das Eingabewort akzeptiert. Damit der Benutzer als nächstes mit dem linken Mausknopf die Position des ersten Punktes angeben kann, werden bei diesem Ereignis intern die folgenden Aktionen erforderlich (da ja erst die Information für den ersten Punkt, aber noch nicht für den zweiten und daher auch nicht für die ganze Linie zur Verfügung steht, kann Regel 6.6 nicht angesteuert werden):
:LINE-Schlüssel an Parser senden, damit Regel 6.3 ausgewählt wird;
aus der Position des Mausklicks die Punktkoordinaten gewinnen und den Punkt generieren (oder selektieren);
diesen Punkt an den Parser schicken.

Der Parser wartet dann in Regel 6.3 auf den zweiten Punkt. Über welche der beiden Regeln 6.2 oder 6.4 dieser kommen wird, weiß er zu diesem Zeitpunkt noch nicht, und es ist für ihn auch (noch) nicht von Bedeutung.

Ein weiterer Mausklick des Benutzers liefert die zweite Position und damit den zweiten Punkt. Damit ist Regel 6.3 abgeschlossen, die Linie wird aus den beiden Punkten aufgebaut und retourniert. Regel 6.7 erhält die Linie (ohne sie zu verwenden; ihre Generierung war ein Seiteneffekt) und wartet auf eine neue. Wenn eine Eingabe erfolgt, die mit den Regeln für ,,Linie`` nicht akzeptiert werden kann, terminiert die Schleife von Regel 6.7 und diese Regel gilt als abgearbeitet.

Um alle Regeln der höchsten Hierarchie zusammenzufassen, gibt es ein weiteres Nonterminal main mit den entsprechenden Regeln:

  equation968

  equation972

wobei point-mode analog zu line-mode ist:

  equation978

und schließlich, um beliebiges Wiederholen dieser Regeln zu ermöglichen,

  equation983

Dieses Nonterminal root ist das sogenannte Startsymbol, dessen Angabe zwingend zu jeder Grammatikdefinition gehört.

Die Benutzerschnittstelle des PED ist nur zu verstehen durch das abgestimmte Zusammenwirken von Parser und Konfiguration der Bedienelemente. Diese zwei Komponenten werden vorgestellt, und dann die gemeinsame Funktion erklärt.


next up previous contents
Next: 6.2.4 Parser Up: 6.2 Eingabeanalyse Previous: 6.2.2 Lösungsansatz

Martin Knaipp
Wed Jun 12 15:41:33 MET DST 1996