next up previous contents
Next: A restricted version of Up: Parsing and generation Previous: Unrestricted parsing problem

Problems with the unrestricted parsing problem

Defining parsing- and generation problems as goals implies that the parser will enumerate all feature structures that have a compatible value for the phon attribute; and similarly such a generator will enumerate feature structures that have a compatible value for the sem attribute. This approach faces a number of problems however. For example, consider the generation problem for a grammar that defines among others the following signs:

\begin{displaymath}
\avm{
phon : \mbox{\lq\lq the priest drinks''} \\
\mbox{\it sem}...
...x{\it arg1} : \avm{ \mbox{\it pred} : \mbox{\rm priest} }
}
}
\end{displaymath}

\begin{displaymath}
\avm{
phon : \mbox{\lq\lq the priest drinks whisky''}\\
\mbox{\i...
...\it arg2} : \avm{ \mbox{\it pred} : \mbox{\rm whisky}
}
}
}
\end{displaymath}
For a given logical form

\begin{displaymath}
\avm{ \mbox{\it pred} : \mbox{\rm drink} \\
\mbox{\it arg1} : \avm{ \mbox{\it pred} : \mbox{\rm priest} }
}
\end{displaymath}
the generator delivers the strings ``the priest drinks'' and ``the priest drinks whisky'', and perhaps also ``the priest drinks strong cheap whisky from a brown paper bag''. On the other hand, the generator also delivers ``the priest drinks'' for the logical form 2.5

\begin{displaymath}\avm{ \mbox{\it pred} : \mbox{\rm drink} \\
\mbox{\it arg1}...
...x{\it arg2} : \avm{ \mbox{\it pred} : \mbox{\rm whisky}
}
}
\end{displaymath}

A related problem can be illustrated with respect to parsers. For example, in parsers for Definite Clause Grammars [65] strings are (usually) represented by difference lists; for example `the priest drinks from a brown paper bag' is represented as:

\begindcg
[the,priest,drinks,from,a,brown,paper,bag\vert X]-X
\enddcg
However, the parser usually does not expect to find an input goal such as:

\begindcg
?- s([the,priest,drinks,from,a,brown,paper,bag\vert X]-X
\enddcg
but instead expects the tail variable of the difference list to be instantiated with some constant (often the empty list: []), eg:

\begindcg
?- s([the,priest,drinks,from,a,brown,paper,bag]-[]).
\enddcg
This `trick' simplifies the parser considerably because it is now impossible to further instantiate the tail variable. Most DCG parsers will not terminate without this convention because these parsers will try to further instantiate the variable tail by longer and longer lists of words.


next up previous contents
Next: A restricted version of Up: Parsing and generation Previous: Unrestricted parsing problem
Noord G.J.M. van
1998-09-30