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 execution. Finally, it executes the circuit internal form. 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.
The next assignment will ask you to enhance the circuit simulator that you create for this assignment.
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:
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. A statement ends with a semicolon. 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. A program can contain any number of input statements. An input statement can declare any number of 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. A program can contain any number of flip flop statements. A flip flop statement can declare any number of 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 infix expression. The expression defines the next state of the specified flip flop in terms of the circuit's 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.
More formally...
A program consists of these tokens:
| Token | Description |
| NUMBER_TOKEN | The character '0' or '1'. |
| IDENTIFIER_TOKEN | An alphabetic character, followed by any number of alphanumeric characters. Underscore ('_') counts as an alphabetic character. |
| LEFT_PAREN_TOKEN | The character '('. |
| RIGHT_PAREN_TOKEN | The character ')'. |
| AND_TOKEN | The character '&'. |
| OR_TOKEN | The character '|'. |
| NOT_TOKEN | The character '~'. |
| INPUT_TOKEN | The character sequence "INPUT". |
| FLIPFLOP_TOKEN | The character sequence "FLIPFLOP". |
| NEXT_TOKEN | The character sequence "NEXT". |
| SEMICOLON_TOKEN | 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 ::= NUMBER_TOKEN element ::= IDENTIFIER_TOKEN element ::= LEFT_PAREN_TOKEN expr RIGHT_PAREN_TOKEN factor ::= NOT_TOKEN* element term ::= factor [AND_TOKEN factor]* expr ::= term [OR_TOKEN term]* inputstmt ::= IDENTIFIER_TOKEN+ flipflopstmt ::= IDENTIFIER_TOKEN+ nextstmt ::= IDENTIFIER_TOKEN expr stmt ::= INPUT_TOKEN inputstmt SEMICOLON_TOKEN stmt ::= FLIPFLOP_TOKEN flipflopstmt SEMICOLON_TOKEN stmt ::= NEXT_TOKEN nextstmt SEMICOLON_TOKEN program ::= stmt+
The input that the circuit simulator reads from stdin consists of lines. Here is an example of an input line:
50: 011
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 50 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
The output that the circuit simulator writes to stdout should list the value of each input and flip flop immediately after each clock. Specifically...
The first line of the output should be a heading. The heading should contain the names of the circuit inputs, followed by the names of the circuit's flip flops, separated by single spaces. The names should be listed in the order in which they are declared in the circuit description's INPUT and FLIPFLOP statements.
All lines other than the first should be of this form:
50 011 10
Each such line should contain the current clock pulse in a field of width four, a space, the value of each input at that clock pulse, a space, and the value of each flip flop at that clock pulse. 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 50 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 was 1, and the value of the second flip flop was 0.
To reduce the bulk of the output, the simulator should list the state of each flip flop for only those clocks that are listed in the input.
Finally, the circuit simulator should write to stderr an indication of how much CPU time the computer spent executing the circuit (printed using "%f" format), followed by a space, followed by the word "seconds."
Here is the output that your simulator should generate when given the "two-bit counter" circuit description and the input shown above:
x A B 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 0.010000 seconds
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.
The files defining the Lexer and Parser modules are available in directory /u/cs217/Assignment7. The executable version of a sample simulator is also available in that directory.
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 7 yoursourcecodefiles threebitaccum.pgm makefile readme