Chapter 1 Introduction

Prof Chung.

1
 Outlines
 1.1 History of Compilation
 1.2 What Compilers Do
 1.3 Interpreters
 1.4 Syntax and Semantics
 1.5 Organization of Compiler
 1.6 Programming Language and Compiler Design
 1.7 Computer Architecture and Compiler Design
 1.8 Compiler Design Considerations

2
History of Compilation (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
History of Compilation (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
What 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)

5
What 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

6
What 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

7
Interpreters (1)

Interpreter Output

Source Program Input

Encoding Data

 Machine-independent
 Significant overhead

8
Syntax and Semantics (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

9
Syntax and Semantics (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

10
The Organization 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

11
 The Organization of a Compiler (2)

Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Stream) Structure Routines

Intermediate
Representation

Symbol and Optimizer

Attribute
Tables

(Used by all Phases of The Compiler)

Code
Generator
12
Target machine code
 The Organization of a Compiler (3)

Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Stream) Structure Routines

Intermediate
Scanner Representation

 The scanner begins the analysis of the source program by

reading the input, character by character, and grouping
Symbol and Optimizer
characters into individual words and symbols (tokens)
Attribute
Tables
 RE ( Regular expression )
 NFA ( Non-deterministic Finite Automata )
 (Used by) all
DFA ( Deterministic Finite Automata
 LEX Phases of
The Compiler) Code
Generator
13
Target machine code
 The Organization of a Compiler (4)

Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Stream) Structure Routines

Intermediate
Parser Representation

 Given a formal syntax specification (typically as a context-free

grammar [CFG] ), the parse reads tokens and groups them into
Symbol and Optimizer
units as specified by the productions of the CFG being used.
Attribute
 As syntactic structure is recognized, the parser either calls
Tables
corresponding semantic routines directly or builds a syntax
tree.
(Used
 CFG ( Context-Free Grammar ) by all
 BNF ( Backus-Naur Form ) Phases of
 GAA ( Grammar Analysis Algorithms )
The Compiler) Code
 LL, LR, SLR, LALR Parsers Generator
 YACC
14
Target machine code
 The Organization of a Compiler (5)

Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Stream) Structure Routines

Intermediate
Semantic Routines Representation
 Perform two functions
 Check the static semantics of each construct
Symbol and
 Do the actual translation Optimizer
 The heart of a compilerAttribute
Tables
 Syntax Directed Translation
 Semantic Processing Techniques
(Used
by all
 IR (Intermediate Representation)
Phases of
The Compiler) Code
Generator
15
Target machine code
 The Organization of a Compiler (6)

Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Stream) Structure Routines

Intermediate
Optimizer Representation

 The IR code generated by the semantic routines is analyzed and

transformed into functionally equivalent but improved IR code
Symbol and Optimizer
 This phase can be very complex and slow
Attribute
 Peephole optimization
Tables
 loop optimization, register allocation, code scheduling
(Used by all
 Register and Temporary Management
 Peephole Optimization Phases of
The Compiler) Code
Generator
16
Target machine code
 The Organization of a Compiler (7)

Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Stream) Structure Routines

Intermediate
Code Generator Representation
 Interpretive Code Generation
 Generating Code from Tree/Dag
 Grammar-Based Code Generator
Optimizer

Code
Generator
17 Target machine code
 The Organization of a Compiler(8)
Code Generator
[Intermediate Code Generator]

Non-optimized Intermediate Code

Scanner
[Lexical Analyzer]

Tokens

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

Code Optimizer
Semantic Process
[Semantic analyzer] Target machine code

Abstract Syntax Tree w/ Attributes

18
The Organization of a Compiler(9)
 Compiler writing tools
 Compiler generators or compiler-compilers
E.g. scanner and parser generators
Example : Yacc, Lex

19
Programming Language and Compiler Design(1)

 An interesting aspect is how programming language

design and compiler design influence one another.

 Programming languages that are easy to compiler have

many advantages

20
Programming Language and Compiler 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?

21
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

22
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.

23