3 Tools

Various tools are used in CS241. Historically, they were all available only on the student Linux server. They are now slowly being duplicated as browser/web-based versions, to avoid overloading the servers. The web-based versions of these tools are available on this page.

All of these tools are available on the student Linux servers (linux.student.cs.uwaterloo.ca), by running source /u/cs241/setup.

If you can’t run the tools on the Linux environment, make sure you’ve run source /u/cs241/setup!

After you have run the setup command, simply type the name of the tool to use it. The tools do not get copied to your user folder or anything like that, the setup script simply does some configuration that lets you run the tools from anywhere.

The setup command only lasts for one login session. If you do not want to manually enter it every time you log in, put the command in the hidden .bash_profile file in your home directory, or in .profile if .bash_profile does not exist.

3.1 marmoset_submit

This tool lets you submit to Marmoset from the command line. Use it as follows:

marmoset_submit CS241 <AssignmentProblem> file1 file2 file3 ...

The <AssignmentProblem> part should be replaced with the name of the problem you are submitting to, like A4P2 or A9Bonus. This must exactly match the name shown on the Marmoset web interface and it is case sensitive. After the <AssignmentProblem part>, list all the files you want to submit.

For many problems you will just be submitting a single file, but you can provide multiple files on the command line, for example if your solution for a question is split into several modules. In this course, even if the assignment only specifies one particular file name, you are allowed to submit other files alongside the one with that name. For C++ programs, Marmoset will simply pass all the .cc files you submit to the compiler; a Makefile is not needed, and in fact any Makefile you submit will be ignored. (This is specific to the way CS241’s Marmoset scripts are set up and may not apply to other courses.)

Note that this is just a wrapper script for the command /u/cs_build/bin/marmoset_submit. You can use the /u/cs_build/bin/marmoset_submit command directly without running the CS241 setup command. Y You can also use marmoset_submit (whether through our wrapper script or directly using the cs_build command) in other courses that use Marmoset by just replacing CS241 with that course name.

3.2 cs241.binview

You can run cs241.binview online.

This tool lets you view the binary data stored in files in a human-readable form. If you view a file with cat or open it in a text editor like vim, your terminal will attempt to display the binary data as ASCII (or maybe Unicode) characters. For a text file, this is exactly what you want, but for something like MIPS machine code it will probably look like gibberish.

The cs241.binview tool formats and prints the binary data as a sequence of 0 and 1 characters. It also has options for printing in decimal, hexadecimal, and ASCII.

3.2.1 Example

Suppose the file program.mips contains the machine code version of the following MIPS program (translated using an assembler like cs241.binasm):

You can use cs241.binview with the --all option to view the machine code in binary, decimal, hexadecimal and ASCII form.

If --all or other similar options are not used, the default is to produce binary output only.

3.2.2 Notes

• Run cs241.binview without arguments to get a help message showing all the options.

• When piping data to cs241.binview, you must pass the argument - to tell cs241.binview to read from standard input, like this: cs241.binasm < input.asm | cs241.binview -

• Aside from viewing things like machine code, this tool can also be used to check if the output of a program you write has unnecessary characters (like whitespace or "null" bytes) that normally wouldn’t show up with cat.

• cs241.binview is a simplified version of the standard Unix tool xxd. xxd is really helpful when poking around binary files, and you may find it useful for future courses as well.

3.3 cs241.bits

You can run cs241.bits online.

This tool converts text input containing sequences of ASCII 0 and 1 characters into the corresponding raw binary data. It will ignore all characters other than 0s and 1s in the input.

Note that the tool can only output data in chunks of bytes, because on modern operating systems, a file is a sequence of bytes rather than bits. If the number of 0s and 1s is not a multiple of 8, this means the last byte is incompletely specified. In this case, cs241.bits will print an warning and discard this incomplete byte.

3.4 mips.twoints

You can run mips.twoints online.

This is an emulator for running MIPS machine language programs. Once you have produced a machine language program using one of our assemblers, you can run it with this tool.

Obtaining input from standard input in MIPS is rather awkward, so for convenience, this tool allows you to provide two integers as input. The integers will be stored in registers 1 and 2.

To use the tool, give it the filename of the MIPS program you want to run as the first command line argument. By default, it will load the program at address 0x00. A second (optional) command line argument can be provided to load the program at a different address, although this is essentially never necessary in the course.

3.4.1 Example: cs241.bits and mips.twoints

We have prepared an ASCII text file representing a MIPS machine language program that loads two values, 11 and 13, into registers $8 and $9 respectively, then adds the values together and stores the result in $3.

Of course, the MIPS machine does not understand sequences of ASCII 0 and 1 characters. To actually run this program, we need to convert it to proper machine code. Fortunately, cs241.bits can do this. It will ignore the spaces and newlines and translate the text into the corresponding raw bits, producing a file containing six 32-bit words.

Now we pass the resulting machine language program to mips.twoints.

3.4.2 Error Messages

Here are brief explanations of some the error messages you might see from this tool. This is not necessarily a comprehensive list.

• Invalid opcode, Invalid function, Invalid trap: These basically all mean the same thing, that the MIPS emulator tried to execute something that is not a valid instruction. Whether it says opcode, function or trap depends on exactly what the 32 bits are that it tried to execute. A very common reason for this is that you forgot to assemble your program, and the emulator is attempting to execute the ASCII text source code instead of machine code. However, it can also happen in actual programs if you jump or branch to a location containing non-instruction data, or if you accidentally overwrite part of your code with non-instruction data.

• Unaligned access: This means the emulator tried to access a memory address that is not word-aligned (that is, not a multiple of 4). Usually the "access" is a Store Word (sw) or Load Word (lw) instruction, but this error can also occur if you try to jump to a non-aligned address with Jump Register (jr) or Jump and Link Register (jalr).

• Out of bounds: The MIPS emulator only allows your program to access a certain area of memory, from 0x00000000 to 0x00ffffff (inclusive). Accessing memory address 0x01000000 or larger gives this error. Because the stack pointer ($30) starts at 0x01000000, this error is sometimes (but not always) related to incorrect stack management. As with "unaligned access", the "memory access" that causes the error could be a store or load, but it could also be a jump.

• Division by zero: You tried to divide by zero in your program.

• Bad numeric input: This error does not happen when running the MIPS program, but rather when entering the numbers for $1 and $2 before the program starts. It means your input could not be parsed as a number, or was out of range.

3.5 mips.stepper_twoints

This is a version of mips.twoints that allows you to interactively step backwards and forwards through the assembly language program. You may need to increase the size of your terminal window to run it. Further usage instructions are given in the program itself. The tool is maintained by Nomair Naeem and bugs can be reported to mailto:nanaeem@uwaterloo.ca. Unfortunately there is no equivalent stepper for mips.array or mips.stdin currently.

3.6 mips.stdin

You can run mips.stdin online.

This is a MIPS emulator that works almost exactly like mips.twoints but does not ask the user to input two integers. It is useful when testing programs that primarily work with standard input rather than taking input from registers.

3.7 mips.array

You can run mips.array online.

Usage: mips.array program.mips

This is another MIPS emulator that is almost identical in functionality to mips.twoints, except that it allows you to provide an array as input instead of just two integers. When you run the program, it will ask for an integer representing the size of the array, and then ask you to enter each element of the array. The array will be loaded into memory somewhere shortly after the end of the program code. The emulator will assign $1 to be the starting address of the array, and $2 to be the size of the array, then run the program.

For general usage and error message information, see the section on mips.twoints.

3.8 cs241.DFA

You can run cs241.DFA online.

Usage: cs241.DFA < input.dfa

This tool reads a file in the DFA file format from standard input, and checks the file for errors. If no errors are found, the strings in the input section of the file are processed with the DFA. The tool outputs one line per input string, containing the string followed by true if the string was accepted and false otherwise.

3.9 mipsscan

You can run mipsscan online.

Usage: mipsscan < program.asm > tokens.scanned

This tool reads a MIPS assembly program from standard input and scans it into tokens. The result is a list of lines representing MIPS tokens, with each line containing a "kind" (the type of token) followed by a "lexeme" (the string the token corresponds to).

Scanning a MIPS program is a useful first step for implementing an assembler such as cs241.binasm.

3.10 cs241.binasm

You can run cs241.binasm online.

This is an assembler that takes a MIPS assembly language program as input (from standard input) and produces a MIPS machine language program in binary as output (on standard output).

3.10.1 Example

Suppose input.asm contains the following text:

You can assemble this program as follows:

If you pass the command line argument --prescanned, then cs241.binasm will take its input in the format produced by mipsscan. For example, if input.prescanned contains the following text:

3.11 wlp4c

You can run wlp4c online.

Usage: wlp4c < program.wlp4 > output.mips

This tool reads a WLP4 program from standard input and produces on standard output a compiled MIPS machine language program. The compiled program should be run with either mips.twoints if the parameters of wain are (int, int), or with mips.array if the parameters of wain are (int*, int). The values for $1 and $2 are used as the first and second parameters. The return value of the program is placed in $3.

The input should be WLP4 source code like below, not the result of the scanning or parsing phase. The wlp4c tool will do the scanning and parsing itself.

Note that wlp4c performs semantic analysis and will reject programs that do not follow the name and type rules. Thus you can use wlp4c to check the semantic validity of a WLP4 program.

3.12 wlp4scan

You can run wlp4scan online.

Usage: wlp4scan < program.wlp4 > tokens.scanned

This tool reads a WLP4 program from standard input similar to wlp4c, but only performs the scanning phase of compilation. The result is a list of lines representing WLP4 tokens, with each line containing a "kind" (the type of token) followed by a "lexeme" (the string the token corresponds to).

3.13 wlp4parse

You can run wlp4parse online.

Usage: wlp4parse < tokens.scanned > program.wlp4

This tool takes a scanned WLP4 program (that is, a list of tokens produced by wlp4scan) on standard input, and produces on standard output a WLP4I file representing the parse tree for the program. A WLP4I file is essentially just a preorder traversal of the parse tree, so it encodes all the same information as the tree itself.

Typically you wouldn’t call wlp4parse on its own, and you would instead pipe it the output from wlp4scan, since wlp4parse requires the input to be scanned first. For example, if program.wlp4 contains WLP4 source code (not scanned yet) you could run the following command:

This avoids the need to create a temporary file to hold the scanned program.

3.14 wlp4type

You can run wlp4type online.

This tool can be used to convert a WLP4 Intermediate (.wlp4i) file to a WLP4 Typed Intermediate (.wlp4ti) file. The tool checks the program represented by the .wlp4i file for semantic errors, and if there are no errors, it outputs a .wlp4ti file representing the type-annotated parse tree.

Usage: wlp4type < program.wlp4i > program.wlp4ti

3.15 cs241.cfgcheck

You can run cs241.cfgcheck online.

Usage: cs241.cfgcheck < input.cfg

This tool reads a CFG component followed by a sequence of zero or more DERIVATION components. If the CFG and derivations are valid, it prints information about the CFG, and prints the rules used in each derivation. It then prints the terminal string arrived at by the derivation. If the CFG is malformed, or the derivation is invalid, an error message is printed, and the tool quits.

3.16 cs241.treeprint

You can run cs241.treeprint online.

Basic Usage: cs241.treeprint < input.cfg

This tool reads a CFG component followed by a sequence of one or more DERIVATION components. It prints a representation of the parse tree corresponding to each derivation.

By default, the tool uses Unicode characters to make the tree look nicer. If your terminal does not display these characters correctly, you can pass the command line argument --ascii:

cs241.treeprint --ascii < input.cfg

This tool also allows you to print parse trees for WLP4 Intermediate (.wlp4i) file to a WLP4 Typed Intermediate (.wlp4ti) files Pass the command line argument --wlp4 to indicate that the input is one of these file formats.

cs241.treeprint --wlp4 < input.wlp4i
cs241.treeprint --wlp4 < input.wlp4ti

3.17 cs241.slr

You can run cs241.slr online.

Usage: cs241.slr < input.cfg > output.slr1.

This tool takes a CFG component representing a non-augmented grammar on standard input, augments the CFG, and produces a file representing the augmented CFG and its SLR(1) DFA. This information can be used to write parsers for any SLR(1) grammar.

This tool uses the SLR(1) DFA construction, so the tool will not work for all grammars. It will only work if the SLR(1) construction happens to produce a conflict-free DFA for the grammar. In particular, the tool will not work for ambiguous grammars.

3.18 cs241.linkasm

You can run cs241.linkasm online.

This assembler has all the features of cs241.binasm and supports two additional directives: .import and .export. These can be used to import label definitions from assembled MIPS programs, or to export label definitions which allow other programs to import them. This allows the creation of MIPS "libraries" which export useful procedures that other code can use.

This assembler produces MERL files rather than plain machine code. If your program imports labels from other MERL files, you will need to use cs241.linker to combine the MERL files.

3.18.1 Example

Suppose we have the following assembly files that use the .import and .export directives:

These programs don’t do anything interesting, and are just to give an example of the syntax. We can assemble these programs as follows:

Using cs241.binasm to assemble these would produce an error since it does not support .import or .export.

Note that here we have simply assembled two separate programs that don’t know anything about each other. If we tried to execute import.merl it would get stuck in an infinite loop, since the label import has not been resolved, and unresolved labels default to value 0. To resolve the import we would have to use cs241.linker.

3.19 cs241.linker

You can run cs241.linker online.

Usage: cs241.linker file1.merl file2.merl file3.merl ... > linked.merl

This tool links two or more MERL files together into a single MERL file. The files are provided as command line arguments, not using standard input. For example, we could link the MERL files produced in the cs241.linkasm example as follows:

3.20 cs241.merl

(There is no web version of this tool. Instead, its functionality in the web version is included in cs241.linker, above)

Usage: cs241.merl address < input.merl > output.mips

This tool reads a MERL file from standard input and produces plain MIPS code on standard output. It strips out the relocation and linking metadata, and relocates the program to run at the address specified by the command line argument. The address in the above usage example should be replaced by a number; it does not mean the literal string "address".

Normally address 0 is used, since the MIPS machine loads programs at address 0 by default, so typical usage would look like: cs241.merl 0 < input.merl > output.mips

The tool will produce information about the MERL metadata on standard error. You can use this to programmatically compare the metadata for two MERL files: sort the standard error results (since the MERL files may have the same metadata entries but different ordering) and run diff on the sorted files. If you do not want to see this metadata information, you can redirect standard error to /dev/null as follows: cs241.merl 0 < input.merl > output.mips 2> /dev/null