[an error occurred while processing this directive]

Table-Driven Design

Introduction

In many programs, there is a need to deal with entities whose handling requires a variety of distinct behaviors. A straight-forward approach to algorithm design deals with the different kinds of entities using case statements or extended if-then-else statements. However, if the number of types of the entities is large then this approach lead to large amounts of code, often with poor run time characteristics. A table driven approach uses tables to classify the different kinds of entities, aiming at a reduction of the number of cases requiring distinct code.

For example, an assembler needs to translate a variety of machine instructions into machine code. These instructions often have varying numbers of operands and varying operands types. Translating an instruction involves combining information based on the instruction mnemonic and the operands into a binary coded instruction. For fixed-length instruction coding, the binary code instruction is constructed by starting with a base code for the mnemonic and adding operand data using bitwise or operations.

One obvious use of a table in algorithm design is the for retrieving the base code for an instruction. However, this use does not involve any classification of instructions. With careful classification, tables can often be put to more profitable uses.

Classification

The heart of table-driven design is a classification of the kinds of entities that the software needs to handle. For example, in some simple assembly languages, there are only a few types of instructions when classified according to the number and types of their operands.

If the programming language supports enumerated types then an enumerated type can be defined with a value for each type of instruction. Then a table of instruction data can be constructed that contains operand type information in addition to the base code for each instruction. The operand type can be used in a case or switch statement to control handling of operands.

For languages, such as C, that allow functions to be treated like other kinds of data, functions for handling operands can be stored in the instruction table. Each instruction has the particular function that is needed for dealing with its operands stored in its instruction data entry.

Often, there are different levels of granularity possible in the classification involved in a table-driven design. For example, in an assembler the machine instructions may be assigned a single classification based on all of the operands (course granularity), or individual operands can be classified (finer granularity).

Example Code

A portion of a simple example of table-driven design can be found in instructionTable.C. This example deals with code generation for a simple assembly language. All operands are integer literals representing immediate values, addresses, or register numbers. The instruction data table contains structs with two members: an operand classifier and an instruction base code. Since the information in the table is known in advance, the table is constructed as an initialized array. It is searched using the C standard library function bsearch(). The correctness of this approach depends on putting the instruction mnemonics in alphabetical order.

The instruction set for this example is simple enough that there are only four categories of instructions, based on the types of all operands for an instruction. For more complex instruction set, individual classification of operands may lead to better code organization. If this is done then the structs in the instruction data table contain one member for each operand in an instruction in addition to the instruction base code.

[an error occurred while processing this directive]