From the point of view of parsing and generation, a grammar as considered above defines a relation between strings of a natural language and representations of the meaning modelled as part of the grammar, which we call semantic expressions. Parsing then involves the computation of this relation from strings to semantic expressions, and generation involves the computation from semantic expressions to strings.
More formally this relationship can be defined as a binary
relation R between objects of two different domains, i.e., 
, where S is the domain of strings and LF the
domain of semantic expressions.
Parsing as well as generation can be thought of as a program P that
is able to enumerate all possible pairs of R for a given element
either from the domain of strings or from the domain of semantic
expressions.
More precisely, in the case of
parsing P computes 
and in the case of generation
. Thus, P is just a constructive realization of
R, no matter whether P constructs R only during parsing or during
generation.
Since P can construct R for both domains we call P a reversible program and R a P-reversible relation, in order to emphasize that P can construct R from both directions.
Clearly, up to now we have only assumed that R is a (recursively) enumerable relation. As usual, we assume that the set S of the well-formed strings of a language is enumerable. For a reversible program P this implies that it can enumerate R also from the set LF. Furthermore, we also assume that at least S has an infinite cardinality, so that R has to be defined by some finite recursive device, i.e., a grammar. Intuitively we assume that the same grammar is used for defining both sets of R, therefore we will call this grammar a reversible grammar.
We have only assumed that P should be able to compute a
reversible relation. In principle this does not exclude the
case that there are infinitely many solutions for some 
or 
. For example this would imply that there are infinitely many
readings for some sentence or infinitely many paraphrases for some
logical form. If this is the case then either the grammar is
intrinsically infinitely enumerable or P does not terminate (see also
[Dymetman1991]). Therefore we restrict a program P to be
effectively reversible in the following sense (see also
[VanNoord1993]):
This means that P is decidable and that the enumeration of the set of solutions must be finite, i.e., for each input (either sentence or logical form) the resulting set is `one to finitely many'.
Considered under the CLP view, the parsing and generation problem consists of a goal that has to be resolved with respect to a given grammar G, specified as a definite clause specification. Parsing and generation differ with respect to the constraints specified for the goal. Since for parsing we want to find the corresponding semantic expressions to a particular string, we require that the constraints at least entail the representation of the string in question, and analogously for generation we require that the semantic expression for which possible strings should be computed is specified. For parsing the feature that represents the string can be considered as an input variable and the feature that represents the semantics found can be considered as the output variable, and vice versa for generation. We will call the feature that represents the input the essential feature, short . For parsing we will assume that is the path PHON and for generation it is SEM.
A parsing goal then can be defined as a goal of which the essential feature is PHON and whose value is bound to the string in question.
Thus, the parsing problem for the string ``heute erzählt peter lügen'' would be
and analogously we define a generation goal as a goal of which the essential feature is SEM and whose value is bound to the semantic expression in question. For example for the logical form ``heute(erzählen(peter,lügen))'' would be
Note that in both cases further constraints may be added to restrict the possible feature structures of found results, for example to be of a specific category, or that the subcategorization list should be empty. Moreover, it would also be possible to specify the entire syntactic information, for example in the case of generation, to perform some grammar checking. However, what we at least require for parsing and generation is that the value of the essential feature is instantiated. In the next paragraph we define more precisely what ``instantiation of the essential feature means.''