As we have seen, the chart data structure itself is neutral with respect to the search strategy employed, since we can go depth first, breadth first or whatever way we want. The same neutrality extends to the rule invocation strategy. Our illustration was of a bottom-up rule, but we could just have well have substituted a top-down strategy:
Top-down strategy
(1) At initialization, for each rule A -> W, where A is a category that can span a chart (typically S), add <0, 0, A -> .W> to the chart.
(2) If you are adding edge <i, j, C -> W1.B W2> to the chart, then for each rule B -> W, add <j, j, B -> .W> to the chart.
Here, the first clause ensures that the parsing process gets started by a bunch of empty active S edges added to the first vertex. The second clause entails that every active edge spawns further empty active edges that are looking to find the first (non-preterminal) category in the to-be-found list. Note that once again, for clarity, we have omitted discussion of building the parse tree. Applying the first clause to our initialized chart example gives us the chart shown in Figure 6.15(a) and applying the second clause gives that in Figure 6.15(b)
In addition to the straightforward top-down and bottom-up rule invocations, lots of other strategies can be constructed by, for example, making the rules sensitive to particular classes of categories or rules. Thus, we might, say, combine a basically top-down strategy with bottom-up rule invocation triggered by closed class 'function words', or by verbs. Or we might combine a basically bottom-up strategy with top-down invocation of just the rules responsible for unbounded dependency and ellipsis constructions. In devising such strategies, we must always address the question of the completeness of the parser, that is, whether or not it is guaranteed to find all possible parses. It is straightforward to construct hybrid strategies that are guaranteed to miss possible parses, and this is unacceptable in most contexts. For instance if, given Grammar5 (page 00, above), we decided to parse bottom up, left to right, except that prepositions would be sought top down, we would never recognize a single prepositional phrase because a top-down prediction of a preposition will never arise.
Send us a comment.