i219 Software Design Methodology
9. Dynamic modeling 2
Kazuhiro Ogata (JAIST)

2

Outline of lecture• Another simple calculator• Use case, state diagram & class diagram of simplecalculator• Simple calculator in Java
• State diagram of virtual machine• Virtual machine in Java
• Class diagram, object diagram & sequence
diagram of parse tree
• Parse tree in Java
• Parsing expression

3

Another simple calculator
Let us design another simple calculator:
 it uses a virtual machine that has a set of commands(instructions),
 it generates a list of such commands (instructions) from aparse tree, and it calculates an expression in string by first converting it intoa list of tokens (tl), making a parse tree (pt) from tl, generating
a list of commands (cl) from pt, and making the virtualmachine execute cl.

4

Use case of simple calculator (1)In Expression in String

CompileMain Success Scenario:
1. User inputs an exp in string,making sc (source code)
available
2. System converts it into a token
list tl
3. System makes a parse tree pt
from tl

Main Success Scenario:
1. User inputs command compile
2. System generates a command(instruction) list cl from pt
3. System makes vm that has cl

Extensions:
3a: There is a syntax error.1: System lets user know it,
and makes pt and vm (virtualmachine) unavailable;

Extensions:
2a: pt is unavailable.1: System lets user know it5

Use case of simple calculator (2)Run

Show SC (Source Code)Main Success Scenario:
1. User inputs command run
2. System executes vm
3. System displays the result

Main Success Scenario:
1. User asks system to display sc
2. System displays scExtensions:
2a: vm is unavailable.1: System lets user know it
2b: runtime error such as “divisionby zero” occurs.1: System lets user know itShow PT (Parse Tree)
Main Success Scenario:
1. User asks system to display pt
2. System displays pt
Show CL (Command List)
Main Success Scenario:
1. User asks system to display cl
2. System displays cl in vm

6

State diagram of simple calculator“Show CL” use case“Show PT” use case“Show SC” use case

“In Expression in String”
use case“Run” use case“Compile” use case

7

Class diagram of simple calculator
Because every instance ofbecause sc may be null
SourceCode is not owned by someinstance of SimpleCalculator

three attributes sc, ept & vm are expressed as associations
note that ExpParseTree is an abstract class, and then an object to which ept refers isof a (concrete) class (such as AddParseTree) that extends ExpParseTree8

Simple calculator in Java (1)public class SimpleCalculator {private SourceCode sc;
private ExpParseTree ept;
private VirtualMachine vm;
public SimpleCalculator() { sc = null; ept = null; vm = null; }public void in(String expInStr) {…}public void compile() {…}explained later
public void run() {…}public void showSourceCode() {…}similar to the body of
public void showParseTree() {…}showCodeList
public void showCodeList() {if (vm == null) { System.err.println("No compiled!"); }else { System.out.println(vm.getComList()); } }}9Simple calculator in Java (2)public void in(String expInStr) {a token list tl is madesc = new SourceCode(expInStr);by lexically analyzing sc
TokenList tl = sc.scan();a parse tree ept istry {made by parsing tl; aept = tl.parse();
SyntaxErrorExceptionvm = null;
may be thrown
System.out.println("Successfully loaded.");} catch (SyntaxErrorException e) {ept = null;
vm = null;
System.err.println(e.getMessage());}
a SyntexErrorException is caught;}
a syntax error message is displayed
and the control goes back to thecaller

10

Simple calculator in Java (3)a list cl of commands
public void compile() {(instructions) is generated
if (ept == null) {System.err.println("No program loaded!"); from a parse tree ept} else {List<Command> cl = ept.genCode();vm = new VirtualMachine(cl);System.out.println("Successfully compiled.");}a virtual machine vm is made}of the command list cl

11

Simple calculator in Java (4)public void run() {if (vm == null) {vm is set to the program counter
System.err.println("No compiled!");0 and the empty stack stk} else {try {Stack<Integer> stk = new Stack<Integer>();vm.reset(0,stk);vm is executed; a VMException
int x = vm.run();may be thrown
System.out.println(x);} catch (VMException e) {a VMException is caught
System.err.println(e.getMessage());
}
}
}

12

State diagram of virtual machine (1)superstate
substate13

State diagram of virtual machine (2)14State diagram of virtual machine (3)15Virtual machine in Java (1)public class VirtualMachine {private List<Command> comList; private int pc; private Stack<Integer> stk;
public VirtualMachine(List<Command> cl) { comList = cl; }public void reset(int pc, Stack<Integer> stk) { this.pc = pc; this.stk = stk; }public List<Command> getComList() { return comList; }public int run() throws VMException { …
while (true) {If pc is out of bounds, aVMException is thrown
if (pc < 0 || pc >= comList.size()) {throw new VMException(pc,comList.size()); }com = comList.get(pc);switch (com.getName()) {what will be done depends on the command…
(instruction) in comList at pc
default:
throw new IllegalStateException("pc1: " + pc + "cl1: " + comList); }} } }this can be used at runtime to check if all cases are covered

16

Virtual machine in Java (2)case PUSH: stk.push(com.getNum()); pc++; break;case MUL: if (stk.size() < 2) { throw new VMException(stk); }x2 = stk.top(); stk.pop(); x1 = stk.top(); stk.pop();x = x1 * x2; stk.push(x); pc++; break;case QUO: if (stk.size() < 2) { throw new VMException(stk); }x2 = stk.top(); stk.pop(); x1 = stk.top(); stk.pop();if (x2 == 0) { throw new VMException(); }x = x1 / x2; stk.push(x); pc++; break;…
case QUIT: if (stk.size() != 1) { throw new VMException(stk,stk.size()); }x = stk.top(); stk.pop(); return x;

17Class diagram of parse tree

18

Object diagram of parse tree
1. “3+4*5” is converted into the token list [NUM{num=3},
PLUS, NUM{num=4}, MUL, NUM{num=5}].
2. The parse tree represented by the following object
diagram is made by sending parse() to the token list:

3. A list of commands (instructions) is generated by sendinggenCode() to the parse tree.

19

Sequence diagram of parse tree

20

Parse tree in Java (1)abstract method
public abstract class ExpParseTree {public abstract List<Command> compile();a list of commands
public List<Command> genCode() {(instructions) is generated by
List<Command> cl;sending compile() to thiscl = this.compile();cl.add(new Command(CommandName.QUIT));
command (instruction) QUIT is put into thereturn cl; } }list of commands (instructions) at the end

public class NumParseTree extends ExpParseTree {private int val;
PUSH{num=val} is generated
public NumParseTree(int x) { val = x; }public List<Command> compile() {List<Command> cl = new ArrayList<Command>();cl.add(new Command(CommandName.PUSH,val));return cl; } }21Parse tree in Java (2)public class AddParseTree extends ExpParseTree {private ExpParseTree ept1, ept2;
public AddParseTree(ExpParseTree e1, ExpParseTree e2) {ept1 = e1; ept2 = e2; }public List<Command> compile() {List<Command> cl;
cl = ept1.compile();cl.addAll(ept2.compile());
cl.add(new Command(CommandName.ADD));
return cl;}}
a command list like the following is generated:command list for ept1 command list for ept2 ADD

22Parsing expression (1)The grammar for expressions is as follows:

high*,/
precedence
E ::= num | ( E ) | E * E | E / E | E + E | E – E+,–num ::= [0-9]+
every operator is left associativelow

It is not straightforward, however, to make a parser that directly
deals with this grammar, and then the grammar is modified asfollows:This grammar (LL(1)) can be dealt with by
F ::= num | ( E2 )a predictive parser (a recursive descent
E1 ::= F E11
E11 ::= ε | * F E11 | / F E11
parser that needs no backtracking) that
E2 ::= E1 E22
can be straightforwardly implemented.
E22 ::= ε | + E1 E22 | – E1 E22 A parser is implemented in classE ::= E2
TokenList.

23Parsing expression (2)public class TokenList extends ArrayList<Token> { private int idx;
public TokenList() { idx = 0; } … }public ExpParseTree parse() throws SyntaxErrorException { return E(); }F ::= num | ( E2 )private ExpParseTree F() throws SyntaxErrorException { …
if (idx == size()) { throw new SyntaxErrorException(…); }switch (t1.getName()) {case NUM: return new NumParseTree(t1.getNum());
case LPAR: e = E2();
if (idx == size()) { throw new SyntaxErrorException(…); }t2 = get(idx++);if (t2.getName() != TokenName.RPAR) { … /* syntax error */ }return e;
default: … /* syntax error */ } }24Parsing expression (3)E1 ::= F E11
private ExpParseTree E1() throws SyntaxErrorException {ExpParseTree e = F(); return E11(e); }E11 ::= ε | * F E11 | / F E11
private ExpParseTree E11(ExpParseTree e) throws SyntaxErrorException {… if (idx == size()) { return e; }t1 = get(idx++);switch (t1.getName()) {case MUL: e1 = F(); e2 = new MulParseTree(e,e1); return E11(e2);case QUO: e1 = F(); e2 = new QuoParseTree(e,e1); return E11(e2);default: idx--; return e; } }25Parsing expression (4)E2 ::= E1 E22
private ExpParseTree E2() throws SyntaxErrorException {ExpParseTree e = E1(); return E22(e); }E22 ::= ε | + E1 E22 | – E1 E22
private ExpParseTree E22(ExpParseTree e) throws SyntaxErrorException {… if (idx == size()) { return e; }t1 = get(idx++);switch (t1.getName()) {case PLUS: e1 = E1(); e2 = new AddParseTree(e,e1); return E22(e2);case MINUS: e1 = E1(); e2 = new SubParseTree(e,e1); return E22(e2);default: idx--; return e; } }26Parsing expression (5)E ::= E2
private ExpParseTree E() throws SyntaxErrorException {ExpParseTree ept = E2();
if (idx != size()) {throw new SyntaxErrorException("One exp in one line!"+ "; something following one exp!");}return ept;}

if two or more expressions are written in one line suchas “3+4 5*5”, then a SyntaxErrorException is thrown27Summary• Another simple calculator• Use case, state diagram & class diagram of simple
calculator• Simple calculator in Java
• State diagram of virtual machine• Virtual machine in Java
• Class diagram, object diagram & sequence
diagram of parse tree
• Parse tree in Java
• Parsing expression