5.4.1 Redundant Derivations

Let's now try our parser:

{Inspect {Parse [man] RULES}}

This displays [n man]. These are all the single categories which have been recognized. Indeed, since we start with the single category man, it is recognized, and, after application of lexical rule n -> man, the single category n is also recognized. Now let's try:

{Inspect {Parse [the man] RULES}}

This displays [np np]. Indeed, according to our algorithm, there are two ways to arrive at the single category np:

the man ==> det man ==> det n ==> np
the man ==> the n   ==> det n ==> np

Oops! One way to fix this problem is to avoid inferring twice the same conclusion. For example, in the 2nd derivation above, when we infer det n, we should notice that we already produced this conclusion earlier in the 1st derivation and discard it instead of processing it again to redundantly infer n. You will have to do this as an exercise.

A different and better way to address this problem is to try to share the recognition of subsequences between derivations using memoization. In our example: both derivations reduce man to n, the to det, and det n to np. This approach leads to the idea of Chart Parsing and will be the subject of a later chapter.