Project 3

This is an extra project for graduate students. Undergraduate students are not expected to do it (you can do it for fun, of course, but there will be no bonus credit).

Your task is to write a program that creates chip descriptions in our HDL format. More precisely, the input is a Boolean formula, the output is a chip that implements this formula.

A Boolean formula uses the binary operators + for OR, * for AND, -> for implication, and the unary operator ~ for NOT. AND * binds more closely than OR +, OR + binds more closely than implication ->, and ~ binds most closely. Parentheses can be used to group subexpressions. The only other input tokens are identifiers, consisting of the letters A to Z, a to z, and the digits 0 to 9, and not starting with a digit.

Remember that a -> b is equivalent to ~a + b.

Here are some examples:

  ~a + b * c
  a -> ~b + c
  ~(a + b)
  x * ~y + ~x * y

Your program reads from standard input. Each input line is of the form:

  Name = formula

where Name is an identifier and formula is a Boolean formula. Your program then writes a file Name.hdl that describes a chip with name Name that implements the formula. Every identifier in the formula becomes an input to the chip. There is only one output pin with name out. The formula must contain at least one operator, it cannot just be one variable.

The name out and all names starting with pin are forbidden as variable names, so you can use pin1, pin2, etc., for your internal connections.

If an input line is incorrectly formatted or the formula contains a syntax error, your program must print an error message and skip the line (continuing with the next line).

For instance, the first four chips from project 1 could be generated by the following input file:

  Not = ~in
  And = a * b
  Error1 = a * * b
  Or = a + b
  Error2 = a
  Xor = ~a * b + a * ~b

(The Error1 and Error2 lines only demonstrates error handling and generate no output file.)

Your output chips must only use Nand gates, nothing else. To get full points for the project, your generated circuits are not allowed to perform superfluous negations (that is, negate a signal twice). For instance, for these two inputs:

  Nand1 = ~(a * b)
  Nand2 = ~x + ~y

the output must contain exactly one Nand gate. Also, if you need an input in negated form, you must perform this negation only once (not for every subexpression where it is used). You are not expected to perform other optimizations.

You can use any of the following programming languages: Python, Java, Kotlin, Scala, C, C++. If you want to use a language not in this list, you need to get permission from me on Piazza first.

To help you debugging, here is a test input file:

Not = ~in
Error1 = a * * b
And = a * b
Or = a + b
Xor = ~a * b + a * ~b
Test1 = ~a + b * c
Test2 = a -> ~b + c
Nor = ~(a + b)
Nand1 = ~(a * b)
Nand2 = ~x + ~y
Equiv = (inA -> inB) * (~inA -> ~inB)
Error2 = a
LongNameTest = longInputA -> xy + ~xyz * xyzu + ~xyzuvwabc
Boat = (wolf + cabbage) * goat * ~farmer + (~wolf + ~cabbage) * ~goat * farmer
TV = (a -> b) * (~c + ~d) * ~(b * ~c + ~b * c) * (~a -> b * d)
Food = (potatoes * ~noodles + ~potatoes * noodles) * (potatoes -> ~bread) * (bread + ~potatoes -> ~noodles)
Drinks = (~water -> wine) * (wine * water -> ~juice) * (juice + ~water -> ~wine)

The file pp3.zip contains a sample HDL file generated by my example solution, as well as a test script for each generated chip. The two lines labeled Error1 and Error2 must generate an error message but no output chip.

You can either submit a single source file or a zip file with all sources to our submission server.

Do not submit any executable files (no JVM .class files!). If compilation is nontrivial, you must include a Makefile.