The purpose of this assignment is to demonstrate the usefulness of the data structures known as linked lists and trees. In addition, the assignment requires the student to carefully examine the syntax and hierarchy of Java programs. It is our hope that this assignment will help students transition from the Java mini 46-935 to the exciting world of Artificial Intelligence.
In this assignment, your task will be to write a program that takes one or more Java source files as input and creates a tree that represents the static calling structure described in the source code. The "static calling structure" is the hierarchy of methods that COULD be called if the source files were compiled and executed. Therefore, the root of the tree will always be the public method "main" -- the first method to be executed in any Java program. Furthermore, the children of the "main" node would be the methods called from the "main" method.
Due to the complexity of the Java language, you can make the following assumptions:
Your program will only have to work on groups of source code where all of the methods have completely unique names. In other words, no two classes have methods with the same name. This is definitely not true in the Java language due to inheritance and overloading, but it simplifies the assignment quite a bit.
Methods in the call structure that are not declared in the input source file group can be ignored. Java programs can call methods in imported classes or packages. These imported methods will be used in the source file data sets, but should not be a part of the calling structure tree that is created by your program (unless the source file for the imported package is explicitly included in the input group).
To aid you in your task, we have provided a template and a significant amount of supporting code. A linked list class and a tree node class have already been implemented. In addition a MyStringTokenizer class (an extension of Java's string tokenizer) and a Vector class containing all of Java's reserved words and symbols has been included. Please see the Assign1.java file for more information on these classes.
Your task can be broken into two stages. The first stage involves parsing the input source file group to obtain a linked list (LList) of single tree nodes (TreeNode). A single tree node contains the name of a method (String nodeName), a string to be used for printing the tree which contains the class name and method name (String printString), a reference to a parent TreeNode (TreeNode parent), and a linked list of children (LList children). During the first stage, you are only building a linked list of single nodes. Thus, the parent field should be null. In addition, the children linked list should contain the names of all of the methods called by the nodeName method, but should not be further expanded (the children TreeNodes should not have an expanded children LList). The support code will help you with this stage, and the beginning of the text parsing code is completed for you.
The second stage involves using the linked list of single tree nodes to build the calling structure tree. This can be accomplished by creating a new tree node (root), and COPYING the data from the linked list of single tree nodes (starting with the LList entry for "main"). Once the "main" method data has been copied to the root node, you can start to add children from the single list of tree nodes. Remember that each child has a separate entry on the top level of the single tree node list. Fully expand the tree by adding children, and expanding the children LList of each child that you add.
During this process, you must be careful not to end up in an endless loop. If you blindly add a child and expand its children LList, you will create an endlessly expanding tree branch if the method was recursive (a recursive method would have itself as a child). Therefore, it is up to you to recognize when you are about to add a method name that is already in your path. If you are in this situation, you should not expand the branch further. Instead, add a terminal node with the nodeName and printString set to the following: "RECURSIVE: CLASSNAME::FUNCTIONNAME." See the example for clarification on these points. The output of your program should be identical to the example for the example input program.
Revised on Friday, October 03, 1997