Flex/Bison Programming Project

Programming Project 2
Implementation of a subset of Whitespace

Due: Saturday October 23, 2004
Late Deadline (no penalty for late submission): Monday October 25, 2004

Further simplification of the language: Please push items from standard input onto the stack directly as opposed to pushing them onto the (nonexistant) heap. This will change the language definition, but will make the project a bit easier for input/output.

Scenario

Flex and Bison are best for 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 wsPerl.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.
- It is possible to extend the whitespace language. As an example, the terminal bell (ASCII 7) does not receive fair treatment in programs. Let your imagination be the guide to how the terminal bell could add to your ordinary, musically untalented whitespace program. How do you think the terminal bell could be used?
- How easy would it be to change the Perl program to deal with this language extension?
Write a partial Whitespace interpreter using flex/bison. 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 tutotial page, you should implement all IMP commands except for heap access and flow control. You also do not have to implement the copy or slide operations for the stack. See the section below for more information.

Create a text file called wsBison.txt in which you should 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 easy do you think it would be to extend your implementation to use your terminal bell idea from the previous text exercise? Please compare/contrast it to the difficulty to the Perl extension.

Write an optional file that contains any problems you had with the code for your program.

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 try. 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) 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).

Collaboration

You may work on the programming project in groups with a maximum of 2 people. Any group containing more than 2 people will receive 0's for the assignment. Please put both of your names on all group submissions and submit from one account. All text answer files should be written and submitted individually. Please give me your partner's name (in the format "Partner: < partner >") as well as your own name on individual files. This redundancy helps me to make sure that I'm grading both people on a team, especially since a member often forgets to put the other person's name on the original submission file.

Submission

NOTE: try is not set up yet

For this particular project there are 4 possible submissions. Note that try will not be testing or compiling your code, so it is up to you to make sure that your code works prior to submission on the Sun system. Code that does not compile will not be looked at and you will receive a 0 for that part of the project.:

(50 points) The flex and bison program. Use the following command to submit:
- try jdb-grd project2-1 wspace.y wspace.lex *.h *.c
(30 points) The Perl questions file. This file should be an ascii text file:
- try jdb-grd project2-2 wsPerl.txt
(20 points) The bison file. This file should be an ascii text file:
- try jdb-grd project2-3 wsBison.txt
The optional problems.txt file. This file can help you if there are known problems with your program.
- try jdb-grd project2-4 problems.txt

You can resubmit as often as you like before the deadline. Projects that are not submitted before the late deadline will not be looked at and will get a grade of 0.