27.1 Aufgabe eines Parsers

Parser

umfang = 2 * pi * radius;

wird z.B. der Tokenstrom

< id "umfang" >
< op "=" >
< num 2 >
...

erzeugt. In den Token-Werten 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 sowie das Semikolon fehlen).

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

Wie Sie vielleicht schon 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 einen Tokenstrom wie

< sw "while" >
< br "(" >
< id "i" >
< op "<" >
...

Die Werte eines Tokens spielen für die syntaktische Analyse überhaupt keine Rolle, nur der Typ bzw. Name des Tokens. Eine Zeile wie

WHILE i < 0

ist in Java genau so falsch wie die Zeile

WHILE x < 12

Kommen wir nun zu einer Definition des Begriffs Parser:

Wie diese Überprüfung erfolgt, wird im nächsten Abschnitt erklärt.

Arbeitsweise eines Parsers

Der Input eines Parsers ist der Tokenstrom, der vom Lexer bereitgestellt wurde. Die Werte der Token interessieren den Parser dabei nicht im Geringsten, entscheidend sind die Tokentypen.

Erinnern Sie sich an das Thema "kontextfreie Grammatiken" in der Folge 26? Hier hatten wir als Beispiel eine einfache Grammatik für arithmetische Ausdrücke entworfen:

P1: Expr ---> Expr + Expr
P2: Expr ---> Expr * Expr
P3: Expr ---> num
P4: Expr ---> id
P5: Expr ---> ( Expr )

Durch Anwendung der Produktionsregeln 1, 3 und 3 kann man beispielsweise den Ausdruck

num + num

erzeugen:

Expr ==1==> Expr + Expr ==3==> num + Expr ==3==> num + num

Ein Parser muss nun rückwärts arbeiten. Er erhält vom Lexer beispielsweise den Tokenstrom

< num "12" >
< op "+" >
< num "17" >

den wir jetzt vereinfacht als

num + num

darstellen wollen. Nun versucht der Parser, diesen Tokenstrom bzw. dieses "Wort" auf das Startsymbol der Grammatik zurückzuführen. Als erstes "sieht" der Parser das linke "num" und wendet die Produktion P3 an:

num + num <==3== expr + num

Dann "sieht" der Parser das Plus-Zeichen, überspringt es aber erst einmal. Als Nächstes "sieht" der Parser wieder "num" und führt es mit P3 auf expr zurück:

expr + num <==3== expr + expr

Diesen Ausdruck erkennt der Parser jetzt als Produktionsregel 1, die Rückwärtsanwendung dieser Regel ergibt dann das Startsymbol der Grammatik, nämlich expr:

expr + expr <==1== expr

Gelingt dem Parser eine solche Rückwärtsableitung oder Reduktion, dann gilt der Ausdruck als gültiges Wort der Sprache L(G).