Interpreter 4: Parser

Download the folder with the starter code from the link below. Like for previous homeworks, unzip the folder and move it to where you'd like: most likely the folder for the Docker container. Then get started in VS Code.

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter files.

You should create a parser.c file that implements the functions specified in parser.h. Particularly, you will need to write a function parse that uses the token list from the last assignment to construct a list 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.

Your parse function 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 SchemeItem:

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

Do 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, since not all of the input is preserved.)

Parsing languages can be pretty complicated. The good news is that parsing Scheme is relatively straightforward. Since 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:

• 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.
  • If the token is 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). 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 the file. I.e., in the example 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!). 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.

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 left to right followed by ). To output a leaf node (a non-parenthetical token), just output its value as you in the tokenizer, sans type.

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 (in other words, if you ever encounter a closing symbol that doesn't match a previous open paren), print Syntax error: too many close parentheses.
2. If the parse function returns an incomplete parse tree and the end of the input is reached and there are too few close parentheses, print Syntax error: not enough close parentheses.
3. If the parse function encounters mismatched parentheses 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 the function texit. Before exiting, you should output the text "Syntax error". Also feel free to print Scheme code around the error to be helpful if you can, though this is optional.

Most production parsers continue to try to 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!

$ cat test-in-01.scm
(if 2 3)
(+ ))

$ cat test-in-02.scm
(define map
  [lambda (f L)
    (if (null? L)
        L
        (cons (f (car L))
              (map f (cdr L))))])

$ cat test-in-03.scm
1 2 (3)

$ ./interpreter < test-in-01.scm
Syntax error: too many close parentheses

$ ./interpreter < test-in-02.scm
(define map (lambda (f L) (if (null? L) L (cons (f (car L)) (map f (cdr L))))))

$ ./interpreter < test-in-03.scm
1 2 (3)

• Sample code

Here is a rough approximation of part of my parse function. My addToParseTree function takes in a pre-existing tree, a token to add to it, and a pointer to an integer depth. depth is updated to represent the number of unclosed open parentheses in the parse tree. The parse tree is complete if and only if depth is 0 when the parse function returns.

SchemeItem *parse(SchemeItem *tokens) {

    SchemeItem *tree = makeEmpty();
    int depth = 0;

    SchemeItem *current = tokens;
    assert(current != NULL && "Error (parse): null pointer");
    while (current->type != EMPTY_TYPE) {
        SchemeItem *token = car(current);
        tree = addToParseTree(tree, &depth, token);
        current = cdr(current);
    }
    if (depth != 0) {
        syntaxError();
    }
    ...
}

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

You'll note that you may want helper functions in parser.c (or indeed, in any number of other locations). A common question is whether you can/should modify the .h files to add these functions. Generally, you would only do this if you intend for these functions to be called outside of the file in which you're defining them. Since we won't need to do that for this project, you should not 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 being 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 protoype 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, without the body - each function part in the .h file is a prototype. Within that .c file, this is equivalent to having put all the prototypes in the .h file, but outside of that .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, please modify the justfile to include these .c and .h files. The grader will be using your version of the justfile, not the original copy (that also allows you to switch to our binaries if need be).

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 only need to pass all of the E tests:

• Proceed as usual so long if the stack doesn’t have a single quote ' on top.
• Also proceed as usual if pushing 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.

For the final project submission, you will get to choose what additional functionality you want your interpreter to have, and you'll implement (several small, a few medium, or 1-2 large) enhancements.

• Format your output so that it resembles Guile output as closely as

possible. Specifically, don't have an extraneous space after the last item in a list before the closing paren. (Small enhancement)

• Correctly handle square brackets. Some dialects of Scheme allow you to use square brackets as an alternative to

parentheses anywhere you like, so long as they match accordingly. Here is an example:

(define [lambda (x) [+ x 1]])

Once your parse tree is constructed, you should retain no memory of whether parentheses or square brackets were used, and your output should only show parentheses (just as Guile does). However, you'll need to add some extra details to the parse to make sure the input is correct. For example, even though you'll eventually transform (a [b c] d) to (a (b c) d), the input (a [b c) d] should result in a syntax error. (Small enhancement, requires you to also handle square brackets in Tokenization.)

• Correctly parse dotted pairs, e.g. (a . b). (Medium enhancement, requires you to also handle dotted pairs in Tokenization and in Evaluation.)

Look back at the tokenizer assignment, in the section titled "The files that you start with," on how to build your code as well as how to use my binaries for the previous assignments if you wish.