thanks,
Brian
<<inline: ncurses.png>>
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <curses.h> #include <unistd.h>
#include "turing.h"
/* displays a menu to the user */
void display_menu()
{
clear();
slk_restore();
slk_set(1,"AddRule",0);
slk_set(2,"DelRule",0);
slk_set(3,"Load",0);
slk_set(4,"SetState",0);
slk_set(5,"ClrTape",0);
slk_set(6,"Step",0);
slk_set(7,"Run",0);
slk_set(8,"Quit",0);
slk_set(9,"",0); /* get rid of the Break label if it exists */
slk_refresh();
}
/* prints the tape, including several spaces on either side of the r/w head */
void print_tape(tape_t t)
{
int n;
int first;
int last;
for (n=0; n<(COLS/2); n++)
printw(" ");
printw("\\=/\n");
first=t.pos - (COLS/4);
last=t.pos + (COLS/4);
for (n=first; n<last; n++)
printw("|%c",t.data[n]);
}
/* displays the state */
void print_state(int s,int o)
{
char str[30]="";
sprintf(str,"State: %d\tPrevious State: %d\n",s,o);
printw(str);
}
/* input a new state from the user */
int get_new_state()
{
int result;
char str[1000]={0}; /* FIXME vulnerable to buffer overflows */
clear();
printw("Enter new state: ");
echo();
getstr(str);
noecho();
sscanf(str,"%d",&result);
return result;
}
/* notify user that the tape is halted */
void do_halt()
{
char str[1000]={0}; /* FIXME vulnerable to buffer overflows */
clear();
printw("No rule corresponding to current state; machine halted\n");
printw("press Enter:\n");
getstr(str);
ungetch(KEY_F(9)); /* so the machine will halt if it is runningt */
}
/* initial setup */
void init_tm(turing_machine_t *tm)
{
/* set up the tape */
tm->tape.size=100;
tm->tape.data=malloc(tm->tape.size * sizeof (char));
memset(tm->tape.data,' ',tm->tape.size);
tm->tape.pos=50; /* start in the middle */
/* set up the rules */
tm->ruleset.num_rules=0;
tm->ruleset.rules=calloc(1 ,sizeof (rule_t));
/* set up the state */
tm->state=0;
tm->old_state=0;
}
/* make the tape larger by adding blank spaces at the begging */
void grow_tape_left (tape_t *t)
{
int grow_size = 5000; /* as good a number as any */
t->data=realloc(t->data,t->size + grow_size);
memmove(t->data+grow_size, t->data,t->size);
memset(t->data,' ',grow_size); /* fill new area with spaces */
t->size += grow_size;
t->pos += grow_size; /* since we added to beginning of tape, before pos */
}
/* grow the tape to the right. */
void grow_tape_right(tape_t *t)
{
int grow_size = 5000; /* as good a number as any */
t->data=realloc(t->data,t->size + grow_size);
memset(t->data+t->size,' ',grow_size); /* fill the new area with spaces */
t->size += grow_size;
}
/* move the head one space to the left, growing as needed */
void move_left(tape_t *t)
{
if (t->pos <= COLS) /* print_tape needs to be able to peek ahead */
grow_tape_left(t);
t->pos --;
}
/* move one space to the right, growing as needed */
void move_right(tape_t *t)
{
if ((t->size - t->pos) <= COLS) { /* COLS / 2 would really be enough */
grow_tape_right(t);
}
t->pos ++;
}
/* write a character to the tape in the current position */
void tape_write(tape_t *t, char c)
{
if (isprint(c))
t->data[t->pos]=c;
}
/* read a character from the tape at the current position */
void tape_read(tape_t t, char *c)
{
*c = t.data[t.pos];
}
/* gets a rule from the user */
rule_t input_rule ()
{
rule_t r;
char str[1000]; /* FIXME vulnerable to buffer overflows */
char dir;
clear();
printw("Use the following syntax for rules:\n");
printw("S0 R S1 W M\n");
printw("where:\n");
printw("S0 = current state\n");
printw("R = symbol to read\n");
printw("S1 = new state\n");
printw("W = symbol to write\n");
printw("M = movement, one of L, R, or S (Left, Right, Stay)\n");
printw("use _ to represent a blank space.\n");
printw("Enter rule: ");
echo();
getstr(str);
noecho();
sscanf(str,"%d %c %d %c %c",
&(r.cur_state), &(r.read), &(r.new_state), &(r.write), &dir);
if ((toupper(dir)=='L') || (dir=='<'))
r.direction=LEFT;
else if ((toupper(dir)=='R') || (dir=='>'))
r.direction=RIGHT;
else
r.direction=STAY;
if (r.read=='_')
r.read=' ';
if (r.write=='_')
r.write=' ';
return r;
}
/* display (a subset of) the rules */
void display_rules(ruleset_t r, int hilite)
{
int n;
int start_rule_num=0,end_rule_num=r.num_rules;
int num_rows = LINES - 4; /* save room for menu, tape display etc. */
if (r.num_rules > num_rows) {
if (hilite <=(num_rows / 2))
start_rule_num=0;
else if ((r.num_rules - hilite) <= (num_rows / 2))
start_rule_num=r.num_rules - num_rows;
else
start_rule_num = hilite - num_rows / 2;
end_rule_num=start_rule_num + num_rows;
}
printw("%d %s:\n",r.num_rules, (r.num_rules != 1) ? "rules" : "rule");
for (n=start_rule_num; n<end_rule_num; n++) {
printw("%d %c %d %c %s",
r.rules[n].cur_state,
(r.rules[n].read==' ') ? '_' : r.rules[n].read,
r.rules[n].new_state,
(r.rules[n].write==' ') ? '_' : r.rules[n].write,
(r.rules[n].direction==LEFT) ? "LEFT" :
(r.rules[n].direction==RIGHT) ? "RIGHT" :
"STAY");
if (n == hilite)
printw(" <--\n");
else
printw("\n");
}
}
/* adds a rule to the rule set */
int insert_rule(ruleset_t *rs, rule_t r)
{
int n;
int valid_rule = 1;
for (n=0;n<rs->num_rules;n++)
if((rs->rules[n].read==r.read) && (rs->rules[n].cur_state ==
r.cur_state))
valid_rule = 0;
if (!valid_rule) {
printw("Error, conflict with an existing rule: %d %c %d %c %s\n",
r.cur_state,
r.read,
r.new_state,
r.write,
(r.direction==LEFT) ? "LEFT" :
(r.direction==RIGHT) ? "RIGHT" :
"STAY");
return 0;
} else {
rs->num_rules++;
rs->rules=realloc(rs->rules,rs->num_rules * sizeof r);
rs->rules[rs->num_rules-1]=r; /* because we start at 0 */
return 1;
}
}
void bulk_insert_rules(ruleset_t *rs)
{
char str[1000]; /* FIXME vulnerable to buffer overflows */
clear();
printw("Enter name of rule file: ");
echo();
getstr(str);
noecho();
while (! load_rules_from_file(str,rs)) {
printw("Unable to open file \"%s\", please try again.\n",str);
printw("Enter name of rule file: ");
echo();
getstr(str);
noecho();
}
}
int load_rules_from_file(const char *flnm, ruleset_t *rs)
{
rule_t r;
char dir;
FILE *f;
f=fopen(flnm,"ro");
if (f == NULL)
return 0;
while (! feof(f)) {
fscanf(f,"%d %c %d %c %c",
&(r.cur_state), &(r.read), &(r.new_state), &(r.write),
&dir);
if ((toupper(dir)=='L') || (dir=='<'))
r.direction=LEFT;
else if ((toupper(dir)=='R') || (dir='>'))
r.direction=RIGHT;
else
r.direction=STAY;
if (r.read=='_')
r.read=' ';
if (r.write=='_')
r.write=' ';
insert_rule(rs,r);
}
return 1;
}
/* delete a rule from the rule set */
void delete_rule (ruleset_t *rs, int rule_num)
{
/* don't delete if there are no rules */
if (rs->num_rules >= 1) {
/* shift all the elements in the array down one */
memmove(rs->rules + rule_num,rs->rules + rule_num + 1,(rs->num_rules -
rule_num) * sizeof (rule_t));
rs->num_rules --;
rs->rules=realloc(rs->rules,rs->num_rules * sizeof (rule_t));
}
}
/* check to see if the current conditions match any rule in the set */
int match_rule(tape_t t, ruleset_t r, int st)
{
char current;
int n;
tape_read(t,¤t);
for (n=0;n<r.num_rules;n++)
if ((r.rules[n].read == current) && (r.rules[n].cur_state == st))
return n;
return -1; /* no rule matched */
}
/* set the tape to all blanks. */
void clear_tape(tape_t *t)
{
memset(t->data,' ',t->size);
}
/* perform action specified by rule */
int execute_rule(tape_t *t, rule_t r)
{
tape_write(t,r.write);
if (r.direction==LEFT)
move_left(t);
if (r.direction==RIGHT)
move_right(t);
return r.new_state;
}
/* run the machine one step */
int single_step(turing_machine_t *tm)
{
int result=0;
result=match_rule(tm->tape,tm->ruleset, tm->state);
if (result != -1) {
tm->old_state = tm->state;
tm->state=execute_rule(&(tm->tape),tm->ruleset.rules[result]);
} else
do_halt();
return result;
}
/* run the machine until halted, or forever if it doesn't halt */
int auto_run(turing_machine_t *tm)
{
int current_rule=0;
int n=0;
while (1) {
/* usleep(1); */
current_rule=single_step(tm);
clear();
for (n=1;n<=8;n++)
slk_set(n,"",0); /* clear the function keys */
slk_set(9,"Break",0);
slk_refresh();
print_tape(tm->tape);
print_state(tm->state, tm->old_state);
display_rules(tm->ruleset,current_rule);
printw("\nRunning, press F9 to stop");
refresh();
nodelay(stdscr,TRUE); /* make the getch non-blocking */
if (getch()==KEY_F(9)) {
nodelay(stdscr,FALSE);
nocbreak(); /* get out of half-delay mode */
cbreak();
printw("Stopped\n");
refresh();
return current_rule;
}
}
nocbreak(); /* get out of half-delay mode */
cbreak();
}
/* curses setup */
void do_ncurses_setup()
{
slk_init(3); /* enhanced PC-style function key line */
initscr();
cbreak();
noecho();
nonl();
intrflush(stdscr, FALSE);
keypad(stdscr, TRUE);
curs_set(0); /* hide the cursor */
}
int main(int argc,char* argv[])
{
turing_machine_t my_tm;
int choice=0;
int highlight=0;
int old_highlight=0;
init_tm(&my_tm);
do_ncurses_setup();
if (argc == 2)
if (! load_rules_from_file(argv[1], &(my_tm.ruleset))) {
fprintf(stderr,"Error loading file: %s\n",argv[1]);
return EXIT_FAILURE;
}
while (choice != KEY_F(8)) {
display_menu();
print_tape(my_tm.tape);
print_state(my_tm.state,my_tm.old_state);
display_rules(my_tm.ruleset, highlight);
choice=getch();
switch (choice) {
case KEY_LEFT:
move_left(&(my_tm.tape));
break;
case KEY_RIGHT:
move_right(&(my_tm.tape));
break;
case KEY_UP:
if (my_tm.ruleset.num_rules >= 1)
highlight = (highlight +
my_tm.ruleset.num_rules - 1) % my_tm.ruleset.num_rules;
break;
case KEY_DOWN:
if (my_tm.ruleset.num_rules >= 1)
highlight = (highlight + 1) %
my_tm.ruleset.num_rules;
break;
case KEY_F(1):
case KEY_IC:
while (! insert_rule(&(my_tm.ruleset),input_rule()))
; /* do nothing until a valid rule is input */
break;
case KEY_F(2):
case KEY_DC:
delete_rule(&(my_tm.ruleset),highlight);
if (my_tm.ruleset.num_rules >= 1)
highlight = highlight %
my_tm.ruleset.num_rules;
else
highlight = 0;
break;
case KEY_F(3):
bulk_insert_rules(&(my_tm.ruleset));
break;
case KEY_F(4):
my_tm.state=get_new_state();
break;
case KEY_F(5):
clear_tape(&(my_tm.tape));
break;
case KEY_F(6):
old_highlight=highlight;
highlight=single_step(&my_tm);
if (highlight==-1)
highlight=old_highlight;
break;
case KEY_F(7):
old_highlight=highlight;
highlight=auto_run(&my_tm);
if (highlight==-1)
highlight=old_highlight;
break;
case KEY_F(8):
case KEY_F(9):
case KEY_F(10):
case KEY_F(11):
case KEY_F(12):
break;
default: /* if no special key entered, it must be a regular
char, so put it on the tape and keep going */
tape_write(&(my_tm.tape),choice);
move_right(&(my_tm.tape));
}
}
free(my_tm.tape.data);
free(my_tm.ruleset.rules);
endwin(); /* free all the curses stuff */
return EXIT_SUCCESS;
}
#ifndef TURING_H
#define TURING_H
struct tape_struct {
char *data;
size_t size;
int pos;
}
typedef tape_t;
struct rule_struct {
int cur_state;
char read;
int new_state;
char write;
enum {LEFT,RIGHT, STAY} direction;
}
typedef rule_t;
struct ruleset_struct {
int num_rules;
rule_t *rules;
}
typedef ruleset_t;
/* the formal definition of a turing machine also includes an alphabet. */
struct turing_machine_struct {
tape_t tape;
ruleset_t ruleset;
int state;
int old_state; /* not strictly required, but makes life easier */
}
typedef turing_machine_t;
void do_ncurses_setup();
void display_menu();
void print_tape(tape_t t);
void print_state(int s, int o);
int get_new_state();
void display_rules(ruleset_t, int hilite);
void do_halt();
void init_tm(turing_machine_t *tm);
void grow_tape_left (tape_t *t);
void grow_tape_right(tape_t *t);
void move_left(tape_t *t);
void move_right(tape_t *t);
void tape_write(tape_t *t, char c);
void tape_read(tape_t t, char *c);
int insert_rule(ruleset_t *rs, rule_t r);
int load_rules_from_file(const char *flnm, ruleset_t *rs);
void bulk_insert_rules(ruleset_t *rs);
void delete_rule (ruleset_t *rs, int rule_num);
int match_rule(tape_t t, ruleset_t r, int st);
void clear_tape(tape_t *t);
int execute_rule(tape_t *t, rule_t r);
int single_step(turing_machine_t *tm);
int auto_run(turing_machine_t *tm);
#endif
-- Unsubscribe info: http://cygwin.com/ml/#unsubscribe-simple Bug reporting: http://cygwin.com/bugs.html Documentation: http://cygwin.com/docs.html FAQ: http://cygwin.com/faq/
