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
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.
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
bison stuff; very verbose) (default: don't)
- 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.
- Execute the machine and write its output to
runfile (default: write to
The output from the interpreter is messy; each pair of lines has the
[state number] operation
tape contents ||scanned cell|| more of the tape
where the tape contents is every cell ever touched by the tape head.
- December 1998: initial release (1.0.0).
- July 2000: Applied Eric Raymond's patch, minor touchups. (1.0.1).
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
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