Generation of an utterance given a marked derivation tree informally proceeds as follows. The generator simply `repeats' the previous generation in a top-down fashion, as long as it encounters unmarked nodes. This part of the generation algorithm thus simply copies previous results. If a marked node is encountered the embedded generation algorithm is called for this partial structure. The result should be a different derivation tree from the given one. Now clearly, this may or may not be possible depending on the grammar. The next paragraph discusses what happens if it is not possible.
The function mgen is used to generate an utterance, using a marked derivation tree as an extra guide.
mgen(sign(LF,Str,S,D),t(Name,Ds,y)):- generate(sign(LF,Str,S,D)), \+ D = t(Name,Ds,_). mgen(sign(LF,Str,S,D),t(Name,Ds,n)):- rule(Name,sign(LF,Str,S,D),Kids), mgen_ds(Kids,Ds). mgen_ds([],_). mgen_ds([S|T],[Stree,Ttree]):- mgen(S,Stree), mgen_ds(T,Ttree).
mgen(MarkedTree): if marked_node(root_node(MarkedTree)) then generate(semantics(root_node(MarkedTree))) else apply_rule(root_node(MarkedTree)); mgen_dtrs(dtrs(MarkedTree)). mgen_dtrs(Dtrs): if empty(Dtrs) then return T else mgen(first(Dtrs)); mgen_dtrs(rest(Dtrs)).
This function scans a marked tree, and if it encounters a marked node it just
calls the normal generator GENERATOR with the semantic expression of the
marked node. For each unmarked we redo the previous made computation of
the normal generator and proceed by scanning the subtrees of the next level.