Lecture# 01

Compiler Construction

Topics
• Compilation, Objectives, Course Learning Outcomes, Compiler Introduction, Classification
of Compilers, Model of Compilation, Phases of Compiler, Language-Processing System, The
Analysis Task for Compilation
Compilation

2
2
 Objectives
• Main objective of the course is to teach the students the
basic techniques that underlie the practice of Compiler
Construction.
• It will be introduced the theory and tools to perform
syntax-directed translation of a high-level programming
language into an executable code.
• The students will be trained for multiple applications
including verification and program analysis.
• In addition, the course will provide deeper insights into
the more advanced semantics aspects of the
programming languages.
3
3
 Course Learning Outcomes
At the end of the course the students will be able to:
• Understand the basic techniques used in compiler
construction such as lexical analysis, top-down, bottom-
up parsing, context-sensitive analysis, and intermediate
code generation.
• Understand the basic data structures used in compiler
construction such as abstract syntax trees, symbol tables,
three-address code, and stack machines.
• Design and implement a compiler using a software
engineering approach.
• Use generators (e.g. Lex and Yacc).

4
4
 Introduction to Compilers
• As a Discipline, Involves Multiple CS&E Areas
– Programming Languages and Algorithms
– Theory of Computing & Software Engineering
– Computer Architecture & Operating Systems
– Data structures and Algorithms
• Has Deceivingly Simplistic Intent:

Source Target
Compiler Program
program

Error messages

Diverse & Varied

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 5
5
 Introduction to Compilers
• All 6 phases of Compiler are:
– Lexical/Sequential/Linear Analysis or Scanning
– Syntax/Hierarchical Analysis or Parsing
– Semantic Analysis
– Intermediate Code Generation
– Code Optimization
– Target/Final Code Generation
Source Target
Compiler Program
program

Error messages

Diverse & Varied

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 6
6
 Classification of Compilers
• Compilers Viewed from Many Perspectives

Single Pass
Multiple Pass Construction

Load & Go

Debugging
Functional
Optimizing

7
7
 Classification of Compilers
• Single pass compiler passes each compilation unit
only
once translating each part immediately into its final
machine code
• Multi-pass compiler processes the source code or
abstract syntax tree of a program several times
• Load & Go produces absolute code that is executed
immediately upon compilation or object code. Load & Go
compiler uses a number of passes to translate the source
program into absolute code
• Debugger helps to identify errors. Debuggers are required
as run time errors do not give very helpful information.
8
8
 The Model
• The TWO Fundamental Parts:

Analysis: Decompose Source into an

intermediate representation

Synthesis: Target program generation

from representation

• We Will Discuss Both in This Class, and FOCUS will be on

analysis part of the compiler.

9
9
 Important Notes
• Today: There are many Software Tools for helping with the
Analysis Part. This Wasn’t the Case in Early Days. (some) analysis
is also important in:
– Structure / Syntax directed editors:
Force “syntactically” correct code to be
entered
• Takes input as a sequence of commands to
build a source
program.
• Performs
:
– Text-
creatio
n
11
– Text 00
 Important Notes (Continue…)
• Pretty Printers: Standardized version for program structure (i.e., blank
space, indenting, etc.)
– Analyzes the source program and prints it in such a way that the
structure of the program becomes clearly visible.
– Examples
• Comments may appear in a special font
• Statements may appear with an amount of indentations proportional
to the depth of their nesting in a hierarchical organization of the
stmts.
• Static Checkers: A “quick” compilation to detect rudimentary errors
– Examples
• Detects parts of the program that can never be executed
• A variable used before it is defined
• Interpreters: “real” time execution of code a “line-at-a-time”
11
11
 Important Notes (Continue…)
• Compilation Is Not Limited to Programming Language Applications

– Text Formatters
• LATEX & TROFF Are Languages Whose Commands
Format Text ( paragraphs, figures, mathematical structures etc.)

– Silicon Compilers
• Textual / Graphical: Take Input (Similar to programming Language) and
Generate Circuit Design
– Database Query Processors
• Database Query Languages Are Also a Programming Language
• Input is compiled Into a Set of Operations for Accessing the Database
or information systems
• Examples:
– SQL: is a well-known query language;

– YQL: is an SQL like query language created by yahoo 12

The Many Phases of a Compiler
Source Program

1
Lexical Analyzer

2
Syntax Analyzer

3
Semantic Analyzer
Symbol-table Error Handler
Manager 4 Intermediate
Code Generator

5
Code Optimizer

6
Code Generator

Target
Program
11
33
 Language-Processing System
Skeleton Source Program

1
Pre-Processor
Source program
2
Compiler
Target Assembly
program 3
Assembler

4 Relocatable
Machine Code

5 Library,
Loader
relocatable
Link/Editor
object
files
Executable

11
44
 The Analysis Task for Compilation
• Three Phases:
– Linear / Lexical Analysis:
• L-to-R Scan to Identify Tokens
token: sequence of chars having a collective meaning
– Hierarchical Analysis:
• Grouping of Tokens Into Meaningful Collection
– Semantic Analysis:
• Checking to ensure Correctness of Components

11
55
The End

16