CB-KUSCHE

Wahlpflichtmodul Compilerbau

Inhaltsverzeichnis

• Grundlagen
  • Aufbau klassischer Compiler
  • Begriffe
    • Lexer vs. Parser
    • Value Propagation
• Parser
  • Entwurf
  • Arten
• Lexer-Regeln
• Praxis mit yacc / bison
• Parser mit rek. Abstieg

Grundlagen

Aufbau klassischer Compiler

• Frontend: Lexer, Parser
• Infrastruktur: Symboltabelle, Syntaxbaum
• Backend: Optimierer, Codegenerator

Begriffe

Lexer vs. Parser

• Lexer: Zeichenstrom $\rightarrow$ Tokenstrom (zeichenweise)
  • z.B.: Ziffern $\rightarrow$ Zahlen; Zeichen $\rightarrow$ Schlüsselwörter/Namen; ...
  • verwirft Whitespace und Kommentare
• Parser: Token $\rightarrow$ Syntaxbaum/-graph (tokenweise)
  • wendet Syntaxregeln in korrekter Reihenfolge an und erkennt Syntaxfehler
  • kann auch on the fly Ergebnisse berechnen (Ausdrücke), Operationen durchführen (Interpreter) oder Code erzeugen (Compiler)

Value Propagation

• Compiler bestimmt Wertebereich einer Variable

Parser

Entwurf

• Voraussetzung: Syntax-Definition
  • wesentlicher Teil der Spezifikation eines Compilers
  • Parser wird 1:1 auf Basis der Syntaxregeln codiert
• Lexer nimmt Zeichenstrom, assoziiert diesen mit Tokens, gibt Tokenstrom aus
  • d.h. keine Semantikprüfung von Namen, Terminalsymbole werden erkannt
  • Kommentare etc. werden entfernt
• Parser nimmt Tokenstrom
  • Tokens sind atomar
  • löst Non-Terminalsymbole auf
  • gibt entweder Syntaxbaum oder Operation wird ausgeführt (Interpreter) oder Code wird erzeugt (Compiler)

Arten

• Top-Down-Parser: rekursiver Abstieg
  • für einfache Sprachen, normalerweise handcodiert
  • vom Programm-repräsentierenden Symbol wird Funktion aufgerufen, bis alles zu Terminalsymbolen aufgelöst ist
  • jedes Non-Terminalsymbol hat eine eigene Funktion
• Bottom-Up / Shift-Reduce Parser: tabellengesteuert
  • automatisch generiert
  • effizienter
  • Syntax der Sprache nicht im Code, nur in den Tabellen
  • geht von den einzelnen Tokens aus, findet passenden Weg im Baum hoch
  • Erklärung Shift-Reduce: wenn nicht reduziert werden kann, wird geshiftet, d.h. pushe auf Stack
    • solange shiften, bis reduziert werden kann: poppt alles vom Stack und reduzierte Funktion wird auf den Stack gelegt
  • Entscheidung der Aktion durch "wahnwitzige" Tabellen

Lexer-Regeln

• ganz grundsätzlich muss zwischen alphabetischen und numerischen Zeichen unterschieden werden
• Darstellung mithilfe EBNF
  • Oder-Strich für Alternativen
  • eckige Klammern für optionale Ausdrücke
  • geschweifte Klammern für 0 oder mehr Mal
  • runde Klammern für Gruppierungen

digit = '0' | '1' ... | '9'
letter = 'a' | 'b' | ... | 'Z'
ident = (letter | '_'){digit | letter | '_'}
integer = digit{digit}
integer = digit[integer]
float = ['+'|'-']digit{digit}['.'{digit}][('e'|'E')['+'|'-']digit{digit}]

• der Ausdruck integer = {digit}digit ist unklug, weil man dann zwei Zeichen Lookahead benötigt
• Für den Float wurde absichtlich kein integer verwendet

Achtung: eigentlich ist der falsch; die Regel kann nicht zwischen Float und Int unterscheiden $\rightarrow$ Zweideutigkeit

• Namenstrenner: Freiräume wie Leertasten, Tabs

Praxis mit yacc / bison

• bei rekursiven Non-Terminals sollte die leere Alternative zuerst kommen
• eine Zeile pro Alternative

Bsp.:

Input:
  // Leere Alternative
  | Line Input
  ;

• C-Code wird in geschwungene Klammern geschrieben

Parser mit rek. Abstieg

• einfachste Möglichkeit zur Implementierung eines Compilers