Compiler phases for expression programs

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.

For Expression Programs 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.

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. Implementing these optimizations may also be done in an auxiliary intermediate representation. See the note on the implementation of basic optimizations, which develops an intermediate representation (which is reminiscent of LLVM) and implements these optimizations.