Vortrag Compilerbau, Lugbe 17. Jan. 2002

Inhalt

  1. Kurzzusammenfassung
  2. Kleines Glossar
  3. Ressourcen im Web
  4. Bücher
  5. Lex und Yacc (pdf)
  6. 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:
Der Compiler führt zusätzlich ein paar weitere Schritte aus:
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):
  1. Der Parser fordert vom Scanner (Lexer) ein Token an.
  2. Das Token wird mit der gespeicherten Grammatik der Sprache verglichen.
    Passt es nicht zu den erwarteten Möglichkeiten wird ein Syntax-Fehler ausgegeben.
  3. 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.
  4. 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.
  5. 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
BNFBackus-Naur Form. Darstellungsmethode für eindeutige Grammatiken. Nicht für menschliche Sprache geeignet weil sie oft mehrdeutig ist.
EBNFExtended BNF. Mächtiger und eleganter als BNF.
GrammatikRegelsammlung für die Festlegung der korrekten Kombinationsmöglichkeiten von Zeichen und Wörtern einer bestimmten Sprache.
LexDer Scanner zu Yacc. Kann auch "standalone" verwendet werden.
ParserGrammatik-Validierer.
RegelPrüfung auf gültigen Inhalt.
Scanner / LexerEingabe-Strom-Analysator nach ->Tokens. Liest Zeichen für Zeichen ein und gibt erkannte Tokens an den Parser zurück.
SpracheMenge von bestimmten Wörtern.
TerminalAbschliessendes Token, das einen Wert enthält wie eine Zahl, ein Identifier (Variable), einen String oder ein Schlüsselwort.
TokenUnterscheidbare 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.

Ressourcen im Web

>top
Programmierparadigmen

Programmiersprachen

Compiler
Lex und Yacc (1)
Lex und Yacc (2)
Lex und Yacc (3)
Lex und Yacc (4)
Free Compilers
Compilergeneratoren (Compiler Compiler) (z.B. Coco/R in COCOL)
Compiler Compiler in und für C

Bücher

>top
David A. Watt: Programming Languages Concepts and Paradigms
Aho, Sethi, Ullmann: Compilers: Principles, Techniques and Tools
N. Wirth: Compiler construction (Deutsch: Compilerbau)
D. Grune, H. Bal, C. Jacobs, K. Langendoen: Modern Compiler Design

Lex und Yacc (pdf)

>top
lex_yacc.pdf

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