EECS 478 Fall 2021 Project No. 1INSTRUCTIONS: The University of Michigan, EECS Department EECS 478: Logic Synthesis and Optimization Professor John P. Hayes Jinjie LiuProject 1: Binary Decision Diagrams Distribution Date: Thursday September 16th, 2021 Due Date: Tuesday October 12th, 2021 at 23:59Submit Online via Canvas -Assignments -Project 1 • You must abide by the Engineering Honor Code. All work submitted should be work done by you and you alone. If you are unsure about the level of collaboration, please consult Professor Hayes or GSI. • Make sure your code is indented properly, readable and well commented. • Your code should not output anything at the display, unless explicitly mentioned. Verbose codes will be penalized. • When you are finished, collect the following two deliverables: - projectl.cpp - README { unique name} where { uniquename} is your unique name. • Create a tar bar with only these files. To do this: - Create an empty directory called EECS4 7 8Pl _{ uniquename}. - Copy all your deliverables into this directory. - Type tar -cvf EECS4 7 8Pl _ { uniquename} . tar EECS4 7 8 { unique name} - Typegzip EECS478Pl_ {uniquename}.tar • There are 100 points possible for this project. 1 2.5 BooLexpr.h, BooLexpr.cpp, BooLexpr _parser.h, and BooLexpr _parser.cpp The files BooLexpr. h, Bool_expr. cpp, BooLexpr_parser. h, and BooLexpr_parser. cpp make up a binary that facilitates the parsing and creation of Boolean expressions. The main class is BooLexpr. A Boolean expression is made up of a tree structure of BooLexpr nodes. Each BooLexpr object is of type VALUE, AND, OR, or NOT. If it is of type VALUE, then it is a leaf node that contains the literal. If it is of type NOT, then its right member variable points to a Boo Lexpr node that is to be inverted. If it is of type AND or OR, then its left and right member variables point to the nodes that are ANDed or ORed together. You will not have to work directly with the classes defined in these files for this assignment. 2.6 main.cpp The main function is provided as well as functions that parse the input, and build BDDs. The main function calls bu i l d...bdd_f r om_i n put, which parses the user input using the Boo Le xp r _parser class, and then calls bdd_from_expr. The bdd_from_expr function traverses the BooLexpr object passed to it and builds a BDD using the apply function. 2. 7 projectl.h and projectl.cpp These two files contain the tasks that you will be implementing. Again, you should only be modifying projectl. cpp. 3 Getting Started Download the tar ball eecs4 7 8pl. tar. gz from Canvas. To decompress the tar ball, type: tar -xvf eecs478pl.tar.gz into a directory of your choice. This will create a directory called e e cs 4 7 8 p 1, and will include the necessary files for your program. In that directory, compile the program by typing make. To run the program, type . /project 1. You are allowed to do your development on any platform. However, your code will be tested and evaluated on the CAEN linux machines. If you are unfamiliar with Linux, you can get some help by visiting http://caenfaq.engin.umich.edu or by looking up other tutorials available online. You are encouraged to test your program with a rigorous set of test cases that exercise all of the features of the program. You are allowed to trade test cases with other students, as long as you name all the people with whom you traded the test cases in your README file. 5