JAVA Project Description: A compiler must examine tokens in a program and decide
ID: 3684750 • Letter: J
Question
JAVA Project Description:
A compiler must examine tokens in a program and decide whether they are reserved words in the Java language, or identifiers defined by the user. Design a program that reads a Java program and makes a list of all the identifiers along with the number of occurrences of each identifier in the source code. To do this, you should make use of a dictionary. The dictionary will hold all the identifiers that you find in the Java program and the number of times the identifier appears in the program. In addition, your program will need a data structure containing all the Java reserved words and operators. Write Java code that will create a balanced binary tree of the reserved words and operators in the Java language. A listing of reserved words and operators is to be read from the file, JavaKeywords.txt; the name of the program to be analyed is supplied as a command line argument. Whenever your program encounters a token, it should search the binary search tree of reserved words. If the token is not a reserved word, then search the dictionary of identifiers. If the token is not in either dictionary, add it to the dictionary of identifiers. If the token appears in the identifiers dictionary, increment the frequency counter for that entry. Your main program file should be named Project6.java. Use object-oriented program design for this project. Follow style and documenting examples given in class for earlier projects. Each file must begin with a comment block with your name, program name, course number, and due date. The block must also include the purpose, input, and output of the program.
Input Your program must be able to retrieve the names of the input files from the command line. The first file name is JavaKeywords.txt and the second is the name of the program to be parsed for identifiers. Output Your program is to display an inorder traversal of the tree containing the Java reserved words and operators (one per line) along with labeled information regarding the height and number of nodes in the tree; followed by a list of the identifiers and the number of times each of them appears in the test program.
JavaKeywords.txt :
Explanation / Answer
Project6.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Project6 {
public static void printHeading()
{
System.out.println("Project 6");
System.out.println("Program Parser");
}
public static void main(String[] args) {
// get keyword file and program file from command line
String keywordfile = "";
String programfile = "";
// make key word reader
Scanner kybd = new Scanner(System.in);
// get file names from command line
if(args.length == 2)
{
keywordfile = args[0];
programfile = args[1];
}
// get file names from keyboard
else
{
System.out.print("Enter keyword file name(JavaKeywords.txt): ");
keywordfile = kybd.nextLine();
System.out.print("Enter program file name: ");
programfile = kybd.nextLine();
}
// print heading
printHeading();
// make balance tree to store java keywords and operators
BalancedTree bt = new BalancedTree();
// read operators and keyword file
try{
Scanner fsc = new Scanner(new File(keywordfile));
// for each operator and keyword
while(fsc.hasNext())
{
String word = fsc.nextLine().trim(); // get word from file
if(word.length()> 0)
bt.insert(word); // insert into tree
}
System.out.println("The tree contains " + bt.numNodes() + " items, as follows: ");
// print tree
bt.printTree();
// print statistics
System.out.println("");
System.out.println("Root of tree is " + bt.getRoot().getData());
System.out.println("Height of tree is " + bt.treeHeight());
// make dictionary
Dictionary dict = new Dictionary();
// read program, put identifiers in dictionary
fsc = new Scanner(new File(programfile));
// for each operator and keyword
while(fsc.hasNextLine())
{
String line = fsc.nextLine().trim(); // get line from file
StringTokenizer st = new StringTokenizer(line," ".,;=<>!+*-{}[]()@/\");
while(st.hasMoreTokens())
{
String word = st.nextToken();
if(word.length() > 0 && !Character.isDigit(word.charAt(0)))
{
//System.out.println(word);
if(!bt.search(word))
dict.insert(word); // insert into tree
}
}
}
// print identifiers
System.out.println("");
System.out.println("The following tokens are not Java keywords in the file, "
+ programfile + " ");
dict.print();
} // end try
// file not found
catch(FileNotFoundException ex)
{
System.out.println(ex.getMessage());
}
} // end main
}
JavaKeywords.txt :
true
=
+=
-=
*=
/=
&=
|=
^=
%=
<<=
>>=
>>>=
this
||
&&
|
^
&
==
!=
<
>
<=
void
>=
<<
>>
>>>
+
-
*
/
%
false
byte
short
char
int
long
float
double
boolean
enum
if
else
for
while
do
while
try
catch
finally
switch
case
synchronized
return
throw
throws
default
break
continue
const
assert
public
protected
private
static
abstract
final
native
synchronized
transient
volatile
strictfp
import
class
extends
implements
interface
goto
instanceof
native
new
null
package
super
transient
Dictionary.java
import java.util.ArrayList;
public class Dictionary {
class Item implements Comparable<Item>
{
String word;
int freq;
// construct item
Item(String word, int freq)
{
this.word=word;
this.freq=freq;
}
// compare item
public int compareTo(Item item) {
return word.compareTo(item.word);
}
}
// arraylist of items
ArrayList<Item> items = new ArrayList<Item>();
// insert word int dictionary
public void insert(String word)
{
// find word
for(Item item: items)
{
if(item.word.equals(word))
{
item.freq++;
return;
}
}
// word not found, so add word
items.add(new Item(word,1));
}
// print dictionary
public void print()
{
for(Item item: items)
{
System.out.println(item.word + " " + item.freq);
}
}
}
BalancedTree.java
public class BalancedTree
{
/* balanced tree node */
class BalancedNode
{
String data;
BalancedNode left;
BalancedNode right;
int height;
/**
* BalancedNode constructor
*/
public BalancedNode(String data)
{
this.data=data;
}
public String getData()
{
return data;
}
}
// tree root
private BalancedNode root;
/**
* BalancedTree constructor .
*/
public BalancedTree() {
root = null;
}
/*
* return root
*/
public BalancedNode getRoot()
{
return root;
}
/* return height of tree*/
public int treeHeight()
{
return treeHeight(root);
}
public int treeHeight(BalancedNode N)
{
if (N == null)
{
return 0;
}
else
{
int left = treeHeight(N.left);
int right = treeHeight(N.right);
// return max heoght
if(left > right ) return left +1;
else return right + 1;
}
}
// return height of node
private int height(BalancedNode N)
{
if(N == null) return -1;
else return N.height;
}
/* return number nodes */
public int numNodes()
{
return numNodes(root);
}
private int numNodes(BalancedNode N)
{
if(N == null) return 0;
else return numNodes(N.left) + numNodes(N.right) + 1;
}
public void insert(String data)
{
root = insert(root, data);
}
/* insert data into avl tree */
private BalancedNode insert(BalancedNode T,String data)
{
if(T == null)
{
/* allocate tree node */
T = new BalancedNode(data);
}
else
{
/* insert left */
if( data.compareTo(T.data)<0)
{
T.left = insert(T.left,data);
if((height(T.left)-height(T.right))==2)
{
if(data.compareTo(T.left.data) < 0)
T = rleft_single(T);
else
T = rleft_double(T);
}
else
T.height = Math.max(height(T.left),height(T.right))+1;
}
/* insert right */
else if( data.compareTo(T.data)>0)
{
T.right = insert(T.right,data);
if((height(T.left)-height(T.right))==-2)
{
if(data.compareTo(T.right.data)>0)
T = rright_single(T);
else
T = rright_double(T);
}
else
T.height = Math.max(height(T.left),height(T.right))+1;
}
}
return T;
}
// search for word in tree
public boolean search(String data)
{
return search(root,data);
}
private boolean search(BalancedNode N, String data) {
if (N == null) return false;
int cmp = data.compareTo(N.data);
if (cmp < 0) return search(N.left, data);
else if (cmp > 0) return search(N.right, data);
else return true;
}
/* print tree data elements in order using recursion */
public void printTree()
{
printTree(root);
}
private void printTree(BalancedNode T)
{
if(T != null)
{
printTree(T.left);
System.out.println(T.data);
printTree(T.right);
}
}
/* double rotate left */
private BalancedNode rleft_double(BalancedNode T3)
{
T3.left = rright_single(T3.left);
return(rleft_single(T3));
}
/* single rotate left */
private BalancedNode rleft_single(BalancedNode T2)
{
BalancedNode T1;
T1 = T2.left;
T2.left = T1.right;
T1.right = T2;
T2.height = Math.max(height(T2.left),height(T2.right))+1;
T1.height = Math.max(height(T1.left),T2.height)+1;
return T1;
}
/* double rotate right */
private BalancedNode rright_double(BalancedNode T3)
{
T3.right = rleft_single(T3.right);
return(rright_single(T3));
}
/* single rotate right */
private BalancedNode rright_single(BalancedNode T2)
{
BalancedNode T1;
T1 = T2.right;
T2.right = T1.left;
T1.left = T2;
T2.height = Math.max(height(T2.right),height(T2.left))+1;
T1.height = Math.max(height(T1.right),T2.height)+1;
return T1;
}
} // end class BalancedTree
sample output
Enter keyword file name(JavaKeywords.txt): JavaKeywords.txt
Enter program file name: input.txt
Project 6
Program Parser
The tree contains 84 items, as follows:
!=
%
%=
&
&&
&=
*
*=
+
+=
true
try
void
volatile
while
|
|=
||
Root of tree is false
Height of tree is 8
The following tokens are not Java keywords in the file,
input.txt
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.