Princeton University
COS 217: Introduction to Programming Systems

Assignment 3: A Digital Circuit Simulator


The purpose of this assignment is to help you learn about digital circuits. It will also help you learn about lexical analysis and parsing -- programming techniques that are used extensively in assemblers and compilers. Finally, the assignment will give you more experience with advanced C programming and the GNU/UNIX programming tools. In particular, it will give you experience with using abstract objects, C unions, and the "make" tool.


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

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. 

Part 1

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.

The Circuit Description Grammar

Here is an example of a circuit description:

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.

More formally...

A program consists of these tokens:

Token Description
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

factor ::= TKN_NOT* element

term ::= factor [TKN_AND factor]*

expr ::= term [TKN_OR term]* 




stmt ::= inputstmt
stmt ::= flipflopstmt
stmt ::= nextstmt

program ::= stmt+

The Input to the Circuit Simulator

The input that the circuit simulator reads from stdin consists of lines. Here is an example of an input line:

25: 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 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 from the Circuit Simulator

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.

Part 2

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


As always, we will grade your work on functionality and design, and will consider understandability to be an important aspect of good design. (Function-level comments in both .h and .c files are critical documentation.) To encourage good coding practices, we will take off points based on warning messages during compilation.