Project Description | Provided Files | Implementation | Ensuring Quality | Submission Requirements

Review Of: C

Label Table: Data Structure for an Assembler

Project Description:

In this project you will complete a set of functions for constructing and using a table of labels and their addresses, which will be used later in the Assembler Programming Project. (See What (and Why) is a Label Table?) The implementation of the Lable Table will be similar to the Java ArrayList class so that it can grow dynamically as the program runs, without having to know the eventual capacity up front. (Arrays in C, and in Java also, must be defined with a static capacity when they are constructed.) Thus, the Label Table will be a list of Label Table Entries, where each entry is a (label, address) pair.

C is not an object-oriented language, but the data structures and methods for the Label Table have been packaged together in files ("encapsulated" in OO terminology) in a way that is inspired by OO methods. (More information about this program appears below.)

The goal of the project is to gain more familiarity with C, including dynamic memory allocation, by writing some useful functions for a future programming project.

Later in the quarter you will be writing an assembler program. One of its associated data structures is a table containing instruction labels and their corresponding addresses. For example, in the code fragment below if the first instruction labelled main were at address 1000, then begin would be at address 1004, loop would be at address 1012, and finish would be at address 1032 (since all MIPS instructions are 4 bytes long). This would result in the following label table.

main:   lw $a0, 0($t0)
begin:  addi $t0, $zero, 0        # beginning
        addi $t1, $zero, 1
loop:   slt $t2, $a0, $t1         # top of loop
        bne $t2, $zero, finish
        add $t0, $t0, $t1
        addi $t1, $t1, 2
        j loop                    # bottom of loop
finish: add $v0, $t0, $zero
            

Provided Files:

You should implement the Label Table in a new directory, not the one containing your Disassembler files, so that you don't have naming conflicts, especially with the Makefile. (Note that although this Makefile is different, the printDebug, printError, and process_arguments functions are the same.)

• Main Label Table Files:
  • LabelTableArrayList.h (header file containing declarations for Label Table functions; does not require modification)
  • LabelTableArrayList.c (incomplete: you should complete the printLabels and findLabelAddr functions first, since they are the simplest and can be tested with a statically-created (or "hard-coded") table)
  • testLabelTable.c (incomplete test driver)
• Other Useful Files: (fully implemented)
  • Makefile (compiles program)
  • printFuncs.h (a header file with declarations for printDebug and printError
  • printDebug.c (prints debugging messages)
  • printError.c (prints error messages)
  • process_arguments.c (allows command-line specification of whether to include debugging output; has an associated process_arguments.h header file)
• Other Files Needed by Makefie:
  • assembler.h (header file will be used by Assembler; needed to use Makefile)
  • getToken.h (another Assembler header file needed to use Makefile)

Compiling with Makefile

The Makefile contains information for the make command, telling it how to compile this program. (Type make at a command-line prompt or, if you are using an IDE, your IDE may be able to use makefiles.)

The make command will create a compiled executable called testLabelTable. You can run your program by typing its name at the command line. If you don't want to have to keep typing ./testLabelTable, make use of the filename completion feature in bash/zsh/etc (hit tab after you have provided enough letters to uniquely identify the file) or edit the makefile and change the name of the executable at the end of the gcc command to something shorter, like testLT or even just tlt:

    gcc ... -o testLT

You can run the program, but it won't do anything visible until some appropriate test cases have been added to the main function. (Note: this program, like the DisUtilDriver test driver, allows you to turn on debugging at the command line; see below for more information about printDebug. Unlike DisUtilDriver, though, it does not read input from standard input or a file.)

Debugging with printDebug

If you want to add extra, informative statements to your code that will be helpful when you are debugging, but that you do not want to be part of the final output, you can use the printDebug function. printDebug takes the same type of arguments as printf, but it only prints the messages when debugging has been turned on.

You can run your program with debugging on by calling the program with an argument that specifies the debugging state. For example,

    ./testLabelTable 1

will run the program with debugging turned on, while calling ./testLabelTable 0 will run the program with debugging turned off. (The process_arguments function in the test driver handles this; it looks to see if a debug flag is being passed to the program as an argument, and, if so, sets the debugging state accordingly.)

Implementation:

LabelTableArrayList.h contains two struct definitions. One describes the (label, address) pair that makes up each entry in the table. The second bundles the table (actually a pointer to a dynamically created array of table entries) with the table's current capacity and number of active entries.

LabelTableArrayList.c contains templates or incomplete versions of a number of functions for initializing such a table, resizing it, adding a new entry, finding the address for a particular label name, and printing the contents of the table. LabelTableArrayList.h and LabelTableArrayList.c provide more complete specifications for these functions. (tableResize is complete; the other functions are not.)

• Start by implementing and testing the printLabels function, so that you can use it to help you in testing the other functions. You can use the testLabelTable.c test driver provided above for your testing. This driver has a small, simple static table structure already set up, that you can use for your initial tests. The printLabels function should print all the labels in the table, along with their associated addresses. You should provide descriptors for each field to make the table more readable (either column headings or immediately before the fields, e.g., "Label: StartLoop").
• Next, you should implement and test the findLabelAddr function. The test driver file above contains an incomplete helper function, testSearch, that should call findLabelAddr and print the address associated with the given label if the search was successful. Update the testSearch function in the test driver and call it from main to test the findLabelAddr function in LabelTableArrayList.c.

Note that the printLabels function and the findLabelAddr function are the only Label Table functions that should be called on the static table structure provided to you. The other functions assume a dynamically-allocated data structure and, in fact, may try to change the data structure in ways that would crash your program if the data structure is not dynamic.

• Next, move on to the functions that work with dynamically-allocated table entries — tableInit, addLabel, and tableResize. tableResize is already fully implemented, but you need to be careful about the parameters you pass to it from addLabel to make sure that it resizes correctly even when adding the first label. In the test driver, do not try to test these functions using the static array of label entries; instead, create a new table, initialize it using tableInit, and add entries using addLabel (which should call tableResize if necessary).

Note: the code in LabelTableArrayList.c dynamically allocates space for the internal array of table entries, but not for the top-level table structure itself. Each table function expects a pointer to an existing table structure as its first parameter.

Ensuring Quality

As specified in the syllabus, your program should adhere to the Kalamazoo College CS Program Style Guide and Documentation Standards, including use of the Braces Line Up style pattern.

To ensure that all function calls are syntactically correct (match the function definitions), you should include function declarations for all of your functions in one or more header files, and include the header file(s) in all appropriate C source files (*.c files).

The Makefile I have provided specifies a set of compiler options that will help you catch many errors at compile time. These options generate warnings about questionable constructions that often indicate programmer confusion or actual logic errors. You may have to make adjustments to the Makefile, though, if the specific options or option names for your compiler are somewhat different.

Be sure that your final test program tests all of the functions in LabelTableArrayList.c, including boundary conditions (table is empty, full to capacity, adding a label beyond the current capacity, etc.). The full range of tests should focus on the dynamic table. (The static table is merely provided as a simple tool for your initial testing of printLabels and findLabelAddr, since you use them to verify your testing of the other functions.)

Submission Requirements:

Your submission should contain;

• All the source code for your program (including header file(s) and makefiles).
• The output produced by your program when it runs. In Unix/Linux, you can run your program and save the output to one file and error messages to another file with the following:

          ./testLabelTable >myOutput.out  2>myErrors.err

  (The file names can be anything, but should be meaningful names.)

(Note: It is a good idea to run make clean in the directory before submitting; this will remove the machine-specific executable and intermediate "object code" files, since your code will have to be re-compiled on my machine anyway.)

The old rubric for grading the Label Table Programming Project was based on the following general categories. The current rubric is similar, but adjusted to fewer points to match the general grading scheme this quarter.

  Compiles and runs                                            5 pts
  Correctness (satisfies 17 specific criteria)                17 pts
  Updated comments at top of LabelTableArrayList.c                      1 pt
  Test driver (include sufficient test cases)                  6 pts

  Total:                                                      29 pts

Note that roughly 20% of the points were related to testing.