A first naive algorithm that performs generation of paraphrases using a reversible grammar can be described as follows. Consider the situation in fig. 5.3. Suppose S is the input for the parser then the set
{(S, LF'), (S, LF'')}is computed. Now LF' and LF'' are respectively given as input to the generator to compute possible paraphrases. The sets
{(LF', S'), (LF', S)}and
{(LF'', S), (LF'', S'')}result. By means of comparison of the elements of the sets obtained during generation with the set obtained during parsing one can easily determine the two paraphrases S' and S'' because of the relationship between strings and logical forms defined by the grammar. Note that if this relationship is effectively reversible (see section 3.4) then this problem is effectively computable.
This `generate-and-test' approach is naive because of the following reasons. Firstly, it assumes that all possible paraphrases are generated at once. Although `all-parses' algorithms are widely used during parsing in natural language systems a corresponding `all-paraphrases' strategy is not practical because in general the search space during generation is much larger (which is a consequence of the modular design discussed in section 5.2). Secondly, the algorithm only guarantees that an ambiguous utterance is restated differently. It is possible that irrelevant paraphrases are produced because the source of the ambiguity is not used directly.