Lecture 1: Introduction
What is this course about?
Source Code Compiler Target Code
What is this course about?
• How are programs written in a high-level language translated into
machine code?
• How can we ensure a program is somewhat meaningful?
• How is the program’s memory managed?
• How programming languages are designed?
• Why there are so many different kinds of programming languages?
Why study compilers?
Textbooks and Resources
1. Compliers Principles technique and Tools (Second Edition)
Alfred [Link], Ravi Sethi, Jeffrey [Link]
2. Trình biên dịch
Phan Thị Tươi
3. Introduction to Programming Languages/Grammars
4. Write your own compiler
5. The lox language
Compiler vs Interpreter
Structure of a compiler
Lexical Analysis
Parsing
Semantic Analysis
Optimization
Code Generation
Lexical Analysis
• First steps: recognize words
- Smallest unit above letters
This is a sentence
ist his asen tence
Lexical Analysis
• Lexical analysis devides program text into “words” or “tokens”
if num1 == num2 then result = 1; else result = 2;
Keywords: if, then, else
Variable names: num1, num2, result
Constants: 1, 2
Operators: double equals, assignment
Other tokens: semi colons, the punctuation, the separators (blank)
How do we know that is double equals, not two individual equals signs?
How do we know that we want this? A double equal, not two single euqals?
Parsing
• Once words are understood, the next step is to understand sentence
structure.
• Parsing = Diagramming Sentences
• The diagram is a tree
Parsing
This line is a longer sentence.
article noun verb article adjective noun
subject object
sentence
Parsing
if num1 == num2 then result = 1; else result = 2;
num1 == num2 result = 1 result = 2
relation assignment assignment
predicate then-statement else-statement
if-then-else
Semantic Analysis
• Once sentence structure is understood, we can try to understand
“meaning”.
• Compilers perform limited semantic analysis to catch inconsistencies.
Semantic Analysis
Tom said Jerry left his key at home.
Tom said Tom left his key at home?
Semantic Analysis
• Programming languages define {
strict rules to avoid such int Tom= 20;
ambiguities
{
int Tom= 50;
cout << age;
}
}
Semantic Analysis
• Compilers perform many semantic checks besides variable bindings
• Example: Tom left her homework at home.
• A ‘type mismatch’ between Tom and her, we know they are different
people.
Optimization
• Automatically modify programs so that they
• Run faster
• Use less memory
• Reduce the amount of power
• Reduce the number of network messages
• Reduce the number of database accesses.
Optimization
A = B * 0 is the same as A = 0
Code Generation
• Produces assembl code (usually)
• A translation into another language (analogous to human translation)
Semantic Code
Lexical Analysis Parsing Optimization
Analysis Generation
Lexical Code
Parsing Semantic Analysis Optimization
Analysis Gen
• Why are there so many programming languages?
• Why are there new programming languages?
• What is a good programming language?
Why are there so many programming languages?
Application domains have distinctive
Scientific computing
- need good floating point support,
- need good for arrays and operations on arrays
- need parallelism
Business applications
- need persistence
- report generation
- data analysis
Systems programming
- control of resources
- real time constraints
Why are there new programming languages?
What is a good programming language?
There is no universally accepted metric for language design.