You have to write the code in the truthtable.c file and use malloc. To run the program you have to use the grader.py file and test out the test case provided in the data file. Finally you have to make sure there aren't any memory leaks. The full instructions are in the pdf file attached below and there is a zip file which has the full folder where the code needs to be in src/truthtable.c.
The whole program has to be dynamic so nothing can be restricted and the main method has to be this: “ int main(int argc, char *argv[]) { /* ... */ } “
MAKE SURE THIS IS IN C AND NOT C++ PLEASE I DON'T WANT YOU TO REWRITE THE CODE FULLY
This assignment will provide more practice programming in C and working with circuits and digital logic. You will write a program that reads a circuit specification and generates a truth table for that circuit. Section 2 describes the required interface and behavior of your program, and section 3 describes the specification language. Advice Start working early. Before you do any coding, make sure you can run the auto-grader, create a Tar archive, and submit that archive to Canvas. You don’t want to discover on the last day that scp doesn’t work on your personal machine. Decide your data structures and algorithms first. Section 4 describes one method for implementing the program that performs well, but you are free to design your own. Writing out pseudocode is not required, but it may be a good idea. When writing your program, use the auto-grader to create the build directory, and use make in that directory to compile your code. This will save you time, keep your source code separated from your compiled files, and ensure that you are compiling your program consistently. Start working early. You will almost certainly encounter problems you did not anticipate while writing this project. It’s much better if you find them in the first week. 1 Overview You will 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. 3 • OUTPUT n o1 · · · on Declares n output variables. This directive must always occur second in a circuit description. • NOT i o Represents a not gate in logic design. Computes o = i. • AND i1 i2 o Represents an and gate in logic design. Computes o = i1i2. • OR i1 i2 o Represents an or gate in logic design. Computes o = i1 + i2. • NAND i1 i2 o Represents a nand gate in logic design. Computes o = i1i2 • NOR i1 i2 o Represents a nor gate in logic design. Computes o = i1 + i2 • XOR i1 i2 o Represents an xor gate in logic design. Computes o = i1 � i2, where � indicates exclusive or. • DECODER n i1 · · · in o0 · · · o2n�1 Represents an n : 2n decoder gate in logic design. The first argument gives the number of inputs, n. The next n parameters are the inputs, followed by 2n parameters indicating the outputs. The inputs are interpreted as an n-bit binary number s in the range 0, · · · , 2n � 1, where i1 is the most significant bit and in is the least significant bit. The output os will be 1 and all others will be 0. • MULTIPLEXER n i0 · · · i2n�1 i01 · · · i0n o Represents a 2n : 1 multiplexer gate in logic design. The inputs to a multiplexer are either regular inputs or selectors, indicated by i and i0, respectively. The first parameter, n, gives the number of selectors. The next 2n parameters give the regular inputs, followed by n selector inputs, and finally the output. The selector inputs are interpreted as an n-bit binary number s in the range 0, · · · , 2n � 1. The output is o = is. • PASS i o Represents the absence of a gate. Computes o = i. This may be used to convert a temporary variable into an output variable. 3.2 Parsing The specification language can be thought of as a sequence of tokens separated by whitespace. No keyword or variable name in the language exceeds 16 characters, so it is safe to use fscanf() with the format code %16s, which will read a token of up to 16 non-whitespace characters. Each directive will be either be followed by a fixed number of parameters or by a number that will determine the number of parameters. Thus, your parsing code will always be able to tell whether it expects a directive name, integer, input parameter, or output parameter next. 4 For safety, your program should always check that fscanf() succeeded and that it received the expected token type. If something has gone wrong, either because of bad input or a program error, you want to know about it! 3.3 Examples This circuit describes a half-adder, where s is the sum and c is the carry. INPUT 2 A B OUTPUT 2 C S AND A B C XOR A B S This circuit computes z = ab+ ac: INPUT 3 a b c OUTPUT 1 z AND a b x AND a c y OR x y z Note that x and y are temporary variables, since they were not declared in INPUT or OUTPUT. This circuit description is invalid, becuase it uses an output variable as an input parameter: INPUT 3 IN1 IN2 IN3 OUTPUT 2 OUT1 OUT2 AND IN1 IN2 OUT1 OR