Send us a comment.
In addition to the matters already discussed, a real implementation of a chart parser needs to take care of certain vital housekeeping matters. When one of our rules proposes a new edge, we only want to add it to the chart if it is not already there. So, edge addition needs to be preceded by a check to see if the edge exists. Without this check, the chart would not be removing any duplication from the search space, of course.
An equally important piece of housekeeping for a parser, rather than a recognizer, is the organization of the building of the phrase structure tree for the string under consideration. As with a WFST, the idea is to have elements of the edge data structure be trees, rather than simple categories. The elements to which this applies is the sequence of found categories for an edge. Thus the found of an edge will be the sequence of parse trees of the found phrases, rather than simply the categories.
The fundamental rule must be altered to take tree building into account. The fundamental rule creates a new edge with one more found phrase than the active arc that helped to spawn it. We must ensure that the new item in the sequence is a tree, not a bare category. Fortunately, we can easily construct the parse tree from the participating inactive edge by using the existing label of the edge, together with the sequence of trees for its subphrases, given in the existing found structure.
Send us a comment.