1. SIMP - Syntax

Informal semantics can be imprecise, which can lead to different compilers generating different code. For example, take the C expression f(i++, --i), the order of execution of i++ and --i (the parameters of functions) is not specified in the definition of the C language.

One approach to give a precise, formal description is in terms of an abstract machine, which is a transition system which specifies an interpreter for the programming language.

Abstract Syntax

Programs

$$P::=C|E|B$$

Commands

$$C::=skip|I:=E|C;C|\text{ if }B\text{ then }C\text{ else }C|\text{ while }B\text{ do }C$$

Integer Expressions

$$E::=!I|n|E\text{ op }E$$ $$\text{op }::=+|-|\ast |/$$

• where $n\in \mathbb{Z}$ (integers)
• where $I\in L=\{l_0,l_1,\dots \}$ (locations or variables) $!I$ denotes the value stored in $I$

Boolean Expressions

$$B::=\text{True}|\text{False}|E\text{ bop }E|\neg B|B\wedge B$$ $$\text{bop}::=>|<|=$$

Tree Representation

Consider if 5 > 0 then skip else (skip; I := 0):

Example Problems

Swap the contents of the variables $x$ and $y$:

z := !x; x := !y; y := !z

Assuming variable $I$ contains a natural number $n$, compute factorial of $n$:

factorial := 1;
while !I > 0 do
	(factorial := !factorial * !I;
	 I := !I - 1)