Manuel Vilares Ferro
Miguel Angel Alonso Pardo
David Cabrero Souto
in Proc. of Logical Aspects of Computational Linguistics (LACL'97), pp. 61-64, Nancy, France, 1997.
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 briefly present a proposal to avoid these drawbacks. We choose to work in the context of fixed-mode programs, focusing on two aspects: Avoiding limitations on the parsing process, and extending the unification to composed terms without overload for non-cyclic structures.
Keywords: DCG, Dynamic Programming, Logical Push-Down Automaton, Cyclic Term.