# An Operational Model for Parsing Definite Clause Grammars with Infinite Terms

Manuel Vilares Ferro

Miguel Angel Alonso Pardo

David Cabrero Souto

in A. Lecomte, F. Lamarche and G. Perrier (eds.), *Logical Aspects
of Computational Linguistics*, volume 1582 of *Lecture Notes in
Artificial Intelligence*, pp. 212-230, Springer-Verlag,
Berlin-Heidelberg-New York, 1999. ISBN 3-540-65751-7.

## Abstract

Logic programs share with context-free grammars a strong reliance on
well-formedness conditions. Their proof procedures can be viewed as a
generalization of context-free parsing. In particular, definite clause
grammars can be interpreted as an extension of the classic
context-free formalism where the notion of finite set of non-terminal
symbols is generalized to a possibly infinite domain of directed
graphs. In this case, standard polynomial parsing methods may no
longer be applicable as they can lead to gross inefficiency or even
non-termination for the algorithms. We present a proposal to avoid
these drawbacks, focusing on two aspects: avoiding limitations on the
parsing process, and extending the unification to composed terms
without overload for non-cyclic structures.

Manuel Vilares Ferro /
vilares@dc.fi.udc.es

Miguel Angel Alonso Pardo /
alonso@dc.fi.udc.es

David Cabrero Souto /
cabrero@dc.fi.udc.es