Vortrag Compilerbau, Lugbe 17. Jan. 2002

Inhalt

Kurzzusammenfassung
Kleines Glossar
Ressourcen im Web
Bücher
Lex und Yacc (pdf)
Regular Expressions

Kurzzusammenfassung

>top
Ein Compiler ist ein Programm, das Eingaben in Ausgaben umwandelt (math. abbildet). Ein Interpreter produziert keinen Output. Er analysiert den Input und führt ihn gleich aus.
Compiler und Interpreter haben viele Gemeinsamkeiten:

Scanner
Parser
Symboltabelle
Parsetree
Framestack
ev. Ausführungsstack

Der Compiler führt zusätzlich ein paar weitere Schritte aus:

ev. Erzeugung von Zwischencode
Codeoptimierung
Ausgabe in einem anderen Format

Da ein Compiler nicht wissen kann, was für Input er erhält, muss er den Input in logische Einheiten zerlegen. Daraus baut er einen Parse-Baum. Ein Parsevorgang könnte so aussehen (mit Lex und Yacc):

Der Parser fordert vom Scanner (Lexer) ein Token an.
Das Token wird mit der gespeicherten Grammatik der Sprache verglichen.
Passt es nicht zu den erwarteten Möglichkeiten wird ein Syntax-Fehler ausgegeben.
Die Grammatik besteht aus Regeln und Terminalen (siehe Glossar). Der Parser versucht, den Input ganz mit einer Regel in Einklang zu bringen. Der Ast ist fertiggeparst wenn der Vorgang überall auf Terminale gestossen ist.
Ist ihm das gelungen, werden die attributierten Anweisungen ausgeführt. Z.B. Symbol in die Symboltabelle abfüllen, Symbol abfragen, Ast an den Parsebaum anhängen. Dann werden die korrekten Tokens vom Parsestack entfernt und durch den Namen der Regel ersetzt.
Ist die oberste Regel erfüllt, gilt das Programm als korrekt und validiert. Als Nebeneffekt wurde noch das Programm ausgeführt. Der Parser hat sein Ziel erreicht: ACCEPT.

Beispieltokens als reguläre Ausdrücke:

[a-zA-Z][a-zA-Z0-9_]*    // IDENT ...
[1-9][0-9]*              // ZAHL ...

Beispielgrammatik:

rechnen: IDENT '=' operation

operation: '(' operation ')'
         | operation '+' operation
         | operation '-' operation
         | ZAHL
         ;

Hier sind IDENT und ZAHL Terminale. Die Regel 'operation' ist rekursiv. Dadurch ermöglicht sie sehr viele verschiedene gültige Ausdrücke.
Die Labels vor dem Doppelpunkt sind die Namen der Regeln. Hinter dem Doppelpunkt folgen die eigentlichen Regelkörper.

Gültiger Ausdruck:

abc_8 = (33 + 198 + 3 - 4) + 5

Attributierte Grammatik (yacc für C):

rechnen: IDENT '=' operation        { printf("%d%\n", $3); }

operation: '(' operation ')'        { $$ = $2; }
         | operation '+' operation  { $$ = $1 + $3; }
         | operation '-' operation  { $$ = $1 - $3; }
         | ZAHL                     { $$ = $1; }
         ;

Yacc ist ein Tabellengesteuerter Parser. Er generiert einen endlichen Automaten (finite state machine), mit Hilfe dessen der Input Token für Token auf Gültigkeit überprüft wird. Yacc ist ein bottom-up Parser. Andere solche Parser sind 'Parser mit rekursivem Abstieg' (recursive descent parser). Coco/R, entwickelt an der ETH Zürich ist ein sehr eleganter solcher Compiler-Compiler mit viel bequemerem Fehlerhandling als mit Lex/Yacc, die schon ein bisschen in die Jahre gekommen sind. Auch kann die Grammatik in EBNF dargestellt werden statt nur in BNF wie bei Yacc.

Kleines Glossar

>top

BNF	Backus-Naur Form. Darstellungsmethode für eindeutige Grammatiken. Nicht für menschliche Sprache geeignet weil sie oft mehrdeutig ist.
EBNF	Extended BNF. Mächtiger und eleganter als BNF.
Grammatik	Regelsammlung für die Festlegung der korrekten Kombinationsmöglichkeiten von Zeichen und Wörtern einer bestimmten Sprache.
Lex	Der Scanner zu Yacc. Kann auch "standalone" verwendet werden.
Parser	Grammatik-Validierer.
Regel	Prüfung auf gültigen Inhalt.
Scanner / Lexer	Eingabe-Strom-Analysator nach ->Tokens. Liest Zeichen für Zeichen ein und gibt erkannte Tokens an den Parser zurück.
Sprache	Menge von bestimmten Wörtern.
Terminal	Abschliessendes Token, das einen Wert enthält wie eine Zahl, ein Identifier (Variable), einen String oder ein Schlüsselwort.
Token	Unterscheidbare und aus einem Eingabestrom herausfilterbare Text-Einheit. Das kann sein: ein Schlüsselwort wie "until", ein Operator wie "++", ein Separator wie "{", ein Bezeichner wie "abc_8", ein Wert wie "0.314159265e1", ein String wie "Hello World!", eine Zahl wie "0x3b78efab".
Yacc	"Yet another compiler compiler". Der bekannteste in der Gattung der Compiler - Generatoren.

Regular Expressions

>top
Werden hier nicht erklärt, sind Bestandteil jedes Tutorials für Lex und Yacc.

Copyleft ohne Gewähr Matthias Hürlemann (matteo at datacomm.ch), 2002

Vortrag Compilerbau, Lugbe 17. Jan. 2002

Inhalt

Kurzzusammenfassung

Kleines Glossar

Ressourcen im Web

Bücher

Lex und Yacc (pdf)

Regular Expressions