Transcript Chapter 1 Introduction

INTRODUCTION
Languages and Compilers
Outline
2
Programming
languages
• Syntax
• Semantics
Paradigms in
programming
languages
•
•
•
•
Language
processors
Imperative languages
Object-oriented languages
Logic programs
Functional programs
• Compilers
• Linkers
• Loaders
2301380 Chapter 1 Introduction
05/04/60
Programming Languages
3
Syntax
• Define the form or structure of the
language
• Use context-free grammar
Semantics
• Define the meanings of the
language.
• For programmers and language
processors.
• For checking program correctness
Pragmatics
• Usage
2301380 Chapter 1 Introduction
05/04/60
Syntax
4


Describe correct forms of language constructs.
In English, a sentence is composed of the subject part
and the verb part, as shown below.
sentence
Subject
part

predicate
In a programming language, the syntax describes what
a program, a statement, an expression, etc. are
composed of.
2301380 Chapter 1 Introduction
05/04/60
Semantics
5

Operational semantics
 Describe
the meaning of a program by telling how a
computer executes the program.
 Based on the model of computers.

Axiomatic semantics
 Describe
the meaning of a program by telling the
“condition” before and after the execution of the program.
 Conditions are expressed in predicates or assertions.

Denotational semantics
 Meaning
of a program is a function from a language
construct to a value.
2301380 Chapter 1 Introduction
05/04/60
Operational Semantics
6


Describe the meaning by the sequence of operations
executing for programs.
Example: A=B+C;
move r1, mem[addr B] add r3, r1, r2
move r2, mem[addr C] load mem[addr A], r3



Operations are based on some machine.
Good for programmers to understand programs.
Difficult to define in detail, due to machine
dependency.
2301380 Chapter 1 Introduction
05/04/60
Axiomatic Semantics
7


Pre-post form: {P} statement {Q}
An example: a = b + 1 {a > 1}
One possible precondition: {b > 10}
Weakest precondition:
{b > 0}
An axiom for assignment statements (x = E):
{QxE} x = E {Q}
Example: {y*y-9>0} x=y*y-9 {x>0}
{y>3 or y<-3} x=y*y-9 {x>0}

2301380 Chapter 1 Introduction
05/04/60
Axiomatic Semantics
8
Inference rule:
{P} S {Q} and P’=> P and Q => Q’
Then, {P’} S {Q’}.
Example:
Let {y > 3 or y < -3} x=y*y-9 {x > 0}.
Then, {y < -3} x=y*y-9 {x> -9} (because y < -3 implies
y>3 or y < -3 and x> 0 implies x>-9).

2301380 Chapter 1 Introduction
05/04/60
Axiomatic Semantics
9

An inference rule for sequences
For a sequence S1;S2:
{P1} S1 {P2}
{P2} S2 {P3}
the inference rule is:
2301380 Chapter 1 Introduction
05/04/60
Axiomatic Semantics
10

An inference rule for logical pretest loops
For the loop construct:
{P} while B do S end {Q}
the inference rule is:
where I is the loop invariant (the inductive
hypothesis)
2301380 Chapter 1 Introduction
05/04/60
Characteristics of the loop invariant
11
Loop invariant I must meet the following conditions:
 P => I
(the loop invariant must be true initially)
 {I} B {I}
Evaluation of Boolean must not change the validity of I
 {I and B} S {I}
I is not changed by executing the body of the loop
 (I and (not B)) => Q
If I is true and B is false, Q is implied.
 The loop terminates
(this can be difficult to prove)
2301380 Chapter 1 Introduction
05/04/60
Denotational Semantics
12



The state of a program is the values of all its current
variables
s = {<i1, v1>, <i2, v2>, …, <in, vn>}
Let VARMAP be a function that, when given a
variable name and a state, returns the current value of
the variable
VARMAP(ij, s) = vj
The meaning of a program is a function mapping the
program construct to the state of the program.
2301380 Chapter 1 Introduction
05/04/60
Denotational Semantics
13
<dec_num>  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| <dec_num> (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)
Mdec('0') = 0,
Mdec ('1') = 1, …,
Mdec ('9') = 9
Mdec (<dec_num> '0') = 10 * Mdec (<dec_num>)
Mdec (<dec_num> '1’) = 10 * Mdec (<dec_num>) + 1
…
Mdec (<dec_num> '9') = 10 * Mdec (<dec_num>) + 9
2301380 Chapter 1 Introduction
05/04/60
Denotational Semantics
14
Me(<expr>, s) :
case <expr> of
<dec_num> => Mdec(<dec_num>, s)
<var> => if VARMAP(<var>, s) == undef
then error
else VARMAP(<var>, s)
<binary_expr> => if (Me(<binary>.<left_expr>, s)==undef OR
Me(<binary_expr>.<right_expr>, s)==undef)
then error
else if (<binary_expr>.<operator> == ‘+’)
then Me(<binary_expr>.<left_expr>, s) +
Me(<binary_expr>.<right_expr>, s)
else Me(<binary_expr>.<left_expr>, s) *
Me(<binary_expr>.<right_expr>, s)
...
2301380 Chapter 1 Introduction
05/04/60
Paradigms in Programming languages
15
Imperative languages
Object-oriented languages
Logic programs
Functional programs
2301380 Chapter 1 Introduction
05/04/60
Imperative Languages
16


Programs specify steps of what to do.
Major concepts are
 Variables
 Control

flows
Examples:
 FORTRAN
 Pascal
C
2301380 Chapter 1 Introduction
05/04/60
Object-oriented Languages
17

Major concepts are
 Objects
 Control

flows
Objects have
 Attributes
 Methods
 Inheritance
2301380 Chapter 1 Introduction
05/04/60
Logic Programs
18


Programs are definitions of what “things” are.
Running the program is to infer from the definitions
what the answer are.
2301380 Chapter 1 Introduction
05/04/60
Example of Logic Programs
19
sort([],[]).
sort(A,B) :- half(A,X,Y), sort(X,M), sort(Y,N), merge(M,N,B).
half([],[],[]).
half([A], [A],[]).
half([A,B|R], [A|R1], [B|R2]) :- half(R, R1, R2).
merge(A, [], A).
merge([], A, A).
merge([X|A], [Y|B], [X|Z]) :- X<Y, merge(A, [Y|B], Z).
merge([X|A], [Y|B], [Y|Z]) :- X>=Y, merge([X|A], B, Z).
2301380 Chapter 1 Introduction
05/04/60
Functional Languages
20






A program is a collection of mathematical functions.
A function is a composition of functions.
The execution of a program is the application of a
function (mostly) on some data.
Functions produce results which are used by other
functions.
There is no variable in pure functional languages.
No side effect.
2301380 Chapter 1 Introduction
05/04/60
Functional Languages
21



Functions are a basic data type.
Functions can be passed as parameters.
Examples:
 LISP:
a functional language with list as a basic data type
 Scheme: a variation of LISP
 ML
 Haskell
2301380 Chapter 1 Introduction
05/04/60
Example of Functional Program
22
sort [] = []
sort (h : t) = sort [b | b<-t, b<=h]
++ h
++ sort[b | b <-t, b>h].
2301380 Chapter 1 Introduction
05/04/60
Language Processors
23
Preprocesser
Find macros or directives and add parts of code
for the directives.
Compiler
Translate high-level language programs into
object code.
Linker
Combine object codes and resolve address
reference. But this code is not tied to real address.
Loader
Find real address.
2301380 Chapter 1 Introduction
05/04/60
Phases of Compilers
24
Error handler
Symbol & literal tables
Scanner
Parser
Semantic
analyzer
Intermediate
code
generator
2301380 Chapter 1 Introduction
Code
generator
05/04/60
Code
optimizer
Compiler Process
25
Source
code
Sequence
of tokens
Parse
tree
Annotated
tree
2301380 Chapter 1 Introduction
Intermediate
code
05/04/60
Target
code