Syntaxdiagramme: Aufbau
Jeder Chomsky-Grammatik der Klasse 2 oder 3 kann man
folgendermaßen eine Kollektion von Syntaxdiagrammen zuordnen:
-
Aus jeder Produktion machen wir einen gerichteten Graphen, der für
jedes Symbol auf der rechten Seite einen Knoten enthält.
Für Terminalsymbole zeichnen wir runde bzw. ovale Knoten,
die mit dem Symbol markiert sind; ebenso verwenden wir rechteckige
Kästen zur Veranschaulichung der Nichtterminalsymbole.
Die Symbole bzw. ihre Darstellungen sind in der Reihenfolge der
Aufschreibung verkettet; dazu kommt als Eingang noch ein Pfeil,
der von außen auf das erste Symbol der rechten Seite zeigt,
und als Ausgang ein Pfeil vom letzten Symbol nach außen.
Ist eine rechte Seite leer, so entspricht ihr ein Pfeil,
der sowohl Eingang wie Ausgang ist.
-
Alle so aufgebauten Ketten, die zum gleichen
Nichtterminalsymbol gehören,
bekommen einen gemeinsamen Eingang und einen gemeinsamen Ausgang;
das so entstandene Gebilde ist ein Syntaxdiagramm
für das Nichtterminalsymbol.
Es gibt dann also für jedes Nichtterminalsymbol genau ein Diagramm;
oft läßt es sich noch vereinfachen, indem man
am Eingang oder am Ausgang gemeinsame Teile zusammenfaßt.
Umgekehrt kann man aus jeder Kollektion von Syntaxdiagrammen
durch Aufspalten und womöglich Einführen von neuen
Nichtterminalsymbolen eine Grammatik herleiten, welche dieselbe
Sprache erzeugt. Wir gehen darauf nicht ein.
Ist die Grammatik von der Klasse 3, so lassen sich in den Diagrammen
die Nichtterminalsymbole entfernen.
Das Verfahren ist zu mühsam, um es hier vorzuführen;
das Diagramm direkt hinzuschreiben, ist meist einfacher.
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36