IT3323E

COMPILER CONSTRUCTION

1
Why study compiler construction? (1)

1. understand what is going on inside the tools that you use.

2. the theoretical and practical knowledge that is needed to
implement a programming language, know the
characteristics of many programming languages.
3. design and implement your own domain-specific language.
4. a gentle introduction to formal methods that are used for
general purpose software design.

2
Why study compiler construction? (2)

5. A large variety of applications can be modelled after a

compiler (or some part thereof). Simulators, debuggers,
program analysis tools, editors, IDEs, RDBMSs
6. complicate techniques in text processing
7. optimization techniques
8. working with really big data structures and complex
interactions between algorithms

Help you out on your next big

programming project.

3
More details about the course

• How do computers work?

(instruction set, registers, addressing modes, run-time data

structures, ...)

• How do compilers work?

• What machine code is generated for certain language

constructs?

• What is good language design?

4
Course Outline

• Functions of a language processor

• The phases of a compiler

• Generative grammar

• BNF and syntax diagrams

• Scanner

• Top down parsing with Backtracking

• Predictive parsing

• LL(k) grammars

5
Course Outline

• Recursive Descent Parsing

• The Parser of KPL

• Semantic Analysis

• Stack calculator

• Intermediate Code Generation

• Object Code Generation

• Code optimization

6
Textbooks

• Aho.A.V, Sethi.R., Lam M., Ullman.J.D.

Compiler : Principles, Techniques and Tools.
Addison Wesley. 2007.
Vietnamese translation (1986 edition)
Trình biên dịch: Nguyên lý, Kỹ thuật và Công cụ
Nhà xuất bản Thống kê, 2000

7
Text books

• Andrew.W.Appel
Modern Compiler Implementation in Java
Princeton University.1998
• Bal.H. E.
Modern Compiler Design.
John Wiley & Sons Inc (2000)
• William Allan Wulf.
The Design of an Optimizing Compiler
Elsevier Science Ltd (1980)
• Charles N. Fischer.
Crafting a Compiler
Benjamin-Cummings Pub Co (1987)

8
Course Grade Components

Approximate percentage of grade

Midterm (Practice) 50

Final exam (Quiz) 50

Reward points  1: evaluation in labs.

9
Unit 1.
Functions of
a Language Processor

10
High Level Programming Languages

• Programming languages have taken 5 generation

• A language is considered high or low level depending on its

abstraction

A high level language may use natural language elements,

be easier to use, or more portable across platforms

Low level languages are closer to the hardware

11
The first and the second generation

• The first generation: machine language

• The second generation : Assembly

• Languages of the first and the second generation are low

level languages

12
The Third Generation

• Easier to read, write and maintain

• Allow declarations
• Most 3GLs supports structured programming
• Examples: Fortran, Cobol, C, C++, Basic . . . .

13
The Fourth Generation

• Designed with a specific purpose in mind, such as the

development of commercial business software
• Reduce programming effort, cost of software development
• May include form or report builder
• Examples :SQL, Visual Basic, Oracle (SQL plus, Oracle Form,
Oracle Report). . . .

14
The Fifth Generation

• Based around solving problems using constraints given to the

program, rather than using an algorithm written by a
programmer
• Are designed to make the computer solve a given problem
without the programmer
• Most constraint-based and logic programming languages and
some declarative languages are fifth-generation languages.

15
Characteristics of high-level languages

• Hardware independence
• Close to natural languages
• Easy to read, write and maintain
• Programs written in a high-level language must be translated
into machine language
• Often result in slower execution speed, higher memory
consumption

16
Syntax and Semantics of Programming Languages

• Syntax:The way symbols can be combined to create well-

formed sentence (program) in the language
• Semantics: The meaning of syntactically valid strings in a
language

17
Language Processors

• A program that performs tasks, such as translating and

interpreting, required for processing a specified programming
language.For example,

• Compiler

• Assembler

• Interpreter

• Compiler - Compiler

18
Compilers and Interpreters

• A Compiler is a program that translates code of a programming language into

machine code (assembly)

 An interpreter translates some form of source code into a target representation that
it can immediately execute and evaluate

 Modification of Interpreter :a program that implements or simulates a virtual machine using the
base set of instructions of a programming language as its machine language

19
Language Translation

• A compiler or an interpreter is a computer program (or set of

programs) that converts program written in high-level
language into machine code understood by the computer
• Native-code compiler: produces machine code
• Compiled languages: Pascal, C, C++, …
• Interpreter: translates into internal form and immediately
executes
• Interpreted languages: Javascript, PHP, Haskell…
• Hybrid approaches: VB.net, Python, Java

20
Language Compilation

• Compiler: program that translates a source language into a

target language
• Target language is often, but not always, the assembly language for a
particular machine

C
source code C ASM Assembler/ op codes
compiler Interpreter

21
Compilers

• Scans the entire program and translates it as a whole into

machine code.
• Takes large amount of time to analyze the source code but
the overall execution time is comparatively faster.
• Generates the error message only after scanning the whole
program.
Input

Source Target
Compiler
Program Program

Error messages Output

22
C translator: compiler

23
Compilers (cont’d)

• The most common reason for wanting to transform source

code is to create an executable program.
• To run a program, execute the compiler (and possibly an
assembler) to translate the source program into a machine
language program.
• Execute the resulting machine language program, supplying
appropriate input.

24
Checks During Compilation

• Syntactically invalid constructs

• Invalid type conversions

• A value is used in the “wrong” context, e.g., assigning a float to an int

• Static determination of type information is also used to

generate more efficient code
• Know what kind of values will be stored in a given memory region
during program execution

• Some programmer logic errors (not all compilers)

• Can be subtle: if (a = b) … instead of if (a == b) …

slide 25
 Compilation Process

Syntax and static

type errors

Lexical tokens Syntax ASTs Intermediate IC ICopt Final code

analyzer + Optimizer gen
analyzer code gen
type checker
raw source ASM
code text

Assembler/
Preprocessor Interpreter

Source code with Machine code

preprocessor directives

26
Phases of Compilation
• Preprocessing: conditional macro text substitution
• Lexical analysis: convert keywords, identifiers, constants into a
sequence of tokens
• Syntactic analysis: check that token sequence is syntactically
correct
• Semantic Analysis: Generate abstract syntax trees (AST), check
types
• Intermediate code generation: “walk” the ASTs (or Parse Trees) and
generate intermediate code
• Apply optimizations to produce efficient code
• Target code generation: produce Assembly code

slide 27
Interpreters
• Translates program one statement at a time
• Takes less amount of time to analyze the source code but the overall
execution time is slower.
• Continues translating the program until the first error is met, in which
case it stops.
• Oversimplified view:

Source
Program Interpreter Output

Input
Error messages
• Accepts the source language program and the appropriate input
• Itself produces the output of the program.

28
Language Interpretation
• Parse the source code and perform its behaviour directly
• Translate source code into some efficient intermediate representation
of object code and immediately execute that
• Explicitly execute stored precompiled bytecode made by a compiler
and matched with the interpreter virtual machine.
• Read-eval-print loop (REPL)
• Read in an expression, translate into internal form
• Evaluate internal form
• This requires an abstract machine and a “run-time” component (usually a compiled
program that runs on the native machine)
input
• Print the result of evaluation expression REPL result
• Loop back to read the next expression interpreter

Interpreter
runtime

slide 29
Console of javascript

• JavaScript is an interpreted language

• It has no compilation step.
• An interpreter in the browser reads over the JavaScript code, interprets each
line, and runs it.
• The function console.log prints
“Hello world” to the console.

30
Write a program (.js file) with Kdevelop

31
Bytecode Compilation

• Combine compilation with interpretation

• Idea: remove inefficiencies of read-eval-print loop
• Bytecodes are conceptually similar to real machine opcodes,
but they represent compiled instructions to a virtual machine
instead of a real machine
• Source code statically compiled into a set of bytecodes
• Bytecode interpreter implements the virtual machine

Bytecode Bytecode
source compiler bytecodes interpreter result
program

Virtual machine
runtime

32
Python translator: hybrid solution

Python editor window

33
Python translator: hybrid solution

Python shell window

34
Pros and cons of compiled and interpreted languages

35
Interpreter as a part of compiler

• In a compiler implementations
• The source code is compiled to a machine language for an
idealized virtual machine
• The interpreter of accepts the codes and the input, produces
the output.
• This technique is quite popular to make the compiler
independent with the computer (portability of the compiler)

36
Cousins of the compiler

• Interpreter
• Assembler
• Linker
• Loader
• Preprocessor
• Editor
• Debugger
• Profiler

37
The context of a compiler in a language processor

Skeletal Source Program

Preprocessor
Source Program
Compiler
Target Assembly Program
Assembler/Interpreter
Relocatable Object Code
Linker+Loader Libraries and
Relocatable Object Files
Absolute Machine Code
38