Due: Friday, May 15, 2026, at 10pm (was previously listed as Wednesday May 13)

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

Goals

This assignment is designed to help you with the following:

• building parse trees given a labeled list of tokens

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 any of P1/P2/P3, you must work with the same partner or work alone for P4.

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 parse and printTree functions

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 building a parse tree.

Now that you can tokenize an input Scheme program, you can begin to parse that program! In this assignment, you will read in the list of tokens and their types from the previous assignment, and output a list representing a series of parse trees.

For example, here is a syntactically correct Scheme program:

(define x (quote a))
(define y x)
(car y)

Any Scheme program consists of a list of S-expressions. An S-expression always has parentheses around it, unless it is an atom. Note that a Scheme program itself, then, is not a single S-expression; it is a list of S-expressions (but without ( ) at the top level to indicate that list).

To satisfy Core requirements, you need to handle the case functionality (see the CR tests). To satisfy Advanced requirements, you additionally need error handling (see below) and to be able to handle the single quote character.

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

Parsing Scheme

You will write a parse function that should therefore return a list, using the linked list structure that we have been using, of parse trees.

A parse tree, in turn, uses the linked list structure again to represent a tree.
For example, the expression (define x (quote a)) would become the following parse tree, where each box is a scheme_item_t:

The above parse tree structure would be the first item in a 3-item linked list that represents the above Scheme program.

You should not include parentheses in your parse tree. Their purpose is to tell you the structure of the tree, so once you have an actual tree you don’t need them anymore; they’ll only get in the way. (Technically, this means that you’re creating an abstract syntax tree, not a parse tree, as not all of the input is preserved.)

Printing your tree

You’ll also need to write a printTree function. The output format for a parse tree of valid Scheme code is very simple: it looks exactly like Scheme code! To output an internal node in the parse tree, output ( followed by the outputs of the children of that internal node from let to right, followed by ). To output a leaf node (a non-parenthetical token), just output its value as you did in the tokenizer, just without the type.

Note: When printing, you’ll always use ( and ), regardless of whether the original code used parentheses or brackets. Your parse tree shouldn’t actually know which the original code used!

Syntax errors

As with the tokenizer, your parser should never crash with a segmentation fault, bus error, or the like. Here are the different types of syntax errors you should handle:

1. If the input code ever has too many close grouping symbols (e.g., you find a closing symbol that doesn’t match a previous open paren/bracket), print Syntax error: too many close parentheses.
2. If the end of the input is reached and there are too few close parentheses, print Syntax error: not enough close parentheses.
3. If you’re handling brackets and the parse function encounters mismatches grouping symbols (like ([)]), print something beginning with Syntax error. You may follow that with whatever error message you like to describe the situation.

If you ever encounter a syntax error, your program should exit after printing the error–don’t do any more parsing. This is why we wrote that function texit. Before exiting, you should output the text Syntax error. Feel free to also print Scheme code around the error to be helpful if you can, although this is optional.

Note: Most production parsers continue to try and parse after an error to provide additional error messages. Your efforts here may help you to gain some sympathy as to why all error messages after the first one are questionable!

An algorithm to parse Scheme

Parsing a programming language in general can be pretty complicated. The good news is that parsing Scheme is relatively straightforward. Because your Scheme code is a tree, you just need to be able to read it as such and turn it into a tree in memory. You can do it with a stack of tokens, as discussed in class. Here’s that algorithm again:

• Initialize an empty stack
• While there are more tokens:
  • Get the next token.
  • If the token is anything other than one of the close grouping symbols, push it onto the stack.
  • Otherwise, if the token is a close grouping symbol, start popping items from your stack until you pop off the matching open symbol (and form a list of them as you go). Then push that list back on the stack.

So, you’ll need a stack…your linked list is a fine candidate for it.

One small extension to the idea above: you’ll end up with a stack at the end, and you’ll need to decide what to do with it. You’ll want to be sure to remember that you are reading a list of S-expressions, not just a single S-expression, and the list you return should match the order of that file. For example, in the code above, (define x (quote a)) was the first thing in the file, and its parse tree should be the first item in a 3-item linked list if parsing the entire example above.

At the end of parsing a file, make sure you check that you don’t have any open grouping symbols that are still waiting to be closed (i.e., (define a 3 should lead to a parse error, as discussed above). Using a variable to store the current depth of the tree may be helpful. This variable could start at 0, and track how many open parentheses we’re waiting to close at any given time.

Helper functions

You will want to add helper functions in parser.c (or, I suppose, in other files). You may be wondering whether you can/should modify the .h files in addition to add these fucntions. Generally, you would only do this if you intend for these functions to be used outside of the file in which you’re defining them. You shouldn’t need to do that, so you shouldn’t change the .h files you’re given (and doing so may break the Gradescope tests).

If you’re writing helper functions without putting them in .h files, you might experience an error about something begin undefined. This occurs during compilation because the compiler doesn’t know that the function will be defined later in the file. You have two options:

• Declare a prototype for the function within your .c file, underneath your includes, just as you would in the .h file. The prototype is just the function return type, name, and parameters, but with a ; instead of the body. Within that .c file, this is equivalent to having put all of the prototypes in the .h file, but outside of this .c file, no one else knows about the function.

• Write the function prior to calling it. This is basically strategically ordering your file so functions that are called by other functions are defined before the functions that call them.

If you want to add in additional .c and .h files to separate out particular functionality, that is possible (but not at all required). If you do this, make sure to modify the justfile to include these .c and .h files. The grader will be using your version of the justfile, not the original copy.

Handling the single quote

Dealing with the special case of the single quote (i.e., 'a or '(a b c)) means that we need to redefine “push onto the stack”, which appears a few times in the parsing algorithm. Here is the new definition of “push onto the stack”, which you’ll need if you want to pass the AD tests:

• Proceed as usual so long as the stack doesn’t have a single quote (') on top.
• Also proceed as usual if push on a left paren, no matter what the stack looks like.
• In all other cases:
  • Pop the single quote off the stack.
  • Then proceed as if the token sequence had (quote ...) wrapped around the value you’re pushing. In other words, create a new subtree consisting of quote and the new token, and then push that subtree onto the stack instead of the original value you were going to push.

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:

• Output format: Format your output so that it resembles Guile output as closely as possible. Specifically, don’t have extraneous space after the last item in a list before the closing paren.

• Square brackets: Add handling of square brackets to your parser, making sure they match separately from parens. Once your parse tree is constructed, you should retain no memory of whether parens or brackets wereused, and your output should only show parentheses (just as Guile does). However, you’ll need to add some extra details while parsing to make sure the input is correct. For example, even though you’ll eventually transform (a [b c] d) into (a (b c) d), the input (a [b c) d] should result in a syntax error. (Note: Your tokenizer also needs to handle square brackets to make this work.)

• Dot: Correctly parse dotted pairs, e.g., (a . b). (Note: Your tokenizer also needs to handle dots to make this 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 same files as in the tokenizer assignment, plus:

• parser.h: the header file for the functions you’ll need to write for this assignment

Copy over your .c files from your Tokenizer assignment. You’ll also create a new file parser.c for this assignment.

Parsing the stream of tokens

The heart of your code will be your parse function, which should use the stack-based algorithm described above to parse the list of tokens provided by the Tokenizer.

Here is a rough sketch of what your parse funtion might look like:

scheme_item_t *parse(scheme_item_t *tokens)
{
    // We're going to build the tree using our linked list structure
    scheme_item_t *tree = makeNull();
    int depth = 0;

    // Validate our input
    assert(tokens != NULL && "Error (parse): null pointer");

    // We'll consider each token, one at a time
    scheme_item_t *current = tokens;
    while (current->type != NULL_TYPE)
    {
        scheme_item_t *token = car(current);
        tree = addToParseTree(tree, &depth, token); // stack algorithm!
        current = cdr(current);
    }

    // If we haven't closed every OPEN, we have an error!
    if (depth != 0)
    {
        syntaxError();
    }

    ...
}

In the above code example, the function addToParseTree might take in a pre-existing tree, a pointer to an integer depth, and a token to add to the tree. Note that depth is updated to represent the number of unclosed open parens in the parse tree, as mentioned above. The parse tree is complete if and only if depth is 0 when the parse function returns.

Of course, you are not required to use this code skeleton, as there are plenty of other good ways to structure your code. For instance, if you wanted to more explicitly represent the difference between the parse stack and tree, you might replace tree with parseStack.

Where do we go from here?

Here are some steps I recommend to get you started:

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

2. Create a new file parser.c based on the functions declared in parser.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. Fill in just enough code to add each token to a stack, and when you come across a ) then print which are getting popped off (but don’t actually build a subtree).

5. Complete the stack-based algorithm to handle a single top-level expression in a file, like in test-files-cr/t03.scm.

6. Extend your code to handle files with multiple top-level expressions, like in test-files-cr/t01.scm and test-files-cr/t02.scm.

7. Make sure you pass the CR tests.

8. Add in error handling.

9. Handle a single quote (').

10. Make sure you pass the AD tests.

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. Look back at the instructions from the tokenizer assignment for using your own Scheme program.

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 parser.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 parser.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.