Erdhy's Brain

Compiler Construction — Concept Map (MOC)

3 min read

Compiler Construction — Concept Map (MOC)

Map of content for Compiler Construction / “Compilerbau” (Univ. Duisburg-Essen, Janis Voigtländer, winter term 2026/27), exam period 2026-winter, written exam 11.03.2027. Course page: compiler-construction.

Source: raw/compilerbau/compilerbau-slides-55.pdf — 55 pages, text-based, OK (slides version 28.10.2026, built with LaTeX Beamer). The professor updates the deck weekly; new pages are appended, so page counts and slide numbers shift — always cite the version date, not only the page number.

Concept pages

#BlockPageOwnsMasterySource
1Lexical analysis, theory (slides 19–51)lexical-analysis-formalismformal languages vocabulary, regular expressions (syntax, both semantics, abbreviations, algebraic laws), ε-NFA/DFA definitions, Thompson construction, ε-closure + fixpoint iteration, powerset construction, DFA minimization (Moore/Hopcroft), worked examples + exercise solutionslearningcompilerbau-slides-55.md, slides 19–51
2Lexical analysis, practice (slides 52–55)practical-lexerstokens vs. lexemes, longest match / first match, maximal-munch driver loop, escaping & quoting, merged-NFA construction, letter labels vs. driver, flex/Alex/re2c/ocamllex, limit of regex (nesting, layout, typedef), C₀ lexer checklistlearningcompilerbau-slides-55.md, slides 52–55

Granularity is deliberate: two pages for the whole lexical-analysis block, not one per lecture, because the deck grows weekly and the theory is a single coherent unit. Split once a section gets quizzed repeatedly (e.g. dfa-minimization.md, practical-lexers-flex.md).

Rendering conventions used on these pages

  • Equations: LaTeX, inline $…$ and display $$…$$.
  • Automata: mermaid only — stateDiagram-v2 for automata, flowchart LR for the Thompson fragment templates (boxes = fragments, circles = new states). Rationale: mermaid renders natively in Obsidian and on the published site (brain.erdhyernando.xyz), Graphviz renders in neither without a plugin. Set-labelled states use state "{A,C}" as AC; opposite-direction edge pairs (B→C and C→B) come out slightly overlapping — the LaTeX transition tables next to each graph carry the exact information.
  • Diagram facts were reconstructed from the rendered PDF pages (the text extraction drops all figures), so the automata are exact, not paraphrased.

Reading order

slides  0–18   organisation, compiler phases, C₀, target AM₀       → course page
slides 19–29   why lexing, formal-language vocabulary               → lexical-analysis-formalism §0–1
slides 30–35   regular expressions (+ exercises 1–4)               → lexical-analysis-formalism §2
slides 36–43   finite automata (NFA, DFA)                          → lexical-analysis-formalism §3
slides 39–42   regex → NFA (Thompson)                              → lexical-analysis-formalism §4
slides 44–47   ε-closure, fixpoint, powerset construction          → lexical-analysis-formalism §5
slides 48–49   worked traces + minimization                        → lexical-analysis-formalism §6
slides 50–51   exercises on automata                               → lexical-analysis-formalism §7
slides 52–55   longest/first match, lexer generators               → practical-lexers

Known gaps

  • Organisation & course mechanics (Prüfungsvorleistung details, milestone deadlines, Moodle specifics) are only summarised on the course page — no dedicated page, and they change every term.
  • Lexical analysis for C₀ in Haskell (the actual milestone design: Alex vs. hand-written, DSL-based code generation) is not documented — the lecture only describes it orally; page it after the first exercise session.
  • Syntactical analysis (CFGs, LL(1), transformations, parse trees, SLR) is in the table of contents but not yet in the deck — slides 2–3 announce it, the 55-page version ends at lexical analysis.
  • Semantical analysis / interpreters / code generation (attribute grammars, AM₀, translation functions) likewise: announced only.
  • DFA minimization algorithm is shown as a result on slide 49, not derived — the algorithm on lexical-analysis-formalism §6.2 comes from literature, flagged as such.
  • No wiki/exams/2026-winter-compiler-construction.md yet and no quiz page for this course → wiki/quizzes/; create both once the first exercise sheet is out.

Maintenance

  • Re-ingest after each weekly slide update: pdf2md raw/compilerbau/ then diff the new .md against the previous version and update the affected page + this table (source column: version date).
  • Mastery moves to reviewing after a quiz, mastered after a mock exam on the block.

2 items under this folder.