Brainf**

README.md

Final

Goal

Write a compiler and interpreter for RUM. RUM is an extension of pbrain, which in turn is an extension of brainf--k.

• Also, finish any two of the four tasks defined in Lab1-BF.pdf.

FYI

Your source code MUST be based on BF.java, a working partial solution to last year's lab. You source code must also test that it works for valid RUM programs.

Hints

First, update the parser, PrintVisitor and InterpreterVisitor for the pbrain subset of RUM. You'll need to add in two new Node types for procedure definition and invocation. Make sure it works with this program:

(++++++++++<[>+>+<<-]>>[<<+>>-])>::::::::::::::<<<<<<<--------.>>>---------.+++++++..>---------.<<<<<<<------.<--------.>>>>>---.>>>.+++.<.--------.<<<<<<<+.

That program is "Hello, World!" in pbrain.

In the InterpreterVisitor you'll need this:

private byte[] array;
private int pointer;
public interface Procedure {
    void execute();
}
private Procedure[] procedures;

Inside the visit method for Program, add this:

procedures = new Procedure[256];

It is NOT necessary to make multiple passes through the source code. This language (RUM) is not that complex. Don't forget to write (and test) the CompilerVisitor for valid RUM programs!

Also: byte in Java is signed. To make byte b unsigned, do: b & 0xFF

Deadline and submission

You must complete this by the end of final exam time on August 10. However, do not wait until then to start.

This is a final exam. It is individual work. Therefore, submit your solution via email to [email protected]

If you submit your solution, and you do not receive email confirmation from me before August 10 that it works correctly, then you must attend the final exam period.

BF.java

import java.io.IOException;
import java.util.LinkedList;

public class BF {
	private interface Visitor {
		void visit (Loop loop);
		void visit (Left left);
		void visit (Right right);
		void visit (Increment increment);
		void visit (Decrement decrement);
		void visit (Input input);
		void visit (Output output);
		void visit (Program program);
	}
	private interface Node {
		void accept (Visitor v);
	}
	private class Left implements Node {
		public void accept (Visitor v) {
			v.visit(this);
		}
	}
	private class Right implements Node {
		public void accept (Visitor v) {
			v.visit(this);
		}
	}
	private class Increment implements Node {
		public void accept (Visitor v) {
			v.visit(this);
		}
	}
	private class Decrement implements Node {
		public void accept (Visitor v) {
			v.visit(this);
		}
	}
	private class Input implements Node {
		public void accept (Visitor v) {
			v.visit(this);
		}
	}
	private class Output implements Node {
		public void accept (Visitor v) {
			v.visit(this);
		}
	}
	private class Sequence implements Node {
		private LinkedList<Node> children;
		public Sequence() {
			children = new LinkedList<Node>();
		}
		public void accept (Visitor v) {
			for (Node child : children) {
				child.accept(v);
			}
		}
		public void add (Node instruction) {
			children.add(instruction);
		}
	}
	private class Loop implements Node {
		public Node body;
		public Loop (Node body) {
			this.body = body;
		}
		public void accept (Visitor v) {
			v.visit (this);
		}
	}
	public static class Program implements Node {
		public Node body;
		public Program (Node body) {
			this.body = body;
		}
		public void accept(Visitor v) {
			v.visit (this);
		}
	}
	private int i = 0;
	private Sequence doParse (String str) {
		Sequence seq = new Sequence();
		char c;
		while (i < str.length ()) {
			c = str.charAt (i);
			i++;
			if (c == '<') seq.add (new Left ());
			if (c == '>') seq.add (new Right ());
			if (c == '+') seq.add (new Increment ());
			if (c == '-') seq.add (new Decrement ());
			if (c == '.') seq.add (new Output ());
			if (c == ',') seq.add (new Input ());
			if (c == '[') seq.add (new Loop (doParse (str)));
			if (c == ']') return seq;
		}
		return seq;
	}
	public static Program parse (String str) {
		return new Program (new BF().doParse(str));
	}
	public static void main(String[] args) {
		Node ascii = BF.parse("+[.+]");
		ascii.accept(new BF.InterpreterVisitor());
		Node hello = BF.parse("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
		hello.accept(new BF.InterpreterVisitor());
		Node beer = BF.parse(">+++++++++[<+++++++++++>-]<[>[-]>[-]<<[>+>+<<-]>>[<<+>>-]>>>[-]<<<+++++++++<[>>>+<<[>+>[-]<<-]>[<+>-]>[<<++++++++++>>>+<-]<<-<-]+++++++++>[<->-]>>+>[<[-]<<+>>>-]>[-]+<<[>+>-<<-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>[<+>-]<<-[>[-]<[-]]>>+<[>[-]<-]<++++++++[<++++++<++++++>>-]>>>[>+>+<<-]>>[<<+>>-]<[<<<<<.>>>>>-]<<<<<<.>>[-]>[-]++++[<++++++++>-]<.>++++[<++++++++>-]<++.>+++++[<+++++++++>-]<.><+++++..--------.-------.>>[>>+>+<<<-]>>>[<<<+>>>-]<[<<<<++++++++++++++.>>>>-]<<<<[-]>++++[<++++++++>-]<.>+++++++++[<+++++++++>-]<--.---------.>+++++++[<---------->-]<.>++++++[<+++++++++++>-]<.+++..+++++++++++++.>++++++++[<---------->-]<--.>+++++++++[<+++++++++>-]<--.-.>++++++++[<---------->-]<++.>++++++++[<++++++++++>-]<++++.------------.---.>+++++++[<---------->-]<+.>++++++++[<+++++++++++>-]<-.>++[<----------->-]<.+++++++++++..>+++++++++[<---------->-]<-----.---.>>>[>+>+<<-]>>[<<+>>-]<[<<<<<.>>>>>-]<<<<<<.>>>++++[<++++++>-]<--.>++++[<++++++++>-]<++.>+++++[<+++++++++>-]<.><+++++..--------.-------.>>[>>+>+<<<-]>>>[<<<+>>>-]<[<<<<++++++++++++++.>>>>-]<<<<[-]>++++[<++++++++>-]<.>+++++++++[<+++++++++>-]<--.---------.>+++++++[<---------->-]<.>++++++[<+++++++++++>-]<.+++..+++++++++++++.>++++++++++[<---------->-]<-.---.>+++++++[<++++++++++>-]<++++.+++++++++++++.++++++++++.------.>+++++++[<---------->-]<+.>++++++++[<++++++++++>-]<-.-.---------.>+++++++[<---------->-]<+.>+++++++[<++++++++++>-]<--.+++++++++++.++++++++.---------.>++++++++[<---------->-]<++.>+++++[<+++++++++++++>-]<.+++++++++++++.----------.>+++++++[<---------->-]<++.>++++++++[<++++++++++>-]<.>+++[<----->-]<.>+++[<++++++>-]<..>+++++++++[<--------->-]<--.>+++++++[<++++++++++>-]<+++.+++++++++++.>++++++++[<----------->-]<++++.>+++++[<+++++++++++++>-]<.>+++[<++++++>-]<-.---.++++++.-------.----------.>++++++++[<----------->-]<+.---.[-]<<<->[-]>[-]<<[>+>+<<-]>>[<<+>>-]>>>[-]<<<+++++++++<[>>>+<<[>+>[-]<<-]>[<+>-]>[<<++++++++++>>>+<-]<<-<-]+++++++++>[<->-]>>+>[<[-]<<+>>>-]>[-]+<<[>+>-<<-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<>>[<+>-]<<-[>[-]<[-]]>>+<[>[-]<-]<++++++++[<++++++<++++++>>-]>>>[>+>+<<-]>>[<<+>>-]<[<<<<<.>>>>>-]<<<<<<.>>[-]>[-]++++[<++++++++>-]<.>++++[<++++++++>-]<++.>+++++[<+++++++++>-]<.><+++++..--------.-------.>>[>>+>+<<<-]>>>[<<<+>>>-]<[<<<<++++++++++++++.>>>>-]<<<<[-]>++++[<++++++++>-]<.>+++++++++[<+++++++++>-]<--.---------.>+++++++[<---------->-]<.>++++++[<+++++++++++>-]<.+++..+++++++++++++.>++++++++[<---------->-]<--.>+++++++++[<+++++++++>-]<--.-.>++++++++[<---------->-]<++.>++++++++[<++++++++++>-]<++++.------------.---.>+++++++[<---------->-]<+.>++++++++[<+++++++++++>-]<-.>++[<----------->-]<.+++++++++++..>+++++++++[<---------->-]<-----.---.+++.---.[-]<<<]");
		beer.accept(new BF.InterpreterVisitor());
		Node fibonacci = BF.parse("+++++++++++>+>>>>++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-<-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<-]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<+>>[-]]<<<<<<<]>>>>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<<<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<[-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]");
		fibonacci.accept(new BF.InterpreterVisitor());
		Node rot13 = BF.parse("+[,+[-[>+>+<<-]>[<+>-]+>>++++++++[<-------->-]<-[<[-]>>>+[<+<+>>-]<[>+<-]<[<++>>>+[<+<->>-]<[>+<-]]>[<]<]>>[-]<<<[[-]<[>>+>+<<<-]>>[<<+>>-]>>++++++++[<-------->-]<->>++++[<++++++++>-]<-<[>>>+<<[>+>[-]<<-]>[<+>-]>[<<<<<+>>>>++++[<++++++++>-]>-]<<-<-]>[<<<<[-]>>>>[<<<<->>>>-]]<<++++[<<++++++++>>-]<<-[>>+>+<<<-]>>[<<+>>-]+>>+++++[<----->-]<-[<[-]>>>+[<+<->>-]<[>+<-]<[<++>>>+[<+<+>>-]<[>+<-]]>[<]<]>>[-]<<<[[-]<<[>>+>+<<<-]>>[<<+>>-]+>------------[<[-]>>>+[<+<->>-]<[>+<-]<[<++>>>+[<+<+>>-]<[>+<-]]>[<]<]>>[-]<<<<<------------->>[[-]+++++[<<+++++>>-]<<+>>]<[>++++[<<++++++++>>-]<-]>]<[-]++++++++[<++++++++>-]<+>]<.[-]+>>+<]>[[-]<]<]");
		rot13.accept(new BF.InterpreterVisitor());
	}
	public static class PrintVisitor implements Visitor {
		public void visit (Left n) { System.out.print('<'); }
		public void visit (Right n) { System.out.print('>'); }
		public void visit (Increment n) { System.out.print('+'); }
		public void visit (Decrement n) { System.out.print('-'); }
		public void visit (Input n) { System.out.print(','); }
		public void visit (Output n) { System.out.print('.'); }
		public void visit (Loop n) { System.out.print('['); n.body.accept(this); System.out.print(']'); }
		public void visit (Program n) { n.body.accept(this); }
	}
	public static class InterpreterVisitor implements Visitor {
		private byte[] array;
		private int pointer;
		
		public void visit (Left n) { pointer--; }
		public void visit (Right n) { pointer++; }
		public void visit (Increment n) { array[pointer]++; }
		public void visit (Decrement n) { array[pointer]--; }
		public void visit (Input n) { try {
			array[pointer] = (byte) System.in.read();
		} catch (IOException e) {
		} }
		public void visit (Output n) { System.out.print((char)array[pointer]); }
		public void visit (Loop n) {
			while (array[pointer] != 0) {
				n.body.accept(this);
			}
		}
		public void visit (Program n) {
			array = new byte[30000];
			pointer = 0;
			n.body.accept(this);
		}
	}
}

Fun.java

// Demonstration of anonymous inner classes in Java
// This is the closest thing Java has to function pointers.
public class Fun {
	public interface Procedure {
		void execute();
	}
	static Procedure[] fun = new Procedure[256];
	public static void main(String[] args) {
		fun[0] = new Procedure() {
			public void execute() {
				System.out.println("Howdy!");
			}
		};
		fun[1] = new Procedure() {
			public void execute() {
				System.out.println("But so is RUM");
			}
		};
		fun[0].execute();
		fun[1].execute();
	}
}

Lab1-BF.pdf