Part 3 - Tokenizer

Due: Wednesday, May 6, 2026, at 10pm

Starter code: p3_tokenizer.zip or p3_tokenizer.tar
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

  • building the actual first real step in your interpreter: tokenizing the input program!

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

If you worked with a partner for P1 and/or P2, you must work with the same partner or work alone for P3.

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

  • all CR tests pass
  • a visual inspection of your code shows that you have not hyper-tailored it to pass the tests
  • readme.txt contains your collaboration statement, sources, and reflection

Note that hyper-tailoring in this case would be doing things like checking for the exact input from the test, meaning you haven’t written your code in a way that would work for other similar inputs.

Advanced requirements:

  • satisfy the Core requirements
  • all AD tests pass
  • your code is not significantly more complex than needed to accomplish the task
  • each function has a comment before it describing its high-level behavior
  • your code uses good C coding style, including using helper functions to reduce the size/complexity of your tokenize function

Assignment overview

Just want to get started? Jump ahead to suggestions for your code, then come back here when you’re ready to dive more deeply into edge cases as well as the nitty-gritty details of Scheme lexemes.

Now that you have a linked list and a (basic) garbage collector, it’s time to start interpreting Scheme in C! In this assignment, you will read in each character of a Scheme program from a file and return a linked list of the tokens (“lexemes”) in it, with each lexeme labeled with a type.

For example, the input file t03.scm contains the following:

("a string" (* 5 4) a1)

Given this file, your program should output:

(:open
"a string":string
(:open
*:symbol
5:integer
4:integer
):close
a1:symbol
):close

Overall, you will have to handle the following token types:

boolean     string      open
integer     symbol      close
real                    quote

Note that the rightmost column above represents (, ), and '. The output format is, per line, token:type.

Note that you must implement the tokenizer from scratch – don’t use Lex or any similar tool, even if you happen to know what it is and how to use it.

Gotchas and assumptions

You should also strip out comments as you tokenize, so that anything after a ; on a line is ignored.

Be careful detecting newlines. On Mac and Linux a newline is marked by a single \n. However, on Windows a newline is \r\n. All of our tests run on Linux, so this should only be a problem if you’re creating your own test files with Windows. Either make sure to save files as LF (see the bottom-right in VS Code for either LF or CRLF) and/or on Mac/Linux, or make sure your tokenizer can also handle \r\n at the ends of lines.

A few guarantees you can rely on:

  • No token will be longer than 300 characters long. This includes strings.

  • No line will be longer than 300 characters long.

FAQ: Should your tokenizer catch errors with mismatches parentheses, i.e., )(a b ))? No, it should tokenize strings like that without error. Catching mismatches parens is the parser’s job, as it checks for structure.

FAQ: What should the tokenizer do with bad input? It should handle it gracefully; it should never crash with a segfault, bus error, etc. If the input code is untokenizable, print an error message to say so. You may print something generic such as “Syntax error: untokenizable”, or you can provide more detailed information in the error message depending on what the problem is. Whatever you print, it should start with the string text “Syntax error” so that it will pass the automated tests. (Upper or lower case doesn’t matter.)

After encountering an error, your program should exit after printing the error – don’t read any more input. This is why we wrote the function texit. Also feel free to follow your error message by printing Scheme code around the error to be helpful if you can (although this is optional).

Syntax details

Scheme is a complex language. In the interest of making things more tractable, here is a simplified syntax for numbers that I expect your tokenizer to handle (adapted from Dybvig’s book):

<number>   ::=  <sign> <ureal> | <ureal>
<sign>     ::=  + | -
<ureal>    ::=  <uinteger> | <udecimal>
<uinteger> ::=  <digit>+
<udecimal> ::=  . <digit>+ | <digit>+ . <digit>*
<digit>    ::=  0 | 1 | ... | 9

Tip: If you want to convert strings into numbers, you can use the functions strtol and strtod in the C standard library.

Similarly, you should recognize symbols (identifiers, which should be case-sensitive) with the following syntax (again adapted from Dybvig’s book):

<identifier> ::=  <initial> <subsequent>* | + | -
<initial>    ::=  <letter> | ! | $ | % | & | * | / | : | < | = | > | ? | ~ | _ | ^
<subsequent> ::=  <initial> | <digit> | . | + | -
<letter>     ::=  a | b | ... | z | A | B | ... | Z
<digit>      ::=  0 | 1 | ... | 9

This is a little inconsistent with the actual behavior of Scheme, but it simplifies things up a bit (at the cost of some minor incompatibilities).

You may also find the syntax section of Dybvig’s book to be helpful. The Scheme dialect described may not be completely consistent with the above, but it’s readable in English. The BNF that I have provided above is considered to be the correct specification for this assignment. It deviates slightly from what Guile allows, but in ways that should end up making some things, like differentiating numbers and symbols, easier.

Scheme provides many different ways of enclosing lists (( ), [ ], etc.). We will only write code that uses parentheses for the purpose of enclosing lists; none of our test code will use square brackets. You can write your tokenizer and subsequent parts of the interpreter to only work on parentheses. That said, if you want your project to also work on square brackets, it isn’t that hard of an extension. If you think you want to go that way, you’ll need to make sure that you tokenize parentheses and brackets differently so you can match them separately.

We will identify the single quote ' as a special token all of its own. It should be stored in a scheme_item_t as a QUOTE_TYPE and displayed by your tokenizer accordingly. Don’t get this confused with the word quote, which is tokenized as a regular symbol.

Tokens are separated by various forms of whitespace (space, newline, tab, etc.). Use the C function isspace to test if a given character is a whitespace character.

Optional extensions

The work in this section is 100% optional and does not contribute to your grade in any way. Still, if you’re looking for an extra challenge or ideas on what to practice to study the material, there will be occasional “optional extensions” sections of assignments that contain one or more additional exercises to try.

Here are some optional extensions that naturally arise at this part of your interpreter project:

  • Square brackets: [ ]. Add openbracket and closebracket token types, and tokenize these as well. This should be a relatively straightforward extension of how you handle parentheses.

  • Dot: .. A dot by itself is useful for handling dotted pairs. A dot token type should be identified if and only if there is a dot with whitespace on both sides of it. A dot at the beginning or end of the file cannot be a dot token. This extension is a bit more work.

Getting started

As before, you should download the starter files as a zip file or tarfile, unzip that file, and copy the folder to where you’ll work (probably your ProgrammingLanguages folder). Refer to the Assignment 1 instructions if you’re unsure what to do.

In the starter code, you should find the following files:

  • schemeitem.h: the same header we’ve been using with a few new types added

  • linkedlist.h: the same header file, more or less, from the last assignment

  • talloc.h: the same header file, more or less, from the last assignment

  • tokenizer.h: the header file for the functions you’ll need to write for this assignment; you also want to create a bunch of helper functions, but they don’t need to be in the header because they will “private”

  • main.c: a very short main function that kicks off the tokenizer

  • justfile: contains instructions for the command just, which we will use to compile and test your code

  • test-files-cr and test-files-ad/: directories of Scheme programs used as test inputs, along with their expected outputs

  • test-cr and test-ad: usual test scripts

  • tester.py: a helper script to handle automated testing

The missing files this time are tokenizer.c, readme.txt, linkedlist.c, and talloc.c. You should copy each of linkedlist.c, talloc.c, and readme.txt from your P2 folder into this one. You’ll create a new file tokenizer.c for this assignment.

Reading the input Scheme file

The heart of your code will be your tokenize function, which reads the input from stdin and returns a list of scheme_item_ts. Here is a rough setch of what that function might look like:

scheme_item_t *tokenize()
{
    scheme_item_t *lst = makeNull();

    // Read character-by-character from stdin
    int ch = fgetc(stdin);
    while (ch != EOF)
    {
        printf("Found char: %c\n", ch);

        /* do something based on ch, add to lst when appropriate */

        // Read the next character at the end of the loop
        ch = fgetc(stdin);
    }

    // We added nodes to the front each time, so it's backwards
    scheme_item_t *reversed_lst = reverse(lst);
    return reversed_lst;
}

This function uses fgetc to read from stdin one character at a time. There are other ways of reading input files, but this one works pretty well for our purposes. You may also find ungetc useful. Here is the documentation for these functions.

Note that the type of ch is an int, not a char. This is because the version of clang that is included with Docker gives a warning if ch is a char and you reach the end of the file (i.e., you compare an unsigned char with EOF, which is represented by -1).

Comparing characters

Every char in C is actually represented internally by the binary number corresponding to its ASCII codepoint. For example, 'A' is actually just the number 65. This means you can easily compare a char (or even an int!) versus existing characters. For example:

if (ch >= 'A' && ch <= 'Z')
{
    // Whatever I do here, I know that ch is an uppercase letter
}

There are similarly contiguous ranges for a-z and 0-9. Note that to compare numbers you have to compare to the character, like this:

if (ch == '2') // '2' is actually 0x32, which is the number 34
{
    // If I'd compared ch == 2 this wouldn't work...
}

Where do we go from here?

Here are some steps I recommend to get you started:

  1. Copy over linkedlist.c, talloc.c, and readme.txt.

  2. Create a new file tokenizer.c based on the functions declared in tokenizer.h. Like before, give each function a return that matches its type (just return; if it’s void).

  3. Try building your code using just build at the terminal.

  4. Read through the first few test cases to remind yourself what the Tokenizer should do. For example, take a look at the input in test-files-cr/t01.scm and its expected output in test-files-cr/t01.output.

  5. Fill in the function tokenize just enough that it prints out each character in the input program using the example above.

  6. Modify your tokenize function to create a linked list that will represent your tokenization output, and add a node to it for each ( and ) you find in the input. Implement displayTokens to print the expected output.

  7. Test early and often – make a simple file myprog.scm that contains something like ( ) (( ) () as its input, and test that you get the right output.

  8. Slowly add in more complexity, continuing to test every time you add something new.

Good luck, and as always, try to have fun with this! If you get stuck, take some time to draw the test cases on a whiteboard/paper and try to use gdb to walk through the code and debug what’s happening. If in doubt, post on the Moodle Q&A forum with any error messages you can’t make sense of!

Testing your work

To run your code, first create a file with some of your own Scheme code in it. For example, if you have a file myprog.scm that contains ( ) (( ) (), then you could run your tokenizer by typing this in the terminal after building (just build):

./interpreter < myprog.scm

Your tokenizer should read data from stdin. in that case, the above command redirects the text from myprog.scm into your tokenizer program.

To run your code through valgrind, you can similarly type:

valgrind ./interpreter < myprog.scm

One challenge you may find is that when your output gets long, it gets hard to read before it scrolls all the way off the top of your terminal window. Piping your output through the UNIX less program helps. It will pause the output at the bottom of the screen, waiting for you to press the space bar to continue, or q if you want to quit. You can do this with or without valgrind:

./interpreter < myprog.scm | less
valgrind ./interpreter < myprog.scm | less

As with previous assignments, there are CR and AD tests for core and advanced functionality. Look at the instructions from A2 if you want a refresher on how to run these tests.

For the interpreter project, the tests will fail if your code has compiler warnings and/or valgrind errors, so make sure to run the tests in the Docker environment.

Submitting your work

For this assignment, you will submit just one code file. You are strongly encouraged to run ./zipitup to use that script to gather your files for Gradescope.

C code

The file tokenizer.c should contain your functions. Make sure to add a comment above each of your functions (including any helper functions you choose to write) to describe its behavior at a high level (e.g., what it takes as input and what it returns as output). It’s okay to just copy the comments from tokenizer.h or you can write your own (shorter) descriptions.

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

  1. Your collaborations with anyone on the assignment
  2. Your use of any outside sources on the assignment
  3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

  • Were there any particular issues or challenges you dealt with in completing this assignment?
  • How long did you spend on this assignment?

Submitting to Gradescope

As always, use ./zipitup to gather your files. Submit the resulting .zip file to Gradescope.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.