A digital circuit simulator is a program that can simulate any given digital circuit. A circuit simulator begins by reading a digital circuit description. It then parses the circuit description to produce a digital circuit internal form that is convenient for simulation. Finally, it uses the circuit internal for to simulate the circuit. It does so by reading digital inputs, computing the next state of the circuit, writing the state of the circuit, and iterating over some specified period of time.
Your task in this assignment is divided into two parts. Part 1 asks you to create a circuit simulator. Part 2 asks you to create a circuit description for a specified circuit.
In Part 1, you should use some given specifications and code to create a circuit simulator. More precisely...
In this document, you are given some specifications:
On arizona, you are given two code modules:
[The Lexer and Parser modules are defined as "abstract objects." An abstract object is a simpler alternative to an "abstract data type" (ADT). An ADT is appropriate when your program needs to create many objects of the same type; an abstract object is appropriate only when your program uses exactly one object of its type. Such is the case with Lexer and Parser: the circuit simulator uses only one instance of each. See Sections 19.1 and 19.2 of our King textbook for more information about abstract objects.]
Your job is to use the given specifications and Lexer and Parser modules to create four modules:
Your circuit simulator will make use of dynamically allocated memory. It should contain no memory leaks. That is, it should explicitly free all dynamically allocated memory when that memory is no longer required; for each call of the malloc (or calloc) function in your program, eventually there should be exactly one call of the free function.
You should use your SymTable ADT (from Assignment 2) to create the Circuit module. The document The SymTable ADT and the Circuit Simulator contains some suggestions about how to do that. If your SymTable ADT is not working, we will provide you with working symtable.h and symtable.o files at your request. You may also find the DynArray ADT (from precepts) useful; you are permitted to use it.
Here is an example of a circuit description:
INPUT x ; FLIPFLOP A B ; NEXT A = (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x) | (A & B & ~x) ; NEXT B = (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x) | (A & ~B & x) ;
A circuit description is essentially a program expressed in a special-purpose programming language. In that language, a program consists of statements. Each line of the program can contain zero or more statements. A statement begins with a keyword that indicates its type. A statement may cross multiple lines. The example program contains four statements.
An input statement declares inputs to the circuit. It consists of the keyword INPUT, followed by a whitespace-separated list of input names, followed by a semicolon. A program can contain any number of input statements. An input statement can declare one or more inputs. An input must be declared before it is referenced in a "next statement." The example program contains one input statement. It declares one input, whose name is x.
A flip flop statement declares the D flip flops that the circuit contains. It consists of the keyword FLIPFLOP, followed by a whitespace-separated list of flip flop names, followed by a semicolon. A program can contain any number of flip flop statements. A flip flop statement can declare one or more flip flops. A flip flop must be declared before it is referenced in a "next statement." The example program contains one flip flop statement. It declares two flip flops, whose names are A and B.
A next statement defines a D flip flop. It consists of the keyword NEXT, followed by the name of the flip flop that is being defined, followed by an equals sign, followed by an infix expression, followed by a semicolon. The expression defines the next state of the specified flip flop in terms of the circuit's current inputs and current flip flop states. It is erroneous to define a flip flop that has not been previously declared. It is also erroneous for the expression to reference an input or flip flop that has not been previously declared. The example program contains two "next statements." The first defines the A flip flop, and the second defines the B flip flop.
An expression consists of a group of input references, flip flop references, operators, numbers, and parentheses. An operator is either & (meaning "and"), | (meaning "or"), or ~ (meaning "not"). A number is either 0 or 1.
Incidentally, the example program defines a "two-bit counter." The states of A and B can be viewed as comprising a two-bit binary number. If input x is 1, that binary number is incremented. If input x is 0, the binary number is decremented.
A program consists of these tokens:
|TKN_NUMBER||The character '0' or '1'.|
|TKN_IDENTIFIER||An alphabetic character, followed by any number of alphanumeric characters. Underscore ('_') counts as an alphabetic character.|
|TKN_LEFT_PAREN||The character '('.|
|TKN_RIGHT_PAREN||The character ')'.|
|TKN_AND||The character '&'.|
|TKN_OR||The character '|'.|
|TKN_NOT||The character '~'.|
|TKN_INPUT||The character sequence "INPUT".|
|TKN_FLIPFLOP||The character sequence "FLIPFLOP".|
|TKN_NEXT||The character sequence "NEXT".|
|TKN_EQUALS||The character '='.|
|TKN_SEMICOLON||The character ';'.|
One or more whitespace characters (space, tab, or newline) may appear between any two tokens.
Those tokens combine to form a program according to this grammar (expressed in BNF):
element ::= TKN_NUMBER element ::= TKN_IDENTIFIER element ::= TKN_LEFT_PAREN expr TKN_RIGHT_PAREN factor ::= TKN_NOT* element term ::= factor [TKN_AND factor]* expr ::= term [TKN_OR term]* inputstmt ::= TKN_INPUT TKN_IDENTIFIER+ TKN_SEMICOLON flipflopstmt ::= TKN_FLIPFLOP TKN_IDENTIFIER+ TKN_SEMICOLON nextstmt ::= TKN_NEXT TKN_IDENTIFIER TKN_EQUALS expr TKN_SEMICOLON stmt ::= inputstmt stmt ::= flipflopstmt stmt ::= nextstmt program ::= stmt+
The input that the circuit simulator reads from stdin consists of lines. Here is an example of an input line:
Each line contains a clock pulse, a colon, a space, and a sequence of contiguous binary digits. The clock pulse indicates the time at which the input should be presented to the circuit. The binary digit sequence indicates the value of each input. The order of the digits within the sequence corresponds to the order in which the inputs are declared in the program's INPUT statements. There should be one digit for each input. The example input line indicates that at clock pulse 25 the value of the first input should be 0, the value of the second input should be 1, and the value of the third input should be 1.
Here is an example of input to the circuit simulator that is appropriate for the "two-bit counter" circuit description given above:
0: 1 1: 1 2: 1 3: 1 4: 1 5: 1 6: 1 7: 1 8: 1 9: 1 10: 0 11: 0 12: 0 13: 0 14: 0 15: 0 16: 0 17: 0 18: 0 19: 0 50: 0
For simplicity, your circuit simulator may assume that the format of the data in stdin is correct. That is, your simulator need not validate the data that it reads from stdin.
The output that the circuit simulator writes to stdout should list the value of each input and flip flop immediately after each clock. Specifically, each line should be of this form:
25: 011 10
Each line should contain the current clock pulse, a colon, a space, the value of each input at that clock pulse, a space, and the value of each flip flop after the input(s) have been presented to the circuit. The input values and flip flop values should be listed in the order in which they are declared in the circuit description's INPUT and FLIPFLOP statements. The example output line indicates that at clock pulse 25 the value of the first input was 0, the value of the second input was 1, the value of the third input was 1, the value of the first flip flop became 1, and the value of the second flip flop became 0.
The circuit simulator should initially set all flip flops and inputs to 0.
Here is the output that your simulator should generate when given the "two-bit counter" circuit description and the input shown above:
0: 1 01 1: 1 10 2: 1 11 3: 1 00 4: 1 01 5: 1 10 6: 1 11 7: 1 00 8: 1 01 9: 1 10 10: 0 01 11: 0 00 12: 0 11 13: 0 10 14: 0 01 15: 0 00 16: 0 11 17: 0 10 18: 0 01 19: 0 00 50: 0 01
We will check the correctness of your output using automated tools, so your simulator's output should conform precisely to the specified format. You should use the UNIX "diff" command to make sure that your simulator's output is identical to the output produced by the provided sample simulator.
In Part 2, your job is to create a circuit description for a "three-bit accumulator" circuit. The circuit should have three inputs; their names should be i2, i1, and i0 (declared in precisely that order). The circuit should have three flip flops: s2, s1, and s0 (declared in precisely that order).
You should view the three inputs as forming a three-bit binary number. For example, if i2 = 1, i1 = 1, and i0 = 0, then the inputs form the number 110 (binary) or 6 (decimal). Similarly, you should view the three flip flops as forming a three-bit binary number. For example, if s2 = 1, s1 = 0, and s0 = 0, then the flip flops form the number 100 (binary) or 4 (decimal).
The job of the circuit is to accumulate the sum of its inputs, modulo 8, into its flip flops. Given the example inputs given above, the new state of the circuit should be s2 = 0, s1 = 1, s0 = 0, alias 010 (binary) or 2 (decimal).
You should create your circuit description in a file named threebitaccum.pgm. Of course you should use your circuit simulator from Part 1 to test your circuit description. Conversely, you will find your circuit description helpful in testing your circuit simulator.
You should develop on arizona. Use Emacs to create source code. Use gdb to debug.
The directory /u/cs217/Assignment3 contains files that are pertinent to the assignment:
You should submit:
Your readme file should contain:
You should not submit code for the given Lexer or Parser modules.
Submit your work electronically via the command:
/u/cs217/bin/submit 3 sourcecodefiles threebitaccum.pgm makefile readme