Demonstration of Parsing Algorithms

Last Update Time-stamp: "97/08/01 14:01:00 umrigar"

The applets accessible from this page demonstrate the following parsing algorithms:

  1. Recursive-descent parsing.
  2. LL(1) table-driven parsing.
  3. Shift-reduce parsing.
Besides showing a parse tree or forest as it is being constructed, the applet shows the current line in the program (for the recursive-descent parser) or state in the parse table (for the LL(1) and shift-reduce parsers). It also displays a trace of the stack contents followed by the remaining input.

The applets are best viewed using Netscape running on a Unix platform. It largely works on other platforms.

You can also browse the source code, or download the entire package as parsdemo-1.0.tar.gz.

A related project is the zyacc parser generator which is now publically available. It was used to generate the parsing tables for the above shift-reduce parsing applet. It uses some of the parsdemo code to build a GUI for an interactive parser debugger.

Other projects I've worked on.

Feedback: Please email any feedback to zdu@acm.org.