A Tool to Visualize
By Aashi Jain, Archita Goyal, and Pinaki Chakraborty,
Netaji Subhas Institute of Technology
The use of a Predictive Parsing Visualization Tool (PPVT) as a teaching aid in a course on compiler construction
offered in the fall of 2015 helped students better understand
the predictive parsing as they reported in a survey after
the course. PPVT takes as input a grammar, calculates the
FIRST and FOLLOW sets, and constructs the parsing table.
Then for a given string, PPV T performs table-driven parsing
and displays the parse tree and the leftmost derivation.
Parsing algorithms are classified into universal parsing algorithms, top-down parsing algorithms, and bottom-up parsing
algorithms [ 1]. Universal parsing algorithms, as the name suggests, can be used for any context-free grammar. However, universal parsing algorithms are not used in compilers because of
their high time complexities. The parser of a practical compiler
should be able to parse a source program in linear time. This
can be achieved by one of the many top-down and bottom-up
parsing algorithms. Top-down and bottom-up parsing algorithms can parse the programming constructs found in common programming languages.
Predictive parsing is a top-down table-driven parsing tech-
nique. A predictive parser uses a stack to store grammar symbols
that represent how the parser expects the rest of the source pro-
gram to be. In each step, the action to be performed depends on
the next token in the source program and the symbol at the top
of the stack. A step may require consulting the parsing table, pop-
ping off a symbol from the stack and pushing one or more sym-
bols onto the stack. Predictive parsing is invariably included in all
courses on compiler construction. Since predictive parsing can be
used for LL( 1) grammars only, it is less powerful than most bot-
tom-up parsing algorithms. Nevertheless, the predictive parsing
algorithm can be used to parse all commonly used programming
languages and it is comparatively easier to implement a predictive
parser. Consequently, many compilers use predictive parsers. Al-
though predictive parsing is simpler than the bottom-up parsing
algorithms, it is complex enough to require a visualization tool so
that students can understand it better. In this article, we present a
tool called PPVT which can be used as a teaching aid to compre-
hensively visualize the process of predictive parsing.
In universities around the world, faculty design different types of
teaching aids to assist in teaching compiler construction. Many
use programming exercises to enhance their courses on compiler
construction [ 6]. Some faculty tend to use visualization tools as
well to assist in teaching these courses. The visualization tools that
are used to teach courses on compiler construction can be broadly classified as visual compilers and parsing algorithm visualizers.
A visual compiler is a compiler that presents its internal working to the user in a stepwise manner. A visual compiler illustrates,
typically using quality graphics, the different steps involved in
compiling a given program. Visual compilers can be said to be
performing an in vivo analysis of the entire compilation process.
Some visual compilers like PAG [ 17], Tree-viewer [ 19] and VAST
[ 2] emphasize constructing parse trees and annotating them
with information. There are some visual compilers that have
been developed to compile specific programming languages. For
example, ICOMP [ 3] compiles PL/0 and VisiCLANG [ 14] compiles a Pascal-like language called CLANG. Both ICOMP and
VisiCLANG visualize the recursive-descent parsing technique.