DEPARTMENT OF INFORMATION TECHNOLOGY
HD in Software Engineering (IT114105) 2020/2021 ITP4510 DSA: Concepts & Implementation
ASSIGNMENT
Deadline: 11 Apr 2021 (Sun) 11:59pm
A Cross-Reference Map for a program is a list of all the identifiers employed in the program, along with the line numbers on which they appear. It is often useful that a programmer has this information on his or her hand during the debugging stage of programming.
Identifiers are words used in programs to name variables, classes, methods, or labels and are subjected to strict rules. None of the Java keywords/reserved words may be used as identifiers. An identifier can begin with a letter, a dollar sign ($) or an underscore character ( _ ). The following is a list of Java keywords/reserved words for your reference. They are extracted from https://docs.oracle.com/javase/tutorial/java/nutsandbolts/_keywords.html.
abstract assert boolean break byte case catch char class const
continue default do double else enum extends final finally float
for new
goto package if private implements protected import public instanceof return int short interface static long strictfp native super
switch synchronized this
throw throws transient
try
void
volatile while
Note: You may find that the list of Java keywords/reserved words from other sources of information can be a bit different from the above list. However, you should use the above for the purpose of this assignment.
You are required to develop a Java program (XRef.java) that will generate such a cross-reference map for a Java source file. You do not need to handle comments, therefore assume no comments in the input java source file. In the cross-reference map, the identifiers should be listed in alphabetical order, and the line numbers on which each identifier appears should be listed in ascending order.
The following is a sample execution of the program with the given Sample.java as the test file: C:> java XRef Sample.java
v2
Page 1
v2 Page 2
Data Structure – DSample.java scenario
Data structure
– Within the linked list, identifiers are arranged in ASCII order including
those start with dollar sign $ and underscore _.
– Each node in the linked list has an associated linked list to keep line
number references.
SOURCE FILE: DSample.java
0001 | public class DSample {
0002 | 0003 | 0004 | 0005 | 0006 | 0007| 0008 | }
public static void main(String[] args) { int $a = 0, _a = 1, Sample; System.out.println($a);
_a = _a*_a – $a; System.out.println(_a);
}
CROSS REFERENCE:
$a :[345] DSample : [ 1 ]
Sample :[3]
String :[2]
System :[46]
_a :[35556] args :[2]
main :[2]
out :[46] println :[46]
v2 Page 3
IMPLEMENTATION REQUIREMENTS:
Employ the techniques discussed in the ITP4510 DSA teaching materials to develop the linked list package (use of interface, comparator and list exceptions are recommended).
Use an array to hold the Java keywords/reserved words in ascending or descending order.
Devise an efficient searching algorithm (linear or binary search) for the ordered keyword array.
The searching is used to determine if a given token/word is a java keyword or an identifier.
Tokenize the Java source using the code provided in the Tokenizer section.
Implement exception handlers for your program. Specifically, you may want to define custom
exception to catch illegal identifiers that are extracted by the Tokenizer.
Format the program output as close as possible to the sample outputs given. The first part of the
output is the source labelled with line number and the second part is the cross-reference map.
Tokenizer
private static final String
DELIMITER = “\”(?:\\\\\”|[^\”])*?\”|[\\s.,;:+*/|!=><@?#%&(){}\\-\\^\\[\\]\\&&]+";
public static String[] tokenizer(String javaStmt) { String[] tokens = javaStmt.split(DELIMITER); return tokens;
}
This tokenizer will extract Java program tokens from the string parameter based on the DELIMITER. It returns an array of strings/tokens. Sample program elements recognized by the tokenizer are identifier, keyword, numeric literal, and character literal. It will also return invalid elements like unclosed string. Refer to the note “2 – Exception” for an example on split method.
INSTRUCTIONS:
1. This assignment is an individual assignment and each student submits his/her own work. Plagiarism is a serious offence and any assignments that involve any plagiarism will be given ZERO marks. The award of Zero marks will apply to all parties, regardless of whether a student is the original author or the plagiarist. Further disciplinary action will follow.
2. You are asked to include the following documentation at the top of your program.
/**
* class XRef - Cross Reference Map
*
* I understand the meaning of academic dishonesty, in particular plagiarism, copyright infringement
* and collusion. I am aware of the consequences if found to be involved in these misconducts. I hereby
* declare that the work submitted for the "ITP4510 Data Structures & Algorithms" is authentic record * of my own work.
*
* @Name : Your full name in English
* @StdID: 20XXXXXXX
* @Class: IT114105/1X
* @2021-XX-XX
*/
3. You are NOT ALLOWED to use data structure classes provided by Java API. You must use the linked list (and/or other data structures) developed in this module for the assignment. However, it is at your discretion on extending the classes with attributes/methods to suit your case.
v2
Page 4
4. Your programs must follow the coding standard stated in Java coding standard maintained by Oracle (https://www.oracle.com/java/technologies/javase/codeconventions-contents.html). Marks will be deducted if the coding standard is not followed.
5. Program, class and method documentation are essential. Inline comments should be placed as appropriate. User-defined names should be descriptive as much as possible. Marks are given based on correctness, readability, style and quality.
6. All work is to be submitted to Moodle on/before 11th April 2021 11:59pm. Late submission without valid reasons will be given ZERO mark.
7. You are required to hand in:
a) All classes (programs) written and well commented by you for this assignment.
b) The evidence of testing - You should submit at least 4 dump screens (similar to the sample
output given above) to show the run results with your own input files (that means you should design your own test cases).
8. The weighting of this assignment is 40% of EA.
9. Marks allocation: Implementation
Linked list 15% Keyword search 15% Exception 11% Solution design 33%
Evidence of testing 12% Coding Standard 6% Program documentation 8%
References: Linear Search -
https://www.tutorialspoint.com/data_structures_algorithms/linear_search_algorithm.htm
Binary Search -
https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm
v2 Page 5