I designed a source-to-source translation scheme that instrumented input YACC grammars with calls to a graphics library so that as the resulting parser analyzed an input string, these calls would generate a visualization of both the LR parse stack (and attribute values) and the LR parse tree. Based on my design, Laura Deddens, a student visiting me as part of the CRA Distributed Mentorship Program, constructed a prototype tool. When I teach compilers, I give the students a quick tutorial on the use of this tool so that they can experiment with it if they desire. I also have it available on the web, where it has been downloaded by many different people. A Java version of this tool also exists, built by GMU Masters student Jeff Ruby.
One of the challenging aspects of teaching students how compilers work is helping them discover how a stack is used and how attributes are synthesized during LR parsing. The project that Laura Deddens, a senior at UC Santa Cruz, and I are working on this summer is the development of a tool that allows students to write a grammar, augment it with code to do simple attribute synthesis, and then get to watch a visualization of the parse of some input. In order to accomplish this, we have had to determine the following:
Before doing any development work, we needed to determine what aspects of the parsing and attribute synthesis process can and should be visualized. My initial plan was to visualize changes to the parse stack and attributes associated with stack elements as input symbols were processed. However, Laura convinced me that it was possible to visualize the parse tree as well!
We chose to use Motif because of its widespread popularity.
The next task was to determine how to add Motif calls to a YACC grammar specification so that the calls are made as the input is parsed. Much of this will be fairly routine, but some of the more complex aspects requireed experimenting with different call placements and with some manual transformations on the grammar. This was accomplished fairly quickly and the student became an expert on adding calls to arbitrary grammars so that the parsing process could be visualized.
The goal of the fourth step was to develop a tool that takes a YACC grammar (augmented in the restricted manner described in step 1) and produces a YACC grammar that contains the calls to the visualization package. Once this YACC grammar is processed by the YACC tools and is compiled, a compiler that parses and does visualization for the given grammar will result. The most straightforward way to build this instrumentation tool is using a source-to-source translation package such as NewYacc.
Information on using the VisualYacc tool here at GMU
Information on getting a copy of the VisualYacc tool
The final piece of work that I would like to have done here is to build a web-based interface so that the tool would be demonstratable to a wider audience.
This work was supported under the Computing Research Association's Distributed Mentor Program