Monday, April 5, 2010

Here is a RESOL interpreter in Java. I originally wrote it as multiple files, but crammed it into a single file for this post. The input and output queue size is limited to 10. The interpreter in Haskell does not have this limitation.

import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.Reader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

public class ri {
public static class RESOLException extends RuntimeException {
public RESOLException(Statement statement, String message) {
super(statement.getLocation() + ": " + message);
}

public RESOLException(Statement statement, String message, Throwable t) {
super(statement.getLocation() + ": " + message, t);
}

public RESOLException(String fileName, int lineNumber, String message) {
super(fileName + ":" + lineNumber + ": " + message);
}

public RESOLException(String fileName, int lineNumber, String message, Throwable t) {
super(fileName + ":" + lineNumber + ": " + message, t);
}
}

public static class BitInputStream {
private InputStream in;
private int currentByte;
private int currentBit = 0;
private boolean eof = false;

public BitInputStream(InputStream in) {
this.in = in;
}

public boolean eof() {
return eof;
}

public boolean read() throws IOException {
if (currentBit == 0) {
currentByte = in.read();
if (currentByte < 0) {
eof = true;
in.close();
return false;
}
currentBit = 128;
}
try {
return (currentByte & currentBit) != 0;
} finally {
currentBit >>>= 1;
}
}
}

public static class BitOutputStream {
private OutputStream out;
private int currentByte = 0;
private int currentBit = 128;

public BitOutputStream(OutputStream out) {
this.out = out;
}

public void write(boolean b) throws IOException {
if (b)
currentByte |= currentBit;
currentBit >>>= 1;
if (currentBit == 0) {
out.write(currentByte);
currentByte = 0;
currentBit = 128;
}
}
}

public static class Statement {
public enum Op { DATA, CALL, CONTINUE, IF, STOP }

private String fileName;
private int lineNumber;
private String label;
private Op op;
private String arg1;
private String arg2;
private Statement next = null;
private int itemSize = 0;
private LinkedList<LinkedList<Integer>> queueStack = null;
private LinkedList<Statement> callStack = null;

public Statement(String fileName, int lineNumber, String label, Op op, String arg1, String arg2) {
this.fileName = fileName;
this.lineNumber = lineNumber;
this.label = label == null || label.length() == 0 ? null : label;
this.op = op;
this.arg1 = arg1;
this.arg2 = arg2;
switch (op) {
case DATA:
if (arg1 == null)
throw new RESOLException(this, "DATA STATEMENT REQUIRES AN ARGUMENT");
if (label != null) {
itemSize = Integer.parseInt(arg1, 10);
queueStack = new LinkedList<LinkedList<Integer>>();
queueStack.addFirst(new LinkedList<Integer>());
if (arg2 != null)
enqueueLiteral(arg2);
}
break;
case CALL:
if (arg1 == null)
throw new RESOLException(this, "CALL STATEMENT REQUIRES AN ARGUMENT");
break;
case CONTINUE:
if (arg1 == null)
throw new RESOLException(this, "CONTINUE STATEMENT REQUIRES AN ARGUMENT");
break;
case IF:
if (arg1 == null || arg2 == null)
throw new RESOLException(this, "IF STATEMENT REQUIRES TWO ARGUMENTS");
break;
case STOP:
if (arg1 != null || arg2 != null)
throw new RESOLException(this, "STOP STATEMENT CANNOT HAVE ANY ARGUMENTS");
break;
}
if (label != null)
callStack = new LinkedList<Statement>();
}

protected String getFileName() {
return fileName;
}

protected int getLineNumber() {
return lineNumber;
}

public String getLabel() {
return label;
}

protected Op getOp() {
return op;
}

protected String getArg1() {
return arg1;
}

protected String getArg2() {
return arg2;
}

public void setNext(Statement next) {
this.next = next;
}

public String getLocation() {
return fileName + ":" + lineNumber;
}

public void enqueueLiteral(String literal) {
for (int i = 0; i < literal.length(); i++)
enqueueDigit(literal.charAt(i) - '0');
}

public void enqueueItem(LinkedList<Integer> queue, int queueItemSize) {
for (int i = 0; i < Math.min(queue.size(), queueItemSize); i++)
enqueueDigit(queue.get(i));
}

public void enqueueDigit(int digit) {
assert digit >= 0 && digit <= 9;
queueStack.getFirst().addLast(digit);
}

public void dequeueItem() {
for (int i = 0; i < itemSize && queueStack.getFirst().size() > 0; i++)
queueStack.getFirst().removeFirst();
}

public int getCurrentItemSize() {
return Math.min(itemSize, queueStack.getFirst().size());
}

public int getItemDigit(int index) {
assert index < itemSize;
return queueStack.getFirst().get(index);
}

public Statement popCall(Statement t, Statement n) {
if (queueStack != null)
queueStack.removeFirst();
return callStack.removeFirst();
}

public void pushCall(Statement t, Statement n) {
if (queueStack != null)
queueStack.addFirst(new LinkedList<Integer>());
callStack.addFirst(n);
}

public boolean isData() {
return op == Op.DATA;
}

private static void enqueueTo(Statement statement, String arg, Map<String,Statement> labels) {
if (!statement.isData())
return;
Statement argStatement = labels.get(arg);
if (argStatement == null)
statement.enqueueLiteral(arg);
else
for (int i = 0; i < argStatement.getCurrentItemSize(); i++)
statement.enqueueDigit(argStatement.getItemDigit(i));
}

private static boolean equalTo(String arg1, String arg2, Map<String,Statement> labels) {
if (arg1.equals(arg2))
return true;
Statement statement1 = labels.get(arg1);
Statement statement2 = labels.get(arg2);
if (statement1 == null && statement2 == null)
return false;
if (statement1 != null && statement2 != null) {
if (statement1.getCurrentItemSize() != statement2.getCurrentItemSize())
return false;
for (int i = 0; i < statement1.getCurrentItemSize(); i++)
if (statement1.getItemDigit(i) != statement2.getItemDigit(i))
return false;
return true;
}
if (statement1 == null) {
statement1 = statement2;
arg2 = arg1;
}
if (statement1.getCurrentItemSize() != arg2.length())
return false;
for (int i = 0; i < arg2.length(); i++)
if (statement1.getItemDigit(i) != arg2.charAt(i) - '0')
return false;
return true;
}

public Statement run(Map<String,Statement> labels) {
Statement statement = null;
Statement statement2 = null;
switch (op) {
case DATA:
statement = labels.get(arg1);
if (statement == null || !statement.isData())
break;
if (arg2 == null)
statement.dequeueItem();
else
enqueueTo(statement, arg2, labels);
break;

case CALL:
statement = labels.get(arg1);
if (statement == null)
throw new RESOLException(this, "CALL TO UNKNOWN LABEL: " + arg1);
if (next == null)
throw new RESOLException(this, "UNEXPECTED END OF PROGRAM");
statement.pushCall(this, next);
if (arg2 != null)
enqueueTo(statement, arg2, labels);
return statement;

case CONTINUE:
statement = labels.get(arg1);
if (statement == null)
throw new RESOLException(this, "CONTINUE FROM UNKNOWN LABEL: " + arg1);
if (!statement.isData() || statement.getCurrentItemSize() == 0)
return statement.popCall(this, next);
if (arg2 == null)
return statement;
statement = labels.get(arg2);
if (statement == null)
throw new RESOLException(this, "CONTINUE FROM UNKNOWN LABEL: " + arg2);
return statement;

case IF:
if (!equalTo(arg1, arg2, labels)) {
if (next == null || next.next == null)
throw new RESOLException(this, "UNEXPECTED END OF PROGRAM");
return next.next;
}
break;

case STOP:
return null;
}
if (next == null)
throw new RESOLException(this, "UNEXPECTED END OF PROGRAM");
return next;
}
}

public static class FirstStatement extends Statement {
private boolean encodeOutput;
private boolean isIO;
private int[] inputItem = null;
private int inputItemSize;
private BitInputStream in;
private int[] outputItem = null;
private int outputItemSize;
private BitOutputStream out;
private int itemBitCount;

public FirstStatement(Statement statement, boolean encodeOutput) {
super(statement.getFileName(), statement.getLineNumber(), statement.getLabel(), statement.getOp(), statement.getArg1(), statement.getArg2());
this.encodeOutput = encodeOutput;
isIO = getLabel() != null && getOp() == Op.DATA;
if (isIO) {
int itemSize = Integer.parseInt(getArg1(), 10);
inputItem = new int[itemSize];
inputItemSize = 0;
in = new BitInputStream(System.in);
outputItem = new int[itemSize];
outputItemSize = 0;
out = new BitOutputStream(System.out);

int test = 0;
for (int i = 0; i < itemSize; i++)
test = test*10 + 9;
itemBitCount = 0;
boolean decCount = false;
while (test > 0) {
if ((test & 1) == 0)
decCount = true;
test >>>= 1;
itemBitCount++;
}
if (decCount)
itemBitCount--;
}
}

public void enqueueDigit(int digit) {
if (!encodeOutput) {
System.out.print(digit);
return;
}
outputItem[outputItemSize++] = digit;
if (outputItemSize >= outputItem.length)
flushOutput();
}

public void flushOutput() {
int item = 0;
for (int i = 0; i < outputItem.length; i++)
item = item*10 + outputItem[i];
int bit = 1 << (itemBitCount - 1);
while (bit != 0) {
try {
out.write((item & bit) != 0);
} catch (IOException e) {
throw new RESOLException(this, "IO EXCEPTION", e);
}
bit >>>= 1;
}
outputItemSize = 0;
Arrays.fill(outputItem, 0);
}

public void dequeueItem() {
readItem();
}

public int getCurrentItemSize() {
if (inputItemSize == 0)
readItem();
return inputItemSize;
}

public int getItemDigit(int index) {
return inputItem[index];
}

private void readItem() {
inputItemSize = 0;
if (in.eof())
return;
int item = 0;
int bit = 1 << (itemBitCount - 1);
while (!in.eof() && bit != 0) {
boolean b;
try {
b = in.read();
} catch (IOException e) {
throw new RESOLException(this, "IO EXCEPTION", e);
}
if (in.eof())
break;
if (b)
item |= bit;
bit >>>= 1;
}
for (int i = inputItem.length - 1; i >= 0; i--) {
inputItem[i] = item%10;
item = item/10;
}
inputItemSize = inputItem.length;
}

public Statement popCall(Statement t, Statement n) {
if (!isIO)
return super.popCall(t, n);
if (n == null)
throw new RESOLException(t, "UNEXPECTED END OF PROGRAM");
return n;
}

public void pushCall(Statement t, Statement n) {
if (isIO)
throw new RESOLException(t, "ILLEGAL CALL");
super.pushCall(t, n);
}
}

public static class Parser implements Iterable<Statement>, Iterator<Statement> {
private Reader in;
private String fileName;
private int lineNumber;
private int statementLineNumber = 1;
private StringBuilder currentLabel = new StringBuilder();
private StringBuilder currentStatement = new StringBuilder();
private Statement statement = null;
private boolean eof = false;

public Parser(String fileName) throws IOException {
this(fileName, new FileReader(fileName));
}

public Parser(String fileName, Reader in) {
this.fileName = fileName;
this.in = in;
this.lineNumber = 0;
}

public Iterator<Statement> iterator() {
return this;
}

public boolean hasNext() {
while (statement == null && !eof)
try {
readLine();
} catch (IOException e) {
throw new RESOLException(fileName, lineNumber, "IO EXCEPTION", e);
}
return statement != null;
}

public Statement next() {
hasNext();
try {
return statement;
} finally {
statement = null;
}
}

public void remove() {
}

private void readLine() throws IOException {
lineNumber++;
int column = 1;
int c = in.read();
if (c < 0) {
eof = true;
in.close();
finishStatement();
return;
}
if (c == 'C') {
finishStatement();
statementLineNumber++;
while (c >= 0 && c != '\n')
c = in.read();
if (c < 0) {
eof = true;
in.close();
}
return;
}
StringBuilder sb = new StringBuilder();
while (column < 6) {
if (c != ' ') {
if (isDigit(c))
sb.append((char) c);
else
throw new RESOLException(fileName, lineNumber, "ILLEGAL LABEL");
}
c = in.read();
column++;
if (c < 0) {
eof = true;
in.close();
if (sb.length() > 0)
throw new RESOLException(fileName, lineNumber, "UNEXPECTED EOF");
finishStatement();
return;
}
if (c == '\n') {
finishStatement();
return;
}
}
if (c == ' ')
finishStatement();
currentLabel.append(sb);
for (;;) {
c = in.read();
column++;
if (c < 0) {
eof = true;
in.close();
finishStatement();
return;
}
if (c == '\n')
return;
if (c == ' ' || column > 72)
continue;
if (isDigit(c) || isLetter(c) || c == ',')
currentStatement.append((char) c);
else
throw new RESOLException(fileName, lineNumber, "UNEXPECTED CHARACTER");
}
}

private boolean isDigit(int c) {
return c >= '0' && c <= '9';
}

private boolean isLetter(int c) {
return c >= 'A' && c <= 'Z';
}

private void finishStatement() {
assert statement == null;
if (currentStatement.length() == 0 && currentLabel.length() == 0) {
statementLineNumber = lineNumber;
return;
}
int i = 0;
while (i < currentStatement.length() && isLetter(currentStatement.charAt(i)))
i++;
Statement.Op op;
try {
op = Enum.valueOf(Statement.Op.class, currentStatement.substring(0, i));
} catch (IllegalArgumentException e) {
throw new RESOLException(fileName, statementLineNumber, "UNRECOGNIZED STATEMENT");
}
String arg1 = null;
int i2 = i;
while (i2 < currentStatement.length() && isDigit(currentStatement.charAt(i2)))
i2++;
if (i2 < currentStatement.length()) {
if (i2 == i || currentStatement.charAt(i2) != ',')
throw new RESOLException(fileName, statementLineNumber, "ILLEGAL ARGUMENT");
}
if (i < i2)
arg1 = currentStatement.substring(i, i2);
String arg2 = null;
i = i2 + 1;
i2 = i;
while (i2 < currentStatement.length() && isDigit(currentStatement.charAt(i2)))
i2++;
if (i2 < currentStatement.length())
throw new RESOLException(fileName, statementLineNumber, "ILLEGAL ARGUMENT");
if (i < i2)
arg2 = currentStatement.substring(i, i2);
statement = new Statement(fileName, statementLineNumber, currentLabel.toString(), op, arg1, arg2);
statementLineNumber = lineNumber;
currentLabel.setLength(0);
currentStatement.setLength(0);
}
}

public static void main(String[] args) throws Exception {
boolean encodeOutput = true;
int index = 0;
if (index < args.length && "-r".equals(args[index])) {
encodeOutput = false;
index++;
}
FirstStatement first = null;
Statement last = null;
HashMap<String,Statement> labels = new HashMap<String,Statement>();
for (; index < args.length; index++)
for (Statement s : new Parser(args[index])) {
if (first == null)
s = first = new FirstStatement(s, encodeOutput);
else if (last != null)
last.setNext(s);
last = s;
if (s.getLabel() != null) {
if (labels.containsKey(s.getLabel()))
throw new RESOLException(s, "DUPLICATE LABEL");
labels.put(s.getLabel(), s);
}
}
last = first;
while (last != null)
last = last.run(labels);
}
}

No comments:

Post a Comment