Go to the JHAVEPOP main page

Overview

JHAVEPOP (JHAVÉ-Hosted Automated Visualization of Elementary Pointer OPerations) is an algorithm visualization tool specialized in pointer operations.
JHAVEPOP shares with Pascal Pointers, an educational application developed by Jeffrey Popyack at Drexel University, the goal of helping students become comfortable with pointers. Like Pascal Pointers:
  • JHAVEPOP automatically creates snapshots of the memory after each pointer operation in the source code is executed.
  • JHAVEPOP is packaged with programming exercises that engage students in programming and debugging tasks.
The figure to the right summarizes the main functionality of JHAVEPOP. Given as input a source program written in (a subset of) either Java or C++, it generates a visualization of the program as a sequence of snapshots. The next two sections describe the default layout algorithm and the input language accepted by JHAVEPOP.

Layout manager

This section describes the underlying grid and the default algorithm used by JHAVEPOP's layout manager to display memory locations. The following section discusses the layout directives that the visualization designer may use to override the default settings.

Underlying grid

The layout manager draws memory locations in a 2-dimensional grid. Each cell in the grid may contain a group of 5 memory locations: 3 reference boxes for as many pointer variables and 2 memory locations to store a single node's info field and next pointer. The grid appears in green in Figure 1 below. Typically, this grid is only visible during the design stage at times when the visualization designer wants to fine-tune the appearance of the visualization. The user need not even be aware of the grid's existence.
Figure 1: Grid layout with default horizontal spacing equal to half the box width

All memory locations are drawn as square boxes. All boxes in the grid have the same size, which is computed automatically based on the numbers of rows and columns in the grid and the horizontal spacing between the reference boxes (discussed below). The vertical spacing between boxes is always equal to the box width.

Layout algorithm

Initially, when the source program starts executing, the grid is empty. Every time memory locations are allocated (that is, when a pointer variable is being declared or a new node is allocated), the layout manager must select one or more empty memory locations in the grid.

Generally speaking, the default layout algorithm allocates memory for each new node by traversing the grid from left to right across columns, and from the top down within each column. Therefore, the cells in Figure 1 are filled in the following order: (0,0); (1,0); (0,1); (1,1); (0,2); and (1,2). Therefore, the location of each node in the grid is characterized by a 2D index, namely the index of the cell to which it belongs.

In contrast, the location of each pointer variable is characterized by a 3D index where the third element specifies which, among the three reference boxes (left, middle, or right), the pointer occupies. When allocating memory for a pointer, the default layout algorithm traverses the cells in the same order as above, and within each cell, considers the reference boxes in the order: left, right, then middle [may not be correct: check this].

When a single instruction in the source program declares both a pointer variable and a node, the layout manager always allocates memory for the pointer and the node in the same cell. The default algorithm simply combines the strategies for node allocation and pointer allocation described above to find the first cell that can accommodate both a node and a pointer to it.

Input language

JHAVEPOP accepts source programs whose syntax is a shared subset of Java and C++, except that: The rest of this section applies equally to Java and C++ input programs, except where noted.

All source programs input into JHAVEPOP share the following structure:

Comments

JHAVEPOP does not accept free-form comments. Instead, all acceptable comments have a prescribed syntax, since they are interpreted by JHAVEPOP as directives pertaining to the visualization itself. They are mostly useful to override JHAVEPOP's default layout options.

Each comment starts with a double slash ("//") and runs until the end of the line. The newline character is only significant when it marks the end of a comment. Everywhere else in the code, blank spaces, the TAB, and newline characters are ignored by the parser (though they are used by the scanner as token separators).

In this section, we describe the syntax of the second-line comment. Other comments, called layout directives are discussed in the corresponding section below.

The second line of each source file is called the "gridsize" line. Like all comments, it starts with a "//", and is immediately followed by the keyword "gridsize." The next two tokens are positive integers that specify the number of rows and columns in the grid. The size of the grid is fixed for all snapshots and must be chosen carefully in order to take the fullest possible advantage of the default layout algorithm for Node instances.

As a matter of convenience, the gridsize line is also the place to specify: Only the first one of these options is required and must precede the others. When two or more of the last three options are included, they must appear in the same relative order as in the bulleted list above. Here is an example of a gridsize line that includes all options:
  // gridsize 2 3 java drawgrid 2.0 smallfont
In this example, the grid (shown in Figure 2) will contain 2 rows and 3 columns, and it will be drawn. The horizontal spacing will be 4 times larger than the default, for example, to prevent the overlap of variable names that appear as box labels.

Figure 2: Grid layout with horizontal spacing equal to twice the box width


While the "drawgrid" and "smallfont" directives are binary flags (i.e., present or not), acceptable values for the horizontal spacing range from 0 up, taking integer values or fractional values with exactly one digit after the decimal point. Figure 3 displays the grid with a value of 0.0 (or simply 0) for the horizontal spacing.

Figure 3: Grid layout with horizontal spacing equal to 0.0


The last option of the "gridsize" example above, specifies that the source code for this visualization appear in a smaller font than the default one, presumably because the input program is too long to fit nicely in the pseudo-code pane.

Source code

JHAVEPOP contains an interpreter for a subset of Java/C++. Its parser accepts most operations pertaining to memory allocation, pointer/reference assignments, pointer dereferencing, as well as standard control structures. While the full language accepted by JHAVEPOP is formally characterized by the grammar listed at the end of this document, the main language constructs are illustrated in the following examples:

Construct Java example C++ example
1. Declaration
Node n1;
Node *n1;
2. Declaration
Node n2 = n1;
Node *n2 = n1;
3. Declaration
Node n3 = null;
Node *n3 = NULL;
4. Declaration
Node n4 = new Node('A',null);
Node *n4 = new Node('A',NULL);
5. Pointer assignment
n1 = n4.next;
n1 = n4->next;
6. Pointer assignment
n1.next = null;
n1->next = NULL;
7. Pointer assignment
n3 = new Node('B',null);
*n3 = new Node('B',NULL);
8. Data assignment
n1.info = n4.next.info;
n1->info = n4->next->info;
9. Data assignment
n1.next.info = 'C';
n1->next->info = 'C';
10. Memory deallocation Not available
delete n1;
11. If statement
if (n1==null) {...} else {...};
if (n1==NULL) {...} else {...};
12. While loop
while ( (n1!=null) && (n1.info=='A') ) {...};
while ( (n1!=NULL) && (n1->info=='A') ) {...};
13. For loop
for( n1=n2; n1!=null; n1=n1.next) {...};
for( n1=n2; n1!=NULL; n1=n1->next) {...};
14. Break statement
break;
break;
15. Linked list creation
Node head = Utils.createList( 'A','B','C',"tail" );
Node *head = createList( 'A','B','C',"tail" );
16. Linked list realignment
n1.redrawListHorizontally();
n1->redrawListHorizontally();


JHAVEPOP does not implement a parser for the full Java or C++ language. Even though JHAVEPOP assumes the existence of a predefined class called Node with an instance variable of type char called either info or data, and a pointer/reference variable called next, JHAVEPOP does not parse class definitions nor function/method calls, except for the possibility to call the two following predefined functions/methods: Furthermore, the input language can only declare pointer/reference variables to a Node object. JHAVEPOP does not accept any other data types, such as int or char variables. When the input language is C++, JHAVEPOP does not accept the address operator "&", nor does it handle pointers to pointers. Another constraint on the input language is the form of boolean expressions that may only compare pointer variables or character expressions, and may not contain more than two fully parenthesized comparisons each (joined with the logical connector "&&" and "| |"). For a detailed specification of the input language, again please refer to the grammar provided at the end of this document.

Layout directives

This section describes the layout directives available to the visualization designer for overriding the default layout algorithm. Layout directives may follow any instruction in which a pointer variable is being declared (see examples 1-3 above), a new Node object is being created (see example 7), or both (example 4).

For pointer declarations, the designer may choose a specific reference box for it (a 3D index) as well as its label's position, either to the left of the box, or above it (by default). For a Node object, the choice is limited to a specific cell (2D index). In the combined case, the options are simply combined with the added constraint that both the pointer variable and the Node object are always allocated in the same grid cell.

In JHAVEPOP, layout directives take the form of structured comments. Recall that, like in Java and C++, a comment may start with "//" and run until the end of the line. Unlike in Java or C++, the text of each comment is parsed by JHAVEPOP and interpreted as a layout directive. More specifically, a directive may include between 2 and 4 parameters. Consider the following example:
  Node n = new Node( 'A', null ); // 1 2 MIDDLE left
When allocating memory, JHAVEPOP picks a grid cell in which to display the new pointer variable and the new Node object in this case. The first two values in the comment specify the row and column of the target cell, presumably different from the one chosen by default. The third value is a string that specifies which of the three reference boxes in that cell (LEFT, MIDDLE, or RIGHT) will be assigned to the pointer variable. The fourth argument is a toggle for the position of the variable name: either to the left of the reference box, like in the example, or above it, when the argument is omitted. Other layout directive examples include:
  Node n1; // 1 2
  Node n2; // 2 2 ANY left
In the first example, only the grid cell is specified, thus JHAVEPOP will use this cell but will choose the reference box according to its default algorithm. In the second example, in which the label needs to go to the left of the box, the string ANY is used as the third argument to indicate that any reference box in the cell will do. Indeed, as the following grammar enforces, skipping the third argument is not permitted, unless the last argument is also omitted.

EBNF grammar

Non-terminals

Input ::= titleLine gridsizeLine ( newlistLine )? ( ( pointerOperation | layoutOperation | controlOperation ) )* <EOF>
titleLine ::= <TITLE>
gridsizeLine ::= <COMMENT> <GRIDSIZE> <INT> <INT> <LANGUAGE> ( <DRAWGRID> )? ( ( <INT> | <REAL> ) )? ( <SMALLFONT> )? <ENDOFCOMMENT>
newlistLine ::= <NODE> ( <STAR> )? <IDENTIFIER> <EQUAL> <CREATELIST> <LPAREN> <CHARLIST> <STRING> <RPAREN> <SEMICOLON>
pointerOperation ::= ( pointerDeclaration | pointerAssignment | pointerDelete | dataAssignment )
pointerDeclaration ::= <NODE> ( <STAR> )? <IDENTIFIER> ( <EQUAL> ( <NULL> | pointerExpression | allocationExpression ) )? <SEMICOLON> ( layoutDirective )?
pointerAssignment ::= pointerExpression <EQUAL> ( <NULL> | pointerExpression | allocationExpression ) <SEMICOLON> ( layoutDirective )?
pointerDelete ::= <DELETE> pointerExpression <SEMICOLON>
dataAssignment ::= dataExpression <EQUAL> ( dataExpression | <CHAR> ) <SEMICOLON>
pointerAssignmentInForLoop ::= pointerExpression <EQUAL> ( <NULL> | pointerExpression | allocationExpression )
pointerExpression ::= <IDENTIFIER> ( <CHAIN> )?
allocationExpression ::= <NEW> <NODE> <LPAREN> ( <CHAR> | dataExpression ) <COMMA> <NULL> <RPAREN>
controlOperation ::= ( whileLoop | forLoop | ifStatement | breakStatement )
breakStatement ::= <BREAK> <SEMICOLON>
whileLoop ::= <WHILE> <LPAREN> booleanExpression <RPAREN> block
forLoop ::= forLoopPointer
forLoopPointer ::= <FOR> <LPAREN> ( pointerAssignmentInForLoop )? <SEMICOLON> booleanExpression <SEMICOLON> ( pointerAssignmentInForLoop )? <RPAREN> block
ifStatement ::= <IF> <LPAREN> booleanExpression <RPAREN> block ( <ELSE> block )?
block ::= <LBRACE> ( ( pointerOperation | controlOperation | layoutOperation ) )* <RBRACE>
dataExpression ::= pointerExpression <DEREFERENCEOP> <INFO>
booleanExpression ::= ( simpleBooleanExpression | <LPAREN> simpleBooleanExpression <RPAREN> <LOGICALCONNECTOR> <LPAREN> simpleBooleanExpression <RPAREN> )
simpleBooleanExpression ::= ( ( pointerExpression | <NULL> ) <EQUALCOMPARATOR> ( pointerExpression | <NULL> ) | ( dataExpression | <CHAR> ) ( <EQUALCOMPARATOR> | <ORDERCOMPARATOR> ) ( dataExpression | <CHAR> ) )
layoutOperation ::= <IDENTIFIER> <DEREFERENCEOP> <REDRAW> <SEMICOLON>
layoutDirective ::= <COMMENT> <INT> <INT> ( <IDENTIFIER> ( <IDENTIFIER> )? )? ( <ENDOFCOMMENT> | <EOF> )

Terminals (tokens)

<EOF> ::= The end-of-file marker
<TITLE> ::= 0 or more non-newline characters
<COMMENT> ::= "//"
<GRIDSIZE> ::= "gridsize" (not case-sensitive)
<INT> ::= 1 or more occurrences of one of the ten decimal digits "0" through "9"
<LANGUAGE> ::= "java" or "C++" (not case-sensitive)
<DRAWGRID> ::= "drawgrid" (not case-sensitive)
<REAL> ::= a single decimal digit optionally followed by a dot and a single decimal digit
<SMALLFONT> ::= "smallfont" (not case-sensitive)
<ENDOFCOMMENT> ::= A newline character
<NODE> ::= "Node"
<STAR> ::= "*"
<IDENTIFIER> ::= A letter (that is, a lowercase or lower case letter, or "_", or "$") followed by 0 or more letters and decimal digits
<EQUAL> ::= "="
<NULL> ::= "null" or "NULL"
<CREATELIST> ::= "Utils.createList" or "createList"
<LPAREN> ::= "("
<CHARLIST> ::= A comma-separated list of one or more <CHAR>'s
<CHAR> ::= A single quote, followed by a single letter or decimal digit, followed by a single quote
<STRING> ::= An optional <IDENTIFIER> surrounded by double quotes
<RPAREN> ::= ")"
<SEMICOLON> ::= ";"
<DELETE> ::= "delete"
<CHAIN> ::= One or more copies of <DEREFERENCEOP> followed by "next"
<NEW> ::= "new"
<COMMA> ::= ","
<BREAK> ::= "break"
<WHILE> ::= "while"
<FOR> ::= "for"
<IF> ::= "if"
<ELSE> ::= "else"
<LBRACE> ::= "{"
<RBRACE> ::= "}"
<DEREFERENCEOP> ::= "." or "->"
<INFO> ::= "info" or "data" (not case-sensitive)
<LOGICALCONNECTOR> ::= "&&" or "| |"
<EQUALCOMPARATOR> ::= "==" or "!="
<ORDERCOMPARATOR> ::= "<" or "<=" or ">" or ">="
<REDRAW> ::= "redrawListHorizontally()"