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.


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]


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.


Legal mumblings

    Turingol Parser
    Copyright (C) 1998 Peter Gammie (peteg at unsw dot edu dot 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
    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