Chart Parser Demonstration Appliet - S. Tanimoto, Univ. of Washington

CSE 341: Programming Languages
The University of Washington, Seattle, Winter 2012

Caption: This page presents a Java applet that demonstrates a form of chart-parsing. Using a context-free grammar for a small language called "Englishish" the program sets up a chart representation of a directed graph, in which each vertical line represents one vertex of the graph, and each horizontal segment represents one edge of the graph. There exists an edge from vi to vj provided that the algorithm has discovered that there is a possibility of describing the input sentence portion beginning at word i and ending at word j as a partial (or possibly complete) right-hand-side of some production rule in the grammar.

The Applet: To operate the applet, scroll to the bottom of the applet and click on the Execute button. Then scroll back up to see the output.

Additional Example Input Data

To run the following example, first click on Reset. Then copy and paste the example text into the command buffer of the applet. Then click on Execute. This example demonstrates the use of an ambiguous grammar with a simple expression to parse. The resulting edges on lines 12, 15, and 31 represent one cut of a parse tree. The edges on lines 21, 24, and 29 represent a similar cut of a different parse tree.

;Enter commands here.
DELAY 50  ; from here wait only 50 ms between updates
BEGIN-GRAMMAR
E -> NUM
E -> E OP E
E -> ( E )
NUM -> 1 | 2 | 3
OP -> + | *
END-GRAMMAR
BEGIN-TEXT
1 + 2 * 3
END-TEXT
TOKENIZE
BOTTOM-UP-PARSE

As a convenience a screen shot of the output of the chart parser when run on the above example is shown here.