CSC254 Tokenizer Assignment

Due by 11:59pm 09/14/2010


This assignment is lexical scanning---the first step in compilation. Scanning identifies tokens from literals. You are required to build your own tokenizer and use it to process programs in a subset of the C language. (Note: do NOT use lex to generate your tokenizer automatically.) In particular, it should rename all user defined identifiers, i.e. variables and function names, to end with our course number (_cs254). The tokenizer should report an error if a token does not confirm to the token-language definition. If the input program is correct, the output should also be a correct program with the same behavior. (A necessary requirement---the output of your tokenizer is supposed to be compiled successfully by gcc if the original one can be.) See the following examples:

  • A good example
    • Input file: int main() { int i; i=0; printf("%d\n", i);}
    • Output file: int main() { int i_cs254; i_cs254=0; printf("%d\n", i_cs254);}
  • An error example
    • Input file: int main() { int 2010i; printf("%d\n", 2010i);}
    • Abort scanning and report an error of the illegal token "2010i"

The Token Language

For this and later projects on compilation, we use a subset of C language. There are only integer variables and arrays and no external library calls except for I/O. There is no pointers except for reading the input. In this project, we are concerned with the token definition of the language. See the token specifications here.  Note tokens are separated by either white spaces (including tabs and line returns) or by symbols such as operators and semcolon. 

Tokenizer Design

You may use any programming language to write your tokenizer. Note that the tokenizer is the first step in a series of projects through which you will develop a calculator and a compiler. In later projects, you can either reuse your tokenizer or choose the implementation from someone else in the class.

A modular implementation can use two classes---the token and the scanner classes. A token in the token class has information such as type and name (for identifiers) or value (for numbers). The constructor of the scanner class takes the input file name as an argument. It provides an enumerator method that yields the next token when called. The following shows such an interface for the scanner class in Ruby syntax:

class Scanner
def init( file_name )
... ...

# return the next token (as a Token object) or EOF
def next_token
... ...

What/When to Submit

You are required to submit two test cases with an output file (user_id-good.c, user_id-good.out, user_id-error.c) to project_code/c_tests in the hg repository by midnight Thursday 9/9/2010 for use by others in the class. The good test case is a valid C program with all tokens comfirming our token language. The output file is the output from running your tokenizer with the input of the good test case. The output program generated by a correctly implemented tokenizer should produce the same results. The error test case has some lexical errors which should be reported by a tokenizer. You may use others' test cases to help each other in testing. (TA will use all of them in grading.)

Turn in your tokenizer code with instructions to run your tokenizer, a design document on the interface and the design, and a result file listing the passed tests.  Submit these files in project_code/tokenizer/user_id before 11:59pm Tuesday 09/14/2010.