Implement a parser for Racket, in C. (You must implement the parser from scratch - don't use Yacc or Bison or any similar tool, even if you know what it is and how to use it.)
After you check out your blank repository, download this zip file and add the Makefile and the .h and .c files to your git project. (Note: zip file was updated on 10/30, 8:20 pm, with a fixed valgrind.sh file.) The files you get include:
At this point, you have a choice regarding how to proceed linkedlist.c, talloc.c, and tokenizer.c. If you want to continue to build your own interpreter that is truly yours, you can copy in these files from the last project, and move forward. Alternatively, if you would prefer to use my versions instead, you can do so. In the lib directory you'll see linkedlist.o, talloc.o, and tokenizer.o files. These are compiled binary versions of my linkedlist.c and talloc.c. If you would prefer to use one or many of these in your project instead of your own, you can replace them in the Makefile. Specifically, in the Makefile, on the line starting with SRCS, you can replace talloc.c with lib/talloc.o, etc. I suspect you are likely best off taking all of the files together, as opposed to mixing and matching yours with mine, but you may try if you like.
Note that compiled binaries are operating system specific (sometimes version specific). I have compiled these .o files to work with the course virtual machine.
To compile your code, issue the command "make" at the command prompt. (This will give an error if you haven't yet created the .c files you need, or have changed the Makefile to refer to the necessary .o files.)
To run your code, first create a file with some Racket code in it, and give it a filename (e.g., input.txt). Then issue this command at a prompt:
./parser < input.txt
Your code should read data from standard input. In that case, the above command will redirect the text in the input.txt file into your program.
To run your code through valgrind, I have provided a shell script to set all the appropriate options. You can do it this way:./valgrind.sh ./parser < input.txt
Note that to keep your project slightly simpler, we're going to always assume that your Racket programs leave out the "#lang racket" line, as this does not follow the usual Racket syntax. If this bothers you, you can read about how #lang is really shorthand for a module, and you can think about implementing this as an optional extension. We will always be leaving this line out when grading.
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 Racket program:
(define x (quote a)) (define y x) (car y)
Any Racket program consists of a list of S-expressions. An S-expression always has parentheses around it, unless it is an atom. Note that a Racket 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 Value:
The above parse tree stucture would be the first item in a 3-item linked list that represents the above Racket 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 Racket is really easy, at least in a relative sense. Since your Racket 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:
So you'll need a stack... your linked list is a fine candidate for it.
You'll also need to write a printTree function. The output format for a parse tree of valid Racket code is very simple: it looks exactly like Racket 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 did 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:
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. Also feel free to print Racket code around the error to be helpful if you can, though this 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!
(Cosmetic fixes made to tests below on 10/31 at 5 pm)
$ cat test1 (if 2 3) (+ )) $ cat test2 (define map (lambda (f L) (if (null? L) L (cons (f (car L)) (map f (cdr L)))))) $ cat test3 1 2 (3) $ ./parser < test1 Syntax error: too many close parentheses $ ./parser < test2 (define map (lambda (f L) (if (null? L) L (cons (f (car L)) (map f (cdr L)))))) $ ./parser < test3 1 2 (3)
You may find that it is easier to produce output similar to the above but with extraneous white space. For me, I had to hack some extra code to make sure that the last item of a list didn't have a space between it and the closing paren that followed it. You may have extraneous whitespace in your output if you wish, but I would optionally encourage you to make your output match the above. Your final product will look a lot more "real" if you put this effort in. You will not lose points for extra spaces, assuming that they aren't in the middle of strings or something like that.
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 == 0 when the parse function returns.
Value *parse(Value *tokens) { Value *tree = makeNull(); int depth = 0; Value *current = tokens; assert(current != NULL && "Error (parse): null pointer"); while (current->type != NULL_TYPE) { Value *token = car(current); tree = addToParseTree(tree,&depth,token); current = cdr(current); } if (depth != 0) { syntaxError(); // error case 4 } }
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using valgrind. We will be checking this during grading.
Push everything (c files, h files, Makefile, etc.) to your git repository.
You should also include in your submission a collection of at least 4 pairs of test files. (More is better!) Each pair of files should be named parser-test.input.XX and parser-test.output.XX, where XX is a test number. It should be the case that if I run the following command then I get no output:
./parser < parser-test.input.XX | diff parser-test.output.XX -
When we test your code for grading purposes, we will use our own set of test files which we will run using exactly the same command as described above. Test carefully.
Your code should have no memory leaks or memory errors when run on any input (correct or incorrect) using valgrind. We will be checking this as well during grading.
Remember, you can test your code in valgrind this way:
./valgrind.sh ./parser < parser-test.input.XX
Have fun parsing!
This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant and Laura Effinger-Dean.