/* $Id$ */ /* * Copyright (c) 2007 Dimitri Sokolyuk * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ /* TuringMachine */ #include #include #include #include #include #include /* tape, head, table, state register */ struct table { struct tulpe *tulpe; int state; char *init; }; struct tulpe { char curst; /* current state */ char ssymb; /* symbol scanned */ char psymb; /* print symbol/erase E/none N */ char move; /* move tape left L/none N/right R */ char newst; /* new state */ struct tulpe *next; }; struct tape { struct cell *head; struct cell *begin; struct cell *end; }; struct cell { char symb; struct cell *left; struct cell *right; }; /* * beaver: A01RB A11LC B01LA B11RB C01LB C11NH */ typedef struct tape Tape; typedef struct cell Cell; typedef struct table Table; typedef struct tulpe Tulpe; char blank = ' '; char init = 'A'; char stop = 'H'; int width = 15; int counter = 0; int cells = 0; Tape *alloctape(char *); Cell *alloccell(void); Table *alloctable(char *); Tulpe *findtulpe(Table *, Cell *); int movehead(Tape *, char); int execute(Tape *, Table *, int); void printtape(Tape *, Tulpe *, int, char); void printtable(Table *); void printtulpe(Tulpe *, char); Tape * alloctape(char *init) { Tape *t; Cell *c; char *s; t = malloc(sizeof(Tape)); assert(t); c = alloccell(); t->head = c; t->begin = c; t->end = c; s = init; if (init != NULL) { while (*s != '\0' && *s != '\n') { t->head->symb = *(s++); movehead(t, 'R'); } while (s-- != init) movehead(t, 'L'); } return t; } Cell * alloccell(void) { Cell *c; c = malloc(sizeof(Cell)); assert(c); c->left = NULL; c->right = NULL; c->symb = blank; ++cells; return c; } Table * alloctable(char *fname) { Table *tab; Tulpe *t, **pt; FILE *fd; char *buf; size_t len; t = NULL; pt = &t; tab = malloc(sizeof(Table)); assert(tab); tab->init = NULL; fd = fopen(fname, "r"); assert(fd); while ((buf = fgetln(fd, &len)) != NULL) { switch (*buf) { case '#': /* commentar */ case '\n': /* empty line */ continue; case '!': /* initial string */ tab->init = calloc(len, sizeof(char)); assert(tab->init); memcpy(tab->init, ++buf, len); continue; case '%': ++buf; init = buf[0]; blank = buf[1]; stop = buf[2]; continue; default: if (len < 5) continue; *pt = malloc(sizeof(Tulpe)); assert(*pt); (*pt)->curst = buf[0]; (*pt)->ssymb = buf[1]; (*pt)->psymb = buf[2]; (*pt)->move = buf[3]; (*pt)->newst = buf[4]; pt = &(*pt)->next; } } fclose(fd); tab->tulpe = t; tab->state = t->curst; return tab; } Tulpe * findtulpe(Table *tab, Cell *cell) { Tulpe *t; for (t = tab->tulpe; t != NULL; t = t->next) { if (tab->state != t->curst) continue; if (cell->symb != t->ssymb) continue; return t; } return NULL; } int movehead(Tape *tape, char move) { Cell *c; switch (move) { case 'L': case 'l': case '<': if (tape->head->left == NULL) { c = alloccell(); tape->head->left = c; c->right = tape->head; tape->begin = c; } tape->head = tape->head->left; break; case 'R': case 'r': case '>': if (tape->head->right == NULL) { c = alloccell(); tape->head->right = c; c->left = tape->head; tape->end = c; } tape->head = tape->head->right; break; case 'N': case 'n': case ' ': default: break; } return 0; } int execute(Tape *tape, Table *tab, int u) { Tulpe *t; if (tab->init != NULL) printtape(tape, NULL, width, '\r'); while (tab->state != stop) { t = findtulpe(tab, tape->head); /* read, find */ if (t == NULL) { fprintf(stderr, "\ncannot find proper tulpe"); exit(1); } tape->head->symb = t->psymb; /* write */ printtape(tape, t, width, '\r'); usleep(u); movehead(tape, t->move); /* move head */ tab->state = t->newst; /* save new state */ ++counter; } printtape(tape, NULL, width, '\n'); return 0; } void printtape(Tape *t, Tulpe *tulpe, int n, char fin) { int i; Cell *c; char *s; char *ps; s = calloc(n + 1 + n, sizeof(char)); for (i = 0; i < n + 1 + n; i++) s[i] = blank; for (i = 0, c = t->head; i < n && c != NULL; i++, c = c->left) s[n - i] = c->symb; for (i = 0, c = t->head; i < n && c != NULL; i++, c = c->right) s[n + i] = c->symb; s[n] = t->head->symb; /* printf("State: %c %c\t", state, move); */ printtulpe(tulpe, '\t'); ps = s; for (i = 0; i < n; i++) printf("%c ", *(ps++)); printf("(%c)", *(ps++)); for (i = 0; i < n; i++) printf(" %c", *(ps++)); printf("%c", fin); fflush(stdout); free(s); } int main(int argc, char **argv) { Tape *tape; Table *table; int delay = 250000; /* TODO: add scroll flag & execution velocity parameter */ if (argc != 2) exit(1); if (**argv == 'f') delay /= 100; /* fast */ table = alloctable(argv[1]); tape = alloctape(table->init); execute(tape, table, delay); printf("halted after %d steps\n", counter); printf("wasted %d cells\n", cells); return 0; } void printtable(Table *tab) { Tulpe *t; for (t = tab->tulpe; t != NULL; t = t->next) { printtulpe(t, '\n'); printf("\n"); } } void printtulpe(Tulpe *t, char fin) { if (t == NULL) printf("\t"); else printf("%c %c %c %c %c", t->curst, t->ssymb, t->psymb, t->move, t->newst); printf("%c", fin); }