Mips Programming Assignment 6

CSE 378 Homework 1 - Part 3

Assembler Programming

Problem Overview

You're going to write a MIPS simulator, that is, a program that can simulate the execution of MIPS instructions. More precisely, your simulator handles exactly six instructions: , , , , , and . (The last is not an actual MIPS instruction, but is useful for obvious reasons. It's part of the Cebollita instruction set.)

Your program takes as input a program written using only those six instructions. You execute each of the instructions, in order, halting when you encounter a instruction. As you execute each instruction, you update values stored in the simulator's registers. That's pretty much all there is to it.

Your simulator happens to be written in MIPS assembler as well (or, actually, the subset of MIPS assembler that Cebollita implements).

Program Input

Input to your program is a list of instructions, encoded as decimal integer representations of the 32-bit machine instructions. For example: 5 537395212 554237972 554303505 19552293 1073741848 The first integer indicates how many instructions follow. The integers that come next are instructions, written in decimal (because the only routine available to read an integer from assembler requires decimal input). They correspond to the assembler program, and the hex encoded machine instructions, shown in the following output: 00000000 0x2008000c: addi $t0, $0, 12 00000004 0x21090014: addi $t1, $t0, 20 00000008 0x210a0011: addi $t2, $t0, 17 0000000c 0x012a5825: or $t3, $t1, $t2 00000010 0x40000018: halt

Program Output

None. We'll run your program in Cebollita and examine the contents of the simulated registers when it halts.

Skeleton Code

Having a look at skeleton code will probably make things somewhat less confusing. At the top, it allocates space to hold the program to be simulated and to keep the values in the simulated registers. In the section, the code begins by reading in the input: first the number of instructions in the input and then the instructions themselves. It then initializes the simulated PC, as a pointer into the memory holding the program to be simulated, and goes into a loop fetching instructions and updating the simulated PC to mimic sequential flow control. The skeleton doesn't actually simulate the effect of each instruction it fetches, though - that's what you'll implement. Instead, it simply checks whether or not the instruction just fetched is a . If not, it fetches the next instruction. Otherwise, the skeleton program itself halts.

Building Your Application

There are two steps:
  1. Assemble: $ java asm.parser mipsSim.s That produces file .
  2. Link: $ java asm.Linker prologue-standalone.o mipsSim.o (The order of the operands is significant.) That produces .
You can now execute in the Cebollita simulator: $ java dbg.UI a.exe

Preparing Test Input

It's a bit clunky to prepare the input to your simulator. The basic process is
  1. Create a small assembler program () that uses only the instructions your simulator supports.
  2. Assemble it to produce a file.
  3. Use to dump the instructions in hex.
  4. Convert the hex to decimal.
  5. Run your simulator and type in the input.

That's so painful that we're providing some automation to help. The distribution (see below) comes with a simple - it should be intelligible from what you've seen in CSE 303. The has four useful targets:


  1. will assemble and link your simulator ().

  2. will assemble , run on it to get the hex coding of the instructions, then run a program () to extract the hex instructions and turn them into decimal, and finally create a file () that is suitable for feeding as input to your simulator.

  3. will build your simulator, build the input file, and then invoke the Cebollita simulator to run your simulator, providing it with input from . (The switch to causes it to read input from the named file, rather than from the keyboard.)

  4. deletes all intermediate files.
You can (and should) use the even if you're not currently 100% comfortable with - it's easy, just try it. Your system must have installed, though, to use all the facilities provided.

Caveat

The Cebollita assembler doesn't implement everything described in the text. In particular, it doesn't implement pseudo-instructions - instructions that are not actually supported by the hardware, but for which the assembler inserts one or two instructions that achieve the same effect. Examples are things like , , and . It also doesn't implement the full MIPS instructio set. It's very unlikely, though, that you'll want to use an instruction that isn't available.

I would guess that the vast majority of you won't come across any distinctions between what the book describes and what Cebollita implements. If something won't assemble, though, the Cebollita documentation is the place to look for exactly what it supports.

Un-Caveat

You can (and should!) assume in your code that the input is always error free - there are 10 or fewer instructions, and each is one of the six your simulator supports.

This is terrible programming practice, but makes life a lot easier, especially when hand coding assembler. (Never, ever, make this assumption again, though. I hang my head in shame that we need it to make this assignment reasonable.)

Downloading Starter Files

Download hw1programming.tar.gz, and save it in the directory you want to work in. Expand it like this: $ tar xzf hw1programming.tar.gz That will produce files , , , , and .

How To Turn In

TBA

CS 241 — Winter 2018 — Assignment 6

This assignment is the first in a series of four that involve learning WLM and writing a compiler that translates WLM to MIPS assembly language.

Please consult WLM Programming Language Tutorial for an informal explanation of WLM; The WLM Language Specification should be consulted for the definitive specification of the WLM language.

All solutions must be submitted to Marmoset. Your submissions for A6P1 and for A6P2 should each be a file containing a complete WLM program. Your submission for A6P3 should be a DFA in the format used in A5. Your submission for A6P4 should be a Racket, C++, or Scala program that implements a scanner for WLM.

The following WLM program computes the sum of two integers, a and b.

// // WLM program with two integer parameters, a and b // returns the sum of a and b // int wain(int a, int b) { return a + b; // unhelpful comment about summing a and b } You may test this program on the student.cs environment by placing it in a file named and entering the following commands, which compile it to MIPS machine language and run it with the familiar command from A1 and A2: cs241-wlmc test.wlm > test.mips cs241-twoints test.mips A6P1 through A6P3 familiarize you with the WLM programming language. Beginning with A6P4 and through the next four assignments, you will be writing a compiler that translates WLM into MIPS assembly language.

Problem 1 — 10 marks of 60 (filename: )

Write a WLM program like the one above to sum all the numbers between a and b, inclusive, where a and b are parameters. You may assume that -10000 ≤ a,b ≤ 10000, but do not assume that a < b.

Click here to go back to the top of the page.

Problem 2 — 10 marks of 60 (filename: )

Write a WLM program that takes two parameters, x and y, and returns the greatest common divisor gcd(x,y). You may assume that 0 < x,y < 231. Hint:

Click here to go back to the top of the page.

Problem 3 — 20 of 60 marks (filename: )

Using the DFA description file format described in assignment 5, create a deterministic finite automaton that recognizes any valid WLM token, from the list given in the WLM specification. The alphabet consists of every character that may appear in any token; this does not include white space characters.

[While a lexical scanner for WLM must allow WLM tokens to be separated by white space so that it may distinguish between two consequtive tokens (eg 42 and 17) whose concatenation would comprise a single token (eg 4217), a DFA that accepts only input comprising a single token has no such need.]

Hint: WLM tokens include keywords (such as int, return, etc.), as well as identifiers. When scanning WLM, two approaches are equally valid. One approach is to distinguish between keywords within the DFA, using separate states for each keyword. Another approach is to design a DFA that just recognizes identifiers and keywords the same way, and write additional code outside of the DFA to determine whether the token is a specific keyword or an identifier. For this problem and for Problem 4, you may choose either approach.

Click here to go back to the top of the page.

Problem 4 — 20 of 60 marks (filename: or or )

Write a scanner (lexical analyzer) for the WLM programming language. Your scanner should read an entire WLM program and identify the tokens, in the order they appear in the input. For each token, your scanner should compute the name of the token and the lexeme (the string of characters making up the token), and print it to standard output, one line per token.

For example, the correct output for the example WLM program above is:

INT int ID wain LPAREN ( INT int ID a COMMA , INT int ID b RPAREN ) LBRACE { RETURN return ID a PLUS + ID b SEMI ; RBRACE }

If the input cannot be scanned as a sequence of valid tokens (possibly separated by white space as detailed in the WLM language specification), your program should print an error message to standard error containing the string , in upper case. We recommend that you try to make the error message informative to help with debugging.

You can use the tool to help check the correctness of your solution.

You may wish to modify asm.rkt, Asm_scala.zip, or asm_cpp.zip to solve this problem. These are the scanners that were given to you for assignment 3. Note that the lexer in asm.rkt, Asm_scala.zip, and asm_cpp.zip is based on a DFA that repeatedly recognizes the longest prefix of a string that is a token. You should be able to replace the DFA (which recognizes MIPS assembly language tokens) by one which recognizes WLM tokens (see Problem 3 above).

For this problem only, all of the Marmoset tests are public tests. There are no release tests or blind tests.

Click here to go back to the top of the page.

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *