chartParser.py
ourCFG.py

The file ourCFG.py should consist primarily of the starter code from CFG.py. However, you will probably want to modify the definitions for Production and Edge in that file, to support extra functionality. For example, you may add a method getLeftCorner to the Production class, and you may add a method isComplete to the Edge class. If you need to modify some of the existing methods in these classes or the Grammar class, you are welcome to do that, too.

 
The Python file chartParser.py that you turn in for this assignment should contain class definitions, function definitions and possibly variable assignments, but should not contain any calls to the print function except in test functions that you may optionally include. Thus, when your program is imported as a module, it should not cause anything to be printed. This will facilitate grading of your work by allowing grading scripts to control the execution of your functions.

1. (70 points) There is a function parse(grammarFilename, sentenceFilename) that can be called with a pair of strings that specify file names. It should read in a grammar file and process it in a manner similar to what you did in Assignment 2, Problem 6 for sentence generation. It should read in a sentence from the file given by sentenceFilename. It should construct a chart (see handout) and return the chart object. The class of which the chart object is an instance, call it Chart, should implement a method, tostr(), that returns a multiline string containing all the edges of the chart, one per line, in a particular format. That format is automatically produced by the tostr() method of the Edge class in the starter code CFG.py, given out for Assignment 2.
2. (20 points) The edges of the chart should be generated in the following general order. First, all special word edges should be generated. Then an outer loop should be run for j3 going from 1 to n. In each iteration of the outer loop, an inner loop should run in which all possible new edges are added working from complete edges that end at j3. These edges are added in a while loop that in each iteration tries to add some pure prediction edges, and then tries to add some edged using the fundamental rule. If any edges are successfully added, the while loop keeps going. When no new edges can be added, the outer loop increments j3 and the while loop starts again. The sample output (linked below) shows one particular order. We will not require that the edges be in this order as long as the correct set of edges is output, one per line.
3. (10 points) The tostr method of the Chart class should have a keyword parameter that allows the output to be limited to complete edges only: tostr(completeEdgesOnly=False). Thus the default should be to return the string representations of all edges.
4. Extra credit: (10 points) Provide a method tabularChart() that returns a string representation of the chart using "character graphics" to render the chart. There should be a vertical line (drawing with characters such as "|" and "+") for each vertex, and a horizontal segment for each edge. Each edge should have a label similar to that shown in the applet, and the label should be centered along the edge.
5. Extra credit: (10 points) Provide a method allParseTrees() that returns a list of all the valid parse trees for the sentence represented in the chart. Each parse tree should be represented as a list of the form ['S', subtree1, subtree2, ..., subtreeK], where a terminal node is represented like this: ['around']. Thus each tree or subtree is a list whose first element is a string that tells what vocabulary symbol is associated with the root of that tree or subtree. If the node is an internal node, then there are list elements following the vocabulary symbol that represent the subtrees of the node.

The following additional resources are available for this assignment: chart parsing demonstration applet, Grammar file for the simple robot command language GoToSpeak. Sample output for the GoToSpeak grammar and the sentence, "Now go to the table past the door and halt !" (here).