CS241 — Spring 2018 — Assignment 3

Assignments for CS 241
← Assignment 2 Assignment 3 Assignment 4 →
Tuesday, May 22 at 5:00pm Wednesday, May 30 at 5:00pm Wednesday, June 6 at 5:00pm
P1P2P3P4P5P6P7P8P9P10

This assignment may be done in either Racket or C++14. See the language-specific notes for each language at the end of this page.

In this assignment you will build an assembler for the MIPS assembly language you've used thus far in this course. While we try our best not to penalize you twice for the same mistakes, an assembler with serious bugs on early questions may have issues on later questions as well.

Problem 1 — 10% (asm.rkt or asm.cc)

Begin by writing an assembler that correctly translates input containing no labels and no instructions other than .word. You may assume that the input to your assembler contains no labels and no instructions other than .word.

Your assembler should never crash, even if the input is not a valid assembly language program. Your assembler should not silently ignore errors in the input program. If the input contains a line that is not valid in MIPS assembly language, your assembler should print an appropriate error message containing the word ERROR in all capital letters to standard error and stop. It is good practice, but not a requirement, to embed ERROR within a descriptive error message.

Hint: there are relatively few ways in which an assembly language program can be valid (all of which are spelled out here), but many ways in which it can be invalid. You will find it much easier to write code that looks for valid input and rejects everything unexpected rather than code which explicitly looks for all the different ways in which the input could be invalid.

If the input contains a correct MIPS assembly language program, your assembler should output the equivalent MIPS machine language to standard output.

Click here to return to the top of the page.

Problem 2 — 15% (asm.rkt or asm.cc)

Add support for label defintions to your assembler. Other than the inclusion of label definitions, the restrictions, assumptions and output requirements (including error-checking) stated in problem 1 apply here as well.

In addition, if the input is a correct MIPS assembly program, your assembler should output a symbol table: a listing of all the names and values of all defined labels to standard error. This list should be printed on several lines, with one line for each label in the input. Each line should consist of the label (without the trailing colon), a space, and finally the value of the label in decimal. The labels may appear in the symbol table in any order. For example, the following input:

begin: .word 2
middle: .word 0
.word 0
end:

Should print the following to stderr (but possibly with the lines reordered):

begin 0
middle 4
end 12

You may use any data structure(s) you choose to handle labels, but be sure to take efficiency into account.

Click here to return to the top of the page.

Problem 3 — 10% (asm.rkt or asm.cc)

Modify your assembler to allow labels to be defined and also to be used as operands. Other than the inclusion of label definitions and labels as operands, the restrictions, assumptions, and output requirements (including error-checking) stated in problem 1 apply here as well. Note that you do not need to list the names and values of defined labels as in problem 2.

Click here to return to the top of the page.

Problem 4 — 6% (asm.rkt or asm.cc)

Modify your asssembler to correctly handle jr and jalr.

Click here to return to the top of the page.

Problem 5 — 12% (asm.rkt or asm.cc)

Modify your assembler to correctly handle add, sub, slt, and sltu.

Click here to return to the top of the page.

Problem 6 — 8% (asm.rkt or asm.cc)

Modify your assembler to correctly handle beq and bne with a decimal or hex integer offset as the branch offset.

Click here to return to the top of the page.

Problem 7 — 10% (asm.rkt or asm.cc)

Modify your assembler to correctly handle beq and bne with a label as the branch target.

Click here to return to the top of the page.

Problem 8 — 9% (asm.rkt or asm.cc)

Modify your assembler to correctly handle lis, mflo, and mfhi.

Click here to return to the top of the page.

Problem 9 — 12% (asm.rkt or asm.cc)

Modify your assembler to correctly handle mult, multu, div, and divu.

Click here to return to the top of the page.

Problem 10 — 8% (asm.rkt or asm.cc)

Modify your assembler to correctly handle sw and lw.

By the end of this problem, your assembler should be able to correctly translate any MIPS assembly language program and write ERROR to standard error for any input that is not a valid MIPS assembly language program.

Click here to return to the top of the page.

Language-Specific Details

Racket

The provided starter asm_rkt.zip has a function called scan that takes a string and produces a list of tokens.

The Using Racket in CS 241 document contains hints and techniques for using Racket to write the assembler. See also the comments in the provided scanner.

You can run the Racket starter code on the student environment using the command racket asm.rkt.

Click here to return to the top of the page.

C++

The provided starter asm_cpp.zip has a method called assemble that is called with a vector of lines containing tokens.

When submitting to Marmoset, if you have chosen C++, you will need to add all your files to a .zip file and submit that to Marmoset.

The STL Quick Reference for CS 241 document outlines the parts of the STL most likely to be of use in CS 241.

You are strongly advised to check for pointer-related errors by vetting your programs with valgrind. To do this, run "valgrind program optionsAndArguments" instaed of just "program optionsAndArguments" on a Linux computer — valgrind is unreliable or unavailable on other environments. Marmoset will run your sugbmission with valgrind as well, and will reject any submission that is reported to leak memory. Be aware that valgrind increases the execution time of your program by a factor of 5 to 20.

You can compile the C++ starter code using the command g++ -std=c++14 -o asm asm.cc scanner.cc. This command will create a file called asm which contains the compiled program and can be run using the command ./asm.

Click here to return to the top of the page.