Write a program truthtable that reads a file containing a description of a circuit, and
prints that circuit’s truth table. The files specify (1) the number and names of each input to the
circuit, (2) the number and names of each output from the circuit, and (3) the logic gates and
components that make up the circuit. In order to indicate the connections between gates, each
connection is also given a name.
For example, this is a description for a circuit that implements a 3-argument AND gate:
INPUT 3 a b c
OUTPUT 1 d
AND a b x
AND c x d
Note that it contains three inputs (a, b, and c), a single output (d), and two AND gates, each of
which has two inputs and one output. The variable x indicates an internal connection between the
first AND gate and the second. See section 3 for details on the specification language.
1
When given this file, truthtable should print:
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 0
1 0 0 | 0
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1
The three columns on the left correspond to the three inputs, and the column to the right corresponds
to the output.
This assignment has two parts:
Part 1 (100 points) For this part, the circuit descriptions will be sorted so that each temporary
variable appears as an output parameter before any appearances as an input variable.
Part 2 (Extra Credit) For this part, the circuit descriptions will not be sorted, meaning that a
temporary variable may be used as an input parameter before its use as an output parameter.
2 Program
truthtable takes a single argument, which is the name of a file containing a circuit description.
The behavior of truthtable is unspecified if it receives no arguments or more than one argument,
but you should still check that the number of arguments is correct. (One possibility is to have
truthtable read from standard input if no file argument is given.)
Usage
$ ./truthtable my-cool-circuit.txt
0 0 | 0 0
0 1 | 0 1
1 0 | 0 1
1 1 | 1 0
Input The input to your program will be a single circuit description using the language described
in section 3. The first argument to truthtable will identify a file containing this circuit description.
You MAY assume that the input is correctly formatted and that no variable depends on its own
output.
Output The output of truthtable is a truth table showing each combination of inputs and the
corresponding output for the specified circuit. Each column in the table corresponds to a specific
input or output variable, which are given in the same order as their declaration in the INPUT and
OUTPUT directives. Columns are separated by a single space, and a vertical bar (|) occurs between
the input and output variables.
Note that no white space follows the final column.
2
3 Specification Language
In this language, circuits are specified with a series of directives. These directives refer to various
named variables, which correspond to wires in a circuit diagram. Many of the directives describe a
logic gate or similar building block, indicating which varibles correspond to its input and output.
Each directive has the form of a name followed by one or more parameters, separated by
whitespace. The name indicates which directive and determines the number of parameters. Some
directives take a variable number of parameters; their first parameter will always be an integer which
is used to determine the number of parameters. Depending on the directive, some parameters will
be inputs and some will be outputs.
Variables in a circuit can be classified into three non-overlapping sets. Input variables must be
declared by the INPUT directive, and may only occur as input parameters. Output variables must be
declared by the OUTPUT directive and may occur exactly once in an output parameter. All other
variables are temporary variables and must occur exactly once as an output parameter and zero or
more times as an input parameter.
A variable name consists of a letter followed by zero or more letters or digits. You may assume
that variable names are no longer than 16 characters.
In addition to variables, the constant inputs 0 and 1 may be used as input parameters. These
are always false and always true, respectively.
Finally, _ may be used as the output of a gate, indicating that the output of a gate is discarded.
Use of _ is equivalent to using a temporary variable that is not used as an input to any other gate.
Gate Inputs Gate Outputs
Input variables Output variables
Temporary variables Temporary variables
0, 1 _
Note that whitespace may include one or more spaces, tabs, or newline characters. It is
recommended to use fscanf() to read the files, and to use a format code such as ” %16s” to skip
whitespace before reading the next variable or directive name.
By convention, we will use multiple spaces to separate the inputs and outputs of a gate, but this
is not required and has no special meaning. It is purely for readability. Similarly, we will often put
a blank line between OUTPUT and the first gate, but this is also done purely for readability. Your
program should treat repeated newlines the same as single newlines (or, ideally, the same as any
whitespace).
Use of fgets() is not recommended and will only make your life harder. Remember that
fscanf() is not limited to reading an entire line at once.
3.1 Directives
This section describes each of the directives used to describe a circuit. Each directive is followed by
several parameters. A parameter n is always an integer and has a special meaning. Input parameters
are indicated as i and output parameters are indicated as o. Ellipses (· · ·) are used to indicate a
variable number of parameters.
• INPUT n i1 · · ·in
Declares n input variables. This directive must always occur first in a circuit description