Compilerbau

Das Problem der Übersetzung einer Computersprache in eine andere Computersprache gehört zu den klassischen Themen der Informatik. Die Tatsache, dass hierbei auch leicht auch einmal über die natürlichen Sprachen nachgedacht wird, macht das Thema nur noch reizvoller.

Hinsichtlich der Übersetzung unterscheidet man zwischen Compilern und Interpretern. Der Un­terschied besteht lediglich darin, dass ein Compiler immer das komplette Programm über­setzt, bevor es ausgeführt wird, während ein Interpreter zeilenweise vorgeht. Beim Interpreter wird immer eine einzelne Zeile übersetzt und gleich ausgeführt.

Die Grenzen sind minimal und fließend, immerhin kann Turbo-Pascal Programme zeilenweise ausführen.

Die Probleme, die bei diesen Übersetzungen auftauchen, sollen anhand des folgenden Bei­spiels erläutert werden, das sich im Grenzbereich zu den natürlichen Sprachen bewegt.

1. Einführung

Als einführendes Beispiel soll die Übersetzung von Zahlwörtern in die zugehörige Ziffern­folge dienen. Aus dem Wort "Zweihundertsechzehn" soll die Ziffernfolge "216" wer­den. Auf den ersten Blick erscheint dieses Problem trivial, jeder Mensch kann eine derartige Übersetzung ohne größeres Nachdenken vornehmen.

Beim zweiten Nachdenken erscheint das Problem unlösbar. Schon das Beispiel "Zweihun­dertsechzehn" zeigt viele Merkwürdigkeiten unserer Sprache. Die Einer und die Zehners­telle sind vertauscht. Die Zehnerstelle kommt zuletzt. Das ist zwar, zumindest für ein Überset­zungsprogramm, seltsam, wird aber zumindest konsequent so gehand­habt. Die nächste Merk­würdigkeit besteht darin, dass bei dem Wort "Sechzehn" ein Buchstabe fehlt. Eigentlich müsste es "Sechszehn" heißen, doch "Sechzehn" spricht sich besser. Von diesen Merkwür­digkeiten oder Ausnahmen gibt es mehrere.

Will man nun ein Programm schreiben, das derartige Zahlwörter in die Ziffernfolgen über­setzen kann, so muss man systematisch vorgehen.

Bei der Übersetzung von formalen Sprachen geht man normalerweise in drei Schritten vor.

1. Zuerst wird der Eingabetext von einem Scanner auf bekannte Wörter bzw. Befehle unter­sucht, die dann in eine Kurzform, ein Token, übersetzt werden. Der Scanner wird auch le­xikalische Fehler, wie "Sexzehn" monieren, da er das entsprechende Wort nicht kennt.
2. Der vom Scanner komprimierte Text wird dann vom Parser auf seine syntakti­sche Kor­rektheit überprüft. Der Parser müsste Fehler wie "Sechsacht" monieren, die den Scanner anstandslos passieren würden.
3. Wenn der Parser die syntaktische Korrekt­heit des Textes festgestellt hat, dann kann die Codeerzeugung erfolgen, also ein aus­führbares Programm erzeugt werden.

In unserem Fall soll ja kein Programmcode erzeugt werden, insofern kann man hier Par­ser und Codeerzeugung zusammenfassen.

Bei der Liste der Befehlswörter und Token kann man etwas unsauber arbeiten. Die Über­setzung von "elf" in die Tokenfolge "1x" geht schon über die übliche Arbeit eines Scanners hi­naus. Aber da unser Beispiel aus dem Bereich der natürlichen Spra­che stammt, lassen sich hiermit viele Sonderfälle für den Parser vermeiden. Ein eige­nes Token für "elf" müsste im Parser ja auch gesondert behandelt werden. Wie man aus der Liste der Befehls­wörter sieht, gibt es sehr viele derartige Ausnahmefälle, die zu einem relativ aufwändigen Parser führen müssten.

Der Scanner, hat ein kleines Problem zu lösen, zwi­schen den Wörtern gibt es keine Trenn­zeichen. Die Funktion muss also bei "Siebenundzwanz­ig" selber die Länge der Bestand­teile ermitteln, um die Wortteile trennen zu können. Hierzu geht sie z.B. von der maxima­len Länge 10 eines Wortes aus. Die kürze­ste Länge ist 3 Zeichen. In der ersten Runde wer­den die ersten 10 Zeichen aus dem Eingabe­text isoliert und mit allen Symbolen des Feldes verglichen. Falls keinerlei Übereinstim­mung gefunden wird, werden in der nächsten Runde nur die ersten 9 Zeichen betrachtet usw. Findet sich auch bei 3 Zeichen keine Über­einstimmung, so lag ein Schreibfehler vor. Falls der Befehl gefun­den wurde, so wird das zugehörige Token zurückgeliefert, der Befehl aus dem Eingabestring entfernt und mit dem restlichen String die Funktion erneut aufgerufen, falls der Rest nicht leer ist. Dieses rekursive Vorgehen vereinfacht die For­mulierung der Funktion.

Die Formulierung des Parsers ist damit aber noch nicht gelöst. Nun muss man sich über die Regeln, die hinter dem Aufbau der Zahlwörter stehen, Gedanken machen. Zuerst ein­mal soll­te man sich auf Zehnerzahlen, Zahlen bis einschließlich 99 Gedan­ken machen und überlegen, welche Token-Kombinationen richtig sind.

Ein paar unterschiedliche Beispiele:

Einundzwanzig   1u2z
Siebzehn        7x
Achtundvierzig  8u4z
Vierzig         4z
Zehn            x
Sieben          7

Subsumiert man die Ziffern 1..9 unter dem Symbol n, so sind also folgende Tokenfol­gen er­laubt:

x, 
n, 
nz, 
nx, 
nunz

Die Tatsache, dass damit auch ein Wort wie "einszehn" als korrekt bezeichnet wird, soll ein­mal als Ausnahme akzeptiert werden. Zumindest ergibt dieses Wort ja einen Sinn. Wich­tiger ist hier, dass keine korrekten Wörter abgelehnt werden.

Will man den Zahlenbereich nun auf auch Zahlen über Hundert erweitern, so ergeben sich folgende Möglichkeiten:

Hundertundsieben       cu7
Einhundertundsieben    1cu7 
Vierhundert            4c 
Fünfhundertundsiebzig  5c7z
Zweihundertsiebzehn    2c7x 
Zweihundertundsiebzehn 2cu7x
Zwölfhundertundvier    2xcu4 (wieder ein Problem)
Achtzehn               8x

Hier ist auf den ersten Blick eine kaum überschaubare Zahl von Möglichkeiten gege­ben. Benutzt man aber die Tatsache, dass wir das Problem für Zehnerzahlen schon ge­löst ha­ben und setzen das Symbol Z für Zehnerzahlen, so gibt es nur folgende Mög­lichkei­ten:

Z
cZ
cuZ
Zc
ZcZ
ZcuZ

Diese Regeln zeigen, dass man ein u nach dem c einfach überlesen kann, da es ein reines Füllwort ist. Damit bleiben dann nur noch vier Fälle übrig. Die konkrete Umset­zung dieser Regeln in eine Funktion dürfte keine Probleme mehr bereiten. Wie man an diesem Beispiel ersehen kann, liegt das Hauptproblem der Sprachüberset­zung in einer übersichtlichen Beschreibung der Regeln, oder wie man auch sagt, der Grammatik der Sprache. Die lexikalische Seite, die Arbeit des Scanners, lässt sich immer analog zu dem angegebenen Beispiel lösen. Normalerweise ist die Arbeit sogar noch ein­facher, da man zwischen den einzelnen Wörtern Trennzeichen wie “ “, “,“, “;“ erwartet. Damit steht dann die Länge des nächsten Wortes fest und der Vergleich mit der Befehls­liste kann viel einfacher erfolgen.

In den folgenden Abschnitten wollen wir uns also hauptsächlich mit den Möglichkei­ten zur Beschreibung einer Grammatik beschäftigen.

2. Endliche Automaten

Ein Automat ist eine (gedachte) Maschine, die über mehrere innere Zustände ver­fügt und die als Reaktion auf Eingaben eine (möglicherweise leere) Ausgabe pro­du­ziert, die auch vom in­neren Zustand des Automaten abhängt.
Ein Automat heißt endlich, wenn sowohl die Menge der Eingabezeichen, als auch die Menge der Ausgabezeichen, als auch die Menge der Zustände endlich ist.

Hierzu gleich ein einfaches Beispiel:

2.1. Paritätsprüfung mit endlichem Automaten

Bei der Datenübertragung, aber auch bei der Datenspeicherung, wird zur Kontrolle ein Pa­ritätsbit benutzt. Dieses Bit gibt an, ob die Anzahl der Binärziffer 1 im Datenwort gera­de oder ungerade ist. Passt das Paritätsbit nicht zur Parität des Datenwortes, so ist ein Übertra­gungsfehler aufgetreten.

Die Parität eines Datenwortes stellt die folgende Maschine fest, bei der ein Sichtfen­ster bit­weise über das Datenwort fährt.

Diese Maschine verfügt über zwei Zustände, nämlich 0 und 1, die in dem unte­ren Fens­ter angezeigt werden und zwei Eingabezeichen, ebenfalls 0 und 1. Ist das Eingabezei­chen eine 1, so ändert die Maschine ihren Zustand, ansonsten nicht.

Vergleicht man am Ende den Zustand des Automaten mit dem Paritätsbit, so kann man eventuelle Übertragungsfehler feststellen.

Dieser Automat lässt sich sehr übersichtlich beschreiben, wenn man die Übergänge zwi­schen den Zuständen darstellt.

Beim Start geht der Automat in den Zustand gerade über. Liest der Automat eine Null, so wird der Zustand nicht verändert, liest der Automat eine 1, so wechselt der Zustand. Jedes eingegebene Zeichen, das nicht zu den Eingabezeichen gehört, führt zu einem Ab­bruch der Prozedur. Solange kein derartiger „Fehler“ auftritt, läuft der Automat ad infinitum weiter.

;Automat für Paritätsüberprüung geschrieben von Uwe Debacher
;Eingabe erfolgt als Liste

(define (parit zustand liste) 
  (cond ((eqv? zustand 'start)
         (cond ((null? liste) "leer") 
               ((=(car liste) 1) (parit 'ungerade (cdr liste)))
               ((=(car liste) 0) (parit 'gerade (cdr liste)))
               (else "Fehler")))
        ((eqv? zustand 'gerade)
         (cond ((null? liste) "gerade") 
               ((=(car liste) 1) (parit 'ungerade (cdr liste)))
               ((=(car liste) 0) (parit 'gerade (cdr liste)))
               (else "Fehler")))
        ((eqv? zu stand 'ungerade) 
         (cond ((null? liste) "ungerade")
               ((=(car liste) 1) (parit 'gerade (cdr liste)))
               ((=(car liste) 0) (parit 'ungerade (cdr liste)))
               (else "Fehler")))))

In diesem Programm wird mit einer Liste als Argument gearbeitet, sinnvoller dürfte es sein gleich Strings zu benutzen. Für das Arbeiten mit Strings steht in Scheme auch eine Reihe von Funktionen zur Verfügung:

• string-length <string> ermittelt die Länge eines Strings
• substring <string> <start> <ende>gibt einen Teilstring zurück
• string-append <string1> <string2>verknüpft Strings
• string-upcase <string>wandelt alle Buchstaben in Großbuchstaben
• string-downcase <string>wandelt in Kleinbuchstaben

2.2. Realzahlen mit endlichem Automaten

Etwas dichter an unserem Thema ist ein Automat, der die korrekte Darstellung von Real-Zahlen beschreibt. Zur Vereinfachung wollen wir uns auf vorzeichenlose Zahlen ohne Ex­ponentialdarstellung beschränken. Dann ergibt sich folgender Automat:

Die Kreise um die Zustände s₁ und s₃ sind deutlich dicker gezeichnet, um anzudeuten, dass es sich um erlaubte Endzustände handelt. In den Zuständen s₀ und s₂ liegt keine vollständ­ige Realzahl vor.

Der Au­tomat für unser Beispiel Zehnerzahlen sieht schon recht kompliziert aus: Bis auf s₀, s₂ und s₃ stellen alle Zustände erlaubte Endzustände dar.

Zur Vereinfachung wurden hier wieder keine Ausgaben in die Darstellung einbezogen.

Die Darstellung mittels Automaten wird relativ schnell unübersichtlich, wenn die Zahl der möglichen Zustände groß wird. Andererseits gibt es auch Beispiele, in denen die Darstel­lung mittels Automaten unschlagbar ist.

Im nächsten Beispiel soll ein Automat beschrieben werden, der in einer beliebigen Zeichen­kette die Wörter „ER“, „SIE“ und „ES“ findet, auch wenn sich die Wörter überlap­pen. In der Zeichenkette „SIER“ müssten also sowohl „SIE“ als auch “ER“ gefunden werden.

Was nicht dargestellt ist, ist die Tatsache, dass jedes sonstige Eingabezeichen zum Zustand S₀ zurück­führt.

Mit Automaten lassen sich auch weniger ernsthafte Dinge beschreiben. Der folgende Auto­mat beschreibt das Frohlocken, wie man es aus dem Schwank „Ein Münchner im Himmel“ kennt.

Jeder Weg, der zum Endzustand führt, ist ein Wort in der Sprache Frohlocken.

3. Definitionen Alphabet, Wort, Sprache und Automat

In diesem Abschnitt ist mehrfach der Begriff endlicher Automat aufgetaucht. Für diesen Begriff gibt es eine formale Definition, die für das Verständnis von Automaten hilfreich sein kann.

Automat

Ein (deterministischer) endlicher Automat ist ein 6-tupelM=(I, O, Z, δ, z₀, F) wobei

• I ein endliches Eingabealphabet,
• O ein endliches Ausgabealphabet,
• Z eine endliche Menge von Zuständen,
• δ eine Übergangsfunktion δ: Z x I → Z x O,
• z₀ ein Startzustand und
• F eine Menge von Endzuständen ist.

Das Wort deterministisch drückt aus, dass die Arbeitsweise des Automaten eindeutig defi­niert ist. Entweder gibt es genau einen nächsten Zustand, oder der Automat stoppt vorzei­tig. Gelegentlich wird ein endlicher Automat auch als 5-tupel betrachtet, ohne das Ausgabeal­phabet. Derartige einfachere Automaten, die keine Ausgabe erzeugen bezeichnet man als Akzeptor.

Die Übergangsfunktion kann auf verschiedene Weisen angegeben werden:

1. Angabe aller 4-tupel von δ, bei denen die erste Komponente ein Element von Z, die zweite ein Element von I, die dritte der Folgezustand, also ebenfalls ein Element von Z und die vierte ein Element von O ist.
2. Angabe einer Zustandstabelle.
3. Angabe eines Zustandsdiagrammes.

In dieser Definition tauchen weitere Begriffe auf, die einer Erklärung bedürfen, obwohl sie ansonsten recht gebräuchlich sind.

Alphabet

Ein Alphabet ist eine endliche, nichtleere Menge, deren Elemente als Zeichen, Buchstaben oder Symbole bezeichnet werden. Alphabete werden mit großen Buchstaben abgekürzt, meist dem V (vom engl. vocabulary).

Beispiele für Alphabete:
V={a, b, c, ..., z}
B={0,1}
S={do, define, if, cond, case, int?, ....}

Eine endliche Folge (x₁, x₂, ..., x_k) mit x_i ε V (i=1, ..k) heißt Wort der Länge k über V. Es gibt genau ein Wort der Länge 0, das Leerwort, das wir mit ε bezeichnen.Die Länge eines Wortes wird mit |k| symbolisiert.

Die Menge aller Wörter über V bezeichnet man üblicherweise mit V^*. Soll das leere Wort ausgeschlossen sein, so schreibt man V⁺.

Sprache

Jede beliebige Teilmenge von V^* wird als Sprache oder formale Sprache bezeichnet.

Beispiele

Alphabet: V={0, 1}
Wörter über V: „0“, „01“, „0001“, „1101“, „11111“, „0000000“, „010101“
Sprache V²={k ε V^* mit |k|=2} Sprache besteht aus allen Wörtern der Länge zwei über V.

Alphabet: V={ha, l, le, lu, u, ja, !, Komma gefolgt von Leertaste}
Wörter über V: „ha“, „hahaha“, „halleluuja!“,
Sprache: Frohlocken, siehe Beispiel oben.

Alphabet: V=Menge aller Wörter im Duden des Jahres 2003
Wörter über V: „da da“, „der Hund bellt“, „das Mann bellt Hund“
Sprache: deutsche Sprache

Automat für Bezeichner:I = Menge aller ASCII-ZeichenO = {„Ein Bezeichner muss mit einem Buchstaben beginnen“, „Bezeichner akzeptiert“}
Z = {Start, Bezeichner, Ende, Fehler}
Z₀ = StartF = {Ende, Fehler}
δ über die 4-tupel:
(Start, Buchstabe, Bezeichner, -)
(Start, sonst. Zeichen, Fehler, „Ein Bezeichner muss mit einem Buchstaben beginnen“)
(Bezeichner, Buchstabe, Bezeichner, -)
(Bezeichner, sonst. Zeichen, Ende, „Bezeichner akzeptiert“)

δ über Zustandstabelle:

I Z	Buchstabe Zustand         Ausgabe		sonst. Zeichen Zustand                                                 Ausgabe
Start	Bezeichner	-	Fehler	Ein Bezeichner muss mit einem Buchstaben begin­nen
Bezeichner	Bezeichner	-	Ende	Bezeichner akzeptiert
Fehler	-	-	-	-
Ende	-	-	-	-

δ über Zustandsdiagramm:

4. Grammatik

Nicht jedes Wort über einem Alphabet gehört zu der betrachteten Sprache. Man benötigt also Möglichkeiten, um die Sprache zu beschreiben. Im einfachsten Fall kann man alle Wörter aufzählen, die zu der Sprache gehören.Schon beim Frohlocken ist es aber nicht möglich alle Wörter aufzuzählen, es gibt unend­lich viele Wörter in dieser Sprache. In solch einem Fall benötigt man Regeln, nach denen sich die Wörter der Sprache bilden lassen.
Zum Einstieg ein Beispiel aus dem Bereich der natürlichen Sprache, dabei ist V = Menge aller Wörter im Duden. Die daraus zu bildenden Wörter, die zur Sprache Deutsch gehören bezeichnet man üblicherweise als Sätze.
In der deutschen Sprache besteht ein Satz (S) z.B. aus einer Nominalphrase (NP) und einer Verbalphrase (VP), was man folgendermaßen ausdrücken kann:
S → NP VP
Eine Nominalphrase besteht aus einem Nomen (N), einem Nomen mit einem vorangestell­ten Artikel (A) oder einem Nomen mit einer Präpositionalphrase (PP).
NP → N
NP → A N
NP → NP PP
Eine Verbalphrase wiederum kann aus einem Verb (V), einem Verb mit einer folgenden Nominalphrase, oder einer Verbalphrase mit folgender Präpositionalphrase bestehen.
VP → V
VP → V NP
VP → VP PP
Eine Präpositionalphrase wiederum besteht aus einer Präposition und einer Nominalphrase
PP → P NP
Wenn nun noch Artikel, Nomen, Präposition und Verb definiert werden, dann kann man Sätze bilden bzw. überprüfen. Die restlichen Regeln bzw. Ableitungen erfolgen durch Auf­zählen.
A → der
A → die
A → das
A → dem
A → den
P → mit
P → in
N → Mann
N → Hund
N → Park
N → Klaus
V → bellt
V → geht

Nun kann man beginnen Sätze in dieser Sprache zu formulieren, bzw. zu überprüfen, ob ein gegebener Satz zu dieser Sprache gehört.
„Der Hund bellt“ lässt sich folgendermaßen produzieren:
S → NP VP → A N V → der Hund bellt.

Etwas unübersichtlicher wird die Situation schon bei dem Satz „Der Mann geht mit dem Hund“. Hier hilft ein Baumdiagramm zur Übersicht.

Hier dargestellt ist ein Syntaxbaum der betrachteten Sprache.

In den Beschreibungen tauchen recht unterschiedliche Symbole auf. „Der“, „Mann“, „geht“, ... sind Symbole, die nicht weiter vereinfacht werden könne, da sie zum Alphabet gehören, auf dem die Sprache aufbaut. Derartige Symbole bezeichnet man auch als Termi­nalsymbole. Symbole wie Verb, Nomen, Nominalphrase, ... gehören dagegen nicht zum Alphabet und müssen durch Regeln abgeleitet werden, man bezeichnet sie als nichttermi­nale Symbole oder Variablen.Sprache ist oft nicht eindeutig, wie z.B. der Satz „Klaus sah die Frau mit einem Fernglas“. Es bleibt unklar, wer von beiden das Fernglas trägt. Lassen sich für diesen Satz unter­schiedliche Ableitungen finden (die notwendigen Terminalsymbole seien gegeben)?

In der ersten Ableitung wird deutlich, dass Klaus das Fernglas trägt und damit die Frau sieht. In der zweiten Ableitung sieht Klaus eine Frau, die ein Fernglas trägt.

Definition Grammatik

Nun noch eine formale Definition für den Begriff Grammatik.Eine Grammatik ist ein 4-tupel G=(V_N, V_T, P, S) mit
V_T ist die Menge der Terminalsysmbole.
V_N ist die Menge der Variablen
V_N und V_T sind endliche, nichtleere Mengen mit V_N ∩ V_T = {}
P ist eine endliche Menge von Regeln der Form:
α → β mit α ε ( V_N$\cup$V_T)⁺ und β ε ( V_N$\cup$V_T)^*
S ist das Startsymbol.

Der Linguist Noam Chomsky hat unter den so definierten Grammatiken verschiedene Ty­pen identifiziert, deren Reihenfolge eine hierarchische Beziehung widerspiegelt.

Chomsky-Hierarchie

Eine Grammatik G=(V_N, V_T, P, S) heißt vomTyp 0, falls keinerlei Einschränkungen vorliegen,Typ 1 (oder kontextsensitiv), wenn bei jeder Regel α →β der Grammatik die Länge nicht abnimmt, also |α| ≤ |β| gilt,Typ 2 (oder kontextfrei), wenn auf der linken Seite der Regeln nur einzelne Variablen ste­hen,Typ 3 (oder regulär), wenn auf der linken Seite nur einzelne Variablen stehen und auf der rechten nur ein einzelnes Terminalsysmbol, oder ein Terminalsymbol gefolgt von einer Variablen.

Das Beispiel mit dem Mann und dem Hund definiert eine Grammatik vom Type 2. Auch die meisten heute üblichen Programmiersprachen sind von diesem Typ.

5. Beispiele für Grammatiken

Bezeichner
In Programmiersprachen tauchen Bezeichner auf, die meist aus Buchstaben und Ziffern bestehen dürfen, wobei aber das erste Zeichen keine Ziffer sein darf. a25, anton, uwe wä­ren demnach zulässig, 3berta nicht.

Die Grammatik G=(V_N, V_T, P, S) lässt sich formal beschreiben:V_N = {Bezeichner, BezRest, Buchstabe, Ziffer}

V_T = {A, B, ..., Z, a, b, ..., z, 0, 1, ..., 9}

S = Bezeichner

P besteht aus den folgenden Produktionsregeln

Bezeichner → Buchstabe
Bezeichner → Buchstabe BezRest
BezRest → Buchstabe
BezRest → Ziffer
BezRest → Buchstabe BezRest
BezRest → Ziffer BezRest
Buchstabe → A
...
Buchstabe → Z
Buchstabe → a
...
Buchstabe → z
Ziffer → 0
...
Ziffer → 9

Die Beschreibung lässt sich abkürzen, wenn man die Alternativen durch senkrechte Striche getrennt aufführt.
Bezeichner → Buchstabe | Buchstabe BezRest
BezRest → Buchstabe | Ziffer | Buchstabe BezRest | Ziffer BezRest
Buchstabe → A | B | ... | Z | a | b | ...| z
Ziffer → 0 | 1 | ... |9

Die Grammatik ist vom Typ2 (kontextfrei) aber nicht vom Typ3 (regulär). Schon die Regel Bezeichner → Buchstabe BezRest verstößt gegen die Bedingung, dass auf der rechten Sei­te nur ein einzelnes Terminalsysmbol, oder ein Terminalsymbol gefolgt von einer Varia­blen stehen darf.Trotzdem ist die Sprache vom Typ3 (regulär), wie die folgende Grammatik der gleichen Sprache deutlich macht.
Bezeichner → A | B | ... | Z | a | b | ...| z | A BezRest | B BezRest | ... | Z BezRest | a BezRest | b BezRest | ... | z BezRest
BezRest → A | B | ... | Z | a | b | ...| z | 0 | 1 | ... | 9 | BezRest | B BezRest | ... | Z BezRest | a BezRest | b BezRest | ... | z BezRest | 0 BezRest | 1 BezRest| ... | 9 BezRest

Beide Grammatiken beschreiben die gleiche Sprache.

Klammerausdrücke

Gegeben sei G2 = (V_N, V_T, P, S) mit V_N ={S, T, F}, V_T ={+, -, *, /, a, (, ) }, S=S und den Produktionsregeln:

S → T
S → S+T
S → S-T
S → S/T
T → F
T → T* F
F → a
F → (S)

Eine Typ 1 Grammatik

Gegeben sei G = (V_N, V_T, P, S) mit V_N ={A, B, C}, V_T ={a, b, c }, S=S und den Produkti­onsregeln:

1: S → Ac
2: A → ab
3: A → aACB
4: CB →BC
5: B → b
6: Cc → cc

Alternativ können auch die folgenden Regeln benutzt werden:

1: S → aSBC
2: S → aBC
3: CB → BC
4: aB → ab
5: bB → bb
6: bC → bc
7: cC → cc

In beiden Fällen haben die gebildeten Wörter alle den Aufbau aⁿbⁿcⁿ, für ein$n\in \mathbb {N}$.

Hühnersprache

Gegeben sei G=(V_N, V_T, P, S) mit V_N = {Satz, Hühneraussage, Hühnerbemerkung}, V_T = {gluck, kikeriki, einei, gack, tock}, S=Satz und den Produktionsregeln S → gluck Hühneraussage gluck
S → gluck gluck
Hühneraussage → Hühnerbemerkung Hühneraussage
Hühnerbemerkung → gluck
Hühnerbemerkung → einei
Hühnerbemerkung → gack
Hühnerbemerkung → tock
Hühnerbemerkung → kikeriki
Hühneraussage → Hühnerbemerkung

6. Beschreibungsmöglichkeiten für Sprachen

Es lässt sich nachweisen, dass mit einem endlichen Automaten genau alle Typ3-Sprachen beschrieben werden können. Für die meisten praktischen Anwendungen, z.B. zur Beschrei­bung von Computersprachen benötigt man Formalismen, die besser für die maschinelle Verarbeitung geeignet sind. Dabei kommt uns zugute, dass diese Sprachen in der Regel vom Typ2 sind.

Syntaxdiagramme

Wohl jeder hat schon einmal in einen Pascal-Buch Diagramme wie das folgende gese­hen:

Dieses Syntaxdiagramm besagt, dass ein Bezeichner als erstes Zeichen einen Buchstaben besitzen muss. Danach kann Schluss sein, oder der Bezeichner besteht aus wei­teren Buch­staben, Ziffern oder dem Zeichen „_“.

Damit sind Bezeichner wie „ANTON1“, „A“, „An_ton“ zulässig, aber nicht „1Anton“, „_Mueller“ etc. Über die Zulässigkeit von „Müller“ können wir keine Aussage treffen, da uns die Definition von Buchstabe fehlt.

Der Unterschied zwischen den Rechtecken und den Kreisen besteht darin, dass das Symbol „_“ ein Terminal­symbol, ein Grundzeichen ist.

Die übrigen Symbole, Buchstabe, Ziffer und auch Bezeichner, sind Nichtterminalsym­bole. Für jedes Nichtterminalsymbol gibt es eine Regel, aus der hervorgeht, wie dieses Sym­bol aus Terminal- und Nichtterminalsymbolen aufgebaut ist.

Ersetzt man die Terminalsymbole schrittweise nach diesen Regeln, so kommt man zu ei­ner Folge von Terminalsymbolen, zumindest dann, wenn das Ausgangssymbol den Re­geln der Sprache entsprach.

In unserem Beispiel lässt sich nun sehr leicht die Regel für das Nichtterminalsymbol Zif­fer angeben:# Syntax-Diagramme sind also im Prinzip nur graphische Darstellungen einer Grammatik.
Für die meisten Programmiersprachen kann man annehmen, dass in der Regel für Buchsta­be nur die Termi­nalsymbole “A“..“Z“ und “a“..“z“ auftauchen. Fremdsprachige Sonderzei­chen, wie unse­re Umlaute, sind hier nicht als Buchstaben definiert. Darum ist ein Bezeich­ner wie „Müller“ z.B. in Pascal nicht zulässig. Vermutlich werden Zeichen mit einem ASCII-Code größer als 127 vom Compiler als Token benutzt, so dass es anderenfalls zu Kon­flikten käme.Bei den Syntaxdiagrammen kommen die folgenden vier Grundstrukturen vor:

Sequenz

Werden mehrere Symbole (gleich ob Terminal- oder Nichtterminalsymbole) direkt hintere­inander geschrieben, so spricht man von einer Sequenz.

Iteration

Bei der Iteration gibt es zwei unterschiedliche Fälle. Falls es erlaubt ist, dass das Sym­bol auch keinmal durchlaufen wird, so greift man zu folgender Darstellung:

Soll das Symbol mindestens einmal durchlaufen werden, so greift man zu folgender Dar­stellung:

Der Unterschied entspricht dem zwischen REPEAT..UNTIL und WHILE..DO.

Selektion

Kann das Symbol aus zwei oder mehreren Alternativen frei ausgewählt werden, so lässt sich das folgendermaßen darstellen:

Option

Einen Spezialfall der Selektion stellt die Option dar, hier kann ein Symbol einmal durch­laufen werden oder nicht. Es ist also eine Selektion mit leerer Alternative.Die Beschreibung eines kompletten Pascal-Programmes lautet dann:

Der Hauptteil der Syntax verbirgt sich hier also hinter dem Nichtterminalsymbol Block.

Aufgabe 6.1:
Gib das Syntaxdiagramm für eine komplette Real-Zahl an, die ein Vor­zeichen und einen Exponenten besitzen kann.
Achte besonders auf eine logische Gliederung der Bestandteile.

Aufgabe 6.2:
Beschreibe Konstanten-Ausdrücke wie 3*4+5, 3*(4+5) oder 1*2*3*4, bei denen die vier Grundrechenarten und Klammern auftauchen dürfen, mit Syntaxdiagrammen.

Aufgabe 6.3:
Erstelle dass Syntaxdiagramm für Frohlocken.

Erweiterte Backus-Naur-Form (EBNF)

EBNF stellt eine kürzere und maschinenlesbare Form zur Beschreibung von Gramma­tiken dar. Die Grundlagen der Beschreibung sind recht einfach:

• Terminalsymbole werden ohne, Nichtterminalsymbole mit spitzen Klammern ge­schrieben. A B C aber <Ziffer> <Begin>
• Eine Regel wird wie eine Zuweisung dargestellt, mit dem Zuweisungszeichen '::='. <Plus>::=+
• Die Symbole einer Sequenz werden einfach hintereinander geschrieben.<Block>::=<Deklarationsteil> <Anweisungsteil>
• Die Iteration wird durch die geschweiften Klammern ausgedrückt. Wobei eine be­liebige, auch 0-malige, Wiederholung zulässig ist.<Bezeichner>::=<Buchstabe> {<Buchstabe}>
• Die Selektion, die Auswahl zwischen mehreren Möglichkeiten, wird durch senk­rechte Striche zwischen den Möglichkeiten zum Ausdruck gebracht: <Vorzeichen>::= + | -
• Die Option, die Möglichkeit ein Symbol einmal oder keinmal zu setzen, wird durch die eckigen Klammern dargestellt.<positives Vorzeichen>::=[+]
• Runde Klammern regeln Prioritäten (siehe Aufgabe 4.4).

Mit diesem System ergeben sich sehr kompakte Darstellungen einer Grammatik. Spezie­ll Pascal und Modula-2 wurden von Wirth komplett in EBNF beschrieben.

Aufgabe 6.4:
Welche Worte lassen sich durch den folgenden EBNF-Ausdruck erzeu­gen?<Satz>::=[A] {B | (C D)} [;] {*} *

Aufgabe 6.5:
Übertrage die Aufgaben 6.1 und 6.2 analog auf EBNF.

Aufgabe 6.6:
Übertrage Frohlocken in EBNF.

7. Ein Compiler für Ausdrücke

Wir wollen in den folgenden Abschnitten ein Programm erarbeiten, das in der Lage ist, Ausdrücke auszuwerten. Damit ist es dann möglich ein Programm zu schreiben, dass z.B. den Graphen einer eingegebenen Funktion zeichnet.Im ersten Schritt soll ein Ausdruck nur aus Zahlen, den vier Grundrechenarten und Klammern gebildet werden können.

Will man derartige Ausdrücke beschreiben, so muss auch die Vorrangregel: Punkt- vor Strichrechnung berücksichtigt werden. Am einfachsten strukturiert man derartige Aus­drücke, wenn man sie als Summe, bzw. Differenz, von Produkten auffasst. Die Pro­dukte wiederum bestehen aus Faktoren.Die folgenden EBNF-Diagramme zeigen, dass gerade die Klammern ein gewisses Pro­blem beinhalten:

<Ausdruck>::=[+|-] <Summand> { (+|-) <Summand>}
<Summand>::=<Faktor> {(*|/) <Faktor>}
<Faktor>::=<Zahl> | (Klammer_auf <Ausdruck> Klammer_zu)

Dadurch, dass wir Klammern in den Ausdrücken zulassen, kommen wir schon bei der Beschreibung zu einer Rekursion, da innerhalb der Klammer natürlich wieder ein voll­ständiger Ausdruck stehen darf.Aufgabe 7.1:Übersetze die EBNF-Diagramme für Ausdruck, Produkt und Faktor in entsprechende Syntaxdiagramme.Die hier gewählte Beschreibung von Ausdrücken lässt sich relativ leicht erweitern, da Variablen-Bezeichner wie z.B. x und Funktionsaufrufe wie z.B. SIN(..) relativ einfach in das Regelwerk zu integrieren sein werden.

7.1 Der zugehörige Scanner

Ein Scanner ist auf den ersten Blick kaum notwendig, da alle Symbole, außer den Zah­len, nur aus einem einzigen Zeichen bestehen, so dass lexikalische Analysen nicht not­wendig sind. Sowie man aber Funktionen zulässt, wird ein Scanner notwendig, so dass wir ihn gleich mit einsetzen werden.Oft ist es praktisch nicht den ganzen Eingabestring auf einen Schlag zu scannen, son­dern immer zeichenweise vorzugehen. Hierbei kann man dann die Fehlerposition auch für grammatikalische Fehler besser angeben. Im vorliegenden Beispiel soll aber die Aufga­benverteilung noch einmal deutlich werden, so dass die drei Vorgänge deutlich getrennt sind.Im vorliegenden Listing werden die Token als Records abgebildet. Zu jedem Token ge­hört ein Symbol, die Symbole wurden als Aufzählungstyp eingeführt, und ein Wert. Beim Wert wird unterschieden zwischen der Ziffernfolge, ein String, der schon vom Scanner erkannt wird und dem Zahlenwert, der vom Parser ermittelt wird. Sauberer, aber auch unübersichtlicher wäre es, hier mit zwei getrennten Listen zu arbeiten.

; Scanner für Ausdrücke geschrieben von Uwe Debacher im November 2003
; Eingabe wird als String übergeben intern gearbeitet wird mit Zeichen

(define line-feed (string #\newline))

(define (ziffer? zeichen)
  (and (string-ci>=? zeichen "0")
       (string-ci<=? zeichen "9")))

; Aufruf über (scan eingabe)
; liefert als Ergebnis eine Liste:
; Tokenliste, die aus Paaren (Token . Wert) besteht
; bei Fehlern aus (#f . Fehlertext)
(define (scan eingabe)

  ; liefert immer das erste Zeichen als String und verkürzt die Eingabe entsprechend
  (define (lies-char)
    (define speicher eingabe)
    (cond ((zero? (string-length eingabe)) line-feed)
          (else
           (set! eingabe (substring eingabe 1 ))
           (substring speicher 0 1))))

  (define (scan-zahl lookahead)
    (define (nzahl lookahead zustand ergebnis)
      (cond ((eq? zustand 'start)
             (cond ((ziffer? lookahead)
                    (nzahl (lies-char) 'nat-zahl (string-append ergebnis lookahead)))
                   (else (nzahl lookahead 'fehler (string-append "keine Ziffer " lookahead)))))
            ((eq? zustand 'nat-zahl)
             (cond ((ziffer? lookahead) 
                    (nzahl (lies-char) 'nat-zahl (string-append ergebnis lookahead))) 
                   (else (nzahl lookahead 'ende ergebnis))))
            ((eq? zustand 'fehler)
             (list #f ergebnis lookahead))
            ((eq? zustand 'ende)
             (list #t ergebnis lookahead))))
    (nzahl lookahead 'start ""))

      ; diese Funktion ist für die Rekursion zuständig
  (define (naechstes lookahead ergebnis)
    (define zahl ())
    (cond ((equal? lookahead line-feed) ergebnis)
          ((equal? lookahead " ") (naechstes (lies-char) ergebnis))
          ((equal? lookahead "+") (naechstes (lies-char) (append ergebnis (list (cons 't_strich "+")))))
          ((equal? lookahead "-") (naechstes (lies-char) (append ergebnis (list (cons 't_strich "-")))))
          ((equal? lookahead "*") (naechstes (lies-char) (append ergebnis (list (cons 't_punkt "*")))))
          ((equal? lookahead "/") (naechstes (lies-char) (append ergebnis (list (cons 't_punkt "/")))))
          ((equal? lookahead "(") (naechstes (lies-char) (append ergebnis (list (cons 't_klammerauf "("))))) 
          ((equal? lookahead ")") (naechstes (lies-char) (append ergebnis (list (cons 't_klammerzu "(")))))
          ((ziffer? lookahead) 
           (set! zahl (scan-zahl lookahead))
           (cond ((eqv? (car zahl) #t)
                  (naechstes (caddr zahl) (append ergebnis (list (cons 't_zahl (cadr zahl))))))
                 (else 
                  (list (cons #f (string-append "Scan-Fehler: " (cadr zahl) lookahead))))))
          (else
           (list (cons #f (string-append "Scan-Fehler: unerwartetes Zeichen: " lookahead))))))

  (naechstes (lies-char) ()))

7.2 Der Parser

Die gewählte Beschreibung erlaubt es einen relativ übersichtlichen Parser zu schrei­ben, da sie direkt abgebildet werden kann.Es lassen sich folgende Regeln zur Konstruktion des Parsers formulieren:

• Jedes terminale Symbol zieht den Aufruf von LiesSymbol nach sich.
• Jedes nicht-terminale Symbol führt zu einem Prozeduraufruf.
• Es gibt folgende Zusammenhänge zwischen den Regeln und dem zugehörigen Parser, wobei t und s für ein terminales und N für ein nichtterminales Symbol steht:

(cond ((equal? t (car aktuelles-to­ken))
       (next-token)
       (set! ergebnis (parse-N))))

(cond ((or (equal? T (car aktuelles-token))
       (equal? s (car aktuelles-token))) 
         (next-token))
       (else (fehler „s oder t erwar­tet“)))

(set! Ergebnis (parse-N))
(cond ((equal? T (car aktuelles-to­ken))
      (next-token)
      (set! Ergebnis (parse-selbst))))

Eine mögliche Umsetzung dieses Prinzips zeigt das folgende Listing:

(include "scan-ausdruck.scm")

(define (pfehler text token)
  (display "Fehler: ")
  (display text)
  (display token)
  (newline))

(define (parse tokenliste)

  ; globale Ablage des aktuellen Tokens, erspart lookahead
  (define aktuelles-token null)

  ; liefert immer das erste Token und verkürzt die Eingabe entsprechend
  (define (next-token)
    (cond ((null? tokenliste) (set! aktuelles-token (cons 't_ende "ende")))
          (else
           (set! aktuelles-token (car tokenliste))
           (set! tokenliste (cdr tokenliste)))))

  (define (parse-faktor)
    (define ergebnis #t)
    ;Test (display "Aufruf von parse-faktor mit ")(display tokenliste) (newline)
    (cond ((equal? 't_zahl (car aktuelles-token))
           (next-token))
          ((equal? 't_klammerauf (car aktuelles-token))
           (next-token)
           (set! ergebnis (parse-ausdruck))
           (cond ((equal? 't_klammerzu (car aktuelles-token))
                  (next-token))
                 (else
                  (set! ergebnis #f)
                  (pfehler "parse-faktor erwartet Klammerzu nicht: " (car aktuelles-token)))))
          (else
           (pfehler "parse-faktor erwartet eine Zahl oder Klammer-auf nicht: " (car aktuelles-token))
           (set! ergebnis #f)))
    ergebnis) 

    (define (parse-produkt)
    (define ergebnis #t)
    ;Test (display "Aufruf von parse-produkt mit ")(display tokenliste) (newline)
    (cond ((equal? 't_ende (car aktuelles-token))
           (pfehler "parse-produkt erwartet einen Faktor nach * oder / nicht: " (car aktuelles-token)) 
           (set! ergebnis #f))
          (else
           (set! ergebnis (parse-faktor))
           (cond ((equal? ergebnis #t)
                  (cond ((equal? 't_punkt (car aktuelles-token))
                         (next-token)
                         (set! ergebnis (parse-produkt))))))))
    ergebnis)

  (define (parse-ausdruck)
    (define ergebnis #t)
    ;Test (display "Aufruf von parse-ausdruck mit ")(display tokenliste) (newline)
    (cond ((equal? 't_ende (car aktuelles-token))
           (pfehler "parse-ausdruck erwartet ein Produkt nach +/- nicht: " (car aktuelles-token)) 
           (set! ergebnis #f))
          (else
           (set! ergebnis (parse-produkt ))
           (cond ((equal? ergebnis #t)
                  (cond ((equal? 't_strich (car aktuelles-token))
                         (next-token)
                         (set! ergebnis(parse-ausdruck))))))))
    ergebnis)

  (define ergebnis #t)
  (next-token)

  ; die Terminale + und - werden weggelesen
  (cond ((equal? 't_strich (car aktuelles-token))
         (next-token)))

  (set! ergebnis (parse-ausdruck))
  (cond ((equal? ergebnis #t)
         (cond ((not (equal? 't_ende (car aktuelles-token)))
                (set! ergebnis #f)
                (pfehler "da sind noch Token über: " tokenliste)))))
  ergebnis)

(define tl(scan "-3+4/5-234*(3+4)"))

(cond ((eq? (caar tl) #f)
       (pfehler "Lexikalischer Fehler: " (cdar tl)))
      (else
       (parse tl)))

Der Parser hält sich auch in den Bezeichnungen an die EBNF-Diagramme. Die Funk­tion parse-ausdruck, parse-produkt und parse-faktor liefern jeweils einen Wahrheitswert zu­rück, so dass am Ende die erfolgreiche Analyse festgestellt werden kann. Die Proze­duren sind lokal zur Funktion parse, die das Hauptmodul darstellt.

Der Parser arbeitet auf der Tokenliste, die der Scanner erstellt hat.

7.3 Die Berechnung

Der letzte Schritt, die Berechnung läuft analog zum Parsing. Der Unterschied besteht le­diglich darin, dass hier nun keine grammatikalischen Fehler mehr auftauchen können, die entsprechenden Abfragen also unterbleiben können.

Lediglich bei den Berechnungen könnten hier noch Bereichsüberschreitungen auftre­ten, die abgefangen werden können. Ansonsten erfolgt nun die Berechnung.

In der vorliegenden Version führen Bereichsfehler, wie eine Division durch Null oder Bereichsü­berschreitungen zu einem Laufzeitfehler. Hier müssten noch Überprüfungen vorge­nommen werden. Speziell die Division durch Null lässt sich relativ einfach abfan­gen.

7.4 Erweiterungen

Die bisher umgesetzte Definition von Ausdruck ist relativ eng. Erweiterungen sind auf fol­genden Gebieten sinnvoll:

Erweiterung von Zahl

Der Automat aus 5.1 akzeptiert nur Zahlen, die vorzeichenlos sind und keinen Expo­nenten be­sitzen. Hier ist eine Erweiterung recht einfach machbar, da nur der Auto­mat im Scanner entspre­chend erweitert werden muß.

Einführung von Hochzahlen

Ausdrücke wie 2^3 sind in Mathematik-Programmen üblich und sinnvoll. Eine Erweiterung um derartige Ausdrücke muß berück­sichtigen, dass das Potenz­zeichen stärker bindet, als Punktrechnungen.

Einführung von Funktionen

Wichtig ist auch noch die Einführung von mathematischen Funktionen wie SIN, COS, SQRT und dergleichen.