Turing Machine Compiler

About

This is a mini-project that grew out of a class assignment. The assignment was to use lex (flex) and YACC (bison) to create a grammar parser for the TL-Delta grammar introduced by Walter Savitch in his book Abstract Machines and Grammars. Having completed the assignment in a trivial amount of time, I thought it would be nice to take the next step forward and produce an executable deterministic turing machine from a supplied grammar, and that is exactly what I've done here.

Implementation

First, a flex file with regular expressions defining TL-Delta tokens was written. Then a bison grammar describing the TL-Delta grammar was defined. Finally, the two files where compiled together to produce a grammar checker.

I then decided that it would be extremely easy to convert the TL-Delta grammar into valid C code, which I accomplished with a second pass from flex which parsed out the tokens that I needed to define. A C++ wrapper to handle input was written. The wrapper file also defined the basic turing machine operations: move left, move right, read from the tape, and write to the tape. The output from the second flex pass was plugged into a function in the wrapper code via #include. The wrapper is then compiled into an executable.

Download

The following software is being released under a BSD-style license.

tmc-2004.12.tar.gz 8K 7dd4f38038a513c445ac4e3ac892bd748a05e30a (sha-1)
tmc-2004.12.zip 16K cedb1062b5621316ab1340c43243abed55039756 (sha-1)

Usage

To compile the Turing Machine Compiler use "make".

To compile a TL-Delta grammar file into a deterministic turing machine executable:

./tmc grammar1

Where grammar1 is the name of the grammar file to be compiled. The output is an executable named grammar1.tm. Here is a sample grammar.

There are two choices for running the Turing Machine executable:

(1) ./grammar1.tm "input string" [...]

(2) ./grammar1.tm --files <filename> [...]

Use --files for larger input sizes.

The output for (1) above is in the form:

[1] ACCEPT 'output string'
[2] REJECT 'output string'

Where the number in the brackets is the argument number passed into the machine, and the output string is printed between 's.

The output of (2) above is in the form:

[1] ACCEPT <filename.out>
[2] REJECT <filename2.out>

Where the output tape is named the same as the input tape with the addition of the .out suffix.

Known Bugs and Limitations

Currently, the supported input/output tape size is limited (this is true when the input strings are passed in on the command line - no such limitation exists when the inputs are passed as files, though one's hard drive size represents the upper bound for the size of the string that can be processed), so a decent approximation for large input sizes is not currently possible.

TODO

Add a command line option for compiling the machines as Linear Bounded Automata (LBA).
Add support for separate/multiple input/output tapes.