• SI 413
• Calendar
• Classes
• Labs
• Project
• Resources
• Grades
• Submit

Useful Links

• Manpage for beef, the interpreter we will be using.
• Wikipedia page
• Brainfuck page of Brian Raiter. Some useful information and links.
• 99 bottles of beer program.

How I will run your code

Save your program in a file called proj.bf in folders called proj1 and proj2 respectively for phases 1 and 2 of your project.

I will test your code in the same environment as the lab machines in MI 302, using the command

  /usr/bin/beef proj.bf

Phase 2 Assignment

For phase 2 of your project, you will write a compiler from a highly simplified subset of the C programming language to brainfuck code. You will not submit brainfuck code for this part, but rather a parser and scanner generator using flex and bison, in two files called proj.lpp and proj.ypp.

Specification

I will compile your code to the executable compiler proj as follows:

flex -o proj.yy.cpp proj.lpp
bison -d proj.ypp
g++ -o proj proj.tab.cpp proj.yy.cpp

Then, if test.c contains a program in the C subset described below, I will test your compiler as follows:

./proj < test.c > test.bf
/usr/bin/beef test.bf

Of course, the result of the second command should be the same as if I had compiled the test.c program using gcc and run the resulting executable.

Now don't worry, the subset of C that we are going to compile from is going to be very restricted. Specifically, our C subset has the following properties:

• Any line that starts with the # character is ignored by your compiler.
• The code must consist of a single int main() { function. There must be no function prototypes or global variables. This main function must end with a return 0; statement, which is ignored by your compiler.
• As always in C, every variable must be declared at the top of the code block. There may not be any nested code blocks, so every variable must be declared at the beginning of main.
• Every variable must have type int, but may never store any integer larger than 127.
• Variables must be declared one at a time, so for example int x,y; is not allowed.
• Variables may be initialized with a constant integer value when they are declared, but not with an arbitrary expression. So for example int x = 5; is OK, but int x = 5 + 2 is not.
• Every assignment statement must take the form VAR = ANY OP ANY;. Here ANY is either a variable name or an integer in the range 0-127, and VAR must be a variable name. OP can be any of the following: +, -, >, <, ==. Addition and subtraction work as usual, and the comparison operators set the variable to 1 if the statement is true, and to 0 if it is false.
• Besides assignment statements, we can also have input and output statements. An input statement has the form VAR = getchar();, and an output statement has the form putchar(ANY);.
• You should support (by ignoring) both types of C-style comments.

Tips

I suggest you write your program in the following steps. Of course you are free to develop however you wish. As always, you are encouraged to submit every time you get some small step of the program working.

1. First get your simplified C++ scanner and parser working, and doing nothing. This should be very easy for you by now in this course! As a comment, you may be tempted to make a token called OP for all the operators, but I advise against this. Ultimately your parser is going to have to be writing brainfuck code, and this code will be very different for something like 5 + 2 compared to 5 == 2. So it might make your job easier to just have every operator be a different token.
2. Now start building your compiler, from the very very basics. Start with variable declarations. Where should variables be stored in the brainfuck program? What does your parser have to remember to facilitate this? (Hint: you will need a symbol table.)
3. After you get variable declarations, the input and output commands shouldn't be too much trouble. Then venture into some of the operators, adding in their functionality one at a time. For each one, think about how you would actually write the brainfuck program to do that operation. Then get your parser to write that code in a way that won't interfere with anything else. Test after you add each operation, and don't try to do everything at once.

Example

So for instance, given the following C program:

#include <stdio.h>

int main() {
  int x = 5;
  int y;
  y = getchar();
  x = x + y;
  putchar(x);
  return 0;
}

+++++
>
,
<[->>+>+<<<]
>>>[-<<<+>>>]
<<[->+>+<<]
>>[-<<+>>]
<<<[-]
>>[-<<+>>]
<<.

Of course your actual program might differ from this one. As long as they behave identically, it's fine.