Chapter 1 Introduction

1
 Outlines
 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
Overview and History (1)
 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
Overview and History (2)

 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
Objectives
 Be able to build a compiler for a (simplified)
(programming) language
 Know how to use compiler construction tools,
such as generators of scanners and parsers
 Be familiar with virtual machines, such as
the JVM and Java bytecode
 Be able to define LL(1), LR(1), and LALR(1)
grammars
 Be familiar with compiler analysis and
optimization techniques
 … learn how to work on a larger software
project!
Compilers and Interpreters
 “Compilation”
 Translation of a program written in a source
language into a semantically equivalent program
written in a target language

Input

Source Target
Compiler
Program Program

Error messages Output

Compilers and Interpreters (cont’d)
 “Interpretation”
 Performing the operations implied by the source
program

Source
Program
Interpreter Output
Input

Error messages
The Analysis-Synthesis Model of
Compilation

 There are two parts to compilation:

 Analysis determines the operations implied by the
source program which are recorded in a tree
structure
 Synthesis takes the tree structure and translates
the operations therein into the target program
Other Tools that Use the Analysis-
Synthesis Model
 Editors (syntax highlighting)
 Pretty printers (e.g. Doxygen)
 Static checkers (e.g. Lint and Splint)
 Interpreters
 Text formatters (e.g. TeX and LaTeX)
 Silicon compilers (e.g. VHDL)
 Query interpreters/compilers (Databases)
Preprocessors, Compilers, Assemblers,
and Linkers

Skeletal Source Program

Preprocessor
Source Program
Try for example:
Compiler
gcc -v myprog.c
Target Assembly Program
Assembler
Relocatable Object Code
Linker Libraries and
Relocatable Object Files
Absolute Machine Code
The Grouping of Phases
 Compiler front and back ends:
 Front end: analysis (machine independent)
 Back end: synthesis (machine dependent)
 Compiler passes:
 A collection of phases is done only once (single
pass) or multiple times (multi pass)
 Single pass: usually requires everything to be defined
before being used in source program
 Multi pass: compiler may have to keep entire program
representation in memory
Compiler-Construction Tools
 Software development tools are available to
implement one or more compiler phases
 Scanner generators
 Parser generators
 Syntax-directed translation engines
 Automatic code generators
 Data-flow engines
What Do Compilers Do (1)

 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)

13
What Do Compilers Do (2)
 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

14
What Do Compilers Do (3)
 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

15
The Structure of a Compiler (1)

 Any compiler must perform two major

tasks
Compiler

Analysis Synthesis

 Analysis of the source program

 Synthesis of a machine-language program
16
 The Phases of a Compiler
Phase Output Sample
Programmer (source code producer) Source string A=B+C;
Scanner (performs lexical analysis) Token string ‘A’, ‘=’, ‘B’, ‘+’, ‘C’, ‘;’
And symbol table with names
Parser (performs syntax analysis Parse tree or abstract syntax tree ;
|
based on the grammar of the =
programming language) / \
A +
/ \
B C

Semantic analyzer (type checking, Annotated parse tree or abstract

etc) syntax tree
Intermediate code generator Three-address code, quads, or int2fp B t1
RTL + t1 C t2
:= t2 A
Optimizer Three-address code, quads, or int2fp B t1
RTL + t1 #2.3 A
Code generator Assembly code MOVF #2.3,r1
ADDF2 r1,r2
MOVF r2,A
Peephole optimizer Assembly code ADDF2 #2.3,r2
MOVF r2,A
 The Structure of a Compiler (2)

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
18
Target machine code
 The Structure of a Compiler (3)

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 ( Regular expression )
 (Used
NFA ( Non-deterministic by Automata
Finite all )
 DFA ( DeterministicPhases of
Finite Automata )
 LEX The Compiler) Code
Generator
19
Target machine code
 The Structure of a Compiler (4)

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 structureTables
is recognized, the parser
either calls corresponding semantic routines
(Used by all
directly or builds a syntax tree.
 CFG ( Context-Free Phases
Grammarof )
 BNF ( Backus-Naur The
Form Compiler)
) Code
 GAA ( Grammar Analysis Algorithms ) Generator
 LL, LR, SLR, LALR Parsers
20
 YACC
Target machine code
 The Structure of a Compiler (5)

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 Directed Translation
 Semantic Processing Techniques
(Used by all
 IR (Intermediate Representation)
Phases of
The Compiler) Code
Generator
21
Target machine code
 The Structure of a Compiler (6)

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
The Compiler)
 Register and Temporary Management Code
 Peephole Optimization Generator
22
Target machine code
 The Structure of a Compiler (7)

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

Code
Generator
23 Target machine code
 The Structure of a Compiler (8)
Intermediate Code Generator
[Intermediate Code Generator]

Non-optimized
Scanner
[Lexical Analyzer] Intermediate Code

Tokens

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

Code Generator
Semantic Process
[Semantic analyzer] Target machine code

Abstract Syntax Tree w/

Attributes

24
The Structure of a Compiler (9)
 Compiler writing tools
 Compiler generators or compiler-
compilers
E.g. scanner and parser

generators
Examples : Yacc, Lex

25
The Syntax and Semantics of
Programming Language (1)
 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

26
The Syntax and Semantics of
Programming Language (2)
 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

27
Compiler Design and Programming
Language Design (1)

 An interesting aspect is how programming

language design and compiler design
influence one another.

 Programming languages that are easy to

compile have many advantages

28
Compiler Design and Programming
Language Design(2)

 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?

29
Computer Architecture and Compiler
Design
 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
30
Compiler Design Considerations
 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.

31