Background A computer program in Java, Javascript or C are made up of many different functions that starts with fucntion main() {......} and functions are declared like: function(parameters) { …....

Background

A computer program in Java, Javascript or C are made up of many different functions that starts with fucntion main() {......} and functions are declared like: function(parameters) { …. Calling other functions, etc…}.

We can view a program as a string

testProgram = “function myF() { statement1; statement2; funF1(); statement 3; funF2(); funF3(); statement 4} function funF1() {Statement;} function funF2() { statement A; Statement B; funF3(); funcF2(); } function funF3{} { funF2(); funF1();}”

In a program, functions call each other.

Part 1: write a program that parses the testProgram string and any other programs that has functions calling each other. The program needs to print out:

1. 
   

   A Python Dictionary with key:value pairs where the key is the name of a function, and the value is a list of the functions being called by that function. So, for testProgram, the dictionary would look like: { “myF”: [ ‘funF1’. ‘funF2’, ‘funF3’ ]. “funF1”: [], “funF2”: [ ‘funF3’, ‘funF2’], ‘funF3’: [‘funF2’, ‘funF1’’] }

   
   


2. 
   

   A list of tuples with the name and the number of statements in each program. For this test, the statements are terminated by ‘;’, a program begins with ‘{‘ and end with ‘}’

   
   

So, testProgram would have [(‘myF’, 7), (‘funF1’, 1), (‘funF2’, 3), (‘funF3’, 1)]

Part 2: a function that calls another can be viewed as a relationship between two functions. This means we can use graph to represent the call relationship. E.g. myF -> funF1. This means the functions can be nodes, and the call would be a DIRECTED edge connecting the calling function and the function being called. This is called the FUNCTION CALL GRAPH (FCG) of the program. This means you can print out:

1. 
   

   An adjacency matrix that represents the call graph.

   
   

Part 3: Using Depth First Seach (DFS) on the FCG, write a function notCalled( functionName ) that returns the list of the function that is not called directly or indirectly by a given function,including, of course, itself. I.e. myF would be an empty list, funF1 would be everything including itself, funF2 would be [‘myF’ ], etc.

Part 4: Using the FUNCTION CALL GRAPH, as represented by the adjacency matrix, find all the STRONGLY CONNECTED COMPONENTS of the program string. These are functions that could be calling each other recursively. Your program should print out the NUMBER OF SCCS. and each SCCS as a list of function names.