Overview

The frontend:

Scanner:

• Maps character stream into words: the basic unit of syntax
• Produce pairs: a word and its part of speech (the pair is called a token)
• $x=x+y$ becomes $<id,x>=<id,x>+<id,y>$

Parser

• Recognizes context-free syntax & reports errors

Backend

Instruction Selector

• Produce fast, compact code
• Take advantage of target features such as addressing modes
• Usually viewed as a pattern matching problem

Register Allocation

• Have each value in a register when it is used
• Manage a limited set of resources
• Can change instruction choices & insert LOADs & STOREs
• Optimal allocation is NP-Complete

Instruction Scheduling

• Avoid hardware stalls and interlocks.
• Use all functional units productively
• Can increase lifetime of variables

Traditional Three-Pass Compiler

The Optimizer (or Middle End)