Princeton University
COS 217: Introduction to Programming Systems

Purpose

Background

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:

• A circuit description grammar that defines the circuit description language.
• The format of the input that the circuit simulator should read from stdin.
• The format of the output that the circuit simulator should write to stdout.

On arizona, you are given two code modules:

• Lexer. Lexer is a lexical analyzer. It reads the sequence of characters that comprises a circuit description, and converts it into a sequence of tokens. The types of tokens that it creates are listed below.
• Parser. Parser is a syntactic analyzer. It accepts the sequence of tokens generated by Lexer, and verifies that the sequence forms a circuit description that conforms to the circuit description grammar. While doing so it calls functions of other modules (that you will create) to validate the semantics of the circuit description, and to translate the circuit description into a circuit internal form.

[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:

• Circuit. Circuit should be an abstract object that stores a circuit internal form. Parser calls Circuit functions to validate the semantics of the circuit description and to create the circuit internal form. Your Simulator module should call Circuit functions as it simulates the circuit.
• Expr. Expr should be an ADT that defines an expression. Parser calls Expr functions to create expressions. Your Simulator module should call Expr functions as it simulates the circuit.
• Simulator. Simulator should be an abstract object that simulates the circuit.  It should maintain the current state of the circuit. At each clock pulse it should (1) read the circuit inputs from stdin, (2) use those inputs, the current circuit state, and the circuit internal form stored in Circuit to compute the new circuit state, and (3) write the new circuit state to stdout. It should call Circuit and Expr functions while performing the simulation.
• A main module, containing a main function (and perhaps others). The main module should call the functions of the other modules to form the complete program. The main function should accept one command-line argument: the name of a text file that contains a circuit description.

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:

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.

More formally...

A program consists of these tokens:

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 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.

Logistics

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:

• The Lexer module source code files (lexer.h and lexer.c).
• The Parser module source code files (parser.h and parser.c).
• An executable version of a sample circuit simulator (samplecircuitsim). You can test your simulator by comparing its output to that of the samplecircuitsim.
• Numerous circuit description files (*.pgm) and input files (*.in) that you can use to test your circuit simulator.
• Files that you can use as input to test your three-bit accumulator circuit description (threebitaccum1.in, threebitaccum2.in), and the files that a circuit simulator should create when given your three-bit accumulator circuit description and those input files (threebitaccum1.out and threebitaccum2.out).
• A UNIX shell script (grade3 and supporting files) that automates the process of testing your circuit simulator and your three-bit accumulator circuit description.  You should make sure that your circuit simulator and circuit description pass the tests in grade3.

You should submit:

• The source code files defining your Circuit, Expr, Simulator, and main modules. You should also submit any additional modules (for example, SymTable, DynArray) that those modules use.
• A makefile. The first rule in the makefile should command the make utility to build a file named circuitsim containing the executable version of your program. Your makefile should use the "-Wall", "-ansi", and "-pedantic" compiler options. Your makefile should maintain object (.o) files to allow for partial builds.
• Your three-bit accumulator circuit description.
• A readme file.

Your readme file should contain:

• Your name.
• A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policies" web page.
• (If you are submitting your work late) An indication of how many "free late days" you wish to apply to this assignment.
• (Optionally) An indication of how much time you spent doing the assignment.
• (Optionally) Your assessment of the assignment.
• (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

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

Grading