In this section, we will analyze different approach to build our animation system and their feasibility. We will also evaluate several algorithm animation tools on their suitability to build the animation system. The most appropriate and suitable tool will be selected and justification on this selection is provided.
There are three possible approaches to build the parsing animation system. The first approach is to build the system from scratch using a platform-independent language like Java. The second approach is to select an appropriate general purpose algorithm animation system to build the interactive components of the parsing system from scratch. The last approach is to choose an existing parsing algorithm animation system and modify that system into the final system.
One of the possible approaches is to build the interactive parsing animation system from scratch. This includes building up a new algorithm animation system, animated parsing algorithms, parsing exercises and an interactive user control interface.
Being confined to the requirements of the system that it should be platform-independent and accessible via the web, Java is an ideal language that can be used to build the system. The whole system can be run as an applet accessible via any web browsers. Besides this, all the system components can be easily written in Java.
The Java "Abstract Window Toolkit" (AWT) provides the capability to create platform-independent, graphical user interface program. It provides a vast number of useful components, controls and events to build the interactive user interface. The Java Utility and java.lang packages provide useful utilities and data types to implement the various parsing algorithms and exercises. Moreover, the java.lang Thread class or Runnable interface, the AWT Graphics and Image classes make the animation system easy to build. The Thread class or Runnable interface can be implemented to create thread object to control and run animation whereas the Graphics and Image classes provide functions and background images for drawing animated objects.
Java is a portable language. Applications built in Java are platform-independent, accessible via any web browser and plug-in free. Java's built-in libraries provide useful routines for building the system.
Using this approach of building the entire system from scratch one can implement customized features and functionalities as opposed being forced to modify an existing package. This is because constraints and limitations may occur when modifying an existing package where adding or eliminating a function may involve extensive modifications to existing code.
Although Java is easy to program and it provides enormous numbers of useful objects, building an entire system from scratch still requires extensive design work, coding hours and implementation work. Given the time limitation of building the system, the entire system could not be completed within the specified period of time. Extensive time for testing the system will also be unavailable.
The second approach is to use a general purpose algorithm animation system to build the interactive components of the parsing animation system from scratch. There are a number of algorithm animation systems written in Java with the same architecture as shown in Fig. 2, Section 5 of this thesis. In section 6.4, we will evaluate each of these systems and select the most suitable one for building our parsing animation system.
JSamba, (see http://www.cc.gatech.edu/gvu/softviz/algoanim/samba.html) is a Java version of the POLKA's front-end Samba. It is a general purpose algorithm animation system that runs as an applet. JSamba has built-in primitive objects (text, lines, rectangles, triangles, circles and polygons). Different built-in sizes of text are included in the system. It can draw animated objects in a fairly fast speed. Movements of animated objects are smooth and fast. No flicking effects when animation is running. Animated objects are displayed in an applet window, which is separate from the control panel of the animation. It can allow user to resize animated objects by dragging corners of the window.
There are a number of user control facilities. Default controls include start, stop, pause and speed of running animation. Other more specific controls include rewind and fast forward control over animation running.
JSamba is a general purpose algorithm animation system and therefore, can be used for programs written in any kind of language. It uses Java built-in libraries to generate animation of fairly good quality. The speed of drawing animated objects is fairly fast and movement of animated objects is also fast. It derives all advantages from Java such as portability, platform-independence, easy accessibility via a Web browser and no plug-ins are required. It runs as an applet which eliminates the need for local software installation.
The main disadvantage of JSamba is that it does not have any built-in data structure objects. This keeps the system compact and simple but, on the other hand, constraint its possible application areas. This disadvantage requires users to write more complex script file commands to model data structure objects.
JAWAA (see http://www.cs.duke.edu/~rodger/tools), in principle, is similar to JSamba. It is a simple command language for creating animations of data structures and displaying them with a Web browser. Commands are stored in a script file that is retrieved and run by the JAWAA applet. JAWAA commands allow for creation and movement of primitive objects (circles, lines, text and rectangles) and data structure objects (arrays, stacks, queues, lists, trees and graphs). It also provides grouping of animated objects and performs a single animation command over animated objects in the same group, e.g., moving group of animated objects. The speed of drawing animated objects and running the animation are fast and movement of animated objects is also fairly fast. JAWAA redraws animated objects on to the screen by using the double-buffering technique, which involves using two images, one held in memory and one that is displayed on the screen. To redraw the screen, a new image containing each graphic object is created and then placed over the image currently on the screen, creating a flicker-free animation.
User controls include start, stop, pause, step and speed of execution.
As with JSamba, JAWAA is written in Java, hence, it has all the advantages derived from Java. However, JAWAA has a number of significant advantages over JSamba. JAWAA contains built-in data structure objects like stacks and trees which do not exist in JSamba. Users can model these data structures easily.
JAWAA has another advantage in that its script commands can be executed individually or in block execution.
JAWAA is free for distribution.
JAWAA does not provide as much user control on running animation as JSamba. It does not have any undo animation capability. It was built in 1996 and may contain deprecated methods.
JAnime (see http://www.cs.wm.edu/~noonan/jay/index.html) wasd developed by Noonan at the College of William and Mary. It is a web-based animation system which serves as a teaching aid. It is written in Java and runs as an applet. Like JAWAA, it also directs the input of a script file to a local file. It is very similar to JAWAA as they both have similar built-in primitive and data structure objects, and script commands. In JAnime, primitive objects include text, rectangles, circles, lines and polygons. Data structure objects include arrays, stacks and queues. It implements less data structure objects than JAWAA but provides more script commands and user control over the execution of the animation. Speed of drawing animated objects and running of animation is considerably fast.
Like JSamba and JAWAA, JAnime is also written in Java, thus having all the advantages derived from Java. Similar to JAWAA, it has the advantage over JSamba because it consists of primitives and data structure objects and its script commands can be executed individually or in block execution. One more advantage over JAWAA, JAnime enables users to undo animation execution.
However, while it has an advantage of providing more user control than JAWAA, it has a disadvantage that a number of built-in data structure objects in JAWAA such as tree and graph are not implemented in the JAnime system. If JAnime is used for building the parsing animation system, this will limit the possible future extension of the system to animate LR parsing which will need graph objects to animate the Deterministic Finite Automata.
Another disadvantage of JAnime is that it is not available for redistribution.
JELLRAP (Java Enhanced LL/LR Animated Parser) is an interactive exercises of LL(1), LL(2) and LR parsing. It provides exercises for building First, Follow and parsing table for all three parsing techniques. All three parsing techniques end up with a step mode animated parsing of an input string entered by user. The animation illustrates one step at a time the parsing process of the input string and the derivation of an inverted or non-inverted parse tree.
Users are allowed to input any types of grammar for doing the exercise. Each exercise section runs in a separate window with an input text box for users to enter answers. Users can enter the answers and request the package to check their accuracy or simply request the system to provide the correct answers to the exercise. Incorrect answers are highlighted to indicate errors and users are free to correct their answers or request the correct answers from system.
JELLRAP is written in Java and can be run as an applet or application.
Like all previous evaluated general purpose algorithm animation tool, JELLRAP is written in Java, thus having all the advantages derived from Java. It is a well developed on-line parsing exercises covering most of the parsing topics that will be implemented in this project. Users can input any grammars to the exercise.
It covers most of the exercises that this project needs to implement and the tool can be easily adapted for the purposes of this project.
It is free for distribution.
The animated parsing process is in step mode only. Users have to click on the step button for each step of the parsing to view one action of the process.
Adopting this tool might involve spending extra time in understanding the code. Modifications may be problematic because it may require extensive changes to existing code. This may lead to compromise with the current implementation.
This section consider three different approaches in building the parsing animation system, i.e., building the system from scratch, building it with a general purpose algorithm animation tool or building it with a specific purpose algorithm animation tool. The first option seemed unfeasible because it would take extensive time compared with the other two approaches. Although this approach provided more flexibility in designing and implementing the system than the other two, the tradeoff was not worthwhile.
Reducing the options to two, there were three general purpose algorithm animation tools and one specific purpose algorithm animation tool to choose from. The three general purpose tools had some features in common, for example, they were written in Java, which made them meet the project requirement that the parsing system be portable, platform-independent and accessible via the Web from any Web browsers. When choosing the tool, one of the major considerations was whether the tool was capable of animating the internal data structures of all the LL parsing algorithms. Data structures of the parsing algorithms including stack and array. Other animated objects included table, text and basic primitive objects. Another consideration was the time needed to develop the animation. This was because there were time constraints in completing the animation system. Other considerations included speed of drawing and running the animation and the possibility of future extensions to animate other parsing algorithms.
Amongst the three general purpose tools, JSamba was the only tool that was not capable of animating data structure objects. Using JSamba required extra time to extend its capability to draw and lay out these data structure objects. This was unfeasible as the task was time consuming and there were other possible choices with this capability. Although JSamba possessed other useful controls and for the reason above JSamba was considered not suitable for the task.
The remaining general purpose tools, JAnime and JAWAA, had built-in data structure objects like stack and other primitive objects which were sufficient for building the parsing animation system. Time taken to develop animation was estimated to be very much the same for both JAnime and JAWAA as they had a similar script commands format. However, there was one major difference between JAnime and JAWAA in that JAnime did not have other data structure objects like graph and tree which JAWAA possessed. Therefore, JAnime lacked a future extension capability. Although these data structure objects were not needed to implement the LL parsing algorithms, it was sensible to choose a tool that had at least one more advantage over the other, where both could provide the same functions.
JELLRAP, the specific purpose tool, had classes that implemented the LL parsing algorithms and exercises. These classes could be reused to implement the same algorithms in the parsing animation system. Only minor modifications and some testing were needed to verify its accuracy. It also had other classes that represented and validated a grammar, implemented the graphical user interface and managed a list of active windows. Again, these classes could also be reused in building the parsing animation system so as to save implementation time. Although modifications were needed to modify the source codes before they could be used, it was expected that the amount of time taken in this strategy would be less than building a new interface and other supporting classes from scratch.
Therefore, our final approach was to use both JAWAA to build animation for the parsing algorithms and reuse the existing classes in JELLRAP to implement part of the animation system. Reuse components included all LL parsing algorithms, grammar objects, graphical user interface objects.