Project 2

• Marmoset secret tests: Unlike questions, the Marmoset tests for projects include secret tests, which are completely invisible before the project deadline. Secret test results will be made visible a few days after the deadline (once any extensions given for special circumstances have passed).
  • For projects, the majority of the marks are for secret tests.
  • While you cannot see how many marks are allocated to secret tests on Marmoset itself, we will post a mark breakdown on this page once the Marmoset tests are set up.
  • For projects, the public tests and release tests do not constitute a thorough test suite. They are meant to ensure your output follows the correct format, and that you have implemented all the specifications, but they do not test functionality on a deep level.
  • For projects, passing the public and release tests does not mean you are "done". You need to test your program thoroughly so that you are confident it will pass the secret tests.
• Notes for C++ users:
  • Valgrind is used to check for memory errors in your program. This does not only include leaks, but also other memory errors like invalid memory accesses or use of an uninitialized value. You will fail tests if Valgrind detects errors in your program. See this guide for tips on how to deal with Valgrind errors.
  • The exit function does not call destructors for stack-allocated objects, which may cause you to leak memory and fail tests. To exit after printing an error, throw an exception and catch it in main, then exit normally with return. Or if the error happens in main itself, you can just exit directly with return.
• Note for Racket users: Our Marmoset scripts cannot distinguish between an error produced by the error function, and other runtime errors caused by mistakes in your code. To report errors, rather than using error, print to standard error (e.g., with eprintf) and then call exit.

If you did not complete Part A of Project 1, you will need to use the Prescanned Format. Otherwise, you can choose which you prefer. The marking scheme is identical for both formats, and the Standard Format is arguably the more difficult option, since you need to ensure your scanner does not have bugs. The main reasons to choose the Standard Format are:

• You will have more flexibility about how to perform scanning and process the scanned input, since your scanner feeds directly into your assembler.
• You won't have to run all your inputs through mipsscan when testing.
• You will have a complete assembler that doesn't rely on course tools to work (well, aside from the MIPS emulator used to run your assembled programs). At the end of the course, if you complete all the projects, you can put them together into a complete compiler!

Given the following input, in Standard Format:

lis $3
.word 241
jr $31

ID lis
REGISTER $3
NEWLINE
DOTID .word
DECINT 241
NEWLINE
ID jr
REGISTER $31
NEWLINE

./asm < input.asm > output.mips

Note that you can run cs241.binasm with the Standard Format input to produce an expected output file:

cs241.binasm < input.asm > expected.mips

Given the following input, in Standard Format:

jar $31

ID jar
REGISTER $31
NEWLINE

./asm < input.asm > output.mips
ERROR: Invalid instruction jar

First, write code to process the scanned input line by line.

If using the Prescanned Format, create a struct or class for tokens that contains a kind and lexeme field. Read the tokens from the input and separate the input into lines (sequences of tokens). For example, maybe you could create a vector of vectors of tokens, where the inner vectors are individual lines, and the outer vector represents the whole program. When you encounter a NEWLINE token, this indicates the end of the current line and the start of a new line.

If using the Standard Format together with your own scanner, you have a little more flexibility, but in either case, set up your program so you can read the input line by line, and examine the tokens on each line.

Now, implement support for the .word directive, ignoring labels for now (so only decimal and hexadecimal integers are allowed as the operand).

For each line, first make sure the line is non-empty (it has at least one token on it). If the line is empty, just skip it.

Otherwise, check if the first token is a DOTID token with lexeme .word. If so, verify that the line has exactly one other token on it, and that this token is a DECINT or HEXINT token. If these conditions are not met, produce an error.

If the line is valid, convert the DECINT or HEXINT token into a numeric value and output the 32-bit binary encoding of this value. Repeat until all lines are processed.

Supporting labels requires structuring your assembler to perform two passes over the input, so it's best to add support for labels early on. This way you won't have to make major structural changes later on when your assembler is more complicated.

Split up your loop from Step 1 that processes the scanned lines into two loops. Move the part of the code that checks for syntax errors to the first loop. Move the part of the code that outputs the 32-bit binary encoding to the second loop.

Now add support for labels in .word directives.

• Modify the first loop to check for LABELDEF tokens at the start of lines and add them to the symbol table. Remember to check for duplicate definition errors.
• Update your .word syntax checking to allow ID tokens as operands.
• In the second loop, if the operand is an ID token, check if the label is defined. Produce an error if it is not defined. Otherwise, output the 32-bit encoding of the label's address.

First implement support for the add instruction. Check the instruction syntax in the first loop, and output the encoding in the second loop.

The other three instructions all have the same syntax as add: they take three register operands. The only difference is that the function bits in the machine language encodings are different for each instruction.

Think about how to structure your code to handle these instructions in a uniform way (as opposed to just copying and pasting your add code and changing it).

Remember to do error checking. Each of the instructions should have exactly three operands, which should be REGISTER tokens, and the operands should be separated by COMMA tokens. Any deviation from this is a syntax error.

Once you've figured out how to implement one instruction in your assembler, most of the remaining instructions will be easier. However, the branch instructions are a little more difficult to handle than something like add:

• The add instruction only allowed REGISTER operands, but in branch instructions, the third operand can be a DECINT, HEXINT, or ID (representing a label).
• To handle label operands, you need to convert the label to a branch offset. The conversion for branch instructions works differently from .word directives.
• The branch offset needs to be checked for out-of-range errors. Getting this range check correct is harder than you might expect.
• The encoding for branch instructions is a little more complicated than add and requires using bit masking with bitwise AND.

Implement support for the remaining instructions.

Most of the remaining instructions are similar to add, but with different numbers and positions of the register operands. Pay attention to the positioning when encoding.

The memory access instructions lw and sw are like beq and bne in terms of encoding. However, the syntax is totally different. You fortunately don't need to support label operands for lw and sw, but you do need to do range checking on the immediate operand.

Kind	Description of Associated Lexemes
ID	Identifiers: Strings starting with an alphabetic character (a-z or A-Z), followed by zero or more alphanumeric characters (a-z or A-Z or 0-9).
DOTID	Dot-Identifiers: An . character followed by an ID lexeme.
LABELDEF	Label Definitions: An ID lexeme followed by a : character.
DECINT	Decimal Integers: Strings which optionally start with a - character, followed by one or more decimal digits (0-9).
HEXINT	Hexadecimal Integers: Strings starting with 0x, followed by one or more hexadecimal digits (0-9 or a-f or A-F).
REGISTER	Registers: A $ character followed by one or more decimal digits (0-9). The numeric value of the string of decimal digits cannot exceed 31.
COMMA	Comma: A , character.
LPAREN	Left Parenthesis: A ( character.
RPAREN	Right Parenthesis: A ) character.
NEWLINE	Either a line feed character (ASCII 0x0a), or the two-character sequence carriage return, line feed (ASCII 0x0d, ASCII 0x0a). When printing this token, do not print the lexeme. Print a line containing only the kind.
?WHITESPACE	Whitespace: A sequence of one or more space (ASCII 0x20) or tab (ASCII 0x09) characters.
?COMMENT	Comment: A ; character, followed a sequence of zero or more ASCII characters that does not contain a line feed (ASCII 0x0a) or carriage return (ASCII 0x0d). (In other words, once a ; character is encountered, everything up to the next line feed or carriage return is a ?COMMENT.)

Restrictions:

• In a REGISTER token, the numeric value of the decimal integer following the $ character must not exceed 31.
• In a DECINT token, the numeric value of the decimal integer must lie between -2147483648 and 4294967295, inclusive. (This is the union of the signed and unsigned ranges for 32-bit integers.)
• In a HEXINT token, the numeric value of the hexadecimal integer must not exceed 0xFFFFFFFF.