Lexer, Parser und Syntaxbaum

Kurz: Ein Compiler liest Quelltext zuerst als Zeichenstrom. Der Lexer zerlegt ihn in Token, der Parser baut daraus anhand der Grammatik einen Syntaxbaum (AST).

Genauer: Der Lexer erkennt Wörter, Zahlen, Operatoren und Klammern und ignoriert Leerraum und Kommentare. Der Parser prüft, ob die Token der Grammatik der Sprache entsprechen, und bildet die Struktur ab, z. B. 1 + 2 * 3 als Baum, in dem die Multiplikation tiefer liegt.

Im Detail

• Token: z. B. IDENT(x), NUMBER(42), PLUS.
• Grammatik: Regeln in Backus-Naur-Form (BNF). Rekursion bildet verschachtelte Strukturen ab.
• Recursive-Descent-Parser: Pro Regel eine Funktion; leicht von Hand zu schreiben.
• Operator-Vorrang: Durch Grammatikebenen oder Pratt-Parsing.
• AST: Abstract Syntax Tree, ohne überflüssige Details wie Klammern.
• Fehlermeldungen: Gute Parser melden Zeile und Spalte und fangen sich nach Fehlern wieder.
• Werkzeuge: ANTLR, tree-sitter, Parser-Kombinatoren.

Siehe auch: Zwischendarstellung und Compiler-Optimierung, Typsysteme und Typinferenz