A restricted version of the parsing problem

It seems, then, that what we really intend with the generation problem is something like: `show me all signs that place exactly the following constraints on the following semantic representation'. In [108] this is formalized for generation with LFG's by requiring that the input structure subsumes (is more general, is less informative) the structure that is generated (completeness), and moreover, the structure that is generated subsumes the input structure (coherence). ^2.6 In Wedekind's proposal no distinction is made between different kinds of information. That is, the generator is not allowed to add any syntactic, morphological and semantic information. However, in the case of eg. generation, it seems reasonable to require completeness and coherence only for the value of the path that is used to represent the semantic representation. The generator should be allowed to add all kind of syntactic information, and most notably of course the value of the phon attribute itself! Similarly, for parsing I require completeness and coherence of the attribute representing the string.

Therefore, it is useful to be able to refer to the meaning of a certain constraint $\phi$ restricted to a path p. I define the restriction of a constraint $\phi$ with respect to path p, written $\phi$ /p to be

$\begin{displaymath} (\phi/p)^{\cal{I}} =_{def} \{ \beta \in ASS^{\cal{I}} \vert ... ...ox{ such that } p^{\cal{I}}_{\alpha} = p^{\cal{I}}_{\beta} \} \end{displaymath}$

Furthermore, I introduce the notion p-parsing problem, that generalizes over parsing and generation (and transfer, cf. chapter 5), where p is some (fixed) path. The idea is that for something to be a proper answer to the goal it must be the case that the constraints on the path p proposed by that answer are equivalent to the constraints on path p that were already present in the formulation of the goal. In the next definition of the parsing problem we require that for some path p the constraint in the goal restricted to p is equivalent to the answer restricted to p.

The parsing problem restricted to a path p, called the p-parsing problem is defined as follows. Note that the path p is fixed.

Definition 12 (p-Parsing Problem) A p-parsing problem consists of a grammar G and a goal q:

$\begin{displaymath}\prologq \mbox{\it sign}(\mbox{\rm X}),\phi.\end{displaymath}$
The answer to a p-parsing problem is a solved constraint $\psi$ such that

$\psi$ is an answer to q with respect to G; and
( $\phi$ /Xp) = ( $\psi$ /Xp)

Returning to the usual implementation of parsers for DCG, it turns out that instantiating the out-variable of the difference list with the empty string in fact implements one part of this extra equivalence condition (the `coherence' part in Wedekind's terminology); as in DCG (i.e. Prolog) it is possible to implement a coherence check by `freezing' all variables (replacing them with fresh constants, eg. by the numbervars predicate) occurring in the original goal.

Coherence can be implemented in the current framework by a similar technique. It is possible to add constraints to the input structure instantiating all parts that are not mentioned in the constraint on the path p to constants c₁...c_k that are not used otherwise in the grammar. This will block any further instantiation of the value at p, and hence implements coherence. Completeness can be implemented, as discussed in [87], by maintaining a distinction in the derivation between the constraints added by the grammar and the constraints stemming from the original goal. At the end of the derivation it is then possible to compare the two constraints to see whether they are indeed equivalent. [108] discusses the implementation of completeness and coherence for LFG's.

I will assume in the following that the p-parsing problem is defined as in definition 12. However, in the meta interpreters for $\cal {R}$ ( $\cal {L}$ )-grammars that are defined in the next chapters I abstract away from the implementation of completeness and coherence, for didactic reasons. This move is justifiable because the implementation is rather straightforward and quite independent of the different inference strategies to be discussed. Therefore, leaving completeness and coherence out clarifies the differences between the different strategies. On the other hand, I continue to assume that the parsing problem is defined as above (with completeness and coherence) in order to be able to discuss certain termination properties.

In the remainder of this thesis I assume the previous definition of the p-parsing problem as in 12. For some applications it may be useful to consider other definitions. Some possibilities are discussed shortly.