CS 342 Turing machine simulator design % $Header: ce.equ,v 1.4 90/03/24 14:07:41 leavens Exp $ % State labels are represented by integers label = int % constants used in the syntax prog_separators = "()" % self-delimiting tokens (chars) in programs tape_separators = "" % semantic constants simulated_blank = '_' % the "blank" character on the tapes. % options (you don't have to implement or use these) tracing = false % should trace output be produced? % $Header: simulate.clu,v 1.3 90/03/24 14:08:16 leavens Exp $ % CS342 turing machine simulator % % AUTHOR: start_up = proc() % MODIFIES: stream$primary_input(), stream$primary_output(), % stream$error_output() % REQUIRES: primary input contains a turing machine program % and an initial tape (the syntax is in the course handout). % EFFECT: if the turing machine encoded by the program halts, % the output is the final tape (see the course handout). end start_up % $Header: program.spc,v 1.3 90/03/24 14:07:57 leavens Exp $ program = cluster is parse, delta % OVERVIEW: The transition function of a turing machine (immutable) % % Abstractly, a program is a mapping from (state-label, read-char) pairs % to (state-label, write-char, direction) triples. % % AUTHOR: Gary T. Leavens rep = null parse = proc(tks: tok_stream) returns(program, label) signals(syntax_error) % MODIFIES: tks % EFFECT: consume and return the mapping described by the program on tks, % and the program's initial label (as specified in the handout). % Signal syntax_error if the input is not in the proper format. end parse delta = proc(p: program, ip: label, r: char) returns(label, char, proctype(tape) signals(run_time_error)) signals(halt) % EFFECT: if p is not defined for ip and r, signal halt; % otherwise, return the next state label, the character to write, % and a procedure that moves the tape head left or right. end delta end program % $Header: instr.spc,v 1.3 90/03/24 14:07:51 leavens Exp $ instr = cluster is parse, unparse, get_label, get_read_char, get_write_char, get_next_state, get_direction % OVERVIEW: Turing machine program instructions (immutable) % % The parts of an instruction are its label, read character, % write character, direction, and next state. % % AUTHOR: Gary T. Leavens rep = null parse = proc(tks: tok_stream) returns(instr) signals(syntax_error) % MODIFIES: tks % EFFECT: consume and return the next instruction on tks % (see handout for syntax). % Signal syntax_error if the input is not in the proper format. end parse unparse = proc(i: instr) returns(string) % EFFECT: Return the external representation of i; % that is, a string that when parsed will be the same as i. % Note: you do not need to implement this operation, % but it may be useful for debugging. end unparse get_label = proc(i: instr) returns(label) % EFFECT: Return the label of i. end get_label get_read_char = proc(i: instr) returns(char) % EFFECT: Return the read character of i. end get_read_char get_write_char = proc(i: instr) returns(char) % EFFECT: Return the write character of i. end get_write_char get_next_state = proc(i: instr) returns(label) % EFFECT: Return the next state of i. end get_next_state get_direction = proc(i: instr) returns(proctype(tape) signals(run_time_error)) % EFFECT: Return the direction of i, % which is either tape$move_left or tape$move_right. end get_direction end instr % $Header: tape.spc,v 1.3 90/03/24 14:08:00 leavens Exp $ tape = cluster is parse, unparse, read, write, move_left, move_right % OVERVIEW: A unbounded tape of characters % with a position at which characters are read and written (mutable). % % AUTHOR: Gary T. Leavens rep = null parse = proc(tks: tok_stream) returns(tape) signals(syntax_error) % MODIFIES: tks % EFFECT: consume and return a new tape containing the characters in tks % (syntax in the course handout). % Signal syntax_error if the input is not in the proper format. end parse unparse = proc(t: tape) returns(string) % EFFECT: return a string that has as its ith character the ith char of t. end unparse read = proc(t: tape) returns(char) % EFFECT: Return the character at the current position of t. end read write = proc(t: tape, c: char) % MODIFIES: t % EFFECT: Make c be the character at the current position of t. end write move_left = proc(t: tape) signals(run_time_error) % MODIFIES: t % EFFECT: If the current position of t is at the extreme left, % then signal run_time_error; % otherwise make the position of t be one cell to the left of % the position before the call to this operation. end move_left move_right = proc(t: tape) signals(run_time_error) % MODIFIES: t % EFFECT: If the current position of t is at the extreme right, % then first add a blank character to the right of t; % make the position of t be one cell to the right of % the position before the call to this operation. end move_right end tape % $Header: tok_stream.spc,v 1.4 90/03/24 13:41:19 leavens Exp $ tok_stream = cluster is create, match, peek, next, at_end % OVERVIEW: A stream of tokens obtained from a stream of characters (mutable) % % A token is a one-character string consisting of a separator (user-specified) % or string of consecutive characters, none of which % is a white-space character (blank, tab, or newline). % A token is thus defined by the following grammar: % ::= * | % % Abstractly a tok_stream consists of a stream of tokens and a error message % procedure. A stream is characterized as a list of items % (tokens in this case), the first of which is the "next" item. % Consuming an item means that one removes the first item from the list. % % The stream of tokens is generated piece-by-piece, with the next token only % being read from the input when needed. % % AUTHOR: Gary T. Leavens rep = null create = proc(str: stream, separators: string, errormsg: proctype(string)) returns(tok_stream) % REQUIRES: str is open for reading % EFFECT: return a new token stream consisting of all the tokens in str % with the elements of separators as the set of separator chars, % that will use errormsg to print error messages. end create match = proc(tks: tok_stream, s: string) signals(syntax_error) % MODIFIES: tks, whatever stream errormsg writes % EFFECT: If there is no next token of tks, write an error message % using the error message component of tks % and signal syntax_error. % Otherwise let t be the next token of tks. % If s = t, consume the next token of tks (i.e., t) and return; % otherwise, consume the token, write an error message % with "expecting "||s as the argument, and signal syntax_error. end match next = proc(tks: tok_stream) returns(string) signals(none) % MODIFIES: tks % EFFECT: consume and return the next token from tks; % signal none if there is no next token available. end next peek = proc(tks: tok_stream) returns(string) signals(none) % EFFECT: return the next token from tks without consuming it; % signal none if there is no next token available. end peek at_end = proc(tks: tok_stream) returns(bool) % EFFECT: Are there no more tokens left in tks? end at_end end tok_stream % $Header: tape_char.spc,v 1.1 90/03/24 13:39:20 leavens Exp $ tape_char = proc(c: char) returns(bool) % EFFECT: is c a simulated blank, digit or alphabetic character? end tape_char % $Header: errormsg.spc,v 1.1 90/03/18 13:48:40 leavens Exp $ errormsg = proc(s: string) % MODIFIES: stream$error_output() % EFFECT: Print an error message to standard error output. end errormsg