11:59:59pm (via the submit server)

In this project, you will implement a data flow analysis for (a slight modification of) the simple language of commands we have explored in lecture and in project 1.

Grab this file to get started. When you unpack
the tarball and type `make` this will build an executable
`impflow`.

The `main` function (in `impmain.ml`)
invokes the parser to build an abstract syntax tree. After the file is
parsed successfully, it will either be printed or analyzed, depending on the
command-line options provided. Invoke `impflow -help` for usage
information.

You should submit the file `flow.ml` that contains your
implementation of the function `analyze : Imp.command -> analysis ->
unit`. This function takes as its argument a command (which itself is
possibly a compound list of commands) and an analysis to perform, according
to the following type (defined in `flow.ml`):

type analysis = LiveVars | ReachDefs | AvailExps | BusyExpsThis function will then analyze the given command using the specified analysis and print out the results before returning. Which argument is provided depends on the command-line options. For example, if

type raw_comm = Skip | Assign of string * exp | If of exp * comm * comm | While of exp * comm and comm = Stmt of int * raw_comm | Block of comm listCommands are either a single command or a list of commands (a

We have also extended expressions to include two relational operators.

You will implement four dataflow analyses that we discussed in class.

- Live variables (option
`-live`) -- for every variable, determine for every statement whether the variable may be subsequently used. Your output should be of the form`{x,y,z}`where`x`,`y`, and`z`are the variables live at that point, and no other variables are live. - Reaching definitions (option
`-reach`) -- for each statement that assigns to a variable, determine which statements the assignment may reach. Your output should be of the form`{n1,n2,n3}`, where`ni`are the*numbers*of defining statements that reach that point. Do not put a`#`in front of the numbers. - Available expressions (option
`-avail`) -- for each expression`e1 + e2`or`e1 * e2`determine which expressions are available at each statement. Your output should be of the form`{e1,e2,e3}`, where`ei`are the expressions available at that point. - Very busy expressions (option
`-busy`) -- for each expression, determine which are very busy at each program point. Your output should be of the form`{e1,e2,e3}`, where`ei`are the expressions that are very busy at that point.

#n <facts>where

Below are the results of running the four analyses on `test1.imp`.
*Warning*: I produced these results by hand, so there could be small
typos in them. Use your own understanding of the analyses to verify the
output.

Live variables:

#0 {b,c} #1 {b,c,t1} #2 {t2,b,c} #3 {t2,t3,b} #4 {t2,t4} #5 {t5}

Reaching definitions:

#0 {0} #1 {0,1} #2 {0,1,2} #3 {0,1,2,3} #4 {0,1,2,3,4} #5 {0,1,2,3,4,5}

Available expressions:

#0 {-1 * c} #1 {-1 * c,b * t1} #2 {-1 * c,b * t1} #3 {-1 * c,b * t1,b * t3} #4 {-1 * c,b * t1,b * t3,t2 + t4} #5 {-1 * c,b * t1,b * t3,t2 + t4}

Very busy expressions:

#0 {-1 * c} #1 {-1 * c,b * t1} #2 {-1 * c} #3 {b * t3} #4 {t2 + t4} #5 {}

The order in which you print the statements does not matter. You can also adjust spacing however you like. Please list the dataflow facts for each statement on a separate line, however.

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please **carefully read** the academic honesty section of the
course syllabus. **Any evidence** of impermissible cooperation on
projects, use of disallowed materials or resources, or unauthorized
use of computer accounts, **will be submitted** to the Student
Honor Council, which could result in an XF for the course, or
suspension or expulsion from the University. Be sure you understand
what you are and what you are not permitted to do in regards to
academic integrity when it comes to project assignments. These
policies apply to all students, and the Student Honor Council does not
consider lack of knowledge of the policies to be a defense for
violating them. Full information is found in the course
syllabus---please review it at this time.