# Compiler phases for expression programs
(eprog-phases)=

Recall that a compiler is organized as a sequence of phases. Each phase
consumes the representation produced by the previous one and produces the
next: the lexer turns the input text into tokens, the parser turns the
tokens into an abstract syntax tree (AST), semantic analysis checks the
AST, rejecting invalid programs and producing a typed AST for those
accepted for code generation, IR generation translates the typed AST
into an intermediate representation (IR), optimization rewrites the IR,
and machine code generation translates the IR into assembly.

```{image} phases-general.svg
:alt: input, lexer, tokens, parser, AST, semantic analysis, typed AST, IR generation, IR, optimization, machine code generation, assembly
:align: center
```

For [Expression Programs](assignment-2) the picture is leaner in three
ways.

- There is no lexer and no parser. Programs are written directly as OCaml
  values of type `eprog`, which is the AST.
- Semantic analysis does not produce a new data structure. In a language
  with types, it decorates the AST with type information for the later
  phases. The expression language is simple enough that no decoration is
  needed: when the program is well-formed, the phases after semantic
  analysis work on the same AST.
- There is no intermediate representation. Machine code generation
  translates the AST into assembly.

```{image} phases-eprog.svg
:alt: AST, semantic analysis, AST, optimization (dashed, not required by the assignment), machine code generation, assembly
:align: center
```

The optimization phase is dashed because the assignment does not
require it. Optimizations can be studied in two ways. Many standard
optimizations can already be described at the level of our AST. See
examples of these optimizations in
[Optimizations for expression programs](eprog-optimizations.md).
Implementing these optimizations may also be done in an auxiliary
intermediate representation. See the note on the
[implementation of basic optimizations](basic-opt.md), which develops
an intermediate representation (which is reminiscent of LLVM) and
implements these optimizations.