Lecture #3
Programming Languages MISHRA 95
if a then p if a then p else q if a then if b then p else qConcrete syntax tells us which
then
the else
-part
matches to.
---Slide 2---
Meta-Languages for Concrete Syntax
---Slide 3---
Backus-Naur Formalisms
a
, b
, 1
, 2
, +
, *
,
or
, div
,
<expression>
, <term>
, <literal>
,
LHS ::= RHS <expression> ::= <term> | <expression> <addop> <term> <term> ::= <factor> | <term> <multop> <factor>
---Slide 4---
Example: Grammar for Expression
<expression> ::= <term> | <expression> <addop> <term> <term> ::= <factor> | <term> <multop> <factor> <factor> ::= <identifier> | <literal> | <expression> <identifier> ::= a | b | c | ... | z <literal> ::= 1 | 2 | 3 | ... | 9 <addop> ::= + | - | or <multop> ::= * | / | div | mod | and
---Slide 5---
Phrase Structure
<multop>
than
<addop>
.
a + b*c a*b + c <expression><addop><term>
<multop>
and <addop>
associate to the left.
a / b / c a - b - c <term><multop><factor> <expression><addop><term>
---Slide 6---
Extended BNF
...|...
= choice, (...)
= grouping{...}
= repetition (zero or more)[...]
= optional construct
<expression> ::= <term> {<addop> <term>} <term> ::= <factor> {<multop> <factor>} <factor> ::= <identifier> | <literal> | <expression> <identifier> ::= a | b | c | ... | z <literal> ::= 1 | 2 | 3 | ... | 9 <addop> ::= + | - | or <multop> ::= * | / | div | mod | and
---Slide 7---
Syntax Charts
---Slide 8---
Syntax Charts (contd)
---Slide 9---
Formal Semantics
---Slide 10---
Example: Binary Numerals
N ::= 0 | 1 | N0 | N1
---Slide 11---
Semantic Domains
;
---Slide 12---
Hierarchy of Languages
---Slide 13---
Classes of Language
---Slide 14---
Imperative Language: Assignment
X := X + 1; (* Pascal *) X := .X + 1; (* BLISS *) X := !X + 1; (* ML *)
X
in LHS is the L-value of X
and
X
in RHS is the R-value of X
.
X
refers to the L-value and .X
, the
R-value. BLISS allows arithmetic on L-values (pointer
arithmetic). .
is an explicit dereferencing
operator in BLISS.
X
refers to the L-value and !X
, the R-value.
!
is an explicit dereferencing operator in ML.
---Slide 15---
L-values
C++
:
int a[10]; int& f(int i){return (a[i]);} f(5) = 17;
f
is an L-valued function
EQUIVALENCE
construct.
---Slide 16---
Variations on Assignment
L +:= E; (* ALGOL 68 *) L += E; /* C */
L
contains the sum of R-values of L
and
E
. R-value of L
is obtained from a single evaluation of
its L-value.
L1 := L2 := ... := Ln := E; (* ALOGOL 60 *)
L1
, L2
, Ln
, and the R-value of E
are evaluated. Then all the
L-values are updated.
---Slide 17---
Variations on Assignment (contd)
L1, L2, ..., Ln := E1, E2, ..., En; (* ALOGOL 60 *)
L1
, L2
, Ln
, and then all the R-values of E1
, E2
,
En
are evaluated. Then all the L-values are updated,
while maintaining positional correspondence.
L := E (* ALOGOL 68 *) L = E /* C */
L
. The expression
updates L
as a side effect.
if((n += a) > 0) n--; /* C */ a = b = c = d = e; /* C, = is right-associative */
---Slide 18---
Pointer
E
whose R-value is an L-valued expression
(or a special value null
).
Its L-value is a location giving access to a storage
indirectly. The L-value of E^
is an anonymous variable
which can be updated as any other L-valued expression
E^ := E^ + 1;
In some languages, allocated locations are subsequently disposed of explicitly by the user. In others, inaccessible locations are automatically searched for and disposed--- garbage collection.
new(p); p := nil;
---Slide 19---
Storage Insecurities
Extent (lifetime) of the location ended before all ways of accessing the location have ended.
var p, q: ^integer; var p: ^integer; begin procedure q; new(p); var i: integer; q := p; begin dispose(p) p := ADDR(i) end; end;
---Slide 20---
Binding
The later the binding, the more flexible is the language.
---Slide 21---
Referential Transparency
function succ(x:integer):integer; begin succ := x + 1; end; function succ(y:integer):integer; begin succ := y + 1; end;
---Slide 22---
Types
---Fewer programming errors
---Better compiled code.
---Slide 23---
Type Insecurities & Coercion
var (* PASCAL *) wide:1..100; narrow:10..20; farout:150..300; begin narrow:=farout; wide:=narrow; narrow:=wide end;
var (* PASCAL *) x: real; i: integer; x := i;
---Slide 24---
Type Equivalence
declare type BLACK is INTEGER; type WHITE is INTEGER; B:BLACK; W:WHITE; I:INTEGER; begin W := 5; B := W; I := B; end;
---Last Slide---
Type Equivalence (Contd)
--Ada type T1 is record type T2 is record X:INTEGER; X:INTEGER; N:access T1 N:access T2 end record; end record; type T3 is record type T4 is record X:INTEGER; X:INTEGER; N:access T2 N:access record end record; X: INTEGER; N: access T4 end record; end record;
[End of Lecture #3]