/****************************************************************************
* tm2fsm.c
* David Boozer
* 04 November 2007
*****************************************************************************
* Turing machine compiler; convert .tm to .fsm
****************************************************************************/

#include <stdio.h>

#define NUM_STATES 1000

char jmp_name[NUM_STATES][32];
int jmp_offset[NUM_STATES];

#define NUM 1
#define ARW 2
#define NOP 3
#define JMP 4
#define HLT 5
#define NAME 6

FILE *input_file;

int pass;
int line_num;
int token_val;
int lookahead;

int local_state;
int global_state;
int local_ref;

struct node {
  char name[32];
  int val;
  struct node *next;
};

struct node *head = NULL;

char buffer[32];

void syntax_error () {
  fprintf (stderr, "Error: syntax error in line %d\n", line_num);
  exit (0);
}

/* return the value bound to a name */
int lookup_name (char *name) {
  struct node *ptr;

  ptr = head;
  while (ptr != NULL) {
    if (strcmp (ptr->name, name) == 0)
      return ptr->val;
    ptr = ptr->next;
  }
  fprintf (stderr, "Error in line %d:  name '%s' not defined\n",
	   line_num, name);
  exit (0);
}

/* define a new name and bind it to num */
void define_name (char *name, int num) {
  struct node *ptr, *ptr_last;

  ptr = head;
  while (ptr != NULL) {
    if (strcmp (ptr->name, name) == 0) {
      fprintf (stderr, "Error in line %d: name '%s' already defined\n",
	       line_num, name);
      exit (0);
    }
    ptr_last = ptr;
    ptr = ptr->next;
  }
  ptr = (struct node *) malloc (sizeof (struct node));
  if (head == NULL) head = ptr;
  else ptr_last->next = ptr;
  strcpy (ptr->name, name);
  ptr->val = num;
  ptr->next = NULL;
}

int next_token () {
  char t;
  int i;
  
  while (1) {
    t = getc (input_file);
    if (t == 'R' || t == 'L' || t == '>' || t == EOF) return t;
    else if (isalpha(t)) {
      i = 0;
      while (isalpha(t) || t == '_' || isdigit(t)) {
	buffer[i++] = t;
	t = getc (input_file);
      }
      buffer[i] = '\0';
      if (t != EOF) ungetc (t, input_file);
      if (strcmp (buffer, "hlt") == 0) return HLT;
      else if (strcmp (buffer, "nop") == 0) return NOP;
      else if (strcmp (buffer, "jmp") == 0) return JMP;
      else return NAME;
    }
    else if (isdigit(t)) {
      ungetc (t, input_file);
      fscanf (input_file, "%d", &token_val);
      return NUM;
    }
    else if (t == '-') {
      if (getc (input_file) != '-') syntax_error ();
      if (getc (input_file) != '>') syntax_error ();
      if (pass == 1) printf ("-->");
      return ARW;
    }

    if (pass == 1) printf ("%c", t);

    if (t == ' ' || t == '\t');
    else if (t == '\n') line_num++;
    else if (t == ';') {
      do {
	t = getc (input_file);
	if (pass == 1) printf ("%c", t);
      }
      while (t != '\n' && t != EOF);
      line_num++;
    }
    else return t;
  }
}

void match (int token) {
  if (lookahead == token) lookahead = next_token ();
  else syntax_error ();
}

int parse_bit () {
  int bit;

  if (lookahead == NUM && (token_val == 0 || token_val == 1)) {
    bit = token_val;
    if (pass == 1) printf ("%d", bit);
    match (lookahead);
  }
  else
    syntax_error ();
  return bit;
}

void parse_action () {
  parse_bit ();
  if (lookahead == 'R' || lookahead == 'L') {
    if (pass == 1) printf ("%c", lookahead);
    match (lookahead);
  }
  else syntax_error ();
}

void parse () {
  int new_local_state;
  int n, bit;

  if (lookahead == NAME) {
    if (pass == 0)
      define_name (buffer, (global_state/2)+1);
    else
      printf ("; %s", buffer);
    match (lookahead);
    match (':');
    local_state = 0;
    local_ref = global_state/2;
  }
  else if (lookahead == NUM) {
    if (pass == 1) printf ("%03d", (global_state/2)+1);
    n = token_val;
    match (NUM);
    bit = parse_bit ();
    new_local_state = n<<1 | bit;
    if (new_local_state != local_state++) {
      fprintf (stderr, "Error: table entry skipped in line %d\n", line_num);
      exit (0);
    }
    global_state++;
    match (ARW);

    switch (lookahead) {
    case NUM:
      if (pass == 1) printf ("%03d", token_val+local_ref+1);
      match (NUM);
      parse_action ();
      break;
    case HLT:
      if (pass == 1) printf ("000");
      match (HLT);
      parse_action ();
      break;
    case JMP:
      if (pass == 1)
	printf ("%03d", lookup_name (jmp_name[global_state]) +
		jmp_offset[global_state]);
      match (JMP);
      parse_action ();
      if (pass == 1) printf (";");
      match ('>');
      if (pass == 0) {
	strcpy (jmp_name[global_state], buffer);
	jmp_offset[global_state] = 0;
      }
      if (pass == 1) printf ("%s", jmp_name[global_state]);
      match (NAME);
      if (lookahead == '+') {
	match ('+');
	if (pass == 0) jmp_offset[global_state] = token_val;
	if (pass == 1) printf ("%d", token_val);
	match (NUM);
      }
      break;
    case NOP:
      if (pass == 1) printf ("001 0 R");
      match (NOP);
      break;
    default:
      syntax_error ();
    }
  }
  else syntax_error ();
}

int main (int argc, char *argv[]) {
  if (argc != 2) {
    fprintf (stderr, "Syntax: tm2fsm <input file>\n");
    exit (0);
  }
  input_file = fopen (argv[1], "r");
  if (input_file == NULL) {
    fprintf (stderr, "Error reading from file: %s\n", argv[1]);
    exit (0);
  }

  pass = 0;
  line_num = 1;
  global_state = 0;
  lookahead = next_token ();
  while (lookahead != EOF) parse ();

  rewind (input_file);

  pass = 1;
  line_num = 1;
  global_state = 0;
  lookahead = next_token ();
  while (lookahead != EOF) parse ();

  return 0;
}