Parsing with a systemic grammar involves much unification of disjunctive descriptions. The usual way to unify such is as follows:
DNF expansion of a description is however an expensive task -- the process takes exponential time in the worst case (Kasper and Rounds, 1986). Space is also a problem -- DNF expansion is a transformation whereby a disjunctive description is replaced with a set of descriptions each of which contains no disjunction. For a description containing a high level of disjunction, the size of the DNF form can be excessive.
Space has not however been a problem in our processing, but time has. Systemic parsing is very slow. We thus focus on means for speeding up, or avoiding, the unification process.
There have been proposals for unification without DNF expansion. Karttunen, for instance, has proposed an algorithm which ``uses constraints on disjuncts which must be checked whenever the disjunct is modified'' (Kasper, 1987, p81). However, as noted by Kasper (1987, p61), Karttunen's unification algorithm works only for a limited type of disjunctive description, and not for general disjunction as is needed in the present work.
Kasper has proposed a method of re-representing disjunctive descriptions which in some cases avoids the need for expansion. His approach separates a disjunctive description into two parts -- a definite component (which contains no disjunction), and an indefinite component (containing the disjunctive information of the description). A unification process can first check whether the definite components of two descriptions unify, and only proceeds to unify the indefinite components if the definite components unify successfully. The unification of the indefinites is avoided if the unification of the definites fails.
The Kasper-Rounds form also allows us to delay expansion until a later time. When two descriptions are unified, only the definite components need to be checked for compatibility. The result of a Kasper-Rounds unification contains the indefinite descriptions from both descriptions without expansion. At some point in the processing it may be necessary to resolve the indefiniteness, and the disjunctive components are then expanded. However, in many cases, the definite component of the description may become inconsistent before this is necessary, expansion is thus avoided.
If DNF-expansion is required, then it should be performed as efficiently as possible. We here discuss some methods to achieve this goal:
The parser makes extensive use of caching -- when any expansion is calculated which is likely to be used again, the result is stored away for later re-use.
Precompilation has also been a useful technique to improve parsing efficiency. Precompilation is basically a pre-caching of all the values which might be used in the parsing process. By performing most of the DNF expansion of the grammar as a precompilation step, we avoid doing that calculation during the parsing of a sentence.