TMSLTMSL_Project_Report.pdfTMSL (TURING MACHINE SIMULATION LANGUAGE) Language Manual and Project Report Isaac McGarvey (iam2108) Joshua Gordon (jbg2109) Keerti Joshi (kj2217) Snehit Prabhu (sap2131)Table of Contents 1. Introduction 1.1.1. Overview 01 1.1.2. Example 01 2. Language Tutorial 2.1 Compilation and Execution 02 3. Language Manual 3.1. Lexical Conventions 03 3.2 Declarations 04 3.3 Statements 04 4. Project Plan 4.1 Process 09 4.2 Programming Style 09 4.3 Project Timeline 09 4.4 Roles and Responsibilities 10 4.5 Development Environment 10 4.6 Project Log 10 5. Architectural Design 5.1 Block Diagram of Translator 11 5.2 Description of Architecture 11 6. Testing Plan 6.1 Compiler tests 13 6.2 Machine tests 13 6.3 End-to-end tests 13 6.4 Examples 13 7. Lessons Learned 18 8. Appendix 191 1. Introduction 1.1.1. Overview A Turing Machine is a simple but powerful computer. It is useful in thinking about the nature and limits of computability because its method of computation is about as simple as can be imagined. Important theoretical results about what can be computed that are expressed in the terms of Turing Machines are clearer to intuition than the same results expressed in other terms. The Turing Machine is an automaton whose temporary storage is a tape. This tape is divided into cells each of which is capable of holding one symbol. Associated with the tape is a read-write head that can travel left of write on the tape and that can read or write a single symbol on each move. The automaton that we use as a Turing Machine will have neither an input file nor any special output mechanism. Whatever input and output is necessary will be done on the machine's tape. The Turing Machine Simulation Language (TMSL) is a programming language that is designed allow users to write programs that will be compiled into a Turing Machine that can execute the program. Because Turing Machines are very different from normal computers and also far more restrictive in terms of the number of available operations, TMSL is very different from a typical imperative programming language. Programming a Turing Machine by specifying states and transitions is analogous to programming a modern computer in assembly, at best. We hope that TMSL will be a high-level language (relatively speaking) for Turing Machines. 1.1.2. Example As an example program we begin with the following which demonstrates unsigned addition. Comments and bracketing are c-style. Notice that the alphabet is specified on the first line of the program. This is mandatory, and serves the purpose of describing those symbols which may be written to and read from the tape. The empty symbol "_" is included by default. /* alphabet specification */ 0,1 /* true while the symbol under the tape head is 1 */ while (1){ /* move the tape head one position to the right */ right /* if the symbol under the tape head is 0 */ if (0){ /* move the tape head one position to the right */ right /* if the symbol under the tape head is 1 */ if (1){ write 0 /* replace the current symbol under the tape head with 0 */ left /* move the tape head one position to the left */ write 1 /* replace the current symbol under the tape head with 1 */ } } }2 2. This chapter represents a tutorial for a novice to get started with TMSL. 2.1 Compilation and Execution A TMSL program consists initially of a plain text ".tmsl" file, which contains the user defined program. For now, let us consider the example program of 1.1.3, unsigned addition. Let us call this file "unsignedAdd.tmsl". While this file alone is a complete specification of a TMSL program, typically the user must also specify 1) the input tape for the Turing machine which is to execute the program, and 2) the output tape file, which is a blank target file overwriten with the final state of the tape when a Turing machine executes its program. As a convention, the input and output tape are given the extensions ".tape". The input tape is a plain text file of format: "L "*, where L is a symbol in the alphabet specified in the user program, followed by a space, repeated zero or more times. For instance, to add the numbers four and two, we specify an input.tape file as "1 1 1 1 0 1 1" (the contents of the input.tape are program specific). For the output tape, we specify a blank file, "output.tape". Compilation: given "unsignedAdd.tmsl", we compile the program by: ".\compiler\compiler.exe unsignedAdd.tmsl transition.tm", where unsignedAdd.tmsl is the user specified program, and "transition.tm" is the target output file to contain the resulting compiled state transition table. Execution: given "transition.tm", "input.tape", and "output.tape", a user may execute the program on a turning machine by ".\machine\machine.exe transition.tm input.tape output.tape". The output.tape file will be transformed into a plain text file containing the final state of the tape. For convenience, we have included "run.bat" in the root TMSL directory. Run is a small batch file which automates the steps necessary to compile and execute user defined TMSL programs. To compile, execute, and display the final state of the tape, the user may command "run.bat unsignedAdd.tmsl input.tape output.tape" Language Tutorial3 3. Language Manual 3.1 Lexical Conventions 3.1.1 Tokens There are three types of tokens in this language: identifiers (symbols), keywords,and separators. Tokens are whitespace delineated. 3.1.2 Comments TMSL supports multi-line comments. A section of text beginning with /* and ending with */ is a comment. An example comment is as follows: /* this is a comment */ /* this is another comment */ 3.1.3 Symbols Symbols are values / identifiers that can be read from and written to the tape. A symbol is represented by a sequence of letters and digits. Letters are not case sensitive. <symbol> = ['a'-'z' 'A'-'Z' '0'-'9']+ The only only special symbol is the symbol / keyword '_' (to represent a blank). All uninitialized cells of the tape contain the blank symbol. As with any other
View Full Document
Unlocking...