AN ILLUSTRATIVE EXAMPLE
We demonstrate the working of PPVT using an example. We
provide the following grammar to PPVT.
PPVT calculates the FIRST and FOLLOW sets, and constructs the parsing table (Figure 2). We now enter a string that
is an element of the language generated by this grammar, say
i-i*(i+i%i)/i. PPV T uses the parsing table to parse the string
(Figure 3). PPVT then prints the parse tree in a textual format
using the ‘|’ and ‘_’ characters (Figure 4). The nodes that appear
top-to-bottom in the parse tree are printed left-to-right. The
root node is printed in the leftmost column. All nodes that are
at the same level in the parse tree are printed in the same column. All children of a node are printed in the column right to
it with the leftmost child printed on the top. The leftmost derivation, showing all the sentential forms from the grammar start
symbol to the given string, is also printed (Figure 5). Alternatively, if we enter a string that is not an element of the language
generated by the grammar, say i+i(i-i), then the parser stops
as soon as it detects a syntax error because of the viable-prefix
property of the predictive parsing algorithm. It is interesting to
see how PPVT can succinctly visualize the predictive parsing
algorithm for an arbitrary grammar and an arbitrary string.
This verifies the correctness of the design and the appropriateness of the notation used by PPVT.
PPVT was used as a teaching aid in an undergraduate-level
introductory course on compiler construction in the fall 2015
semester which was attended by 62 students. The objective was
to use PPVT as a visualization tool to help students in understanding how to construct a predictive parser and use it to parse
a string. Due to its ease of use and fidelity to textbooks, it was
easy to integrate PPVT in the course. Students used PPVT to
cross-check their classroom exercises and take-home assignments on predictive parsing. PPVT’s ability to show the details
of the calculations proved particularly helpful here. PPVT also
allowed the students to solve exercises involving large grammars and input strings which they would not have solved otherwise. Although it was not an objective, a few students also
used PPV T to construct parsing tables of their compiler-related
projects. In a survey at the end of the semester, students reported that PPVT helped them in understanding predictive parsing
better (Table 1). They said that after seeing the output of PPVT
they understood how to present their answers to questions on
predictive parsing. The students also asked for a similar tool
to visualize SLR, CLR and LALR parsing algorithms. An executable version of PPVT and two sample grammars have been
made available online [ 13].
Figure 2: FIRST sets, FOLLOW sets and parsing table as calculated by PPVT.
Table 1: Student feedback (number of students = 62).
Yes No No opinion
1. Did PPVT help you in understanding the concept of
predictive parsing? 55 7 —
2. Did PPV T help you in understanding how to
answer questions on predictive parsing? 52 9 1
3. Is it easy to write the grammar in the specified
format and use PPVT? 51 11 —
4. Is the representation of parse tree used by PPVT
easy to understand? 56 5 1