List of Figures

Introduction

Figure 1: Standard deviation using higher-order functions

sd(xs) = sqrt(v) 
         where 
            n = length( xs )
            v = fold( plus, map(sqr, xs ))/n 
                - sqr( fold(plus, xs)/n)

**Figure 2:** Socrates is mortal
1a. `human(Socrates)`	Fact
1b. `human(Penelope)`	Fact
2. `mortal(X) if human(X)`	Rule
3. `¬mortal(Y)`	Assumption
4a. `X = Y`	from 2 & 3 by unification
4b. `¬human(Y)`	and modus tollens
5a. `Y = Socrates`	from 1 and 4 by unification
5b. `Y = Penelope`
6. Contradiction	5a, 4b, and 1a; 5b, 4b and 1b

**Figure 3:** State Sequence
S₀ -O₀-> S₁ - ... -> S_n-1 -O_n-1-> S_n

Syntax

Figure 2.1: G₀a grammar for a fragment of English

The grammatical categories are: S, NP, VP, D, N, V.
The words are: a, the, cat, mouse, ball, boy, girl, ran, bounced, caught.
The grammar rules are:
S  --> NP VP
NP --> N
NP --> D N
VP --> V
VP --> V NP
V  --> ran | bounced | caught
D  --> a | the
N  --> cat | mouse | ball | boy | girl
The most general category is S, a sentence.

Figure 2.2: G₁ An expression grammar

   N = { E } 
   T = { c, id, +, *, (, ) }
   P = {E --> c,
        E --> id,
        E --> (E),
        E --> E + E,
        E --> E * E }  
   S = E

Figure 2.3: G₂An abstract expression grammar

   N = { E } 
   T = { c, id, add, mult}
   P = {E --> c,
        E --> id,
        E --> add E E ,
        E --> mult E E }  
   S = E

Figure 2.4: Top-down Parse

PARSE TREE                 UNRECOGNIZED INPUT

     S                     the cat caught the mouse
    /\
   NP VP                   the cat caught the mouse
  / \  \
 D   N  \                  the cat caught the mouse
 |   |   \
the  |    \                cat caught the mouse
     |     \
    cat     \              caught the mouse
            /\
           V  NP           caught the mouse
           |   \
        caught  \          the mouse
                /\
               D  N        the mouse
               |  |
              the |        mouse
                  |
                mouse

Figure 2.5: Bottom-up Parse

PARSE TREE              UNRECOGNIZED INPUT

                        the cat caught the mouse
  
the                     cat caught the mouse
 |
 D                      cat caught the mouse
 |
 |  cat                 caught the mouse
 |   |
 |   N                  caught the mouse
 \  /
  NP                    caught the mouse
   |
   | caught             the mouse
   |   |
   |   V                the mouse
   |   | 
   |   | the            mouse
   |   |  |
   |   |  D             mouse
   |   |  |
   |   |  |  mouse
   |   |  |   |
   |   |  |   N
   |   |  \  /
   |   |   NP
   |   \  /
   |    VP
   \   /
     S

Figure 2.6 Top-down parse of id+id*id

STACK        INPUT          RULE/ACTION

   E]        id+id*id]     pop & push using E --> E+E
 E+E]        id+id*id]     pop & push using E --> id
id+E]        id+id*id]     pop & consume
  +E]          +id*id]     pop & consume
   E]           id*id]     pop & push using E --> E*E
 E*E]           id*id]     pop & push using E --> id
id*E]           id*id]     pop & consume
  *E]             *id]     pop & consume
   E]              id]     pop & push using E --> id
  id]              id]     pop & consume
    ]                ]     accept

Figure 2.7: Bottom-up parse of id+id*id

STACK    INPUT        RULE/ACTION

      ]  id+id*id]    Shift
    id]    +id*id]    Reduce using E --> id
     E]    +id*id]    Shift
    +E]     id*id]    Shift
  id+E]       *id]    Reduce using E --> id
   E+E]       *id]    Shift
  *E+E]        id]    Shift
id*E+E]          ]    Reduce using E --> id
 E*E+E]          ]    Reduce using E --> E*E
   E+E]          ]    Reduce using E --> E+E
     E]          ]    Accept

Figure 2.8: Context-free grammar for Simple

program ::= LET definitions IN command_sequence END

definitions ::= e | INTEGER id_seq IDENTIFIER .

id_seq ::= e | id_seq IDENTIFIER ,

command_sequence ::= e | command_sequence command ;

command := SKIP 
        |  READ IDENTIFIER
        |  WRITE exp
        |  IDENTIFIER := exp
        |  IF exp THEN command_sequence ELSE command_sequence FI 
        |  WHILE bool_exp DO command_sequence END 

exp ::=  exp + term | exp - term  | term
term :: term * factor | term / factor | factor 
factor ::= factor^primary  | primary 
primary ::=  NUMBER | IDENT | ( exp ) 
bool_exp ::=  exp = exp | exp < exp | exp > exp

Semantics

Figure N.1: Algebraic Definition of Peano Arithmetic

Domains:

Bool = {true, false} (Boolean values)
N in Nat (the natural numbers)
N ::= 0 | S(N)

Semantic functions:

= : (Nat, Nat) -> Bool
+ : (Nat, Nat) -> Nat
× : (Nat, Nat) -> Nat

Semantic axioms and equations:

not S(N) = 0
if S(M) = S(N) then M = N
( n + 0 ) = n
( m + S(n) ) = S( m + n )
( n × 0 ) = 0
( m × S(n)) = (( m × n) + m)

where m,n in Nat

Figure N.2: Algebraic definition of an Integer Stack ADT

Domains:

Nat (the natural numbers
Stack ( of natural numbers)
Bool (boolean values)

Semantic functions:

newStack: () -> Stack
push : (Nat, Stack) -> Stack
pop: Stack -> Stack
top: Stack -> Nat
empty : Stack -> Bool

Semantic axioms:

pop(push(N,S)) = S
top(push(N,S)) = N
empty(push(N,S)) = false
empty(newStack()) = true

Errors:

pop(newStack())
top(newStack()) where N in Nat and S in Stack.

Figure N.3: Program to compute S = sum_i=1ⁿA[i]
S,I := 0,0
while I < n do
   S,I := S+A[I+1],I+1
end

Figure N.4: Verification of S = sum_i=1ⁿA[i]

Pre/Post-conditions

Code

1.

{ 0 = Sum_i=1⁰A[i], 0 < |A| = n }

2.

S,I := 0,0

3.

{S = Sum_i=1^IA[i], I <= n }

4.

while I < n do

5.

{S = Sum_i=1^IA[i], I < n }

6.

{S+A[I+1] = Sum_i=1^I+1A[i], I+1 <= n }

7.

S,I := S+A[I+1],I+1

8.

{ S = Sum_i=1^IA[i], I <= n }

9.

end

10.

{S = Sum_i=1^IA[i], I <= n, I >= n }

11.

{S = Sum_i=1ⁿA[i] }

	Pre/Post-conditions	Code
1.	{ 0 = Sum_i=1⁰`A[i]`, 0 < \|A\| = n }
2.		`S,I := 0,0`
3.	{`S` = Sum_i=1^IA[i], I <= n }
4.		`while I < n do`
5.	{`S` = Sum_i=1^IA[i], I < n }
6.	{`S+A[I+1]` = Sum_i=1^I+1A[i], I+1 <= n }
7.		`S,I := S+A[I+1],I+1`
8.	{ S = Sum_i=1^IA[i], I <= n }
9.		`end`
10.	{`S` = Sum_i=1^IA[i], I <= n, I >= n }
11.	{`S` = Sum_i=1ⁿA[i] }

Figure N.5: Recursive version of summation

S,I := 0,0
loop: if I < n then S,I := S+A[I+1],I+1; loop
      else skip fi

Figure N.6: Denotational definition of Peano Arithmetic

Abstract Syntax:

N in Nat (the Natural Numbers)
N ::= 0 | S(N) | (N + N) | (N × N)

Semantic Algebra:

Nat (the natural numbers (0, 1, ...)
+ : Nat -> Nat -> Nat

Valuation Function:

D : Nat -> Nat

D[( n + 0 )] = D[n]
D[( m + S(n) )] = D[(m+n)] + 1
D[( n × 0 )] = 0
D[( m × S(n))] = D[ (( m × n) + m) ]

where m,n in Nat

**Figure N.6:** Denotational definition of Peano Arithmetic
Abstract Syntax: N in Nat (the Natural Numbers) N ::= 0 \| S(N) \| (N + N) \| (N × N) Semantic Algebra: *Nat* (the natural numbers (0, 1, ...) + : *Nat* -> *Nat* -> *Nat* Valuation Function: D : Nat -> Nat D[( n + 0 )] = D[n] D[( m + S(n) )] = D[(m+n)] + 1 D[( n × 0 )] = 0 D[( m × S(n))] = D[ (( m × n) + m) ] where m,n in Nat

**Figure N.7:** Denotational semantics for Simple
Abstract Syntax: C in Command E in Expression O in Operator N in Numeral V in Variable C ::= V := E \| `if` E then C1 else C2 end \| while E do C3 end \| C1;C2 \| skip E ::= V \| N \| E1 O E2 \| (E) O ::= + \| - \| * \| / \| = \| < \| > \| <> Semantic Algebra: Domains: tau in T = {true, false}; the boolean values zeta in Z = {...-1,0,1,...}; the integers + : Z -> Z -> Z ... = : Z -> Z -> T ... sigma in S = Variable -> Numeral; the state Valuation Functions: C in C -> (S -> S) E in E -> E -> (N union T) C[ skip ] sigma = sigma C[ V := E ] sigma = sigma [ V:E[ E ] sigma C[ C1; C2 ] = C[ C2 ] · C[ C1] C[ if E then C1 else C2 end ] sigma = C[ C₁ ] sigma if E[ E ]sigma = true = C[ C₂ ] sigma if E[ E ]sigma = false C[ while E do C end}]sigma = lim_{n -> infty} C[ (if E then C else skip end)ⁿ ] sigma E[ V ] sigma = sigma(V) E[ N ] = zeta E[ E₁+E₂ ] = E[ E ] sigma + E[ E ] sigma ... E[ E₁=E₂ ] sigma = E[ E ] sigma = E[ E ] sigma

Abstract Syntax:

C in Command
E in Expression
O in Operator
N in Numeral
V in Variable

C ::= V := E | if E then C1 else C2 end |
      while E do C3 end | C1;C2 | skip
E ::= V | N | E1 O  E2  | (E)
O ::= + | - | * | / | = | < | > | <>

Semantic Algebra:
Domains:

tau in  T = {true, false}; the  boolean values
zeta in  Z = {...-1,0,1,...}; the integers
+ : Z -> Z -> Z
...
= : Z -> Z -> T
...
sigma in  S = Variable -> Numeral; the state

Valuation Functions:

C in C -> (S -> S)
E in E -> E -> (N union T)

C[ skip ] sigma = sigma
C[ V := E ] sigma = sigma [ V:E[ E ] sigma
C[ C1; C2 ] = C[ C2 ] · C[ C1]
C[ if E then C1 else C2 end ] sigma
          = C[ C₁ ] sigma  if E[ E ]sigma = true
          = C[ C₂ ] sigma  if E[ E ]sigma = false
C[ while E do C end}]sigma
          = lim_{n -> infty} C[ (if E then C else skip end)ⁿ ] sigma
E[ V ] sigma = sigma(V)
E[ N ] = zeta
E[ E₁+E₂ ] = E[ E ] sigma + E[ E ] sigma
...
E[ E₁=E₂ ] sigma = E[ E ] sigma = E[ E ] sigma

Figure N.8: Operational semantics for Peano arithmetic

Abstract Syntax:

N in Nat (the natural numbers)

N ::= 0 | S(N) | (N + N) | (N × N)

Interpreter:

I: N -> N

I[ ( n + 0 ) ]         ==> n
I[ ( m + S(n) ) ]  ==> S( I[ (m+n ) ] )
I[ ( n × 0 ) ]         ==> 0
I[ ( m × S(n)) ]   ==>  I[ (( m × n) + m) ]


where m,n in Nat

Figure N.9: Operational semantics for Simple

Interpreter:

I: C × Sigma -> Sigma
{nu} in E × Sigma} -> T union Z

Semantic Equations:

I(skip,sigma) = sigma
I(V := E,sigma) = sigma[V:nu(E,sigma)]
I(C₁ ;C₂,sigma) = E(C₂,E(C₁,sigma))
I(if E then C₁ else C₂ end,sigma) = I(C₁,sigma)&if nu(E,sigma) = true}
                                                   I(C₂,sigma)&if nu(E,sigma) = false}
while E do C end = if E then (C;while E do C end) else skip
nu(V,sigma) = sigma(V)
nu(N,sigma) = N
nu(E₁+E₂,sigma) = nu(E₁,sigma) + nu(E₂,sigma)
...
nu(E₁=E₂,sigma) = true if nu(E,sigma) = nu(E,sigma)}
             false if nu(E,sigma) != nu(E,sigma)}
otherwise
...

Translation

Figure N.1: Traditional Compiler Structure

Source code
(in source language)
|
\/

Symbol Tables

Analysis
(front-end)

Scanner

Parser

Semantic
checker

Intermediate
code generator

Error Handler

Optimizer

Code Generator

Peep hole
Optimizer

Synthesis
(back-end)

|
\/
Target code
(in target language)

Figure N.2: Context-free grammar for Simple

program ::= definitions in command_sequence

definitions ::= e | variable

command_sequence ::= e | command_sequence command ;

command := SKIP 
        |  READ variable
        |  WRITE exp
        |  IDENT := exp
        |  IF bool_exp THEN command_sequence ELSE command_sequence FI 
        |  WHILE bool_exp DO command_sequence END 

exp ::=  exp + term | exp - term  | term
term :: term * factor | term / factor | factor 
factor ::= factor^primary  | primary 
primary ::=  INT | IDENT | ( exp ) 
bool_exp ::=  exp = exp | exp < exp | exp > exp

Figure N.3: Grammar Transformation Rules

Convert the grammar to EBNF

Remove left-recursion: replace N ::= E | NF with N ::= E(F)*

Left-factor the grammar: replace N ::= EFG | EF'G with N ::= E(F|F')G

If N ::= E is not recursive, remove it and replace all occurrences of N in the grammar with E

Figure N.2: First[E] and Follow[N]

First[e] = empty set

First[t] = {t} t is a terminal

First[N] = First[E] where N ::= E

First[E F] = First[E] union First[F] if E generates lambda

= First[E] otherwise

First[E|F] = First[E] union First[F]

First[E*] = First[E]

Follow[N] = {t} in context Nt, t is terminal

= First[F] in context NF, F is non-terminal

Figure N.3: EBNF to Parsing Procedures
For each grammar rule N::=E, construct a parsing procedure
parseN {
    parse E
}
Refine parse E

If parse E is: then refine to:

parse lambda skip

parse t accept(t) where t is a terminal

parse N parseN where N is a non-terminal

parse E F parse E; parse F

parse E|F if currentToken.class in First[E] then parse E else if currentToken.class in First[F] then parse F else report a syntactic error

parse E* while currentToken.class in First[E] do parse E

If parse E is:	then refine to:
parse lambda	`skip`
parse t	`accept(t)` where t is a terminal
parse N	`parseN` where N is a non-terminal
parse E F	parse E; parse F
parse E\|F	`if currentToken.class in First[E] then parse E else if currentToken.class in First[F] then parse F else report a syntactic error`
parse E*	`while currentToken.class in First[E] do parse E`

Figure N.M: RE to EBNF

Each regular expression RE_i defining a token class T_i is put into the EBNF form: T_i ::= RE_i.

A regular expression Sep is constructed defining the symbols which sparate tokens.

The EBNF production S ::= Sep*(T₀|...|T_n) is added to the grammar.

Figure N.3: EBNF to Scanning Procedures

For each grammar rule T_i::=E_i, construct a scanning procedure scanT_i {scan E_i}.

Refine scan E_i

scan E_i Refinement

scan lambda skip

scan ch takeIt(t) where ch is a character

scan N scanN where N is a non-terminal

scan E F scan E; scan F

scan E|F if currentChar in First[E] then scan E else if currentChar in First[F] then scan F else report a syntactic error

scan E* while currentChar in First[E] do scan E

scan E_i	Refinement
scan lambda	`skip`
scan ch	takeIt(t) where ch is a character
scan N	`scanN` where N is a non-terminal
scan E F	scan E; scan F
scan E\|F	`if currentChar in First[E] then scan E else if currentChar in First[F] then scan F else report a syntactic error`
scan E*	`while currentChar in First[E] do scan E`

Figure : An attribute grammar for declarations

P ::= D(SymbolTable) B(SymbolTable)
D(SymbolTable)  ::= ...V( insert( V in SymbolTable)...
   
B(SymbolTable) ::= C(SymbolTable)... 
C(SymbolTable) ::= V := E(SymbolTable, Error(if V not in SymbolTable)
                   | ...

Data Types

Figure M.N: Record implementation

Field₁

...

Field_n

Figure M.N: Object implementation

Instance data Shared methods Code

methods

data field₁

...

date field_m

-->

method₁

...

method_n

-->

Figure M.N: Implementation of inheritance

Object supertype Shared methods Code

methods

fields

-->

methods

-->

Object subtype

methods

shared fields

new fields

-->

shared methods

new methods

-->

Run-time environments

Figure M.N: Simple's Virtual Machine and Runtime Environment

CPU

Memory

Code Segment

Data Segment

Figure M.N: Virtual Machine 2

Instruction Counter

Code Segment₁

...

Code Segment_n

Data Segment

Return Address Stack

Figure M.N: Virtual Machine 3

Instruction Counter

Code Segment₁

...

Code Segment_n

Data Segment₁

...

Data Segment_n

Return Address Stack

Figure M.N: Monolithic Block Structure

Global Data

Return Address₁

...

Return Address_n

Figure M.N: Activation Record

Static Link Return Address Dynamic Link

Local Data

Figure M.N: Display and Runtime Stack

Display

Stack

Figure M.N: Runtime Stack

Main

0 0 0

Local data for M

A

SL RA DL

Local data for A

B

SL RA DL

Local data for B

Main calls A which calls B.

Figure M.N: Heap Implmentation

Free

Figure M.N: Pascal Virtual Machine

IC

AR

T

F

Code Segments

Run-time Stack

Heap

Every sequential program residing on a computer typically comes in four parts (Figure M.N):

Figure M.N: A sequential program in the computer

code the procedures, statements, and expressions of the program, translated into machine language by a compiler or assembler.

global data the top-level (static) variables of the program

heap data a pool of storage used by the NEW function when allocating new dynamic variables

stack a storage area used to hold all local variables, procedure parameters, and bookkeeping information during execution

Program Counter

Static pointer

Heap Manager

Stack Manager

Code

Global data

Heap

Stack

The program counter keeps track of the location of the next instruction in memory. The stack manager allocates and deallocates stack memory. The heap manager allocates and deallocates heap memory. Code is often kept in read-only memory, because it is never changed during execution. The size of the static area is determined when the program is linked by adding up the sizes of the static data areas in each module. The heap starts out as an area of unused storage; each time additional memory is requested, a piece is allocated to the program. Either a garbage collector or the program may return storage for future use. The stack starts out as unused, but every time a prodedure is called a chunk of stroage at the top of the stack is reserved to hold the procedure's parameters and local variables. Every time a procedure returns, the storage it used on the stack is returned.

Figure M.N: A multithreaded program in the computer

Thread₁ ... Thread_n Shared memory

Code pointer

Static pointer

Heap access

Stack manager

Local stack

...

Code pointer

Static pointer

Heap access

Stack manager

Local stack

Code

Static and shared data

Heap

Abstraction and Generalization

Author: A. Aaby

First[e]	=	empty set
First[t]	=	{t}	t is a terminal
First[N]	=	First[E]	where N ::= E
First[E F]	=	First[E] union First[F]	if E generates lambda
	=	First[E]	otherwise
First[E\|F]	=	First[E] union First[F]
First[E*]	=	First[E]
Follow[N]	=	{t}	in context Nt, t is terminal
	=	First[F]	in context NF, F is non-terminal

code	the procedures, statements, and expressions of the program, translated into machine language by a compiler or assembler.
global data	the top-level (static) variables of the program
heap data	a pool of storage used by the `NEW` function when allocating new dynamic variables
stack	a storage area used to hold all local variables, procedure parameters, and bookkeeping information during execution