Created
March 25, 2015 18:00
-
-
Save unnikked/2c91bd9ca0bcceae7088 to your computer and use it in GitHub Desktop.
Stack Based Virtual Machine. It uses RPN syntax.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.IOException; | |
| import java.nio.charset.StandardCharsets; | |
| import java.nio.file.Files; | |
| import java.nio.file.Paths; | |
| import java.util.HashMap; | |
| import java.util.List; | |
| import java.util.Scanner; | |
| import java.util.Stack; | |
| /** | |
| * | |
| */ | |
| public class RPN { | |
| private Stack<Integer> stack = new Stack<Integer>(); | |
| private class StackFrame { | |
| public int ip; | |
| public HashMap<String, Integer> variables; | |
| public StackFrame(int ip, HashMap<String, Integer> variables) { | |
| this.ip = ip; | |
| this.variables = variables; | |
| } | |
| } | |
| private Stack<StackFrame> calls = new Stack<StackFrame>(); // call stack | |
| private HashMap<String, Integer> labels = new HashMap<String, Integer>(); | |
| private HashMap<String, Integer> variables = new HashMap<String, Integer>(); | |
| private String program; | |
| public RPN(String file) throws IOException { | |
| List<String> lines = Files.readAllLines(Paths.get(file), StandardCharsets.UTF_8); // http://stackoverflow.com/a/14169729/4004293 | |
| StringBuilder sb = new StringBuilder(); | |
| for (String line : lines) { | |
| line = line.replaceAll("^\\s*#.*$", ""); | |
| if (line.length() > 0 && line.charAt(line.length() - 1) != ' ') { | |
| sb.append(line.trim()).append(' '); | |
| } else if (line.length() > 0){ | |
| sb.append(line.trim()).append(' '); | |
| } | |
| } | |
| program = sb.toString(); | |
| System.out.println(program); | |
| } | |
| public void eval() { | |
| String[] tokens = program.split("\\s(\\s)*"); | |
| int ip = 0, f, s; | |
| String token; | |
| while (ip < tokens.length) { | |
| token = tokens[ip]; | |
| if (token.matches("^label\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| labels.put(label, ip); | |
| } | |
| ip++; | |
| } | |
| ip = 0; | |
| while (ip < tokens.length) { | |
| token = tokens[ip++].trim(); | |
| if (token.matches("[0-9]([0-9])*")) { | |
| stack.push(Integer.valueOf(token)); | |
| } else { | |
| if (token.equalsIgnoreCase("+")) { /* ALU OP */ | |
| s = stack.pop(); | |
| f = stack.pop(); | |
| stack.push(f + s); | |
| } else if (token.equalsIgnoreCase("-")) { | |
| s = stack.pop(); | |
| f = stack.pop(); | |
| stack.push(f - s); | |
| } else if (token.equalsIgnoreCase("*")) { | |
| s = stack.pop(); | |
| f = stack.pop(); | |
| stack.push(f * s); | |
| } else if (token.equalsIgnoreCase("/")) { | |
| s = stack.pop(); | |
| f = stack.pop(); | |
| stack.push(f / s); | |
| } else if (token.equalsIgnoreCase("%")) { | |
| s = stack.pop(); | |
| f = stack.pop(); | |
| stack.push(f % s); | |
| } else if (token.matches("^jmp\\((.+)\\)$")) { /* JUMP OP */ | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| ip = labels.get(label); | |
| } else if (token.matches("^jz\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| if (stack.pop() == 0) { | |
| ip = labels.get(label); | |
| } | |
| } else if (token.matches("^jnz\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| if (stack.pop() != 0) { | |
| ip = labels.get(label); | |
| } | |
| } else if (token.matches("^jgz\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| if (stack.pop() > 0) { | |
| ip = labels.get(label); | |
| } | |
| } else if (token.matches("^jgez\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| if (stack.pop() >= 0) { | |
| ip = labels.get(label); | |
| } | |
| } else if (token.matches("^jlz\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| if (stack.pop() < 0) { | |
| ip = labels.get(label); | |
| } | |
| } else if (token.matches("^jlez\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| if (stack.pop() <= 0) { | |
| ip = labels.get(label); | |
| } | |
| } else if (token.matches("^call\\((.+)\\)$")) { | |
| String label = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| calls.push(new StackFrame(ip, new HashMap<String, Integer>(variables))); | |
| ip = labels.get(label); | |
| } else if (token.equalsIgnoreCase("ret")) { | |
| StackFrame frame = calls.pop(); | |
| ip = frame.ip; | |
| variables = frame.variables; | |
| } else if (token.matches("^!var\\((.+)\\)$")) { /* VARS OP */ | |
| String name = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| variables.put(name, stack.pop()); | |
| } else if (token.matches("^var\\((.+)\\)$")) { /* VARS OP */ | |
| String name = token.subSequence( | |
| token.indexOf('(') + 1, | |
| token.indexOf(')') | |
| ).toString(); | |
| stack.push(variables.get(name)); | |
| } else if (token.equalsIgnoreCase(".")) { /* IO OP */ | |
| // print the ASCII | |
| System.out.print((char) stack.pop().byteValue()); | |
| } else if (token.equalsIgnoreCase(".num")) { | |
| // print int | |
| System.out.print(stack.pop()); | |
| } else if (token.equalsIgnoreCase(",")) { | |
| // read number | |
| System.out.print("(int)>: "); | |
| stack.push(new Scanner(System.in).nextInt()); | |
| System.out.println(); | |
| } else if (token.equalsIgnoreCase("dup")) { /* STACK OP */ | |
| stack.push(stack.peek()); | |
| } else if (token.equalsIgnoreCase("drop")) { | |
| stack.pop(); | |
| } else if (token.matches("^label\\((.+)\\)$")) { /* NO OP */ | |
| // pseudo instruction | |
| } else { | |
| throw new UnsupportedOperationException(token); | |
| } | |
| } | |
| } | |
| } | |
| public static void main(String[] args) throws IOException { | |
| if (args.length == 1) { | |
| RPN rpn = new RPN(args[0]); | |
| rpn.eval(); | |
| } else { | |
| System.out.println("USAGE: java RPN program"); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment