Eine Sprache kann man sich als eine Anzahl von Zeichenketten (Strings = Folgen von Symbolen) vorstellen. In der Sprachdefinition wird festgelegt, welche Strings zur Sprache gehören (Syntax der Sprache) und was sie bedeuten (Semantik). Im Bereich der Programmiersprachen stellt sich die Aufgabe, die Syntax und die Semantik eindeutig und unmißverständlich zu beschreiben. Die Umgangssprache ist für die Beschreibung von Programmiersprachen wenig geeignet. Gründe hierfür sind:
Dessenungeachtet benötigt ein Programmierer eine verbindliche und eindeutige Beschreibung von Syntax und Semantik der Programmiersprache. Wer Compiler entwickelt, ist in derselben Situation, da ja Syntax und Semantik in einen Compiler umgesetzt werden müssen, der den Vorgaben der Sprachbeschreibung genügt.
Ziel dieses Kapitels ist es zu untersuchen, auf welche Arten Sprachbeschreibungen in formaler Weise zweckmäßig erfolgen können. Der Compilerbau wird dadurch deutlich erleichtert, da es auch Werkzeuge gibt, mit denen Compiler oder Teilfunktionen von Compilern aus einer spezifischen Sprachbeschreibung erzeugt werden können, z.B. Compiler-Compiler, Compiler-Generator. Konkrete Beispiele für solche Werkzeuge sind lex und yacc in der UNIX-Umgebung oder der "User-Definable Assembler" auf der HP64000, einem inzwischen antiken Rechner - aber immerhin: 1980 bereits konnte man damit auf einem Arbeitsplatzsystem Übersetzer erzeugen.
Im Bereich der Syntax gibt es bereits bewährte Verfahren zur formalen Beschreibung von Programmiersprachen, während auf dem Gebiet der Semantik die Entwicklung noch nicht so weit gediehen ist.
Eine der Schwierigkeiten in Compilerbau besteht darin, Syntax und Semantik zu verbinden. Überlegen Sie selbst: Was alles kann der Operator "Plus" bedeuten? In der Praxis hilft man sich mehr oder weniger unbeholfen durch eine Beschreibung in natürlicher Sprache, wobei vorausgesetzt wird, daß gewisse allgemein gebräuchliche Annahmen zutreffen. Dazu gehören z.B. die Rechenregeln in den natürlichen Zahlen, aber auch die semantische Vorbelastung von Worten wie if oder while, die in vielen Programmiersprachen als Schlüsselworte verwendet werden.
Dieses Beispiel ist an das Buch von Kopp angelehnt. Gegeben sei ein Satz einer natürlichen Sprache, der aus Gründen der technischen Einfachheit in Kleinbuchstaben geschrieben wird:
der hund beißt den briefträger
Um einen Satz dieser Struktur zu beschreiben, eignet sich hier ein System von sieben Regeln, die wie folgt lauten:
| R1 SATZ ® SUBJEKT PRÄDIKAT OBJEKT
R2: SUBJEKT ® ARTIKEL SUBSTANTIV R3: OBJEKT ® ARTIKEL SUBSTANTIV R4: PRÄDIKAT ® VERB R5: SUBSTANTIV ® hund | briefträger R6: VERB ® beißt R7: ARTIKEL ® den | der |
Alle Begriffe, die in Großbuchstaben geschrieben sind, werden als metasprachliche Begriffe bezeichnet. Sie dienen zur Bezeichnung syntaktischer Einheiten, sind aber nicht Bestandteil der Sprache selbst. Die Begriffe in Nichtproportionalschrift, wie z.B. hund, sind Elemente der zu beschreibenden Sprache; diese heißen auch terminale Symbole. Der Pfeil "®" heißt "besteht aus" oder "wird ersetzt durch". Um einen Satz zu erzeugen, werden - ausgehend von der ersten Regel - solange die anderen Regeln angewendet, bis keine weitere Anwendung der Regeln mehr möglich ist, weil alle Begriffe nur noch terminale Symbole sind.
Für eine reichhaltigere Sprache, korrekte Groß- und Kleinschreibung und andere Feinheiten sind weitere Regeln notwendig.
Der Beispielsatz läßt sich auf diese Art ableiten (= unter Anwendung der Regeln folgern):
| SATZ ® SUBJEKT PRÄDIKAT OBJEKT ® ARTIKEL SUBSTANTIV PRÄDIKAT OBJEKT ® der SUBSTANTIV PRÄDIKAT OBJEKT ® der hund VERB OBJEKT ® der hund beißt OBJEKT ® der hund beißt ARTIKEL SUBSTANTIV ® der hund beißt den SUBSTANTIV ® der hund beißt den briefträger |
Die auf diese Art erzeugten Sätze sind zwar bzgl. der obigen Grammatik syntaktisch korrekt, müssen aber nicht unbedingt sinnvoll, oder gar im Sinne der deutschen Grammatik korrekt sein. So ist der Satz den briefträger beißt den briefträger ebenfalls erzeugbar.
Wie das Beispiel aus dem vorigen Abschnitt nahelegt, ist es - zumindest für rein formale Anwendungen - zweckmäßig, einen Formalismus festzulegen, der die einzelnen Bestandteile einer Grammatik beschreibt.
| Definition: | Ein Alphabet A ist eine endliche Menge von Symbolen. Ein String s (eine Zeichenkette) ist eine endliche Folge von Zeichen aus einem Alphabet. Ist A ein Alphabet, dann bezeichne A* die Menge aller Strings über A. Ist s ein String, dann bezeichne |s| (bzw. #s) seine Länge. Der String der Länge 0 heißt Leerstring und wird mit e bezeichnet. Die Menge aller nichtleeren Strings A+ ist A* \ {e}. Produktionen (Regeln) sind Vorschriften zum Ersetzen von Strings durch andere. In Zeichen: s1 ® s2. |
|---|
Mit diesen Begriffen kann festgelegt werden, wie eine Grammatik aussieht:
| Definition: | Eine Grammatik G ist ein Quadrupel ( N, T, P, X ), wobei | |||
|---|---|---|---|---|
| N | ein Alphabet ist, dessen Elemente als nichtterminale Symbole (Nichtterminale) bezeichnet werden. | |||
| T | ein Alphabet ist, dessen Elemente terminale Symbole heißen; dabei muß N Ç T = Æ sein (das hat den rein praktischen Grund der Eindeutigkeit). | |||
| P | eine endliche Menge von Produktionen ist. | |||
| X Î N | X als Axiom oder Satzsymbol bezeichnet wird. | |||
| V := N È T | als Gesamtalphabet bezeichnet wird. | |||
Beispiele für Alphabete sind:
| A1 = { 0, 1,
2, 3, 4,
5, 6, 7,
8, 9 } A2 = { a, b, g , d, ... , w } A3 = { begin, end, if, then } A4 = { SATZ, SUBJEKT, PRÄDIKAT, OBJEKT, ARTIKEL, VERB, SUBSTANTIV } A5 = { der, den, hund, briefträger, beißt } |
Beispiele für Strings sind:
| s1 = der briefträger beißt den hund | ist ein String über A5 | ||
| s2 = der hund beißt OBJEKT | ist ein String über A4 È A5 | ||
| s3 = hund | ist ein String über { a, b, c,... z }; |s3 |= 4 | ||
| s4 = gnwqi seauton | ist ein String über A2 | ||
| |s1| = 5; | die Länge hängt vom betrachteten Alphabet, hier z.B. A5, ab. | ||
| s3 | ist ein auch String über A5 , |s3| = 1 |
tx
| weiter im Text |
| Stand: 19.11.2002 / |
|