Turingol

An excerpt of the document: D.E. Knuth, Semantics of Context-Free Languages, Mathematical Systems Theory (1968), pp127-145 particular to the language can be found here in LaTeX, DVI and postscript forms. I've written a parser in flex and bison (also tested under lex and yacc on Solaris and OSF1). It will interpret the program as well as output a set of tuples that can hopefully be massaged into the input format of some Turing machine simulator. A tarball (64k) (including this file) is available.

Compiling

Simply type `make'; ignore any warnings produced (but tell me about the errors!). Note you'll need an ANSI C compatible compiler (I'm too young to know anything about K&R :-) - a GNU development environment (gcc/flex/bison) is definitely the way to go.

Doing stuff

The input files to the parser have the form described in the document with the addition of perl-style "#" comments. You can also look at some sample programs and the bison grammar for inspiration. The program itself takes the following options:

turingol [-o outfile] [-r runfile] [-d] [sourcefile]

where:

-d

Dump the state of the parser to STDERR (standard bison stuff; very verbose) (default: don't)

-o outfile

Compile the program and write the tuples to outfile (default: don't)
The tuples have the format:

  (this_state, this_symbol, new_symbol, move, new_state)

where move is one of (L)eft, (R)ight or (N)one. The source for a tuple is paraphrased prior to it as a perl-style '#' comment.

-r runfile

Execute the machine and write its output to runfile (default: write to STDOUT)
The output from the interpreter is messy; each pair of lines has the following meaning:

  [state number] operation
  tape contents ||scanned cell|| more of the tape

where the tape contents is every cell ever touched by the tape head.

ChangeLog

December 1998: initial release (1.0.0).
July 2000: Applied Eric Raymond's patch, minor touchups. (1.0.1).

Legal mumblings

    Turingol Parser
    Copyright (C) 1998 Peter Gammie (peteg@cse.unsw.edu.au)

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA