Folge 30 - Syntaxanalyse

1. Parser

Sie erinnern sich bestimmt: Ein Compiler übersetzt eine leicht verständliche Programmiersprache in Maschinensprache. Dabei durchläuft der Übersetzungsvorgang mehrere Phasen, von denen wir bereits die lexikalische Analyse kennen gelernt haben. Die lexikalische Analyse überprüft die Zeilen des Quelltextes nicht nur auf lexikalische Korrektheit, sondern erzeugt auch noch einen sogenannten Tokenstrom. Aus der Zeile
umfang = 2 * pi * radius;

wird z.B. der Tokenstrom

id assop num mul id mul id semi

erzeugt. In den String- bzw. Zahlenattributen der einzelnen Token wird dann gespeichert, um welche Zahl bzw. welche Variable es sich konkret handelt.

Wir wollen jetzt die nächste Phase des Übersetzungsvorgangs kennenlernen, nämlich die syntaktische Analyse. In dieser syntaktischen Analyse überprüft der Compiler, ob z.B. eine while-Schleife die korrekte Syntax hat:

WHILE i < 0 DO i := i+1;

wäre z.B. für einen Pascal-Compiler syntaktisch korrekt, für einen C-Kompiler dagegen syntaktisch falsch, ebenso für einen Java-Compiler. In Java wird das Schlüsselwort while grundsätzlich klein geschrieben, die Schleifenbedingung muss in runden Klammern stehen, das Schlüsselwort DO gibt es überhaupt nicht, und der Zuweisungsoperator besteht nur aus einem Gleich-Zeichen.

while (i < 0) i = i+1;

wäre für die Sprache Java syntaktisch korrekt, während

while i < 0 i = i+1

syntaktisch falsch wäre (die runden Klammern fehlen).

Der Teil des Compilers, der für diese syntaktische Analyse zuständig ist, wird als Parser bezeichnet.

Parser

Der Teil des Compilers, der für die syntaktische Analyse zuständig ist.

Wie Sie vielleicht schon kritisch bemerkt haben, untersucht der Parser nicht die ursprüngliche Befehlszeile, sondern den Tokenstrom, den der Lexer ihm liefert.

Ein Java-Parser würde also nicht die Zeile

while (i < 0) i = i+1;

untersuchen, sondern den Tokenstrom

whileop openbr id compop num closedbr id assop id add num semi

Das Token compop seht für "compare operator" oder "Vergleichsoperator" und hat als Stringattribut den Wert "<", nur um noch einmal ein Beispiel zu nennen. Die String- und numerischen Attribute spielen allerdings für die syntaktische Analyse überhaupt keine Rolle.

Kommen wir nun zu einer "verschärften" Definition des Begriffs Parser:

Parser

Der Parser ist der Teil eines Compilers, der überprüft, ob ein gegebener String (Terminalkette) zur Sprache L(G) gehört oder nicht. Dieser Vorgang wird auch Syntaxanalyse genannt.

Dazu versucht der Parser, aus dem Tokenstrom (dem bereits durch den Lexer "zerlegten" arithmetischen Ausdruck) durch Rückwärtsableiten oder Reduzieren das Startsymbol der Grammatik zu erhalten. Gelingt es dem Parser, den Tokenstrom auf das Startsymbol zu reduzieren, so ist der Tokenstrom syntaktisch korrekt. Kann das Startsymbol dagegen nicht erhalten werden, so enthält der Tokenstrom einen Syntaxfehler. Nach dem Studium des Beispiels wird klar, dass ein Parser nicht rein mechanisch arbeitet, sondern "mitdenken" oder sogar etwas "vorausdenken" kann.

2. Eindeutige Grammatiken

Was eine kontextfreie Grammatik ist, haben Sie hoffentlich verstanden. Nämlich eine Grammatik, bei der alle Produktionsregeln die Form
  • A --> a

haben; auf der linken Seite der Produktionsregeln steht also immer ein einziges Nichtterminal.

Was ist nun eine eindeutige Grammatik? Betrachten wir zunächst eine Grammatik, die nicht eindeutig ist, dann verstehen Sie das Ganze besser. Wenn man eine Grammatik beschreibt, reicht es meistens aus, wenn man nur die Produktionsregeln angibt. Die Mengen N und T sowie das Startsymbol können dann diesen Regeln entnommen werden.

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

Die Grammatik ist also sehr einfach und umfasst nur vier Produktionsregeln. Aber wieso ist diese Grammatik nicht eindeutig?

Schauen wir uns die Herleitung des Ausdrucks num + num * num näher an.

Expr =1=> Expr + Expr =3=> num + Expr =2=> num + Expr * Expr =3=> num + num * Expr =3=> num + num * num

Wir haben also folgende Regeln in folgender Reihenfolge angewandt: 1, 3, 2, 3, 3.

Da immer das am weitesten links stehende Nichtterminal erweitert wird, ist diese Angabe von Ziffern erlaubt; es ist stets klar, wie die Kette von Terminalen und Nichtterminalen erweitert werden muss.

Betrachten wir nun eine andere Ableitung:

Expr =2=> Expr * Expr =1=> Expr + Expr * Expr =3=> num + Expr * Expr =3=> num + num * Expr =3=> num + num * num

Wir haben also die Ableitung 2, 1, 3, 3, 3 durchgeführt.

Mit anderen Worten: Es gibt zwei völlig verschiedene Wege, den String num + num * num aus dem Startsymbol herzuleiten. Eine solche Grammatik ist nicht eindeutig!

Eindeutige Grammatik

Eine kontextfreie Grammatik G ist dann eindeutig, wenn für jedes Wort L(G) genau eine mögliche Ableitung aus dem Startsymbol existiert.

Für theoretische Betrachtungen ist es recht unerheblich, ob eine Grammatik eindeutig oder nicht eindeutig ist. Will man dagegen einen Parser konstruieren, der Syntaxanalyse betreiben kann, so muss die Grammatik schon eindeutig sein. Wenn der Parser einen Tokenstrom wie

num + num * num

vom Lexer bekommt, so muss der Parser diesen Tokenstrom auf das Startsymbol der Grammatik zurückführen. Dabei muss der Parser bestimmte Entscheidungen treffen. Damit er nicht "hängen bleibt", muss die Grammatik eindeutig sein; es darf nur ein Weg vom Tokenstrom zum Startsymbol existieren.

Übung 30.1 (2 Punkte, als Hausaufgabe geeignet)

Konstruieren Sie einen weiteren Beweis, der zeigt, dass die obige Grammatik nicht eindeutig ist; diesmal soll aber auch die Regel 4 mit verwendet werden.

3. Parsebäume

Eine Ableitung, d.h. die Herleitung eines ausschließlich aus Terminalzeichen bestehenden Strings aus dem Startsymbol einer Grammatik, kann man auch graphisch in Form eines Parsebaums darstellen. Die folgende Zeichnung zeigt einen solchen Parsebaum:

Die Wurzel des Baumes ist identisch mit dem Startsymbol der Grammatik. Die Blätter des Baumes (grün gezeichnet) sind identisch mit den Terminalsymbolen des abgeleiteten Ausdrucks. Die Blätter müssen - ähnlich wie bei einem binären Suchbaum - von links nach rechts gelesen werden. Für den hier gezeigten Baum erhält man dann den Terminalstring

id + ( id + id )

Aus der Sicht des Parsers gesehen ist ein Parsebaum der Weg, wie man von einem Terminalstring (den Blättern) zurück zum Startsymbol (der Wurzel) gelangen kann.

Den Begriff "Eindeutige Grammatik" kann man jetzt neu definieren:

Eindeutige Grammatik

Eine kontextfreie Grammatik G ist dann eindeutig, wenn für jedes Wort L(G) genau ein Parsebaum existiert.

Wenn man jetzt einen konkreten Parser für eine Sprache programmieren möchte, so muss man darauf achten, dass die zu Grunde liegende Grammatik eindeutig ist. Nur dann weiß der Parser bei jedem Reduktionsschritt genau, wie er sich verhalten soll. Bei einer mehrdeutigen Grammatik (mit mehreren Parsebäumen für einen Ausdruck) gibt es Stellen im Reduktionsprozess, an denen der Parser nicht weiß, was er machen soll.

Übung 30.2 (3 Punkte, als Hausaufgabe geeignet)

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

a) Zeichnen Sie jetzt einen Parsebaum für den Ausdruck

aabbab

b) Versuchen Sie, ob Sie einen zweiten Parsebaum für den gleichen Ausdruck zustande bekommen!

Übung 30.3 (3 Punkte, als Hausaufgabe geeignet)

Geben Sie eine eindeutige Grammatik an, die folgende Sprache hat: Alle korrekten Java-Zuweisungen, zum Beispiel

Umfang = 2 * Pi * Radius;

oder

Volumen = Laenge * Laenge * Laenge;

oder

Pi = 3.14;

Ergänzungsaufgabe (3 Punkte, am PC zu erledigen)

Programmieren Sie ein Java-Applet, das durch zufällige Anwendung der verschiedenen Produktionsregeln beliebig lange Java-Zuweisungen erzeugen kann.

4. Codeerzeugung

Kommen wir jetzt zu einem ebenfalls sehr wichtigen Thema. Der Parser soll ja nicht nur analysieren, ob ein Ausdruck syntaktisch korrekt ist, sondern er soll den Ausdruck auch noch übersetzen. Eigentlich ist dies sogar die wichtigste Aufgabe eines Parsers.

Damit das Übersetzen funktionieren kann, muss der Übersetzer natürlich wissen, wann er welchen String ausgeben soll. Dazu muss die Grammatik entsprechend modifiziert werden. Betrachten wir die so veränderte "attributierte" Grammatik:

  1. Expr --> Term
  2. Expr --> Expr + Term [ print "add"]
  3. Expr --> Expr - Term [ print "sub"]
  4. Term --> Fact
  5. Term --> Term * Fact [ print "mul"]
  6. Term --> Term / Fact [ print "div"]
  7. Fact --> num [ print "push "+ token.zahlenAttribut]
  8. Fact --> id [ print "push "+ token.stringAttribut]
  9. Fact --> (Expr)

Spielen wir hierzu ein Beispiel durch: Der Ausdruck (17 + 4) * 3 soll in Stackmaschinencode übersetzt werden. Jedesmal, wenn wir beim Rückwärtsableiten eine attributierte Produktionsregel anwenden, wollen wir den erzeugten Code in eine Textdatei schreiben. Schauen wir mal, was dabei herauskommt.

Schritt Regel Ausdruck nach dem Schritt Code
0 --- (17 + 4) * 3 ---
0 --- ( num + num) * num ---
1 7 ( Fact + num) * num "push 17"
2 4 ( Term + num) * num ---
3 1 ( Expr + num) * num ---
4 7 ( Expr + Fact) * num "push 4"
5 4 ( Expr + Term) * num ---
6 2 ( Expr ) * num "add"
7 9 Fact * num ---
8 7 Fact * Fact "push 3"
9 4 Term * Fact ---
10 5 Term "mul"
11 1 Expr ---

Es wird also folgender Stackmaschinencode generiert (wenn man von unten nach oben vorgeht):

push 17
push 4
add
push 3
mul

Das ist genau der Code, den man auch "per Hand" aus dem Ausdruck (17+4)*3 erzeugt hätte.

Interessant ist also Folgendes: Mit relativ einfachen Mitteln und bereits auf der Ebene der Produktionsregeln kann man bestimmen, wann und wie welcher Code der Zielsprache generiert werden soll.

Übung 30.4 (3 Punkte)

Übersetzen Sie auf die eben gezeigte Art und Weise den Ausdruck (17 + 4) * (21 - 5) in Stackmaschinencode!

weiter mit Folge 31: Parserkonstruktion

Wir wollen nun zum Abschluss des Kurses kommen und überlegen, wie man jetzt einen funktionierenden Parser konstruieren kann, wenn eine eindeutige und kontextfreie Grammatik G vorgegeben ist.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 31. Juli 2006.






IMPRESSUM