PROBLEM DESCRIPTION-
In this assignment, your input is a simplified version of programs written in a C++-like language consisting of a set of functions, and you are required to create a dynamic data structure to store the functions information so that you may answer some questions about the functions in the program. For example, which functions are recursive? Which functions are called by a particular function?
1. The whole program is read into a 2D char array, char code[ ][ ] for you already. All the preceding whitespaces and trailing whitespaces, if present in any line, are removed. Thus, at the end, a typical program will look like Figure 1 in the 2D char array.
2. The numbers in yellow are the line numbers, which are not stored in the array. So code[0] contains "void main()", code[1] contains "{", and code[2] contains "dosomething 1;", etc.
3. Syntax of a function:
o All functions take no formal parameter and return nothing.
o This means that each function header has the form "void function-name()" in which the characters in blue are always there.
o The function header always takes exactly one line.
o The body of a function is always enclosed in a pair of { }, and each of "{" and "}" is written on a line of its own.
o The body consists of a number of statements, one per line, which you don't know in advance. Thus, they will be stored in a linked list in this assignment.
o If function B is called by function A, and B != A, then we say B is A's child. Moreover, B's children are also considered A's children.
o We assume that children of a function f, say, c cannot call f, but f may call itself and it is then a recursive function.
Data Structure
You are required to use the following 2 basic data structures (defined in "pa3.h") to implement this assignment.
The 2 data structures are further described below:
A. struct Function_Definition: each function in an input file will have an entry in a table of this structure.
a. int line_num: the line in the file that a function is defined; it starts from 0.
b. char fname[ ]: name of the function
c. Statement* fbody: if a function has N statements in its body, a linked list of N Statements will be created, one for each of its N statements.
B. struct Statement: the statements of a function in the input file is stored using a Statement node which consists of the following information:
a. bool is_function_call: if the statement is a function call, it should be set to true, otherwise false
b. char content[ ]: the statement as a character string
c. Function_Definition* fp: if is_function_call is true, then this pointer should be set to point to the function's entry in the function definition table, ftable[ ]; otherwise, it should be set to NULL.
d. Statement* next: it should point to the next statement in the body of the function the current statement belongs to.
Tasks-
We describe the tasks here.
1. build_table(): In the given "pa3-main.cpp" file, the main() function will read an input program file into the 2D char array, code[ ][ ] for you. From the code[ ][ ], you have to build up the function definition table ftable[ ] by implementing the build_table() function. That is, when you encounter a new function header, enter its information into the function definition table, ftable[ ], then scan through its function body, and create a linked list of Statement's, one Statement node for each program statement in the function body. Figure 2 you the result of build_table() on the program file of Figure 1.
a. If any function is defined more than once, return the error of FUNCTION_REDEFINITION(defined in "pa3.h" as an object of the enum type Error_Code). Our main function will print an error message and then exit.
For example, the following codes will cause such an error because f1 has multiple definitions.
Hint: you may make use of the provided search_function( ) in "utility.cpp" to check this when you come across a new function while you are building the function definition table.
b. While you are building the function definition table on a statement that is a function call inbuild_table( ), you don't need to set its fp in the Statement node since the called function may not have been seen yet.
The following diagram shows the status of data structures after you finish parsing themain function. Since we haven't seen the definition of f1 and f2, we can't find their definitions on the function definition table, ftable. Thus their fp are NULL.
2. fix_function_pointers(): After build_table( ) is performed, the fp pointers in the Statement nodes of the fbody of each entry need to be fixed. The function fix_function_pointers() goes through the linked list of Statement nodes of each function entry and determines the value of each fp if the statement is a function-call statement. If the called function cannot be found in the function definition table, print an error message and return the error code MISSING_FUNCTION_DEFINITION. For example, the following codes call an undefined function f3:
That is, the complete function definition table is actually built in 2 passes: first by build_table() in the 1st pass, and then by fix_function_pointers() in the 2nd pass.
3. is_recursive(): Given a function entry in the function definition table, determine whether it is a recursive function.
For example, f1 is a recursive function because it calls itself.
4. print_children_list(): Given the index of a function in the function definition table, list all its children.
For the above example, the children of the main function is
f1
f2
since f1 and f2 don't have any child. However, if f1 calls f4, then the children of main will be
f1
f4
f2
5. unfold_function(): It tries to eliminate all non-recursive function calls in a function by replacing each embedded function with all the statements in its body. For example, given the following program code
OBJECTIVE OF THIS ASSIGNMENT
The main objective in this assignment is to complete 5 functions in the given skeleton code in the file "pa3.cpp". Your solution, together with the codes in the given "pa3-main.cpp" and "utility.cpp" files, will create a program that reads a C++-like program file of the format defined in Figure 1 and
• uses the given data structures above to create a representation of the program statements in the memory, and
• deduce some information about the functions in the program using the representation you just create.
We provide you with this assignment skeleton code:
-pa3-main.cpp : It defines the main function.
-pa3.h and utility.cpp : Several useful functions are provided in the two files, such as searching a function, printing out the body of a function. The function read_file() helps to read input program files into the 2D char array code[ ][ ]. It also removes empty lines, comment statements, and whitespaces at the head and at the end of a line.
-pa3.cpp : This contains the functions you are required to implement. It is the ONLY file you are required to submit and we only grade this file. DO NOT change the function names, and their parameters or return types. The 5 functions are:
* - build_table
* - fix_function_pointers
* - is_recursive
* - print_children_list
* - unfold_function
After you complete these tasks, you should compile your "pa3.cpp" with the given "pa3-main.cpp" and "utility.cpp" (using separate compilation) to produce a program that must have the same output as demonstrated in the Sample input/output tab (which you can access from the menu on the left). You must fill in the missing code in the skeleton code. Note that
• you cannot modify anything in the "pa3.h", "pa3-main.cpp" and "utility.cpp" files.
• you cannot modify the function prototypes of any functions that you are required to implement.
• in fact, during grading, we will re-write the given main function, and call the functions you implement in "pa3.cpp" so as to test your program.
• no additional global variables are allowed.
The skeleton code outlines 5 TODO tasks. Below we explain in detail what each function must do, along with several tips.
TODO #1
You must complete the definition of following function:
Error_Code build_table(char code[][MAX_LINE_LENGTH+1], int
num_lines, Function_Definition ftable[],int& num_functions);
This function takes the codes stored in the 2D char array code[ ][ ] and build up the function definition table,ftable[ ]. The parameter num_functions will be set to the number of functions defined in the input program file.
One way to parse the code is using nested while-loops. The outer while-loop goes through each line of code. Each time you parse a function, process all statements in its body using an inner while-loop. Don't forget to check for FUNCTION_REDEFINITION error, and if it occurs, call print_error_msg(redefined_function_name, FUNCTION_REDEFINITION) to output the error message. A function parse(), which parses each line of code and extracts useful information from it, is written for you in "utility.cpp". Note that when you insert a new Statement node to the statement list, you have to pay attention to the case that the list may be currently empty. Return the error type. If there is no error, return SUCCESS.
TODO #2
You must complete the definition of following function:
Error_Code fix_function_pointers(Function_Definition ftable[], int
num_functions);
This function fixes the incomplete function information in the Statement nodes --- in the field of fp which has not been set in build_table().
You can scan through the function definition table and check each of their statements that are function call statements. If there is a function that is called but is not defined in code[][], callprint_error_msg(missing_function_name, MISSING_FUNCTION_DEFINITION) to output the error message.
Return the error type. If there is no error, return SUCCESS.
TODO #3
You must complete the definition of following function:
bool is_recursive(const Function_Definition& function);
Check whether a function is recursive or not given its entry in the function definition table.
TODO #4
You must complete the definition of following function:
void print_children_list(int f, const Function_Definition ftable[], int num_functions);
The function lists all the children of a given function. f is the index of the function in the function definition table, which starts from 0.
Note that the function itself is NOT its own child. You may want to use recursion to implement this function.
TODO #5
You must complete the definition of following function:
Statement* unfold_function(int f, const Function_Definition
ftable[], int num_functions);
This function re-generates a new statement list for a given function with index f in the function definition table,ftable. In doing so, it unfolds any non-recursive function called by the concerned function and replaces it with the statements in its body. If the called function is recursive, it doesn't unfold it. The new statement list should do exactly the same thing as the original statement list.
You probably would implement it as a recursive function. In each recursion step, go through the statement list and check:
• If a statement is not a function call or if it is a call to a recursive function, create a duplicated Statement node for the statement, and append it to the new statement list;
• If a statement is a call to a non-recursive function, first get a statement list that is the result of unfolding the called function. For example, in sample input file "1.txt", f4 calls f5. We try to get the unfolding result of f5 first. Then append the new statement list from f5 to the new statement list of f4.
Attachment:- Assignment.zip