i219 Software Design Methodology
13. Case study 2
Mini programming language processor 1
Kazuhiro Ogata (JAIST)

2

Outline of lecture• Minila• Syntax of Minila• Front end of Minila processor• Minila interpreter

3

Minila (1)• A mini programming language• An imperative programming language• Its processor consists of– An interpreter– A virtual machine– A compiler (code generator)

4

Minila (2)A program in Minila that computes 216:
x := 2;x := x*x;
x := x*x;
x := x*x;
x := x*x;

5Minila (3)A program in Minila that computes the 10th factorial:
x := 1;n := 1;
while (n = 10 || n < 10) do
x := x*n;n := n+1;
od

6Minila (4)A program in Minila that computes the greatest common
divisor of 19110 & 17850 with the Euclid’s algorithm:
x := 19110;
y := 17850;
while y != 0 do
tmp := x%y;
x := y;y := tmp;od7

Minila (5)A program in Minila that computes the positive integral
part of the square root of 20000 with binary search:
v0 := 20000; v1 := 0; v2 := v0;
while v1 != v2 doif (v2 – v1)%2 = 0
then v3 := v1+(v2 – v1)/2;
else v3 := v1+(v2 – v1)/2+1; fi
if v3*v3 > v0
then v2 := v3 – 1;
else v1 := v3; fi
od8

Syntax of Minila (1)P ::= S
S ::= ε| var ':=' E ';'| 'if' E 'then' S 'else' S 'fi'
| 'while' E 'do' S 'od'
| S S

(Program)(empty statement)(assign statement)(if statement)(while statement)(sequential composition)

where var is a variable, E is an expression, and S is a statement.

9

Syntax of Minila (2)E ::= num | '–' num | var | '–' var| '(' E ')' | '–' '(' E ')'| E '*' E | E '/' E | E '%' E| E '+' E | E '–' E| E '<' E | E '>' E | E '=' E | E '!=' E| E '&&' E | E '||' E
num ::= [0-9]+
var ::= [a-zA-Z][0-9a-zA-Z]*

10

Syntax of Minila (3)The precedence of the operators is as follows:(unary) '–''*', '/', '%''+', (bynary) '–''<', '>', '=', '!=''&&', '||'

strongest

weakestEvery operator is left‐associative, e.g. 3–2–1 is parsed as((3–2) –1).

11

Front end of Minila processor (1)Feeding a program in Minila (a source code) into theMinila processor, the source code is stored as an object ofclass SourceCode.
sc refers to a source codethat is a string

The object makes a list of tokens from sc by receiving themessage scan().

12

Front end of Minila processor (2)A list of tokens is represented as an object of classTokenList.
idx refers to the token
that is processed next; 0ththrough idx–1st tokens in
the token list have beenprocessed

The object makes a parse tree from the list of tokens if theinput program obeys the Minila syntax; displays a syntax
error message otherwise.

13

Front end of Minila processor (3)A parse tree is represented as an object of one of concreteclasses that extends the abstract class StmParseTree.

14

Front end of Minila processor (4)15Front end of Minila processor (5)x := 1; n := 1;
while (n = 10 || n < 10) do
x := x*n; n := n+1;
od
lexical analysis[var: x, :=, num=1, ;, var: n, :=, num=1, ;, while, (, var: n,=, num=10, ||, var: n, <, num=10, ), do, var: x, :=, var: x,*, var: n, ;, var: n, :=, var: n, +, num=1, ;, od]

16

Front end of Minila processor (6)The object of TokenList looks like:17

Front end of Minila processor (7)[var: x, :=, num=1, ;, var: n, :=, num=1, ;, while, (, var: n,=, num=10, ||, var: n, <, num=10, ), do, var: x, :=, var: x,*, var: n, ;, var: n, :=, var: n, +, num=1, ;, od]parsing

scomp(assign(x,1),
scomp(assign(n,1),
while(or(eq(n,10),lt(n,10)),
scomp(assign(x,mul(x,n)),assign(n,add(n,1))))))

18

Front end of Minila processor (8)The object diagram of the parse tree:

19

Minila interpreter (1)When an object of EmptyParseTree receives interpret(env),
it just returns env.

20

Minila interpreter (2)When an object of AssignParseTree receives interpret(env),
1. it sends interpret(env) to exp and obtains the result val,
2. modifies env such that val is associated with the nameof var, making a new environment env', and3. returns env'.

21

Minila interpreter (3)x := x–1;
env1

env2

<"x",2><"x",1>

 When anAssign receives interpret(env1), it sends interpret(env1) to aSub,
gets 1 and modifies env1 to get env2; it then returns env2.

22

Minila interpreter (4)When an object of IfParseTree receives interpret(env),
1. it sends interpret(env) to exp and obtains the result val,and
2. if val is not 0, it sends interpret(env) to stm1, obtains a
new environment env' and returns env';
3. if val is 0, it sends interpret(env) to stm2, obtains a newenvironment env' and returns env'.

23

Minila interpreter (5)env1<"x",2>

if x > 0then x := x–1;
else fi

env2

env3

<"x",1><"x",0> When anIf receives interpret(env1), it sends interpret(env1) to aGt and gets
1; This is why it sends interpret(env1) to anAssign and gets env2; it thenreturns env2.
 When anIf receives interpret(env3), it sends interpret(env3) to aGt and gets0; This is why it sends interpret(env3) to anEmp and gets env3; it then returns
env3.

24

Minila interpreter (6)When an object of WhileParseTree receives interpret(env),
1. it sends interpret(env) to exp and obtains the result val,and
2. if val is 0, it returns env;
3. if val is not 0, it sends interpret(env) to stm, obtains a
new environment env', sends interpret(env') to theobject itself, obtains another new environment env'',
and returns env''.

25

Minila interpreter (7)while x != 0
do x := x–1; odenv1

env2

env3

<"x",2><"x",1><"x",0> When aWhile receives interpret(env1), it sends interpret(env1) to anNeq
and gets 1; This is why it sends interpret(env1) to anAssign and gets env2; itthen sends interpret(env2) to itself and gets env3; it finally returns env3.
 When aWhile receives interpret(env2), it sends interpret(env2) to anNeq
and gets 1; This is why it sends interpret(env2) to anAssign and gets env3; itthen sends interpret(env3) to itself and gets env3; it finally returns env3.
 When aWhile receives interpret(env3), it sends interpret(env3) to anNeq
and gets 0; This is why it returns env3.

26

Minila interpreter (8)When an object of SCompParseTree receives interpret(env),
1. it sends interpret(env) to stm1 and obtains a newenvironment env',
2. sends interpret(env') to stm2 and obtains another new
environment env'',3. returns env''.

27Summary• Minila• Syntax of Minila• Front end of Minila processor• Minila interpreter