1

 1.1 Overview and History

 1.2 What Do Compilers Do?
 1.3 The Structure of a Compiler
 1.4 The Syntax and Semantics of Programming
Languages
 1.5 Compiler Design and Programming Language
Design
 1.7 Computer Architecture and Compiler Design
 1.8 Compiler Design Considerations

2
 Cause
◦ Software for early computers was written in assembly
language
◦ The benefits of reusing software on different CPUs started
to become significantly greater than the cost of writing a
compiler

 The first real compiler

◦ FORTRAN compilers of the late 1950s
◦ 18 person-years to build

3
 Compiler technology
◦ is more broadly applicable and has been
employed in rather unexpected areas.
 Text-formatting languages,
like nroff and troff; preprocessor packages like eqn,
tbl, pic
 Silicon compiler for the creation of VLSI circuits
 Command languages of OS
 Query languages of Database systems

4
 A compiler acts as a translator,
transforming human-oriented programming
languages
into computer-oriented machine languages.
◦ Ignore machine-dependent details for
programmer

Programming Machine
Language Compiler Language
(Source) (Target)

5
 Compilers may generate three types of code:
◦ Pure Machine Code
 Machine instruction set without assuming the
existence of any operating system or library.
 Mostly being OS or embedded applications.
◦ Augmented Machine Code
 Code with OS routines and runtime support routines.
 More often
◦ Virtual Machine Code
 Virtual instructions, can be run on any architecture
with a virtual machine interpreter or a just-in-time
compiler
 Ex. Java

6
 Another way that compilers
differ from one another is in the format of
the target machine code they generate:
◦ Assembly or other source format
◦ Relocatable binary
 Relative address
 A linkage step is required
◦ Absolute binary
 Absolute address
 Can be executed directly

7
 Any compiler must perform two major tasks
Compiler

Analysis Synthesis

◦ Analysis of the source program

◦ Synthesis of a machine-language program

8
 Source
Program Tokens SyntacticSemantic
Scanner Parser
(Character StructureRoutines
Stream)
Intermediate
Representation

Symbol and Optimizer

Attribute
Tables

(Used by all Phases of The

Compiler)
Code
Generator

Target machine code

9
 Source
Program Tokens SyntacticSemantic
Scanner Parser
(Character StructureRoutines
Stream)
Intermediate
Scanner Representation
 The scanner begins the analysis of the source
program by reading the input, character by
Symbol and Optimizer
character, and grouping characters into individual
Attribute
words and symbols (tokens)
Tables

 RE
RE (( Regular
Regular expression
expression ))

 NFA
NFA
(Used
(( Non-deterministic by Automata
Non-deterministic Finite
all
Finite Automata ))

 DFA
DFA DeterministicPhases
(( Deterministic Finite of
Finite Automata
Automata ))

 LEX
LEX The Compiler) Code
Generator

Target machine code

10
 Source
Program Tokens SyntacticSemantic
Scanner Parser
(Character StructureRoutines
Stream)
Intermediate
Parser Representation
 Given a formal syntax specification (typically as a
context-free grammar [CFG] ), the parse reads
Symbol and Optimizer
tokens and groups them into units as specified by
Attribute
the productions of the CFG being used.
 As syntactic structure Tables
is recognized, the parser
either calls corresponding semantic routines
(Used by all
directly or builds a syntax tree.

 CFG
CFG (( Context-Free
Phases
Context-Free Grammar
Grammar ))
of
Code

 BNF Backus-Naur The
BNF (( Backus-Naur Form Compiler)
Form ))

 GAA
GAA (( Grammar
Grammar Analysis
Analysis Algorithms
Algorithms )) Generator

 LL,
LL, LR,
LR, SLR,
SLR, LALR
LALR Parsers
Parsers

 YACC
YACC
Target machine code
11
 Source
Program Tokens SyntacticSemantic
Scanner Parser
(Character StructureRoutines
Stream)
Intermediate
Semantic Routines Representation

 Perform two functions
 Check the static semantics of each construct
 Do the actualSymbol and
translation Optimizer
 The heart of a compiler
Attribute
Tables

 Syntax
Syntax Directed
Directed Translation
Translation

 Semantic Processing
Semantic Processing Techniques
Techniques
 IR (Intermediate
(Used by all
Representation)
 IR (Intermediate Representation)
Phases of
The Compiler) Code
Generator

Target machine code

12
 Source
Program Tokens SyntacticSemantic
Scanner Parser
(Character StructureRoutines
Stream)
Intermediate
Optimizer Representation
 The IR code generated by the semantic routines is
analyzed and transformed into functionally
Symbol and Optimizer
equivalent but improved IR code
 This phase can beAttribute
very complex and slow
Tables
 Peephole optimization
 loop optimization, register allocation, code
(Used by all
scheduling
Phases of

 Register The Compiler) Code
Register and
and Temporary
Temporary Management
Management

 Peephole
Peephole Optimization
Optimization Generator

Target machine code

13
 Source
Program Tokens SyntacticSemantic
Scanner Parser
(Character StructureRoutines
Stream)
Intermediate
Code Generator Representation

 Interpretive
Interpretive Code
Code Generation
Generation

 Generating
Generating Code from Tree/Dag
Code from Tree/Dag

 Grammar-Based
Grammar-Based Code
Code Generator
Generator Optimizer

Code
Generator
Target machine code
14
 Code
Code Generator
Generator
[Intermediate Code
[Intermediate Code Generator]
Generator]

Non-optimized
Scanner
Scanner
[Lexical Intermediate Code
[Lexical Analyzer]
Analyzer]

Tokens

Code
Code Optimizer
Optimizer
Parser
Parser
[Syntax
[Syntax Analyzer]
Analyzer]
Optimized Intermediate Cod
Parse
tree

Code
Code Optimizer
Optimizer
Semantic
Semantic Process
Process
[Semantic
[Semantic analyzer]
analyzer] Target machine code

Abstract Syntax Tree w/

Attributes

15
Compiler writing tools
 Compiler generators or compiler-
compilers
 E.g. scanner and parser
generators
 Examples : Yacc, Lex

16
 A programming language must include the
specification of syntax (structure) and
semantics (meaning).
 Syntax typically means the context-free

syntax because of the almost universal use

of context-free-grammar (CFGs)
 Ex.

◦ a = b + c is syntactically legal
◦ b + c = a is illegal

17
 The semantics of a programming language
are commonly divided into two classes:
◦ Static semantics
 Semantics rules that can be checked at compiled
time.
 Ex. The type and number of a function’s arguments
◦ Runtime semantics
 Semantics rules that can be checked only at run time

18
 An interesting aspect is how programming
language design and compiler design
influence one another.

 Programming languages that are easy to

compile have many advantages

19
 Languages such as Snobol and APL are
usually considered noncompilable

 What attributes must be found in a

programming language to allow compilation?
◦ Can the scope and binding of each identifier
reference be determined before execution begins?
◦ Can the type of object be determined before
execution begins?
◦ Can existing program text be changed or added to
during execution?

20
 Compilers should exploit the hardware-specific
feature and computing capability to optimize
code.
 The problems encountered in modern computing

platforms:
◦ Instruction sets for some popular architectures are
highly nonuniform.
◦ High-level programming language operations are not
always easy to support.
 Ex. exceptions, threads, dynamic heap access …
◦ Exploiting architectural features such as cache,
distributed processors and memory
◦ Effective use of a large number of processors

21
 Debugging Compilers
◦ Designed to aid in the development and
debugging of programs.
 Optimizing Compilers
◦ Designed to produce efficient target code
 Retargetable Compilers
◦ A compiler whose target architecture can be
changed without its machine-independent
components having to be rewritten.

22