Flex/Bison Programming Project

Programming Project 2
Implementation of a subset of Whitespace

Due: Sunday October 14, 2007
If turned in late, there is a 20% per day penalty.

Scenario

Flex and Bison accomplish lexical scanning and parsing. Lots of little languages exist that deserve to be scanned and parsed, with one of these languages being Whitespace. Whitespace has existing interpreters written in languages such as Perl and Haskell, so you can compare implementations. It's also a fairly simple language, although since we've got a limited time we're only going to implement a subset of the language. After which, you too can write programs that humans find difficult to read.

Assignment

In this programming project, you will do the following:

Look at the Whitespace web site, especially at the tutorial, examples, and implementations. Download the perl implementation. Make sure you understand the basics of the Whitespace language before going to the next step.
Answer the following questions about the Perl implementation and save them in a file called ws.txt:
- Do you understand the whole program? If so, describe what one of the more difficult parts of the program is doing. If not, then describe the overall structure of the program as you understand it.
Write a Whitespace interpreter using flex/bison. Note that your program should include the language features of Whitespace version 0.2 (i.e. the Perl version) except where indicated below. Your program should be called with the following command:
wspace filename.ws
where filename.ws is the name of the Whitespace program to run. From the tutorial page, you should implement all IMP commands except for flow control. See the section below for more information.

Append to the text file called ws.txt and answer/describe the following:
- Given the data structures needed for implementation, how easy would it be to extend your program to a full whitespace interpreter?
- How does your program work and did you have any problems with it?

More Detailed Information about the Project

Here are some simple files to get you started on the project:

wspace.lex: A simple lex file with basic commands represented. It is highly recommended that you represent whitespace commands as lex patterns as opposed to every single space/tab/etc.
wspace.h: A .h file that contains a sample token format and includes stack.c
wspace.y: A simple parser that counts spaces, pushes them on the stack, and then prints them out whenever another whitespace (tab or lf) character is encountered. It shows both printing for characters and integers.
stack.c: A simple stack implementation. It includes a print command to print the stack (helpful for debugging) and allows the stack to grow in an unbounded way. An example of how to use the stack is included in wspace.y.

It is highly recommended that you build some kind of internal debugging into your program, because whitespace programs are not easy to read. Neither bison or your own debugging should be turned on when you submit your program to WTry. You may also want to consider putting commonly used command sequences for bison in their own C functions.

You should use scanf (see the C Tutorial for more information on the main course page) for formatted input to your program. Note that ascii characters can be stored and written as integers.

Compiling your program may be done in the following manner:

flex wspace.lex; bison wspace.y; gcc -o wpsace wspace.tab.c

Style

As usual, use comments and make your files as readable as possible. Start each file with comments containing your name(s) and account(s).

Submission

Please submit all relevant files through WTry. The appropriate submissions are the following:

(80 points) The flex and bison programs.
(20 points) The questions file. This file should be an ascii text file.