7. The Parsing Animation System

7.1 The Building of the Parsing Animation System

To meet with one of our previous objectives that users should have open access and interaction with the animation, the parsing animation system was designed to be built as an on-line system, which could be conveniently accessed via the World Wide Web and viewed with any popular Web browsers. JavaÔ2 was the programming language used to implement the system. The Sun JDK1.2.2.006 for Windows 98 was used for all compilation of source codes in the system. The two packages JELLRAP and JAWAA were modified to achieve the objectives of the system.

7.2 Components of the Parsing Animation System

The system is a tutorial, which provides information on LL Parsing algorithms. The tutorial comprises two main parts, a non-interactive HTML tutorial and an interactive animation tutorial. Five LL Parsing algorithms have been implemented:

First

First of String

Follow

Construction of LL Parse Table

Parse an Input String

There is a separate tutorial page for each algorithm. Each consists of a non-interactive HTML tutorial together with an interactive animation tutorial. Access to the animated tutorial is through a link in the algorithm's corresponding HTML page. Instructions and help information on using both parts of the tutorial are also provided.

7.2.1 Non-interactive HTML Tutorial

The HTML tutorial provides static text descriptions of the five LL parsing algorithms. It contains a tutorial home page, an introduction page, tutorial pages of the five algorithms and help on using the animation applet page. A site map of the HTML tutorial is shown as follows:

In the diagram, rectangle represents an individual page and line represents hyperlink to another page. As can be seen from the diagram, the tutorial home page links to all main pages in the tutorial. Individual tutorial page also links to other related tutorial pages and the help information. The help information page links to other help pages. Brief description of each page content is given below

This is the first page of the tutorial. It provides information of the tutorial and instructions on using it together with conventions being used throughout the tutorial.

Short introduction on what LL Parsing is.

Description of the First Set algorithm and show step by step operation of the algorithm with the example grammar. Interactive animation applet animating the algorithm locates at the bottom of the page.

Description of the Follow Set algorithm and show step by step operation of the algorithm with the example grammar. Changes in Follow set in each repetition of the execution is illustrated and briefly explained. It provides hyperlink to the First of String algorithm, which is related to its computation. Interactive animation applet animating the algorithm locates at the bottom of the page.

Show step by step operation on deriving the First set for all right hand side productions in the example grammar. Interactive animation applet animating the algorithm locates at the bottom of the page.

Brief description on the algorithm and illustration of step by step operation of constructing the parse table. Interactive animation applet animating the algorithm locates at the bottom of the page.

Use a simple input string example to illustrate the parsing processing and showing the changes to the stack. Interactive animation applet animating the algorithm locates at the bottom of the page.

Instructions to users on finding particular help information and in each help pages. Hyperlinks to all other help pages.

This page contains screen shot of the Grammar Window and has description of each component in the Grammar Window and its corresponding function. It also contains other instruction to user as to how to input a grammar and valid symbols of grammar.

It describes the different types of user control over the animation and information of other components in the control.

It illustrates the layout and displacements of animated objects in the window.

Inside the help information page on each of the algorithms, First, First of String, Follow, Construction of Parse Table and Parsing an Input String, it describes each animated object in the animation window. It also explains the usage of colour in the animation and some of the operational steps in the animation. Instructions on using the exercises are also given.

There is no predetermined order in which tutorial page a user shall start from. Information in each tutorial page is self-contained and user can choose the page that interests them to read. The same example grammar has been used throughout the tutorial to illustrate a complete LL parsing process.

7.2.2 Interactive Animation Tutorial

The interactive animation tutorial is an applet that animates the five LL Parsing algorithms. For each algorithm, an interactive animation and exercises were implemented.

There are three levels of user interaction with the animation. The first level of interaction is user can input any grammars to the parsing animation system. The second level of interaction is user can have control over the animation. The third level of interaction is user can input their answers to exercises and obtain feedback on their answers accuracy.

When the animation applet is first started, a grammar window is displayed and awaiting for user input. A diagram of the grammar window is shown below:

The grammar window is the first screen that user interacts with before viewing animation. This is where user can input his/her own grammar or select an example grammar from the example grammar list. Then user can start up the animation or exercise by clicking buttons at the bottom right section of the window. Both actions activate the grammar validation process to verify the grammar. For invalid grammar, lines with invalid symbols are highlighted and user is notified of the error. User can modify the grammar to a valid one. The animation animates the algorithm with this input grammar. The exercise is also associated with this current input grammar.

When user has input the grammar and starts up the animation, two windows, the animation control and the animation window are displayed. Diagram of these two windows are shown below:

User can have direct interaction with the animation by means of controlling animation running mode. There are eight animation controls, namely, start, stop, pause, rewind, undo, step, fast forward and speed. User can select, according to his/her own need, the appropriate control type to control the flow of information in the animation. For instance, the user is not clear of a certain number of execution steps simulate by the animation, he/she can choose to undo the animation each time by a single step or rewind the animation by multiple steps to return to the previous state of the animation. Then he/she can replay those steps in the animation by using the step button, which run the animation in single step each.

The third level of interaction is the algorithm exercises. A diagram of an exercise window is shown below:

Interaction between the user and the exercise is that user can input their own answers and get immediate response from the exercises regarding accuracy of their answers. The exercises have interactive error checking and when user request to check their answer, it can immediately show errors in user's answers, if there are any. An alternative is that user can simply request to display the correct answer without checking their answers first.

7.3 Design of the Animation

In this section we explain the design of the animation. This includes its underlying architecture, the type of information that is illustrated in each of the animation and its interactivity with users.

7.3.1 Architecture of the Parsing Animation System

The algorithm animation tool, JAWAA, that we use has the same architecture shown in Fig. 2 in Section 5. In the parsing animation system, its new architecture is shown below:

There are two main differences between the two architectures. Under the new architecture, the input of Animation Commands comes from an Animation Command vector object instead of an ASCII script file. Each Animation Command is an object holding all parameters of an animated object. The parameters include the animation command, name of the animated object, x and y coordinates where it appears on the screen, its value, colour and other drawing information of the object depends on its type. These parameters are the same as the original JAWAA script command.

Under the new architecture, the Animation Interpreter does not have to read an ASCII script file. Instead each Animation Command object is passed to the Interpreter and it converts some of the parameters to an appropriate data type, such as converting a colour in String format to its corresponding RGB value. The Interpreter will then base on the command type and call the method in the Animator for that command type and passing all the parameters to that method. After the Animator method has been invoked by the Animation interpreter, the same process occur as in the old architecture, that is the Animator creates the new animated object, draws and displays it on the Animation Viewer.

Another difference is the user interactivity in the new architecture. There are two types of interaction from user, new grammar input or animation control commands. When the user input a new grammar into the system, the system will execute the algorithm which has annotations added to its source code. When the algorithm executes, a new set of Animation Commands is generated and store in a vector object. When the user starts the running of the animation, the new Animation Command is extracted from the vector and pass to the Animation Interpreter to generate animation.

The second type of interaction is user control over the running of the animation. User can choose to run, stop, pause, undo, step, rewind or fastforward an animation. Unlike the previous situation, each of these commands will not cause any new Animation Commands generated. In contrast, it will cause one or multiple Animation Commands to be added or deleted according to user's choice. For example, if the user selects to undo an animation step, this will cause the animation objects created in the previous step to be deleted by the Animator. The Animator then redraws the existing animated objects and displays them to the Viewer to achieve an undo effect.

7.3.2 Animation Information Design

In designing the contents of the animation, one of the principles is to convey appropriate information that can help users understand the algorithm. Besides showing the dynamic changing internal data structures, we consider showing to user other appropriate information that can better illustrate each step of the algorithm in operation. This include the algorithm itself, input data and values of all static and dynamic vairables that are needed in the execution of the algorithm. The following diagram showing a screen shot of an running animation of the Follow algorithm:

As illustrated in the diagram, different information has been included in the animation. First of all, the algorithm itself must appear in the animation. Next information is the input data, that is, the grammar and other static and dynamic changing variables and their corresponding values. Finally, is the set derived from executing the algorithm.

The information included in the animation can illustrate clearly the operation of each step of the algorithm. For example, the currently executing step in the algorithm and the corresponding production in the grammar are highlighted to signify they are under execution. Values of dynamic changing variables are shown in each relevant execution step to supply information to user why the execution step took place. The set derives from the execution of the algorithm which shows how each new symbol is added to the set is also included.

It is intended to incorporate all the information into one screen for user viewing convenience. User can view all the relevant information and its changes at the same time without having to shift from one location to another on the screen to search for the relevant information.

The same layout and format of the information on the screen is also used for all animation. The algorithm appears on the top left corner of the screen with the grammar placed to its right hand side. The deriving set locates at the bottom left of the screen.

7.3.3 Animation Colour Usage

Consistent colour usage has been applied for all the animations in the parsing animation system. Some of the colour has global representation in the parsing animation system while other colour only has local representation in some of the animations.

Both black and blue has global representation and their use are the same in all the animations. Black represents animated objects that were drawn on the screen before the animation start running. Blue represents current action, for example, highlight the algorithm step in execution, current production in grammar or current input string symbol. Blue is also used to represent sets that are derived from algorithms to distinguish them from the black animated objects.

Some colour has local representation in some of the animation. Magenta is used to highlight current set or symbol in grammar in the First, First of String and Follow animations. Magenta has also been used as background colour of parse table. While the data structure magenta represents in each animation is different, therefore, this shall not create any ambiguity to user.

Green text is used to represent new elements added to a set in the current execution. Green line is used to represent elements added to sets in the current repetition of an algorithm. This usage is used in First, First of String and Follow animations. Green has also been used to highlight parse table entry in the parse table construction and parse input string animations.

Red is only used in Follow and parse input string animations. In Follow animation, red represents a current symbol in the right hand side production of a grammar where in parse input string animation, red represents error message.

White is used to highlight the background of input string array element in the Parse an Input String animation.