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

2

Outline of lecture• Minila virtual machine• Minila compiler

3

Minila virtual machine (1)An object of VirtualMachine uses
a program counter pc, a stack stk
and an environment env to exeute
a list comList of instructions (orcommands), which is done by run.
 reset sets this.pc, this.stk and this.env to the 1st argument
pc, the 2nd argument stk and the 3rd argument env.
 getComList returns comList.
 toString returns "pc: " + pc + ", stack: " + stk + ", env: " +env + ", cl: " + comList.

4

Minila virtual machine (2)The set of instructions (or commands):

5

Minila virtual machine (3)If comList.get(pc) isn

pc++
stk

stk

6

Minila virtual machine (4)If comList.get(pc) isn<"x",n><"x",n>

env

stk

env

pc++
stk

If nothings has been associated with "x" in env, null is returned as
the result of env.get("x"). If so, an exception (VMException) isthrown.

7

Minila virtual machine (5)If comList.get(pc) isn<"x",m>

env

pc++

<"x",n>

stk

env

stk

If stk is empty, an exception (VMException) is thrown.

8

Minila virtual machine (6)If comList.get(pc) isn–1 * n

pc++
stk

stk

If stk is empty, an exception (VMException) is thrown.

If comList.get(pc) isn2
n1

n1*n2

pc++
stk

stk

If stk does not contain two or more numbers, an exception(VMException) is thrown.

9

Minila virtual machine (7)If comList.get(pc) isn2
n1

n1/n2

pc++
stkstkn2
n1n1%n2

If stk does not contain two or more numbers, or n2 is zero, then anexception (VMException) is thrown.

If comList.get(pc) ispc++
stk

stk

If stk does not contain two or more numbers, or n2 is zero, then anexception (VMException) is thrown.

10

Minila virtual machine (8)If comList.get(pc) isn2
n1n1+n2pc++
stk

stk

n2
n1

n1–n2

If stk does not contain two or more numbers, an exception(VMException) is thrown.

If comList.get(pc) ispc++
stkstk

If stk does not contain two or more numbers, an exception(VMException) is thrown.

11

Minila virtual machine (9)If comList.get(pc) isn2
n1

m = 1 if n1 < n2m = 0 otherwise
mpc++
stk

stk

n2n1

m = 1 if n1 > n2m = 0 otherwisem

If stk does not contain two or more numbers, an exception(VMException) is thrown.

If comList.get(pc) ispc++
stk

stk

If stk does not contain two or more numbers, an exception(VMException) is thrown.

12

Minila virtual machine (10)
If comList.get(pc) isn2n1m = 1 if n1 = n2m = 0 otherwise
mpc++
stkstkn2n1m = 1 if n1 ≠ n2m = 0 otherwisem

If stk does not contain two or more numbers, an exception(VMException) is thrown.

If comList.get(pc) ispc++
stk

stk

If stk does not contain two or more numbers, an exception(VMException) is thrown.

13

Minila virtual machine (11)
If comList.get(pc) ism = 1 if n1 ≠ 0 ∧ n2 ≠ 0m = 0 otherwise
mn2n1

pc++
stk

stk

If stk does not contain two or more numbers, an exception(VMException) is thrown.

If comList.get(pc) ism = 1 if n1 ≠ 0 ∨ n2 ≠ 0m = 0 otherwise
mn2n1pc++
stkstk

If stk does not contain two or more numbers, an exception(VMException) is thrown.

14

Minila virtual machine (12)If comList.get(pc) is

If comList.get(pc) ispc ← pc+npc ← pc+n if c ≠ 0pc ← pc+1 otherwisec

If stk is empty, an exception(VMException) is thrown.

If comList.get(pc) isstk
env is returnedstk

15

Minila compiler (1)When an object of EmptyParseTree receives compile(), itmakes an object of ArrayList<Command> (the empty list ofcommands) and returns the object.

16

Minila compiler (2)cmd

Where “x” is the name of var

When an object of AssignParseTree receives compile(),1. it sends compile() to exp and obtains the list cl ofcommands for exp,
2. adds cmd to cl at the end, and3. returns cl.
the list cl of commands for exp

cmd

17

Minila compiler (3)
cmd1

cmd2

cmd3

where size2 is the size of cl2 &size3 is the size of cl3

When an object of IfParseTree receives compile(),1. it sends compile() to exp, stm1 & stm2 to obtain the lists
cl1, cl2 & cl3 of commands,
2. adds cmd1 & cmd2 to cl1 at the end in this order,
3. appends cl2 to cl1 at the end,
4. adds cmd3 to cl1 at the end,
5. appends cl3 to cl1 at the end, and6. returns cl1.

18

Minila compiler (4)
cmd1

cmd2

cmd3

where size2 is the size of cl2 &size3 is the size of cl3

When an object of IfParseTree receives compile(),the list cl1 of commands for exp

cmd1 cmd2

if the top of stk is not zero

the list cl2 of commands for stm1 cmd3
the list cl3 of commands for stm2

19

Minila compiler (5)
cmd1

cmd2

cmd3

where size1 is the size of cl1, size2 is the size of cl2& m is –1*(size1+size2+2)

When an object of WhileParseTree receives compile(),1. it sends compile() to exp & stm to obtain the lists cl1 &cl2 of commands,
2. adds cmd1 & cmd2 to cl1 at the end in this order,
3. appends cl2 to cl1 at the end,
4. adds cmd3 to cl1 at the end, and
5. returns cl1.

20

Minila compiler (6)
cmd1

cmd2

cmd3

where size1 is the size of cl1, size2 is the size of cl2& m is –1*(size1+size2+2)

When an object of WhileParseTree receives compile(),the list cl1 of commands for exp

cmd1 cmd2

if the top of stk is not zero

the list cl2 of commands for stm

cmd3

21

Minila compiler (7)When an object of SCompParseTree receives compile(),1. it sends compile() to stm1 & stm2 to obtain the lists cl1& cl2 of commands,
2. appends cl2 to cl1 at the end, and3. returns cl1.
the list cl1 of commands for stm1 the list cl2 of commands for stm2

22

Minila compiler (8)cmd

When a parse tree object of a Minila program p receives
genCode(),1. it sends compile() to itself to obtain the list cl ofcommands,
2. adds cmd to cl at the end, and3. returns cl.
the list cl of commands for p

cmd

23

Minila compiler (9)x := 1; n := 1;
while (n = 10 || n < 10) do
x := x*n; n := n+1;
od
lexical analysis & 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))))))
compilation[push(1), store(x), push(1), store(n),load(n), push(10), eq, load(n), push(10), lt, or,cjmp(2), jmp(10),load(x), load(n), mul, store(x),load(n), push(1), add, store(n),jmp(-17), quit]

24

Summary• Minila virtual machine• Minila compiler