The Structure of a Compiler, and the Theory of Lexical Analysis

0Where this topic sits

Topic 1 covers two things that look unrelated and are not. The first is the architecture of a compiler — why it is built as a sequence of phases at all, and what each phase is responsible for. The second is the theory of the first phase: regular expressions, finite automata, and the equivalence between them that turns lexical analysis from a programming problem into a solved one.

The connection is this. Lexical analysis can be split off as a separate phase because the things it must recognize — keywords, identifiers, numbers, operators — form exactly the class of regular languages, and regular languages have an efficient, automatic recognition procedure. The moment you need to recognize something that is not regular, such as balanced parentheses, you need a different machine, and that machine is the parser. The phase boundary is not an engineering convenience. It is drawn where the mathematics changes.

1What a compiler is, and what surrounds it

A compiler reads a program in one language and produces an equivalent program in another, reporting any errors it finds along the way (Dragon §1.1). That is the whole definition, and notice what it does not say: nothing about optimization, nothing about machine code specifically, nothing about a particular architecture. A source-to-source translator is a compiler. So is a program that emits Java bytecode, or LLVM IR, or MIPS assembly — which is what yours will do.

The compiler is one component of a larger pipeline, and confusing its job with its neighbors' is a common early mistake:

Because SPIM assembles and loads, you can stop at assembly text and still watch your programs run. That is the only reason a one-semester compiler course can reach executable output at all.

2The phases, and the running example

Dragon §1.2 decomposes compilation into six phases. Learn them with the book's own running example, because you will meet it in the reading and in every compiler text afterward:

position = initial + rate * 60

Read that figure as a sequence of representations, not a sequence of actions. The representation is the real content of each phase boundary:

The symbol table is not a phase

It is drawn beside the phases because every phase reads or writes it (Dragon §1.2.7, §2.7). Phase 2 or 3 inserts a name when it meets a declaration; phase 3 looks names up to check they were declared; phase 6 looks them up again to find their storage. Treating the symbol table as belonging to one phase is a design error that becomes expensive in Topic 3, when a second kind of symbol table appears and the distinction between them starts to matter.

Phases and passes are different things

A phase is a logical stage. A pass is one complete traversal of the program being compiled (Dragon §1.2.8). Several phases may be grouped into one pass: a classic one-pass compiler lexes, parses, checks and generates code during a single left-to-right walk, emitting code from inside the parser's semantic actions. Ours is multi-pass — the parser builds a complete tree and later phases traverse it again.

Multi-pass costs memory and buys two things you will want. Optimization cannot act on code it has not seen yet. Forward references — calling a function defined later in the file — need the whole program in hand, which is why Topic 3's semantic analyzer runs twice. Backpatching (Dragon §6.7) is the classic technique for recovering some of that ability within a one-pass design; worth knowing it exists even though we will not need it.

3The front end / back end split

Phases 1–4 form the front end: they depend on the source language and know nothing about the target machine. Phases 5–6 form the back end: they depend on the target and know nothing about the source. The intermediate representation is the interface between them, and the whole value of the arrangement follows from that (Dragon §1.2.8).

This is not an abstract benefit. Topic 5 asks you to compare MIPS and ARM code generation, and the honest answer is a list of which files would change — a list that is short precisely because this boundary exists.

4The role of the lexical analyzer

Dragon §3.1 gives the scanner three jobs: group characters into lexemes and produce tokens; strip whitespace and comments; and correlate tokens with positions in the source so that later phases can report errors usefully.

Token, pattern, lexeme — three different things

These words are used interchangeably in casual speech and must not be here (Dragon §3.1.3):

The distinction earns its keep immediately. The parser decides on the token name alone — it needs to know it has an ID, not which identifier. The attribute matters later: the semantic analyzer needs the name to look it up, the code generator needs its address. And nobody ever needs reminding that a SEMI was spelled ;, which is why most tokens carry no attribute at all.

Why separate the scanner from the parser?

Dragon §3.1.1 gives three reasons, and they are worth being able to state out loud:

1. Simplicity of design. The parser's grammar does not have to describe whitespace and comments, which would otherwise be permitted between every pair of grammar symbols and would bloat every single production.
2. Efficiency. Specialised buffering and matching techniques apply to the character-level task and not to parsing (Dragon §3.2, on input buffering and sentinels).
3. Portability. Input-device and character-set peculiarities — line endings, encodings — are confined to one module.

5Specifying tokens: regular expressions

Dragon §3.3 builds the formal apparatus: an alphabet is a finite set of symbols; a string is a finite sequence of them; a language is any countable set of strings over an alphabet. Regular expressions denote languages, and are defined inductively — the whole definition is six lines:

BASIS       ε           denotes  { ε }
            a           denotes  { a }          for each symbol a of the alphabet

INDUCTION   (r) | (s)   denotes  L(r) ∪ L(s)          union
            (r)(s)      denotes  L(r) L(s)            concatenation
            (r)*        denotes  ( L(r) )*            Kleene closure
            (r)         denotes  L(r)                 grouping

Precedence — * highest, then concatenation, then |, all left-associative — lets most parentheses be dropped, exactly as it does for arithmetic. A language that some regular expression denotes is a regular set.

Regular definitions

Naming subexpressions makes a specification readable, provided each name is used only after it is defined, so that no recursion can creep in (Dragon §3.3.4). Our language's token specification written this way:

letter    ->  A | B | … | Z | a | b | … | z | _
digit     ->  0 | 1 | … | 9
id        ->  letter ( letter | digit )*
number    ->  digit digit*
ws        ->  ( blank | tab | newline )+

6Recognizing tokens: finite automata

A specification is not yet a recognizer. Dragon §3.4 moves from regular expressions to transition diagrams: states, edges labeled with characters, one start state, and accepting states that report a token.

Note the retraction on the edge out of state 1 labeled other. Having read < and then a character that is not =, the scanner must return LT and put that character back, because it belongs to the next token. Every scanner has to do this somewhere; in a generated scanner it is hidden inside the simulation loop.

NFA and DFA

A nondeterministic finite automaton may have several edges leaving a state on the same symbol, and may have ε-edges that consume no input. A deterministic one has exactly one edge per state per symbol and no ε-edges (Dragon §3.6). NFAs are easy to build from regular expressions; DFAs are easy to run — linear in the input, no backtracking. The two are equally expressive, and the two constructions establishing that are the theoretical core of this topic.

Regular expression → NFA: Thompson's construction

NFA → DFA: the subset construction

Together these give a mechanical route from a token specification to an efficient recognizer. DFA minimization (Dragon §3.9.6) then reduces the state count to the unique minimum. You will implement none of it — but you should understand that it is what flex does to your rules, because it explains both the performance and, more usefully, the conflict-resolution rules in §8.

7The limits of regular languages, and why phase 2 exists

This is the most important idea in Topic 1, and the one most often skipped. Consider the language of balanced parentheses:

    { (ⁿ )ⁿ  |  n ≥ 1 }        (  )   ( (  ) )   ( ( (  ) ) )   …

No regular expression denotes it and no finite automaton recognizes it. The argument is short (Dragon §3.3.5). A finite automaton has a fixed, finite number of states, so on a long enough input it must revisit one. Feed it ( repeatedly; after enough of them, two different counts i ≠ j must leave it in the same state. From that state the machine cannot tell them apart, so it accepts (ⁱ )ʲ — which is unbalanced. A machine with finite memory cannot count without bound.

This also settles a question that recurs all term: which phase should catch this error? If detecting it requires remembering an unbounded amount, the scanner cannot. int int int; is three perfectly good tokens — nothing about the vocabulary is wrong — and it is the parser that must object.

8How a scanner generator actually works

Dragon §3.5 and §3.8 describe what lex does with your specification, and it is exactly the theory above, applied:

1. Each pattern p_i is converted to an NFA N_i by Thompson's construction.
2. A single new start state is created, with an ε-edge to every N_i — one combined NFA for the whole specification.
3. The subset construction converts that to a DFA, and each accepting DFA state records which of the original patterns it accepts.
4. The DFA is minimized and emitted as tables inside the generated C.

Two rules then resolve the cases where several patterns match, and both are direct consequences of this construction (Dragon §3.5.3):

Being able to say which rule explains a behavior is worth more than memorising either. <= beating < is longest match, and rule order cannot change it. int coming back as a keyword rather than an identifier is first match, and rule order is the only thing deciding it.

9Errors, and what a compiler owes the programmer

Dragon §1.2 and §3.1.4 treat error handling as a first-class concern rather than an afterthought, and the reason is worth internalising: diagnostics are the part of a compiler that programmers interact with most. Very little can go wrong at the lexical level — essentially only a character that begins no legal lexeme — but how it is handled sets the pattern for every later phase.

A compiler that stops at the first error makes the programmer recompile once per typo. One that recovers reports everything at once, at the risk of cascading — a real trade-off, and one you meet again in Topic 2, where the cascade risk is much higher because the parser has far more context to lose.

The other half of this is location. A token's position is not decoration: it is the only thing connecting a message to the source text. Note that flex maintains line numbers for you but not columns, and that a phase which silently loses position information — by failing to count the newlines inside a comment, say — makes every later diagnostic wrong in a way that is very hard to trace back.

10The approach for this milestone

Theory settled, here is the shape of the implementation and the reasoning behind each decision. The code itself is documented; what follows is why it is arranged that way.

Specify the whole language's vocabulary now

Your grammar will grow for four more topics; your token set barely will. Adding switch to the specification in week 1 costs one line. Discovering in week 12 that you must reopen and re-verify the scanner costs an afternoon. This also mirrors real practice: a language's lexical structure is normally settled long before its grammar is.

Choose the token names carefully

They become the parser generator's %token declarations in Topic 2 and are then used throughout the front end. They are the vocabulary of the interface between phases 1 and 2, and renaming them later touches every file.

Decide where the attribute lives

Dragon §2.7 and §3.1.3 observe that the natural attribute for an identifier is a pointer to a symbol-table entry rather than the string itself. We use the string at this milestone because there is no symbol table yet — but be aware this is a simplification and know what it costs: every identifier is copied, and comparing two identifiers is a string comparison rather than a pointer comparison.

Report all errors, with line and column

Both halves matter. Recovery gives one message per mistake instead of one per compile; position gives a message the programmer can act on. Columns are the part people skip, and they are exactly what is needed on a line holding three statements.

Draw the phase boundary deliberately

When you are unsure whether a check belongs in the scanner, apply the test from §7: could a machine with finite memory decide it by looking at one lexeme? If yes, it may belong here. If it needs to remember an unbounded amount, or to know what came before, it belongs to a later phase. That single question resolves most of the 'which phase?' arguments you will have this semester.

11Self-check

12References

• Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques and Tools, 2nd ed. — §1.1–1.2 (language processors and structure), §1.6 (language basics), §2.6 (a hand-written lexical analyzer), §3.1 (the role), §3.2 (input buffering), §3.3 (specification), §3.4 (recognition), §3.5 (Lex), §3.6–3.7 (finite automata and the two constructions), §3.8 (how a generator is designed), §3.9 (DFA optimization).
• Levine, flex & bison (O'Reilly, 2009), ch. 1 — the tool rather than the theory.
• Jha, Phases of a Compiler, GeeksforGeeks (2021).
• Smith, What is a Compiler Design? Types, Construction Tools, Example, Guru99 (2022).