Implementation

A Prolog version of the monitored generation strategy is described in [Neumann and van Noord1992]. In this version, a semantic-head-driven generation algorithm is used for normal generation, and for parsing a head-corner parser is used. A detailed description of both algorithms can be found in [VanNoord1993].

Using the bottom-up generation algorithm SHDGA, however, has the disadvantage that when is called for revision this can only be performed in a kind of generate-and-test mode. The problem is that basically constructs a derivation tree in a bottom-up fashion. On the other side, revision means to choose an alternative rule for a marked node, which is the root node of the subtree spanned by the ambiguous substring. But then, must first produce a candidate alternative string and an alternative subtree respectively, before it can check, whether the root node of the new subtree is in fact an alternative. This means, that after calling an additional test is necessary which compares the rule name of the marked node with that of the newly generated subtree. The following is the relevant snapshot of the Prolog code presented in [Neumann and van Noord1992]:

mgen(sign(LF,Str,S,D),t(Name,Ds,y)):-
    generate(sign(LF,Str,S,D)),
    \+ D = t(Name,Ds,_).

Here, the term t(Name,Ds,y) represents the (local) derivation tree of a sign, where the symbol y indicates that the root node of this derivation tree has been marked for revision. First, the embedded generator is called, and only if the resulting (local) derivation is not the same the resulting string of revision is accepted. Otherwise (by means of backtracking) another possibility is tried.

Using our uniform algorithm this computational overhead is easily avoided, because of its top/down and goal-directed behaviour. For the uniform algorithm to be usable for the monitored generation strategy we only need to pass the rule name of a marked node as an additional argument to the generation mode. The predictor rule then uses this rule name as a requirement to ignore it. Furthermore, the selection strategy used by the agenda should be depth-first or best-first, and when a string has been found, the generator is forced to stop further computation. Instead of giving more details, we will directly embed the uniform algorithm in the incremental monitored strategy. Before that, however, we will show in the next section how the above described generation method can be used for the generation of paraphrases during the understanding mode of a natural language system.