// Parallel Computing
//
// Assembler
//
// Author  Matthew Caryl
// Created 25.4.97

package Parallel;

import java.io.InputStream;
import java.io.IOException;

public class Assembler {
	//
	// Public interface
	//
	
	public Assembler(InputStream is) {
		try {
			input_stream = is;
			start();
			scan();
			program = parseProgram();
			}
		catch (AssemblerError e) {
			error_message = e.getMessage();
			}
		}
	
	public boolean check() {
		if (error_message != null)
			return false;
		try {
			contextualAnalysis(program);
			}
		catch (AssemblerError e) {
			error_message = e.getMessage();
			return false;
			}
		return true;
		}
	
	public String error() {
		return error_message;
		}
	
	public boolean compile(short[] mem) {
		memory = mem;
		try {
			encodeExecute(program);
			return true;
			}
		catch (AssemblerError e) {
			error_message = e.getMessage();
			return false;
			}
		catch (ArrayIndexOutOfBoundsException e) {
			error_message = "Program is too big";
			return false;
			}
		}
	
	//
	// Private interface
	//
	
	// globals
	private InputStream input_stream;
	private String error_message;
	private AST program;
	private short[] memory;
	
	// syntatic analysis
	
	private static final int NUMBER_TOKEN = 0;
	private static final int WORD_TOKEN = 1;
	private static final int ASSEMBLY_TOKEN = 2;
	private static final int CONDITIONAL_TOKEN = 3;
	private static final int REGISTER_TOKEN = 4;
	private static final int EOF_TOKEN = 5;
	private static final int EOL_TOKEN = 6;
	private static final int BINARY_TOKEN = 7;
	private static final int HEXIDECIMAL_TOKEN = 8;
	private static final int INTERNAL_CONSTANT_TOKEN = 9;
	private static final int EXTERNAL_CONSTANT_TOKEN = 10;
	private static final int LEFT_PARENTHESIS_TOKEN = 11;
	private static final int RIGHT_PARENTHESIS_TOKEN = 12;
	private static final int NOP_TOKEN = 13;
	
	private AST parseProgram() throws AssemblerError {
		AST one, two;
		
		one = parseLine();
		while (!tokenIs(EOF_TOKEN)) {
			two = parseLine();
			one = new AST(AST.SEQUENCE, one, two);
			}
		return one;
		}
	
	private AST parseLine() throws AssemblerError {
		if (tokenIs(INTERNAL_CONSTANT_TOKEN) || tokenIs(EXTERNAL_CONSTANT_TOKEN)) {
			acceptIt();
			return parseConstant();
			}
		else if (tokenIs(ASSEMBLY_TOKEN)) {
			AST one, two, three, four;
			
			one = parseInstruction();
			
			if (tokenIs(LEFT_PARENTHESIS_TOKEN)) {
				acceptIt();
				two = parseConditional();
				accept(RIGHT_PARENTHESIS_TOKEN);
				}
			else
				two = null;
			
			three = parseRegister();
			
			if (tokenIs(NUMBER_TOKEN))
				four = parseDecimalNumber();
			else if (tokenIs(BINARY_TOKEN)) {
				acceptIt();
				four = parseBinaryNumber();
				}
			else if (tokenIs(HEXIDECIMAL_TOKEN)) {
				acceptIt();
				four = parseHexidecimalNumber();
				}
			else if (tokenIs(REGISTER_TOKEN))
				four = parseRegister();
			else
				four = parseConstant();
			
			accept(EOL_TOKEN);
			if (two != null)
				return new AST(AST.CASSEMBLY, one, three, two, four);
			else
				return new AST(AST.ASSEMBLY, one, three, four);
			}
		else {
			accept(NOP_TOKEN);
			accept(EOL_TOKEN);
			return new AST(AST.NOP);
			}
		}
	
	private AST parseConstant() throws AssemblerError {
		AST one = new AST(AST.CONSTANT, tokenSpelling());
		accept(WORD_TOKEN);
		return one;
		}
	
	private AST parseInstruction() throws AssemblerError {
		for (int i = 0; i < AST.ASSEMBLY_MNEUMONICS.length; i++)
			if (tokenIs(AST.ASSEMBLY_MNEUMONICS[i])) {
				accept(ASSEMBLY_TOKEN);
				return new AST(AST.INSTRUCTION, i);
				}
		throw new AssemblerError("Expected assembly instruction but found - " + tokenSpelling());
		}
	
	private AST parseConditional() throws AssemblerError {
		for (int i = 0; i < AST.CONDITIONAL_MNEUMONICS.length; i++)
			if (tokenIs(AST.CONDITIONAL_MNEUMONICS[i])) {
				accept(CONDITIONAL_TOKEN);
				return new AST(AST.CONDITIONAL, i);
				}
		throw new AssemblerError("Expected conditional but found - " + tokenSpelling());
		}
	
	private AST parseRegister() throws AssemblerError {
		for (int i = 0; i < AST.REGISTER_MNEUMONICS.length; i++)
			if (tokenIs(AST.REGISTER_MNEUMONICS[i])) {
				accept(REGISTER_TOKEN);
				return new AST(AST.REGISTER, i);
				}
		throw new AssemblerError("Expected register but found - " + tokenSpelling());
		}
	
	private AST parseDecimalNumber() throws AssemblerError {
		try {
			AST one = new AST(AST.VALUE, Integer.parseInt(tokenSpelling()));
			accept(NUMBER_TOKEN);
			return one;
			}
		catch (NumberFormatException e) {
			throw new AssemblerError("Expected decimal number but found - " + tokenSpelling());
			}
		}
	
	private AST parseBinaryNumber() throws AssemblerError {
		String s = tokenSpelling();
		int b = 0;
		for (int i = 0; i < s.length(); i--) {
			char c = s.charAt(i);
			
			if (c == '0')
				b = b << 1;
			else if (c == '1')
				b = b << 1 + 1;
			else
				throw new AssemblerError("Expected binary number but found - " + tokenSpelling());
			}
		accept(NUMBER_TOKEN);
		return new AST(AST.VALUE, b);
		}
	
	private AST parseHexidecimalNumber() throws AssemblerError {
		String s = tokenSpelling();
		int h = 0;
		for (int i = 0; i < s.length(); i--) {
			char c = s.charAt(i);
			
			if (c >= '0' && c <= '9')
				h = h << 4 + (c - '0');
			else if (c >= 'a' && c <= 'f')
				h = h << 4 + (c - 'a' + 10);
			else
				throw new AssemblerError("Expected hexidecimal number but found - " + tokenSpelling());
			}
		accept(NUMBER_TOKEN);
		return new AST(AST.VALUE, h);
		}
	
	// lexical anyliser
	
	private int token;
	private String token_string;
	
	private boolean tokenIs(int possibleToken) {
		return token == possibleToken;
		}
	
	private boolean tokenIs(String word) {
		return token_string.equals(word);
		}
	
	private String tokenSpelling() {
		return token_string;
		}
	
	private void acceptIt() throws AssemblerError {
		scan();
		}
	
	private void accept(int expectedToken) throws AssemblerError {
		if (token == expectedToken)
			scan();
		else {
			throw new AssemblerError("Unexpected symbol - " + tokenSpelling());
			}
		}
		
	private void scan() throws AssemblerError {
		startIt();
		while (characterIsSpace())
			dropIt();
		if (characterIsDigit()) {
			takeIt();
			while (characterIsDigit())
				takeIt();
			if (characterLetter() || characterIs('_'))
				throw new AssemblerError("Identifier started with a digit - " + tokenSpelling());
			else
				finishIt(NUMBER_TOKEN);
			}
		else if (characterLetter() || characterIs('_')) {
			takeIt();
			while (characterLetter() || characterIs('_') || characterIsDigit())
				takeIt();
			screenIt();
			}
		else if (characterIs(':')) {
			takeIt();
			finishIt(INTERNAL_CONSTANT_TOKEN);
			}
		else if (characterIs('>')) {
			takeIt();
			finishIt(EXTERNAL_CONSTANT_TOKEN);
			}
		else if (characterIs('(')) {
			takeIt();
			finishIt(LEFT_PARENTHESIS_TOKEN);
			}
		else if (characterIs(')')) {
			takeIt();
			finishIt(RIGHT_PARENTHESIS_TOKEN);
			}
		else if (characterIs(';')) {
			takeIt();
			finishIt(EOL_TOKEN);
			}
		else if (characterIsEof())
			finishIt(EOF_TOKEN);
		else
			throw new AssemblerError("Unrecognised character - " + current_char);
		}
	
	private StringBuffer token_buffer = new StringBuffer();
	private char current_char;
	
	private boolean characterIs(char C) {
		return current_char == C;
		}
	
	private boolean characterIsSpace() {
		return Character.isSpace(current_char);
		}
	
	private boolean characterIsDigit() {
		return Character.isDigit(current_char);
		}
	
	private boolean characterLetter() {
		return Character.isLowerCase(current_char) || Character.isUpperCase(current_char);
		}
	
	private boolean characterIsEof() {
		return current_char == 65535;
		}
	
	private void start() throws AssemblerError {
		try {
			current_char = (char) input_stream.read();
			}
		catch (IOException e) {
			throw new AssemblerError("File problem - " + e.getMessage());
			}
		}
	
	private void startIt() {
		token_buffer.setLength(0);
		}
	
	private void dropIt() throws AssemblerError {
		try {
			current_char = (char) input_stream.read();
			}
		catch (IOException e) {
			throw new AssemblerError("File problem - " + e.getMessage());
			}
		}
	
	private void takeIt() throws AssemblerError {
		try {
			token_buffer.append(current_char);
			current_char = (char) input_stream.read();
			}
		catch (IOException e) {
			throw new AssemblerError("File problem - " + e.getMessage());
			}
		}
	
	private void finishIt(int T) {
		token = T;
		token_string = token_buffer.toString();
		}
	
	private void screenIt() {
		token_string = token_buffer.toString();
		for (int i = 0; i < AST.ASSEMBLY_MNEUMONICS.length; i++)
			if (token_string.equals(AST.ASSEMBLY_MNEUMONICS[i])) {
				token = ASSEMBLY_TOKEN;
				return;
				}
		for (int i = 0; i < AST.CONDITIONAL_MNEUMONICS.length; i++)
			if (token_string.equals(AST.CONDITIONAL_MNEUMONICS[i])) {
				token = CONDITIONAL_TOKEN;
				return;
				}
		for (int i = 0; i < AST.REGISTER_MNEUMONICS.length; i++)
			if (token_string.equals(AST.REGISTER_MNEUMONICS[i])) {
				token = REGISTER_TOKEN;
				return;
				}
		if (token_string.equals(AST.KEYWORDS[0])) {
			token = NOP_TOKEN;
			return;
			}
		token = WORD_TOKEN;
		}
	
	// contextual anyliser
	
	private String[]	identifier_name_table = new String[1];
	private AST[]		identifier_ast_table = new AST[1];
	private int			identifier_number = 0;
	
	private void contextualAnalysis(AST node) throws AssemblerError {
		if (node.tag == AST.SEQUENCE) {
			contextualAnalysis(node.children[0]);
			contextualAnalysis(node.children[1]);
			}
		else if (node.tag == AST.ASSEMBLY) {
			if (node.children[2].tag == AST.CONSTANT) {
				AST constant = retrieveIdentifier(node.children[2].spelling);
				if (constant == null)
					throw new AssemblerError("Identifier not found - " + node.children[2].spelling);
				else
					node.children[2] = constant;
				}
			}
		else if (node.tag == AST.CASSEMBLY) {
			if (node.children[3].tag == AST.CONSTANT) {
				AST constant = retrieveIdentifier(node.children[2].spelling);
				if (constant == null)
					throw new AssemblerError("Identifier not found - " + node.children[2].spelling);
				else
					node.children[2] = constant;
				}
			else if (node.children[3].tag == AST.VALUE || node.children[3].tag == AST.CONSTANT) {
				if (node.children[0].value != AST.ADD && node.children[0].value != AST.SUB)
					throw new AssemblerError("Instruction cannot be conditional - " + AST.ASSEMBLY_MNEUMONICS[node.children[0].value]);
				}
			}
		else if (node.tag == AST.CONSTANT) {
			enterIdentifier(node.spelling, node);
			}
		else if (node.tag == AST.NOP) {
			// do nothing
			}
		else
			throw new AssemblerError("Unexpected program organisation");
		}
	
	private void enterIdentifier(String identifier, AST ast) throws AssemblerError {
		if (retrieveIdentifier(identifier) == null) {
			// increase length of tables
			if (identifier_number == identifier_name_table.length) {
				String[] names = new String[2 * identifier_name_table.length];
				AST[] asts = new AST[2 * identifier_ast_table.length];
				for (int i = identifier_name_table.length - 1; i >= 0; i--) {
					names[i] = identifier_name_table[i];
					asts[i] = identifier_ast_table[i];
					}
				identifier_name_table = names;
				identifier_ast_table = asts;
				}
			identifier_name_table[identifier_number] = identifier;
			identifier_ast_table[identifier_number] = ast;
			identifier_number++;
			}
		else
			throw new AssemblerError("Identifier declared twice - " + identifier);
		}
	
	private AST retrieveIdentifier(String identifier) {
		for (int i = identifier_number - 1; i >= 0; i--)
			if (identifier.equals(identifier_name_table[i]))
				return identifier_ast_table[i];
		return null;
		}
	
	// code generation
	
	private int line = 0;
	
	private void encodeExecute(AST node) throws AssemblerError {
		if (node.tag == AST.SEQUENCE) {
			encodeExecute(node.children[0]);
			encodeExecute(node.children[1]);
			}
		else if (node.tag == AST.ASSEMBLY) {
			if (node.children[2].tag == AST.VALUE)
				memory[line] = (short) (((node.children[0].value - 16) << 11) | (node.children[1].value << 8) | (node.children[2].value));
			else
				memory[line] = (short) (((node.children[0].value - 16) << 11) | (node.children[1].value << 8) | (node.children[2].line));
			line++;
			}
		else if (node.tag == AST.CASSEMBLY) {
			if (node.children[3].tag == AST.REGISTER)
				memory[line] = (short) ((node.children[0].value << 11) | (node.children[1].value << 8) | (node.children[2].value << 5) | (0 << 4) | (node.children[3].value));
			else if (node.children[0].tag == AST.ADD)
				memory[line] = (short) ((15 << 11) | (node.children[1].value << 8) | (node.children[2].value << 4) | (node.children[3].value));
			else
				memory[line] = (short) ((-1 << 11) | (node.children[1].value << 8) | (node.children[2].value << 4) | (node.children[3].value));
			line++;
			}
		else if (node.tag == AST.CONSTANT) {
			node.line = line;
			}
		else if (node.tag == AST.NOP) {
			line++;
			}
		else
			throw new AssemblerError("Unexpected program organisation");
		}
	}

class AssemblerError extends Exception {
	public AssemblerError() {
        super();
		}
	
	public AssemblerError(String s) {
        super(s);
		}
	}

class AST {
	// ast tags
	public static final int SEQUENCE = 0;
	public static final int ASSEMBLY = 1;
	public static final int CASSEMBLY = 2;
	public static final int INSTRUCTION = 3;
	public static final int CONDITIONAL = 4;
	public static final int CONSTANT = 5;
	public static final int REGISTER = 6;
	public static final int VALUE = 7;
	public static final int NOP = 8;
	
	// assembly tags and mneumonics
	public static final int MOV = 0;		public static final int LDR = 1;
	public static final int STR = 2;		public static final int AND = 3;
	public static final int ORR = 4;		public static final int EOR = 5;
	public static final int ADD = 6;		public static final int ADC = 7;
	public static final int SUB = 8;		public static final int SBC = 9;
	public static final int MLT = 10;		public static final int SHL = 11;
	public static final int SHR = 12;		public static final int ROL = 13;
	public static final int ROR = 14;
	
	public static final String[] ASSEMBLY_MNEUMONICS =
		{"mov", "ldr", "str", "and", "orr", "eor", "add", "adc", "sub", "sbc", "mlt", "shl", "shr", "rol", "ror"};
	
	// conditional tags and mneumonics
	public static final int AL = 0;		public static final int NV = 1;
	public static final int EQ = 2;		public static final int NE = 3;
	public static final int LE = 4;		public static final int LT = 5;
	public static final int GT = 6;		public static final int GE = 7;
	
	public static final String[] CONDITIONAL_MNEUMONICS =
		{"al", "nv", "eq", "ne", "le", "lt", "gt", "ge"};

	// register tags and menumonics
	public static final int A = 0;		public static final int B = 1;
	public static final int C = 2;		public static final int D = 3;
	public static final int JK = 4;		public static final int RT = 5;
	public static final int SP = 6;		public static final int PC = 7;
	
	public static final String[] REGISTER_MNEUMONICS =
		{"a", "b", "c", "d", "jk", "rt", "sp", "pc"};
	
	// keywords
	public static final String[] KEYWORDS =
		{"nop"};
	
	public int tag;
	public AST children[];
	public int value;
	public String spelling;
	public int line;
	
	public AST(int T, AST one, AST two) {
		tag = T;
		children = new AST[2];
		children[0] = one;
		children[1] = two;
		}
	
	public AST(int T, AST one, AST two, AST three) {
		tag = T;
		children = new AST[3];
		children[0] = one;
		children[1] = two;
		children[2] = three;
		}
	
	public AST(int T, AST one, AST two, AST three, AST four) {
		tag = T;
		children = new AST[4];
		children[0] = one;
		children[1] = two;
		children[2] = three;
		children[3] = four;
		}
	
	public AST(int T) {
		tag = T;
		}
	
	public AST(int T, int V) {
		tag = T;
		value = V;
		}
	
	public AST(int T, String S) {
		tag = T;
		spelling = new String(S);
		}
	}