/****************************************************************************
* tm.c
* David Boozer
* (v1.0) March 30, 1999
* (v1.1) April 28, 2000
* 06 November 2007 (modified)
*****************************************************************************
* Turing machine simulator.
****************************************************************************/

#include <stdio.h>

#define TAPE_LEN 10000
#define OFFSET 2000
#define NUM_FSM_STATES 256

#define NUM 1
#define ARW 2
#define RL  3

int line_num = 1;
int token_val;
int lookahead;

FILE *input_file;

int fsm[2*NUM_FSM_STATES];

typedef struct {
  int head_pos;
  int fsm_state;
  char tape[TAPE_LEN];
} tm_state;

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

int next_token () {
  char t;
  
  while (1) {
    t = getc (input_file);
    if (t == ' ' || t == '\t') ;
    else if (t == '\n') line_num++;
    else if (t == ';') {
      do
	t = getc (input_file);
      while (t != '\n' && t != EOF);
      line_num++;
    }
    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 ();
      return ARW;
    }
    else if (t == 'R' || t == 'L') {
      token_val = t;
      return RL;
    }
    else if (t == EOF) return EOF;
    else syntax_error ();
  }
}

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

int match_index () {
  int fsm_state, bit;

  fsm_state = token_val;
  match (NUM);
  bit = token_val;
  match (NUM);
  if (bit != 0 && bit != 1) syntax_error ();
  return fsm_state<<1 | bit;
}

void parse () {
  int index, n;
  static next_index = 2;
  
  index = match_index ();
  if (index != next_index++) {
    fprintf (stderr, "Error: fsm entry skipped in line %d\n", line_num);
    fclose (input_file);
    exit (0);
  }
  match (ARW);
  n = match_index ();
  if (token_val == 'R') fsm[index] = n<<1 | 0;
  if (token_val == 'L') fsm[index] = n<<1 | 1;
  match (RL);
}

void load_fsm (char *file_name) {

  input_file = fopen (file_name, "r");
  if (input_file == NULL) {
    fprintf (stderr, "Error: cannot load file %s\n", file_name);
    exit (0);
  }

  lookahead = next_token ();
  while (lookahead != EOF) parse ();

  fclose (input_file);
}

void initialize_state (char *file_name, tm_state *state_ptr) {
  char *tape, t;
  int i;

  input_file = fopen (file_name, "r");
  if (input_file == NULL) {
    fprintf (stderr, "Error: cannot load file %s\n", file_name);
    exit (0);
  }

  tape = state_ptr->tape;
  for (i=0; i<OFFSET; i++) tape[i] = 0;
  do {
    t = fgetc (input_file);
    if (t == '0') tape[i++] = 0;
    if (t == '1') tape[i++] = 1;
  }
  while (t != EOF);
  for (; i<TAPE_LEN; i++) tape[i] = 0;

  fclose (input_file);

  state_ptr->head_pos = OFFSET;
  state_ptr->fsm_state = 1;
}

void print_tape (tm_state *state_ptr) {
  char *tape;
  int i;
  
  tape = state_ptr->tape;
  for (i=0; i<TAPE_LEN && tape[i]==0; i++);
  if (i >= state_ptr->head_pos)
    printf ("0");
  else
    for (; i<state_ptr->head_pos; i++) printf ("%c",  tape[i] ? '1' : '0');
  printf ("\n");
}

void simulate_tm (tm_state *state_ptr) {
  int action, fsm_state, head_pos;
  char *tape;

  head_pos = state_ptr->head_pos;
  fsm_state = state_ptr->fsm_state;
  tape = state_ptr->tape;

  do {
    action = fsm[fsm_state<<1 | tape[head_pos]];
    fsm_state = action>>2;
    tape[head_pos] = action>>1 & 1;
    if ((action & 1) == 0) head_pos++;
    if ((action & 1) == 1) head_pos--;
  }
  while (fsm_state != 0 && head_pos >= 0 && head_pos < TAPE_LEN);

  if (fsm_state == 0) {
    state_ptr->head_pos = head_pos;
    state_ptr->fsm_state = fsm_state;
    return;
  }
  else {
    fprintf (stderr, "Error: head exceeded tape bounds\n");
    exit (0);
  }
}

int main (int argc, char *argv[]) {
  tm_state state;

  if (argc != 3) {
    fprintf (stderr, "syntax: tm <machine file> <tape file>\n");
    exit (0);
  }

  load_fsm (argv[1]);
  initialize_state (argv[2], &state);
  simulate_tm (&state);
  print_tape (&state);

  return 0;
}