/* Compile arithmetic expressions into TOY code. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct tree {
	int op;
	struct tree *left, *right;
};
typedef struct tree Tree;

/* maketree - return a tree with the given arguments */
Tree *maketree(int op, Tree *left, Tree *right) {
	Tree *t = malloc(sizeof (Tree));

	t->op = op;
	t->left = left; t->right = right;
	return t;
}

char *input;		/* the "source code" */
int pos;		/* current position in input */

/* get - return the next token if it's in set and advance pos */
int get(char set[]) {
	while (isspace(input[pos]))
		pos++;
	if (input[pos] != '\0' && strchr(set, input[pos]) != NULL)
		return input[pos++];
	fprintf(stderr, "syntax error: expected one of '%s'\n", set);
	return 0;
}

/* look - return the next nonblack character, but don't advance */
int look(void) {
	while (isspace(input[pos]))
		pos++;
	return input[pos];
}

/* expr - parse an expression, return its tree */
Tree *expr(void) {
	Tree *t;

	if (look() == '(') {		/* expr -> ( expr ) */
		get("("); t = expr(); get(")");
	} else if (isdigit(look()))	/* expr -> constant */
		t = maketree(get("0123456789"), NULL, NULL);
	else				/* expr -> identifier */
		t = maketree(get("abcdefghijklmnopqrstuvwxyz"), NULL,NULL);
	if (look() != '\0' && strchr("+-*", look()) != NULL) {
		int op = get("+-*");	/* expr -> expr [+-*] expr */
		t = maketree(op, t, expr());
	}
	return t;
}

/* pgm - parse the input, return its tree */
Tree *pgm(char *string) {
	Tree *t;

	input = string;		/* initialize lexical analyzer */
	pos = 0;
	t = expr();		/* pgm -> expr */
	if (look() != '\0')  {
		fprintf(stderr, "expected end of input\n");
		exit(1);
	}
	return t;
}

/* postorder - print the tree t in postorder */
void postorder(Tree *t) {
	if (t != NULL) {
		postorder(t->left);
		postorder(t->right);
		fprintf(stderr, "%c", t->op);
	}
}

/* codegen - generate code beginning at loc to evaluate t into
   register dst; return the updated value of loc */
int codegen(Tree *t, int dst, int loc) {
	if (isalpha(t->op)) {
		int addr = t->op - 'a';
		if (addr > 15) {
			printf("%02X: B%X%02X\tR%d <- %02X\n", loc++,
				dst, addr, dst, addr);
			printf("%02X: 9%X%X%X\tR%d <- M[R%d+%d]\n", loc++,
				dst, dst, 0, dst, dst, 0);
		} else
			printf("%02X: 9%X%X%X\tR%d <- M[R%d+%d]\n", loc++,
				dst, 0, addr, dst, 0, addr);
	} else if (isdigit(t->op))
		printf("%02X: B%X%02X\tR%d <- %d\n", loc++,
			dst, t->op - '0', dst, t->op - '0');
	else {
		loc = codegen(t->left, dst, loc);
		loc = codegen(t->right, dst + 1, loc);
		printf("%02X: %X%X%X%X\tR%d <- R%d %c R%d\n", loc++,
			strchr("+1-2*3", t->op)[1] - '0', dst,
			dst, dst + 1, dst, dst, t->op, dst + 1);
	}
	return loc;
}

int main(int argc, char *argv[]) {
	Tree *e;
	int i, loc = 0;

	for (i = 1; i < argc - 1; i++)
		printf("%02X: %04X\n", loc++, atoi(argv[i]));
	if (i < argc) {
		e = pgm(argv[i]);
		postorder(e);
		fprintf(stderr, "\n");
		loc = codegen(e, 1, 26);
		printf("%02X: 4102\tprint R%d\n", loc++, 1);
		printf("%02X: 0000\thalt\n", loc);
		printf("%02X\n", 26);
	}
	return 0; 
}